cuddlcache.c

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

  DdNode * h,
  DdNode * value,
  ptrint count)
{
    int result;
    unsigned int posn;
    DdHashItem *item;

#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;
    item->key[0] = f;
    item->key[1] = g;
    item->key[2] = h;
    posn = ddLCHash3(f,g,h,hash->shift);
    item->next = hash->bucket[posn];
    hash->bucket[posn] = item;

    return(1);

} /* end of cuddHashTableInsert3 */


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

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

  Description [Looks up a key consisting of 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     [cuddHashTableLookup cuddHashTableLookup1 cuddHashTableLookup2
  cuddHashTableInsert3]

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

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

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

    while (item != NULL) {
	DdNodePtr *key = item->key;
	if ((f == key[0]) && (g == key[1]) && (h == key[2])) {
	    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 cuddHashTableLookup3 */


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


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

  Synopsis    [Resizes a local cache.]

  Description []

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static void
cuddLocalCacheResize(
  DdLocalCache * cache)
{
    DdLocalCacheItem *item, *olditem, *entry, *old;
    int i, shift;
    unsigned int posn;
    unsigned int slots, oldslots;
    extern void (*MMoutOfMemory)(long);
    void (*saveHandler)(long);

    olditem = cache->item;
    oldslots = cache->slots;
    slots = cache->slots = oldslots << 1;

#ifdef DD_VERBOSE
    (void) fprintf(cache->manager->err,
		   "Resizing local cache from %d to %d entries\n",
		   oldslots, slots);
    (void) fprintf(cache->manager->err,
		   "\thits = %.0f\tlookups = %.0f\thit ratio = %5.3f\n",
		   cache->hits, cache->lookUps, cache->hits / cache->lookUps);
#endif

    saveHandler = MMoutOfMemory;
    MMoutOfMemory = Cudd_OutOfMem;
    cache->item = item =
	(DdLocalCacheItem *) ALLOC(char, slots * cache->itemsize);
    MMoutOfMemory = saveHandler;
    /* If we fail to allocate the new table we just give up. */
    if (item == NULL) {
#ifdef DD_VERBOSE
	(void) fprintf(cache->manager->err,"Resizing failed. Giving up.\n");
#endif
	cache->slots = oldslots;
	cache->item = olditem;
	/* Do not try to resize again. */
	cache->maxslots = oldslots - 1;
	return;
    }
    shift = --(cache->shift);
    cache->manager->memused += (slots - oldslots) * cache->itemsize;

    /* Clear new cache. */
    memset(item, 0, slots * cache->itemsize);

    /* Copy from old cache to new one. */
    for (i = 0; (unsigned) i < oldslots; i++) {
	old = (DdLocalCacheItem *) ((char *) olditem + i * cache->itemsize);
	if (old->value != NULL) {
	    posn = ddLCHash(old->key,cache->keysize,slots);
	    entry = (DdLocalCacheItem *) ((char *) item +
					  posn * cache->itemsize);
	    memcpy(entry->key,old->key,cache->keysize*sizeof(DdNode *));
	    entry->value = old->value;	
	}
    }

    FREE(olditem);

    /* Reinitialize measurements so as to avoid division by 0 and
    ** immediate resizing.
    */
    cache->lookUps = (double) (int) (slots * cache->minHit + 1);
    cache->hits = 0;

} /* end of cuddLocalCacheResize */


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

  Synopsis    [Computes the hash value for a local cache.]

  Description [Computes the hash value for a local cache. Returns the
  bucket index.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
DD_INLINE
static unsigned int
ddLCHash(
  DdNodePtr * key,
  unsigned int keysize,
  int shift)
{
    unsigned int val = (unsigned int) (ptrint) key[0];
    unsigned int i;

    for (i = 1; i < keysize; i++) {
	val = val * DD_P1 + (int) (ptrint) key[i];
    }

    return(val >> shift);

} /* end of ddLCHash */


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

  Synopsis    [Inserts a local cache in the manager list.]

  Description []

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static void
cuddLocalCacheAddToList(
  DdLocalCache * cache)
{
    DdManager *manager = cache->manager;

    cache->next = manager->localCaches;
    manager->localCaches = cache;
    return;

} /* end of cuddLocalCacheAddToList */


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

  Synopsis    [Removes a local cache from the manager list.]

  Description []

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
static void
cuddLocalCacheRemoveFromList(
  DdLocalCache * cache)
{
    DdManager *manager = cache->manager;
#ifdef __osf__
#pragma pointer_size save
#pragma pointer_size short
#endif
    DdLocalCache **prevCache, *nextCache;
#ifdef __osf__
#pragma pointer_size restore
#endif

    prevCache = &(manager->localCaches);
    nextCache = manager->localCaches;

    while (nextCache != NULL) {
	if (nextCache == cache) {
	    *prevCache = nextCache->next;
	    return;
	}
	prevCache = &(nextCache->next);
	nextCache = nextCache->next;
    }
    return;			/* should never get here */

} /* end of cuddLocalCacheRemoveFromList */


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

  Synopsis    [Resizes a hash table.]

  Description [Resizes a hash table. Returns 1 if successful; 0
  otherwise.]

  SideEffects [None]

  SeeAlso     [cuddHashTableInsert]

******************************************************************************/
static int
cuddHashTableResize(
  DdHashTable * hash)
{
    int j;
    unsigned int posn;
    DdHashItem *item;
    DdHashItem *next;
#ifdef __osf__
#pragma pointer_size save
#pragma pointer_size short
#endif
    DdNode **key;
    int numBuckets;
    DdHashItem **buckets;
    DdHashItem **oldBuckets = hash->bucket;
#ifdef __osf__
#pragma pointer_size restore
#endif
    int shift;
    int oldNumBuckets = hash->numBuckets;
    extern void (*MMoutOfMemory)(long);
    void (*saveHandler)(long);

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

    hash->bucket = buckets;
    hash->numBuckets = numBuckets;
    shift = --(hash->shift);
    hash->maxsize <<= 1;
    memset(buckets, 0, numBuckets * sizeof(DdHashItem *));
#ifdef __osf__
#pragma pointer_size restore
#endif
    if (hash->keysize == 1) {
	for (j = 0; j < oldNumBuckets; j++) {
	    item = oldBuckets[j];
	    while (item != NULL) {
		next = item->next;
		key = item->key;
		posn = ddLCHash2(key[0], key[0], shift);
		item->next = buckets[posn];
		buckets[posn] = item;
		item = next;
	    }
	}
    } else if (hash->keysize == 2) {
	for (j = 0; j < oldNumBuckets; j++) {
	    item = oldBuckets[j];
	    while (item != NULL) {
		next = item->next;
		key = item->key;
		posn = ddLCHash2(key[0], key[1], shift);
		item->next = buckets[posn];
		buckets[posn] = item;
		item = next;
	    }
	}
    } else if (hash->keysize == 3) {
	for (j = 0; j < oldNumBuckets; j++) {
	    item = oldBuckets[j];
	    while (item != NULL) {
		next = item->next;
		key = item->key;
		posn = ddLCHash3(key[0], key[1], key[2], shift);
		item->next = buckets[posn];
		buckets[posn] = item;
		item = next;
	    }
	}
    } else {
	for (j = 0; j < oldNumBuckets; j++) {
	    item = oldBuckets[j];
	    while (item != NULL) {
		next = item->next;
		posn = ddLCHash(item->key, hash->keysize, shift);
		item->next = buckets[posn];
		buckets[posn] = item;
		item = next;
	    }
	}
    }
    FREE(oldBuckets);
    return(1);

} /* end of cuddHashTableResize */


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

  Synopsis    [Fast storage allocation for items in a hash table.]

  Description [Fast storage allocation for items in a hash table. The
  first 4 bytes of a chunk contain a pointer to the next block; the
  rest contains DD_MEM_CHUNK spaces for hash items.  Returns a pointer to
  a new item if successful; NULL is memory is full.]

  SideEffects [None]

  SeeAlso     [cuddAllocNode cuddDynamicAllocNode]

******************************************************************************/
DD_INLINE
static DdHashItem *
cuddHashTableAlloc(
  DdHashTable * hash)
{
    int i;
    unsigned int itemsize = hash->itemsize;
    extern void (*MMoutOfMemory)(long);
    void (*saveHandler)(long);
#ifdef __osf__
#pragma pointer_size save
#pragma pointer_size short
#endif
    DdHashItem **mem, *thisOne, *next, *item;

    if (hash->nextFree == NULL) {
	saveHandler = MMoutOfMemory;
	MMoutOfMemory = Cudd_OutOfMem;
	mem = (DdHashItem **) ALLOC(char,(DD_MEM_CHUNK+1) * itemsize);
	MMoutOfMemory = saveHandler;
#ifdef __osf__
#pragma pointer_size restore
#endif
	if (mem == NULL) {
	    if (hash->manager->stash != NULL) {
		FREE(hash->manager->stash);
		hash->manager->stash = NULL;
		/* Inhibit resizing of tables. */
		hash->manager->maxCacheHard = hash->manager->cacheSlots - 1;
		hash->manager->cacheSlack = -(hash->manager->cacheSlots + 1);
		for (i = 0; i < hash->manager->size; i++) {
		    hash->manager->subtables[i].maxKeys <<= 2;
		}
		hash->manager->gcFrac = 0.2;
		hash->manager->minDead =
		    (unsigned) (0.2 * (double) hash->manager->slots);
#ifdef __osf__
#pragma pointer_size save
#pragma pointer_size short
#endif
		mem = (DdHashItem **) ALLOC(char,(DD_MEM_CHUNK+1) * itemsize);
#ifdef __osf__
#pragma pointer_size restore
#endif
	    }
	    if (mem == NULL) {
		(*MMoutOfMemory)((DD_MEM_CHUNK + 1) * itemsize);
		hash->manager->errorCode = CUDD_MEMORY_OUT;
		return(NULL);
	    }
	}

	mem[0] = (DdHashItem *) hash->memoryList;
	hash->memoryList = mem;

	thisOne = (DdHashItem *) ((char *) mem + itemsize);
	hash->nextFree = thisOne;
	for (i = 1; i < DD_MEM_CHUNK; i++) {
	    next = (DdHashItem *) ((char *) thisOne + itemsize);
	    thisOne->next = next;
	    thisOne = next;
	}

	thisOne->next = NULL;

    }
    item = hash->nextFree;
    hash->nextFree = item->next;
    return(item);

} /* end of cuddHashTableAlloc */