src/calBdd/calHashTableOne.c File Reference

#include "calInt.h"

Include dependency graph for calHashTableOne.c:

Defines
#define	HashTableOneDoHash(hashTable, keyBdd) (((CalAddress_t)(CalBddGetBddNode(keyBdd)) / NODE_SIZE) % hashTable->numBins)
Functions
static void	HashTableOneRehash (CalHashTable_t *hashTable, int grow)
CalHashTable_t *	CalHashTableOneInit (Cal_BddManager_t *bddManager, int itemSize)
void	CalHashTableOneQuit (CalHashTable_t *hashTable)
void	CalHashTableOneInsert (CalHashTable_t hashTable, Cal_Bdd_t keyBdd, char valuePtr)
int	CalHashTableOneLookup (CalHashTable_t hashTable, Cal_Bdd_t keyBdd, char *valuePtrPtr)

Define Documentation

#define HashTableOneDoHash	(	hashTable,
		keyBdd		)	(((CalAddress_t)(CalBddGetBddNode(keyBdd)) / NODE_SIZE) % hashTable->numBins)

CFile***********************************************************************

FileName [calHashTableOne.c]

PackageName [cal]

Synopsis [Routines for managing hash table with Bdd is a key and int, long, or double as a value]

Description [ ]

SeeAlso [optional]

Author [Jagesh Sanghavi (sanghavi@eecs.berkeley.edu) Rajeev Ranjan (rajeev@eecs.berkeley.edu) ]

Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software.

IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]

Revision [

Id: calHashTableOne.c,v 1.1.1.3 1998/05/04 00:58:57 hsv Exp

]

Definition at line 65 of file calHashTableOne.c.

Function Documentation

CalHashTable_t* CalHashTableOneInit	(	Cal_BddManager_t *	bddManager,
		int	itemSize
	)

AutomaticEnd Function********************************************************************

Synopsis [Initialize a hash table using default parameters.]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 98 of file calHashTableOne.c.

00099 {
00100   int i;
00101   CalHashTable_t *hashTable;
00102 
00103   hashTable = Cal_MemAlloc(CalHashTable_t, 1);
00104   if(hashTable == Cal_Nil(CalHashTable_t)){
00105     CalBddFatalMessage("out of memory");
00106   }
00107   hashTable->sizeIndex = HASH_TABLE_DEFAULT_SIZE_INDEX;
00108   hashTable->numBins = TABLE_SIZE(hashTable->sizeIndex);
00109   hashTable->maxCapacity = hashTable->numBins*HASH_TABLE_DEFAULT_MAX_DENSITY;
00110   hashTable->bins = Cal_MemAlloc(CalBddNode_t *, hashTable->numBins);
00111   if(hashTable->bins == Cal_Nil(CalBddNode_t *)){
00112     CalBddFatalMessage("out of memory");
00113   }
00114   for(i = 0; i < hashTable->numBins; i++){
00115     hashTable->bins[i] = Cal_Nil(CalBddNode_t);
00116   }
00117   hashTable->numEntries = 0;
00118   hashTable->bddId = (Cal_BddId_t)itemSize;
00119   if(itemSize > NODE_SIZE){
00120     CalBddFatalMessage("CalHashTableOneInit: itemSize exceeds NODE_SIZE");
00121   }
00122   hashTable->nodeManager = bddManager->nodeManagerArray[0];
00123   hashTable->requestNodeList = Cal_Nil(CalRequestNode_t);
00124   return hashTable;
00125 }

void CalHashTableOneInsert	(	CalHashTable_t *	hashTable,
		Cal_Bdd_t	keyBdd,
		char *	valuePtr
	)

Function********************************************************************

Synopsis [Directly insert a BDD node in the hash table.]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 173 of file calHashTableOne.c.

00175 {
00176   int hashValue;
00177   CalBddNode_t *bddNode, *dataPtr;
00178 
00179   hashValue = HashTableOneDoHash(hashTable, keyBdd);
00180   hashTable->numEntries++;
00181   if(hashTable->numEntries >= hashTable->maxCapacity){
00182     HashTableOneRehash(hashTable, 1);
00183     hashValue = HashTableOneDoHash(hashTable, keyBdd);
00184   }
00185   CalNodeManagerAllocNode(hashTable->nodeManager, dataPtr);
00186   memcpy(dataPtr, valuePtr, (size_t)hashTable->bddId);
00187   CalNodeManagerAllocNode(hashTable->nodeManager, bddNode);
00188   CalBddNodePutThenBdd(bddNode, keyBdd);
00189   CalBddNodePutElseBddNode(bddNode, dataPtr);
00190   CalBddNodePutNextBddNode(bddNode, hashTable->bins[hashValue]);
00191   hashTable->bins[hashValue] = bddNode;
00192 }

int CalHashTableOneLookup	(	CalHashTable_t *	hashTable,
		Cal_Bdd_t	keyBdd,
		char **	valuePtrPtr
	)

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 206 of file calHashTableOne.c.

00208 {
00209   CalBddNode_t *ptr;
00210   Cal_Bdd_t tmpBdd;
00211   int hashValue;
00212   
00213   hashValue = HashTableOneDoHash(hashTable, keyBdd);
00214   ptr = hashTable->bins[hashValue];
00215   while(ptr != Cal_Nil(CalBddNode_t)){
00216     CalBddNodeGetThenBdd(ptr, tmpBdd);
00217     if(CalBddIsEqual(keyBdd, tmpBdd)){
00218       if(valuePtrPtr){
00219         *valuePtrPtr = (char *)CalBddNodeGetElseBddNode(ptr);
00220       }
00221       return 1;
00222     }
00223     ptr = CalBddNodeGetNextBddNode(ptr);
00224   }
00225   if(valuePtrPtr){
00226     *valuePtrPtr = Cal_Nil(char);
00227   }
00228   return 0;
00229 }

void CalHashTableOneQuit ( CalHashTable_t * hashTable )

Function********************************************************************

Synopsis [Free a hash table along with the associated storage.]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 140 of file calHashTableOne.c.

00142 {
00143   CalBddNode_t *ptr, *next, *node;
00144   int i;
00145   if(hashTable == Cal_Nil(CalHashTable_t))return;
00146   for(i = 0; i < hashTable->numBins; i++){
00147     ptr = hashTable->bins[i];
00148     while(ptr != Cal_Nil(CalBddNode_t)){
00149       next = CalBddNodeGetNextBddNode(ptr);
00150       node = CalBddNodeGetElseBddNode(ptr);
00151       CalNodeManagerFreeNode(hashTable->nodeManager, node);
00152       CalNodeManagerFreeNode(hashTable->nodeManager, ptr);
00153       ptr = next;
00154     }
00155   }
00156   Cal_MemFree(hashTable->bins);
00157   Cal_MemFree(hashTable);
00158 }

static void HashTableOneRehash	(	CalHashTable_t *	hashTable,
		int	grow
	)			`[static]`

AutomaticStart

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 246 of file calHashTableOne.c.

00249 {
00250   CalBddNode_t *ptr, *next;
00251   CalBddNode_t **oldBins = hashTable->bins;
00252   int i, hashValue;
00253   int oldNumBins = hashTable->numBins;
00254   Cal_Bdd_t keyBdd;
00255 
00256   if(grow){
00257     hashTable->sizeIndex++;
00258   }
00259   else{
00260     if (hashTable->sizeIndex <= HASH_TABLE_DEFAULT_SIZE_INDEX){/* No need to rehash */
00261       return;
00262     }
00263     hashTable->sizeIndex--;
00264   }
00265 
00266   hashTable->numBins = TABLE_SIZE(hashTable->sizeIndex);
00267   hashTable->maxCapacity = hashTable->numBins * HASH_TABLE_DEFAULT_MAX_DENSITY;
00268   hashTable->bins = Cal_MemAlloc(CalBddNode_t *, hashTable->numBins);
00269   if(hashTable->bins == Cal_Nil(CalBddNode_t *)){
00270     CalBddFatalMessage("out of memory");
00271   }
00272   for(i = 0; i < hashTable->numBins; i++){
00273     hashTable->bins[i] = Cal_Nil(CalBddNode_t);
00274   }
00275 
00276   for(i = 0; i < oldNumBins; i++){
00277     ptr = oldBins[i];
00278     while(ptr != Cal_Nil(CalBddNode_t)){
00279       next = CalBddNodeGetNextBddNode(ptr);
00280       CalBddNodeGetThenBdd(ptr, keyBdd);
00281       hashValue = HashTableOneDoHash(hashTable, keyBdd);
00282       CalBddNodePutNextBddNode(ptr, hashTable->bins[hashValue]);
00283       hashTable->bins[hashValue] = ptr;
00284       ptr = next;
00285     }
00286   }
00287   Cal_MemFree(oldBins);
00288 }

src/calBdd/calHashTableOne.c File Reference

Defines

Functions

Define Documentation

Function Documentation