cuddlcache.c

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

	    retval = fprintf(fp,"%ld ", hystogram[i]);
	    if (retval == EOF) return(0);
	}
	retval = fprintf(fp,"\n");
	if (retval == EOF) return(0);
    }

    FREE(hystogram);
    return(1);

} /* end of cuddLocalCacheProfile */
#endif


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

  Synopsis    [Initializes a hash table.]

  Description [Initializes a hash table. Returns a pointer to the new
  table if successful; NULL otherwise.]

  SideEffects [None]

  SeeAlso     [cuddHashTableQuit]

******************************************************************************/
DdHashTable *
cuddHashTableInit(
  DdManager * manager,
  unsigned int  keySize,
  unsigned int  initSize)
{
    DdHashTable *hash;
    int logSize;

#ifdef __osf__
#pragma pointer_size save
#pragma pointer_size short
#endif
    hash = ALLOC(DdHashTable, 1);
    if (hash == NULL) {
	manager->errorCode = CUDD_MEMORY_OUT;
	return(NULL);
    }
    hash->keysize = keySize;
    hash->manager = manager;
    hash->memoryList = NULL;
    hash->nextFree = NULL;
    hash->itemsize = (keySize + 1) * sizeof(DdNode *) +
	sizeof(ptrint) + sizeof(DdHashItem *);
    /* We have to guarantee that the shift be < 32. */
    if (initSize < 2) initSize = 2;
    logSize = cuddComputeFloorLog2(initSize);
    hash->numBuckets = 1 << logSize;
    hash->shift = sizeof(int) * 8 - logSize;
    hash->bucket = ALLOC(DdHashItem *, hash->numBuckets);
    if (hash->bucket == NULL) {
	manager->errorCode = CUDD_MEMORY_OUT;
	FREE(hash);
	return(NULL);
    }
    memset(hash->bucket, 0, hash->numBuckets * sizeof(DdHashItem *));
    hash->size = 0;
    hash->maxsize = hash->numBuckets * DD_MAX_HASHTABLE_DENSITY;
#ifdef __osf__
#pragma pointer_size restore
#endif
    return(hash);

} /* end of cuddHashTableInit */


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

  Synopsis    [Shuts down a hash table.]

  Description [Shuts down a hash table, dereferencing all the values.]

  SideEffects [None]

  SeeAlso     [cuddHashTableInit]

******************************************************************************/
void
cuddHashTableQuit(
  DdHashTable * hash)
{
#ifdef __osf__
#pragma pointer_size save
#pragma pointer_size short
#endif
    unsigned int i;
    DdManager *dd = hash->manager;
    DdHashItem *bucket;
    DdHashItem **memlist, **nextmem;
    unsigned int numBuckets = hash->numBuckets;

    for (i = 0; i < numBuckets; i++) {
	bucket = hash->bucket[i];
	while (bucket != NULL) {
	    Cudd_RecursiveDeref(dd, bucket->value);
	    bucket = bucket->next;
	}
    }

    memlist = hash->memoryList;
    while (memlist != NULL) {
	nextmem = (DdHashItem **) memlist[0];
	FREE(memlist);
	memlist = nextmem;
    }

    FREE(hash->bucket);
    FREE(hash);
#ifdef __osf__
#pragma pointer_size restore
#endif

    return;

} /* end of cuddHashTableQuit */


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

  Synopsis    [Inserts an item in a hash table.]

  Description [Inserts an item in a hash table when the key has more than
  three pointers.  Returns 1 if successful; 0 otherwise.]

  SideEffects [None]

  SeeAlso     [[cuddHashTableInsert1 cuddHashTableInsert2 cuddHashTableInsert3
  cuddHashTableLookup]

******************************************************************************/
int
cuddHashTableInsert(
  DdHashTable * hash,
  DdNodePtr * key,
  DdNode * value,
  ptrint count)
{
    int result;
    unsigned int posn;
    DdHashItem *item;
    unsigned int i;

#ifdef DD_DEBUG
    assert(hash->keysize > 3);
#endif

    if (hash->size > hash->maxsize) {
	result = cuddHashTableResize(hash);
	if (result == 0) return(0);
    }
    item = cuddHashTableAlloc(hash);
    if (item == NULL) return(0);
    hash->size++;
    item->value = value;
    cuddRef(value);
    item->count = count;
    for (i = 0; i < hash->keysize; i++) {
	item->key[i] = key[i];
    }
    posn = ddLCHash(key,hash->keysize,hash->shift);
    item->next = hash->bucket[posn];
    hash->bucket[posn] = item;

    return(1);

} /* end of cuddHashTableInsert */


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

  Synopsis    [Looks up a key in a hash table.]

  Description [Looks up a key consisting of more than three pointers
  in a hash table.  Returns the value associated to the key if there
  is an entry for the given key in the table; NULL otherwise. If the
  entry is present, its reference counter is decremented if not
  saturated. If the counter reaches 0, the value of the entry is
  dereferenced, and the entry is returned to the free list.]

  SideEffects [None]

  SeeAlso     [cuddHashTableLookup1 cuddHashTableLookup2 cuddHashTableLookup3
  cuddHashTableInsert]

******************************************************************************/
DdNode *
cuddHashTableLookup(
  DdHashTable * hash,
  DdNodePtr * key)
{
    unsigned int posn;
    DdHashItem *item, *prev;
    unsigned int i, keysize;

#ifdef DD_DEBUG
    assert(hash->keysize > 3);
#endif

    posn = ddLCHash(key,hash->keysize,hash->shift);
    item = hash->bucket[posn];
    prev = NULL;

    keysize = hash->keysize;
    while (item != NULL) {
	DdNodePtr *key2 = item->key;
	int equal = 1;
	for (i = 0; i < keysize; i++) {
	    if (key[i] != key2[i]) {
		equal = 0;
		break;
	    }
	}
	if (equal) {
	    DdNode *value = item->value;
	    cuddSatDec(item->count);
	    if (item->count == 0) {
		cuddDeref(value);
		if (prev == NULL) {
		    hash->bucket[posn] = item->next;
		} else {
		    prev->next = item->next;
		}
		item->next = hash->nextFree;
		hash->nextFree = item;
		hash->size--;
	    }
	    return(value);
	}
	prev = item;
	item = item->next;
    }
    return(NULL);

} /* end of cuddHashTableLookup */


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

  Synopsis    [Inserts an item in a hash table.]

  Description [Inserts an item in a hash table when the key is one pointer.
  Returns 1 if successful; 0 otherwise.]

  SideEffects [None]

  SeeAlso     [cuddHashTableInsert cuddHashTableInsert2 cuddHashTableInsert3
  cuddHashTableLookup1]

******************************************************************************/
int
cuddHashTableInsert1(
  DdHashTable * hash,
  DdNode * f,
  DdNode * value,
  ptrint count)
{
    int result;
    unsigned int posn;
    DdHashItem *item;

#ifdef DD_DEBUG
    assert(hash->keysize == 1);
#endif

    if (hash->size > hash->maxsize) {
	result = cuddHashTableResize(hash);
	if (result == 0) return(0);
    }
    item = cuddHashTableAlloc(hash);
    if (item == NULL) return(0);
    hash->size++;
    item->value = value;
    cuddRef(value);
    item->count = count;
    item->key[0] = f;
    posn = ddLCHash2(f,f,hash->shift);
    item->next = hash->bucket[posn];
    hash->bucket[posn] = item;

    return(1);

} /* end of cuddHashTableInsert1 */


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

  Synopsis    [Looks up a key consisting of one pointer in a hash table.]

  Description [Looks up a key consisting of one pointer in a hash table.
  Returns the value associated to the key if there is an entry for the given
  key in the table; NULL otherwise. If the entry is present, its reference
  counter is decremented if not saturated. If the counter reaches 0, the
  value of the entry is dereferenced, and the entry is returned to the free
  list.]

  SideEffects [None]

  SeeAlso     [cuddHashTableLookup cuddHashTableLookup2 cuddHashTableLookup3
  cuddHashTableInsert1]

******************************************************************************/
DdNode *
cuddHashTableLookup1(
  DdHashTable * hash,
  DdNode * f)
{
    unsigned int posn;
    DdHashItem *item, *prev;

#ifdef DD_DEBUG
    assert(hash->keysize == 1);
#endif

    posn = ddLCHash2(f,f,hash->shift);
    item = hash->bucket[posn];
    prev = NULL;

    while (item != NULL) {
	DdNodePtr *key = item->key;
	if (f == key[0]) {
	    DdNode *value = item->value;
	    cuddSatDec(item->count);
	    if (item->count == 0) {
		cuddDeref(value);
		if (prev == NULL) {
		    hash->bucket[posn] = item->next;
		} else {
		    prev->next = item->next;
		}
		item->next = hash->nextFree;
		hash->nextFree = item;
		hash->size--;
	    }
	    return(value);
	}
	prev = item;
	item = item->next;
    }
    return(NULL);

} /* end of cuddHashTableLookup1 */


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

  Synopsis    [Inserts an item in a hash table.]

  Description [Inserts an item in a hash table when the key is
  composed of two pointers. Returns 1 if successful; 0 otherwise.]

  SideEffects [None]

  SeeAlso     [cuddHashTableInsert cuddHashTableInsert1 cuddHashTableInsert3
  cuddHashTableLookup2]

******************************************************************************/
int
cuddHashTableInsert2(
  DdHashTable * hash,
  DdNode * f,
  DdNode * g,
  DdNode * value,
  ptrint count)
{
    int result;
    unsigned int posn;
    DdHashItem *item;

#ifdef DD_DEBUG
    assert(hash->keysize == 2);
#endif

    if (hash->size > hash->maxsize) {
	result = cuddHashTableResize(hash);
	if (result == 0) return(0);
    }
    item = cuddHashTableAlloc(hash);
    if (item == NULL) return(0);
    hash->size++;
    item->value = value;
    cuddRef(value);
    item->count = count;
    item->key[0] = f;
    item->key[1] = g;
    posn = ddLCHash2(f,g,hash->shift);
    item->next = hash->bucket[posn];
    hash->bucket[posn] = item;

    return(1);

} /* end of cuddHashTableInsert2 */


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

  Synopsis    [Looks up a key consisting of two pointers in a hash table.]

  Description [Looks up a key consisting of two pointer in a hash table.
  Returns the value associated to the key if there is an entry for the given
  key in the table; NULL otherwise. If the entry is present, its reference
  counter is decremented if not saturated. If the counter reaches 0, the
  value of the entry is dereferenced, and the entry is returned to the free
  list.]

  SideEffects [None]

  SeeAlso     [cuddHashTableLookup cuddHashTableLookup1 cuddHashTableLookup3
  cuddHashTableInsert2]

******************************************************************************/
DdNode *
cuddHashTableLookup2(
  DdHashTable * hash,
  DdNode * f,
  DdNode * g)
{
    unsigned int posn;
    DdHashItem *item, *prev;

#ifdef DD_DEBUG
    assert(hash->keysize == 2);
#endif

    posn = ddLCHash2(f,g,hash->shift);
    item = hash->bucket[posn];
    prev = NULL;

    while (item != NULL) {
	DdNodePtr *key = item->key;
	if ((f == key[0]) && (g == key[1])) {
	    DdNode *value = item->value;
	    cuddSatDec(item->count);
	    if (item->count == 0) {
		cuddDeref(value);
		if (prev == NULL) {
		    hash->bucket[posn] = item->next;
		} else {
		    prev->next = item->next;
		}
		item->next = hash->nextFree;
		hash->nextFree = item;
		hash->size--;
	    }
	    return(value);
	}
	prev = item;
	item = item->next;
    }
    return(NULL);

} /* end of cuddHashTableLookup2 */


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

  Synopsis    [Inserts an item in a hash table.]

  Description [Inserts an item in a hash table when the key is
  composed of three pointers. Returns 1 if successful; 0 otherwise.]

  SideEffects [None]

  SeeAlso     [cuddHashTableInsert cuddHashTableInsert1 cuddHashTableInsert2
  cuddHashTableLookup3]

******************************************************************************/
int
cuddHashTableInsert3(
  DdHashTable * hash,
  DdNode * f,
  DdNode * g,