lsStatus lsDelEnd(
  lsList list			/* List to delete item from */,
  lsGeneric *data		/* Last item (returned)     */)
/*
 * This routine deletes the last item of a list.  The user
 * data associated with the item is returned so the caller
 * may dispose of it.  Returns LS_NOMORE if there is nothing
 * to delete.
 */
{
    lsDesc *realList = (lsDesc *) list;
    lsElem *temp;

    if (realList->botPtr == NIL(lsElem)) {
	/* Nothing to delete */
	*data = (lsGeneric) 0;
	return LS_NOMORE;
    } else {
	*data = realList->botPtr->userData;
	temp = realList->botPtr;
	realList->botPtr = realList->botPtr->prevPtr;
	if (temp->prevPtr != NIL(lsElem)) {
	    /* There is something before the last item */
	    temp->prevPtr->nextPtr = NIL(lsElem);
	} else {
	    /* Nothing before it - top becomes null as well */
	    realList->topPtr = NIL(lsElem);
	}
	FREE(temp);
	realList->length -= 1;
    }
    return LS_OK;
}

/*
 * Name:	CONTsetup
 * Purpose:	copies information from list of CONTcard's to ELCTelectrode's
 * Formals:	cardList: list of cards to setup
 *		electrodeList: previously built list of ELCTelectrode's
 * Returns:	OK/E_PRIVATE
 * Users:	 numerical devices
 * Calls:	CONTcheck
 */
int
CONTsetup(CONTcard *cardList, ELCTelectrode *electrodeList)
{
  CONTcard *card;
  ELCTelectrode *electrode;
  int error;

/* Check the card list */
  if ((error = CONTcheck( cardList ))) return( error );

  for ( card = cardList; card != NIL(CONTcard); card = card->CONTnextCard ) {

    /* Copy workfunction to all matching electrodes */
    for ( electrode = electrodeList; electrode != NIL(ELCTelectrode);
	electrode = electrode->next ) {
      if ( card->CONTnumber == electrode->id ) {
	if ( card->CONTworkfunGiven ) {
	  electrode->workf = card->CONTworkfun;
	} else {
	  electrode->workf = 4.10 /* electron volts */;
	}
      }
    }
  }
  return( OK );
}

lsStatus lsNewEnd(
  lsList list			/* List to append element to */,
  lsGeneric data		/* Arbitrary pointer to data */,
  lsHandle *itemHandle		/* Handle to data (returned) */)
/*
 * Adds a new item to the end of a previously created linked list.
 * This routine appends the item in constant time and
 * can be used freely without guilt.
 */
{
    lsDesc *realList = (lsDesc *) list;
    lsElem *newElem;

    newElem = ALLOC(lsElem, 1);
    newElem->userData = data;
    newElem->prevPtr = realList->botPtr;
    newElem->nextPtr = NIL(lsElem);
    newElem->mainList = realList;
    if (realList->topPtr == NIL(lsElem))
      realList->topPtr = newElem;
    if (realList->botPtr != NIL(lsElem))
      realList->botPtr->nextPtr = newElem;
    realList->botPtr = newElem;
    realList->length += 1;
    if (itemHandle) *itemHandle = (lsHandle) newElem;
    return(LS_OK);
}

/*
 * left_rotate --
 *   Do left rotation operation.
 *   See page 278, "Introduction to Algorithms", 2/e for the
 *   algorithm.
 * Precondition
 *   x ! = NULL and x must have a right child
 */
static Node *left_rotate(T tree, Node * x)
{
    assert(tree && x && x->right);

    /* turn y's left subtree to x's right subtree */
    Node *y = x->right;

    x->right = y->left;
    if (y->left != NIL(tree))
        y->left->parent = x;

    /* link x's parent to y */
    y->parent = x->parent;
    if (x->parent == NIL(tree))
        tree->root = y;
    else {
        if (x == x->parent->left)
            x->parent->left = y;
        else
            x->parent->right = y;
    }

    /* put x on y's left */
    y->left = x;
    x->parent = y;

    /* fix the size field of x and y */
    y->size = x->size;
    x->size = x->left->size + x->right->size + 1;

    return y;
}

/* Compute boundary condition parameters. */
void TWOsetBCparams(TWOdevice *pDevice, BDRYcard *cardList)
{
  int index, xIndex, yIndex;		/* Need to access in X/Y order. */
  TWOelem *pElem, *pNElem;
  BDRYcard *card;

  for ( card = cardList; card != NIL(BDRYcard); card = card->BDRYnextCard ) {
    for (xIndex = card->BDRYixLow; xIndex < card->BDRYixHigh; xIndex++) {
      for (yIndex = card->BDRYiyLow; yIndex < card->BDRYiyHigh; yIndex++) {
	pElem = pDevice->elemArray[ xIndex ][ yIndex ];
	if (pElem != NIL(TWOelem)) {
	  if (pElem->domain == card->BDRYdomain) {
	    for (index = 0; index <= 3; index++) {
	      if (pElem->evalEdges[index]) {
		pNElem = pElem->pElems[index];
		if (card->BDRYneighborGiven) {
		  if (pNElem && pNElem->domain == card->BDRYneighbor) {
		    /* Found an interface edge. */
		    TWOcopyBCinfo( pDevice, pElem, card, index );
		  }
		} else {
		  if (!pNElem || pNElem->domain != pElem->domain) {
		    /* Found a boundary edge. */
		    TWOcopyBCinfo( pDevice, pElem, card, index );
		  }
		}
	      }
	    }
	  }
	}
      }
    }
  }
}

void rbtree_init(rbtree_t *rbtree){
	if(NULL!=rbtree){
		rbtree_black(NIL(rbtree));
		rbtree->root=NIL(rbtree);
		rbtree->tree_size=0;
	}
}

lsStatus lsNewBegin(
  lsList list			/* List to add element to    */,
  lsGeneric data		/* Arbitrary pointer to data */,
  lsHandle *itemHandle		/* Handle to data (returned) */)
/*
 * Adds a new item to the start of a previously created linked list.
 * If 'itemHandle' is non-zero,  it will be filled with a handle
 * which can be used to generate a generator positioned at the
 * item without generating through the list.
 */
{
    lsDesc *realList = (lsDesc *) list;
    lsElem *newElem;

    newElem = ALLOC(lsElem, 1);
    newElem->userData = data;
    newElem->nextPtr = realList->topPtr;
    newElem->prevPtr = NIL(lsElem);
    newElem->mainList = realList;
    if (realList->topPtr == NIL(lsElem)) {
	/* The new item is both the top and bottom element */
	realList->botPtr = newElem;
    } else {
	/* There was a top element - make its prev correct */
	realList->topPtr->prevPtr = newElem;
    }
    realList->topPtr = newElem;
    realList->length += 1;
    if (itemHandle) *itemHandle = (lsHandle) newElem;
    return(LS_OK);
}

void
printTableMapping(__nis_table_mapping_t *t) {
	__nis_object_dn_t	*o;
	int			i;
	char			*myself = "printTableMapping";

	p2buf(myself, "\n%s:", NIL(t->dbId));
	printObjName(&t->index, t->objName);
	p2buf(myself, "\n\t%s \t%s", NIL(t->objName), NIL(t->objPath));
	p2buf(myself, "\n\tTTL = (%d - %d) -> %d\n",
		t->initTtlLo, t->initTtlHi, t->ttl);

	for (o = t->objectDN; o != 0; o = o->next) {
		printobjectDN(o);
		p2buf(myself, "\n");
	}

	p2buf(myself, "\tLDAP -> NIS+\n");
	p2buf(myself, "\tRules:\n");
	for (i = 0; i < t->numRulesFromLDAP; i++) {
		p2buf(myself, "\t\t");
		printMappingRule(t->ruleFromLDAP[i], mit_nisplus, mit_ldap);
		p2buf(myself, "\n");
	}

	p2buf(myself, "\tNIS+ -> LDAP\n");
	p2buf(myself, "\tRules:\n");
	for (i = 0; i < t->numRulesToLDAP; i++) {
		p2buf(myself, "\t\t");
		printMappingRule(t->ruleToLDAP[i], mit_ldap, mit_nisplus);
		p2buf(myself, "\n");
	}
}

/*
 * FUNCTION :	make_nis_container()
 *
 * DESCRIPTION: Sets up container for map_name in the DIT.
 *
 * GIVEN :	Map name
 *		The domain name.
 *		Flag indicating if container should be created.
 *
 * RETURNS :	SUCCESS	= It worked
 *		FAILURE	= There was a problem.
 */
suc_code
make_nis_container(char *map_name, char *domain, bool_t init_containers) {
	int			i, rc, statP = SUCCESS;
	__nis_table_mapping_t	*t;
	char			*dn;
	char			*myself = "make_nis_container";

	if (!map_name || !domain)
		return (FAILURE);

	if (FALSE == init_containers) {
		/*
		 * If we are not creating containers it is debatable what we
		 * should do . Maybe we should check for a pre-
		 * existing container and return failure if it does not exist.
		 *
		 * For now we assume the user will not have called us in this
		 * mode unless they know what they are doing. So return
		 * success. If they have got it wrong then latter writes will
		 * fail.
		 */
		return (SUCCESS);
	}

	/* Get the mapping information for the map */
	if ((t = mappingFromMap(map_name, domain, &statP)) == 0) {
		if (statP == MAP_NO_MAPPING_EXISTS)
			logmsg(MSG_NOTIMECHECK, LOG_ERR,
			"%s: No mapping information available for %s,%s",
				myself, NIL(map_name), NIL(domain));
		return (FAILURE);
	}

	/* Two times. One for readDN and other for writeDN */
	for (i = 0; i < 2; i++) {
		if (i == 0)
			dn = t->objectDN->read.base;
		else {
			if (t->objectDN->write.base == 0) {
				logmsg(MSG_NOTIMECHECK, LOG_INFO,
					"%s: No baseDN in writespec. Write "
					"disabled for %s,%s",
					myself, map_name, domain);
				break;
			}
			if (!strcasecmp(dn, t->objectDN->write.base))
				break;
			dn = t->objectDN->write.base;
		}

		if ((rc = makeNISObject(0, dn)) == FAILURE) {
			logmsg(MSG_NOTIMECHECK, LOG_ERR,
				"%s: Unable to create ldap container (dn: %s) "
				"for %s,%s", myself, dn, map_name, domain);
			return (FAILURE);
		}
	}
	return (SUCCESS);
}

/*
 * insert node
 * */
struct sk_list_node *
sk_insert_node(struct sk_list* lst, sk_node_val val, char * key)
{
    int key_length, i, new_level;
    struct sk_list_node * update[SK_MAX_LEVEL_SIZE];
    struct sk_list_object * obj;
    struct sk_list_node * node;

    node = lst->header;
    assert(node != NULL);
    for (i = lst->level; i>=0; i--)
    {
        assert(node->forward[i] != NULL);
        while (node->forward[i] != NIL(lst) && node->forward[i]->_val < val)
        {
            node = node->forward[i];
        } 
        update[i] = node;
    }
    
    if (node->forward[0] != NIL(lst) && node->forward[0]->_val == val)
    {
        node = node->forward[0];
        key_length = strlen(key);
        obj = (struct sk_list_object *) malloc (sizeof(struct sk_list_object) + (key_length + 1) * sizeof(char));    
        obj->next = node->objects;
        strncpy(obj->value, key, key_length);
        node->objects = obj;
        return node;
    }

    /* check level if need update */
    for (new_level = 0; rand() < RAND_MAX / 2 && new_level < SK_MAX_LEVEL_SIZE - 1; new_level++);
    if (new_level > lst->level)
    {
        for (i = lst->level + 1; i <= new_level; i++)
            update[i] = NIL(lst);
        lst->level = new_level;
    } 

    /* create new node */
    node = NewNodeOfLevel(new_level);
    memset(node,0, sizeof(struct sk_list_node ) + new_level * sizeof(struct sk_list_node*));
    node->_val = val;
    /* create new node object */
    key_length = strlen(key);
    obj = (struct sk_list_object *) malloc (sizeof(struct sk_list_object) + (key_length + 1) * sizeof(char));    
    obj->next = NULL;
    strncpy(obj->value, key, key_length);
    node->objects = obj;

    /* update levels*/
    for(i =0 ; i<= new_level; i++)
    {
        node->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = node;
    }
    return node;
}

/**Function********************************************************************

  Synopsis           [Levelmap command.]

  Description        []

  SideEffects        []

  SeeAlso            [optional]

  CommandName        [optional] 	   

  CommandSynopsis    [optional]  

  CommandArguments   [optional]  

  CommandDescription [optional]  

******************************************************************************/
int
levm_Com(
  network_t **network,
  array_t *llib,
  int argc,
  char **argv)
{
int k = 4, c;
network_t *new_network;
short nl = 0, vpr = 0;
char *ret;
char name[200];
  
  util_getopt_reset();
  while ((c = util_getopt(argc, argv, "vnk:")) != EOF) {
    switch (c) {
      case 'k': {
        if((k = atoi(util_optarg)) < 2) {
          Usage();
          return 1;
        }
      } break;
      case 'n': {
        nl = 1;
      } break;     
      case 'v': {
        vpr = 1;
      } break; 
      default:
        Usage();
        return 1;
    }
  }
  if((llib == NIL(array_t)) && (nl == 1)) {
    fprintf(siserr,"No logic library loaded.\n");
    return 1;
  }
  new_network = levmRun(*network, k);

  if(new_network != NIL(network_t)) {
    network_free(*network); 
    *network = new_network;
  }

  if(nl == 1) {
    Bind(*network, llib, k);
    ret = netl_ClblCreate(*network);
    BindFree(*network);
    if(ret != NIL(char)) {
      fprintf(siserr,"%s\n",ret);
      FREE(ret);
    }
  }

sm_matrix *
sm_allocate()
{
    register sm_matrix *A;

    A = ALLOC(sm_matrix, 1);
    A->rows = NIL(sm_row *);
    A->cols = NIL(sm_col *);
    A->nrows = A->ncols = 0;
    A->rows_size = A->cols_size = 0;
    A->first_row = A->last_row = NIL(sm_row);
    A->first_col = A->last_col = NIL(sm_col);
    A->user_word = NIL(char);		/* for our user ... */
    return A;
}

void
printObjAttr(__nis_obj_attr_t *attr) {
	char	*myself = "printObjAttr";

	if (attr == 0)
		return;

	p2buf(myself, "\tzo_owner  = %s\n", NIL(attr->zo_owner));
	p2buf(myself, "\tzo_group  = %s\n", NIL(attr->zo_group));
	p2buf(myself, "\tzo_domain = %s\n", NIL(attr->zo_domain));
	p2buf(myself, "\tzo_access = ");
	printObjRights(myself, &attr->zo_access);
	p2buf(myself, " (0x%08x)\n", attr->zo_access);
	p2buf(myself, "\tzo_ttl    = %d\n", attr->zo_ttl);
}

/*
 * Name:	MOBcheck
 * Purpose:	checks a list of MOBcards for input errors
 * Formals:	cardList: the list to check
 * Returns:	OK/E_PRIVATE
 * Users:	 numerical device setup routines
 * Calls:	error message handler
 */
int
MOBcheck(MOBcard *cardList, MaterialInfo *matlList)
{
    MOBcard *card;
    MATLmaterial *matl;
    int cardNum = 0;
    int error = OK;
    char ebuf[512];		/* error message buffer */

    for ( card = cardList; card != NIL(MOBcard); card = card->MOBnextCard ) {
        cardNum++;
        if (!card->MOBmaterialGiven) {
            sprintf( ebuf,
                     "mobility card %d is missing a material index",
                     cardNum );
            SPfrontEnd->IFerror( ERR_WARNING, ebuf, NIL(IFuid) );
            error = E_PRIVATE;
        } else {
            /* Make sure the material exists */
            for ( matl = matlList; matl != NIL(MATLmaterial); matl = matl->next ) {
                if ( card->MOBmaterial == matl->id ) {
                    break;
                }
            }
            if (matl == NIL(MATLmaterial)) {
                sprintf( ebuf,
                         "mobility card %d specifies a non-existent material",
                         cardNum );
                SPfrontEnd->IFerror( ERR_WARNING, ebuf, NIL(IFuid) );
                error = E_PRIVATE;
            }
        }
        if (!card->MOBcarrierGiven) {
            card->MOBcarrier = ELEC;
        }
        if (!card->MOBcarrTypeGiven) {
            card->MOBcarrType = MAJOR;
        }
        if (!card->MOBinitGiven) {
            card->MOBinit = FALSE;
        }

        /* Return now if anything has failed */
        if (error) return(error);

    }
    return(OK);
}

Rbc_t *
Rbc_Subst(Rbc_Manager_t * rbcManager,
          Rbc_t         * f,
          int           * subst)
{
  Dag_DfsFunctions_t SubstFunctions;
  SubstDfsData_t     SubstData;

  /* Cleaning the user fields. */
  Dag_Dfs(f, Rbc_ManagerGetDfsCleanFun(rbcManager), NIL(char));

  /* Setting up the DFS functions. */
  SubstFunctions.Set        = (PF_IVPCPI)SubstSet;
  SubstFunctions.FirstVisit = (PF_VPVPCPI)SubstFirst;
  SubstFunctions.BackVisit  = (PF_VPVPCPI)SubstBack;
  SubstFunctions.LastVisit  = (PF_VPVPCPI)SubstLast;

  /* Setting up the DFS data. */
  SubstData.rbcManager = rbcManager;
  SubstData.subst   = subst;
  SubstData.log2phy = (const int *) NULL;
  SubstData.phy2log = (const int *) NULL;
  SubstData.result     = NIL(Rbc_t);

  /* Calling DFS on f. */
  Dag_Dfs(f, &SubstFunctions, (char*)(&SubstData));

  return SubstData.result;

} /* End of Rbc_Subst. */

/*
 * tree_search --
 *   Search for the item whose key is equal to 'k'.
 */
Item tree_search(const T tree, Key k)
{
    assert(tree);

    Node *node = tree->root;

    while (node != NIL(tree) && !EQ(k, KEY(node->item)))
        if (LESS(k, KEY(node->item)))
            node = node->left;
        else
            node = node->right;
    if (node != NIL(tree))
        return node->item;
    else
        return NULLitem;
}

void
printobjectDN(__nis_object_dn_t *o) {
	char		*myself = "printobjectDN";
	int		i;

	p2buf(myself, "\t");
	printSearchTriple(&o->read);
	p2buf(myself, ":\n\t");
	printSearchTriple(&o->write);
	switch (o->delDisp) {
	case dd_always:
		p2buf(myself, ":\n\t\talways");
		break;
	case dd_perDbId:
		p2buf(myself, ":\n\t\tdbid=%s\n", NIL(o->dbIdName));
		for (i = 0; i < o->numDbIds; i++) {
			p2buf(myself, "\t\t\t");
			printMappingRule(o->dbId[i], mit_ldap, mit_nisplus);
		}
		break;
	case dd_never:
		p2buf(myself, ":\n\t\tnever");
		break;
	default:
		p2buf(myself, ":\n\t\t<unknown>");
	}
}

void
printObjName(__nis_index_t *index, char *name) {
	char		*myself = "printObjName";

	printIndex(index);
	p2buf(myself, "%s", NIL(name));
}

void
find_num_comps()
{

    void visit();
    register int i;

    /***********************************************************
    * Initialization.
    ***********************************************************/
    Pstack = NIL(STACK_ELEMENT);
    numcomps = 0;
    for (i = 0; i < totedges; i++)
    {
	val[i] = UNVISITED;
    }

    /***********************************************************
    * Use the depth-first search to find the number of
    * components.
    ***********************************************************/
    for (i = 1; i <= numpins; i++)
    {
	v1 = numnodes + i;
	if (garray[v1]->status == LABEL && val[v1] == UNVISITED)
	{
	    numcomps++;
	    visit();
	}
    }

} /* end of find_num_comps */

lsStatus lsLastItem(
  lsList list			/* List to get item from */,
  lsGeneric *data		/* User data (returned)  */,
  lsHandle *itemHandle		/* Handle to data (returned) */)
/*
 * Returns the last item of a list.  If the list is empty,
 * the routine returns LS_NOMORE.  Otherwise,  'data' will
 * be set to the last item and the routine will return LS_OK.
 * If 'itemHandle' is non-zero,  it will be filled with a
 * handle which can be used to generate a generator postioned
 * at this item.
 */
{
    lsDesc *realList = (lsDesc *) list;

    if (realList->botPtr != NIL(lsElem)) {
	*data = realList->botPtr->userData;
	if (itemHandle) *itemHandle = (lsHandle) (realList->botPtr);
	return(LS_OK);
    } else {
	*data = (lsGeneric) 0;
	if (itemHandle) *itemHandle = (lsHandle) 0;
	return(LS_NOMORE);
    }
}