cuddlevelq.c

主要进行大规模的电路综合

	item = (DdQueueItem *) ALLOC(char, queue->itemsize);
	if (item == NULL)
	    return(NULL);
    } else {
	item = queue->freelist;
	queue->freelist = item->next;
    }
    /* Initialize. */
    memset(item, 0, queue->itemsize);
    item->key = key;
    /* Update stats. */
    queue->size++;

    if (queue->last[level]) {
	/* There are already items for this level in the queue. */
	item->next = queue->last[level]->next;
	queue->last[level]->next = item;
    } else {
	/* There are no items at the current level.  Look for the first
	** non-empty level preceeding this one. */
	plevel = level;
	while (plevel != 0 && queue->last[plevel] == NULL)
	    plevel--;
	if (queue->last[plevel] == NULL) {
	    /* No element precedes this one in the queue. */
	    item->next = (DdQueueItem *) queue->first;
	    queue->first = item;
	} else {
	    item->next = queue->last[plevel]->next;
	    queue->last[plevel]->next = item;
	}
    }
    queue->last[level] = item;

    /* Insert entry for the key in the hash table. */
    if (hashInsert(queue,item) == 0) {
	return(NULL);
    }
    return(item);

} /* end of cuddLevelQueueEnqueue */


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

  Synopsis    [Remove an item from the front of a level queue.]

  Description [Remove an item from the front of a level queue.]

  SideEffects [None]

  SeeAlso     [cuddLevelQueueEnqueue]

******************************************************************************/
void
cuddLevelQueueDequeue(
  DdLevelQueue * queue,
  int  level)
{
    DdQueueItem *item = (DdQueueItem *) queue->first;

    /* Delete from the hash table. */
    hashDelete(queue,item);

    /* Since we delete from the front, if this is the last item for
    ** its level, there are no other items for the same level. */
    if (queue->last[level] == item)
	queue->last[level] = NULL;

    queue->first = item->next;
    /* Put item on the free list. */
    item->next = queue->freelist;
    queue->freelist = item;
    /* Update stats. */
    queue->size--;
    return;

} /* end of cuddLevelQueueDequeue */


/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/


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

  Synopsis    [Looks up a key in the hash table of a level queue.]

  Description [Looks up a key in the hash table of a level queue. Returns
  a pointer to the item with the given key if the key is found; NULL
  otherwise.]

  SideEffects [None]

  SeeAlso     [cuddLevelQueueEnqueue hashInsert]

******************************************************************************/
static DdQueueItem *
hashLookup(
  DdLevelQueue * queue,
  void * key)
{
    int posn;
    DdQueueItem *item;

    posn = lqHash(key,queue->shift);
    item = queue->buckets[posn];

    while (item != NULL) {
	if (item->key == key) {
	    return(item);
	}
	item = item->cnext;
    }
    return(NULL);

} /* end of hashLookup */


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

  Synopsis    [Inserts an item in the hash table of a level queue.]

  Description [Inserts an item in the hash table of a level queue. Returns
  1 if successful; 0 otherwise. No check is performed to see if an item with
  the same key is already in the hash table.]

  SideEffects [None]

  SeeAlso     [cuddLevelQueueEnqueue]

******************************************************************************/
static int
hashInsert(
  DdLevelQueue * queue,
  DdQueueItem * item)
{
    int result;
    int posn;

    if (queue->size > queue->maxsize) {
	result = hashResize(queue);
	if (result == 0) return(0);
    }

    posn = lqHash(item->key,queue->shift);
    item->cnext = queue->buckets[posn];
    queue->buckets[posn] = item;

    return(1);
    
} /* end of hashInsert */


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

  Synopsis    [Removes an item from the hash table of a level queue.]

  Description [Removes an item from the hash table of a level queue.
  Nothing is done if the item is not in the table.]

  SideEffects [None]

  SeeAlso     [cuddLevelQueueDequeue hashInsert]

******************************************************************************/
static void
hashDelete(
  DdLevelQueue * queue,
  DdQueueItem * item)
{
    int posn;
    DdQueueItem *prevItem;

    posn = lqHash(item->key,queue->shift);
    prevItem = queue->buckets[posn];

    if (prevItem == NULL) return;
    if (prevItem == item) {
	queue->buckets[posn] = prevItem->cnext;
	return;
    }

    while (prevItem->cnext != NULL) {
	if (prevItem->cnext == item) {
	    prevItem->cnext = item->cnext;
	    return;
	}
	prevItem = prevItem->cnext;
    }
    return;

} /* end of hashDelete */


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

  Synopsis    [Resizes the hash table of a level queue.]

  Description [Resizes the hash table of a level queue. Returns 1 if
  successful; 0 otherwise.]

  SideEffects [None]

  SeeAlso     [hashInsert]

******************************************************************************/
static int
hashResize(
  DdLevelQueue * queue)
{
    int j;
    int posn;
    DdQueueItem *item;
    DdQueueItem *next;
    int numBuckets;
#ifdef __osf__
#pragma pointer_size save
#pragma pointer_size short
#endif
    DdQueueItem **buckets;
    DdQueueItem **oldBuckets = queue->buckets;
#ifdef __osf__
#pragma pointer_size restore
#endif
    int shift;
    int oldNumBuckets = queue->numBuckets;
    extern void (*MMoutOfMemory)(long);
    void (*saveHandler)(long);

    /* Compute the new size of the subtable. */
    numBuckets = oldNumBuckets << 1;
    saveHandler = MMoutOfMemory;
    MMoutOfMemory = Cudd_OutOfMem;
#ifdef __osf__
#pragma pointer_size save
#pragma pointer_size short
#endif
    buckets = queue->buckets = ALLOC(DdQueueItem *, numBuckets);
    if (buckets == NULL) {
	queue->maxsize <<= 1;
	return(1);
    }

    queue->numBuckets = numBuckets;
    shift = --(queue->shift);
    queue->maxsize <<= 1;
    memset(buckets, 0, numBuckets * sizeof(DdQueueItem *));
#ifdef __osf__
#pragma pointer_size restore
#endif
    for (j = 0; j < oldNumBuckets; j++) {
	item = oldBuckets[j];
	while (item != NULL) {
	    next = item->cnext;
	    posn = lqHash(item->key, shift);
	    item->cnext = buckets[posn];
	    buckets[posn] = item;
	    item = next;
	}
    }
    FREE(oldBuckets);
    return(1);

} /* end of hashResize */