src/calBdd/calHashTableOne.c

Go to the documentation of this file.

#include "calInt.h"

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Stucture declarations                                                     */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/
#ifdef USE_POWER_OF_2
#  define HashTableOneDoHash(hashTable, keyBdd) \
     (((CalAddress_t)(CalBddGetBddNode(keyBdd)) / NODE_SIZE) & ((hashTable)->numBins - 1))
#else
#  define HashTableOneDoHash(hashTable, keyBdd) \
     (((CalAddress_t)(CalBddGetBddNode(keyBdd)) / NODE_SIZE) % hashTable->numBins)
#endif

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static void HashTableOneRehash(CalHashTable_t * hashTable, int grow);

/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/

CalHashTable_t *
CalHashTableOneInit(Cal_BddManager_t * bddManager, int  itemSize)
{
  int i;
  CalHashTable_t *hashTable;

  hashTable = Cal_MemAlloc(CalHashTable_t, 1);
  if(hashTable == Cal_Nil(CalHashTable_t)){
    CalBddFatalMessage("out of memory");
  }
  hashTable->sizeIndex = HASH_TABLE_DEFAULT_SIZE_INDEX;
  hashTable->numBins = TABLE_SIZE(hashTable->sizeIndex);
  hashTable->maxCapacity = hashTable->numBins*HASH_TABLE_DEFAULT_MAX_DENSITY;
  hashTable->bins = Cal_MemAlloc(CalBddNode_t *, hashTable->numBins);
  if(hashTable->bins == Cal_Nil(CalBddNode_t *)){
    CalBddFatalMessage("out of memory");
  }
  for(i = 0; i < hashTable->numBins; i++){
    hashTable->bins[i] = Cal_Nil(CalBddNode_t);
  }
  hashTable->numEntries = 0;
  hashTable->bddId = (Cal_BddId_t)itemSize;
  if(itemSize > NODE_SIZE){
    CalBddFatalMessage("CalHashTableOneInit: itemSize exceeds NODE_SIZE");
  }
  hashTable->nodeManager = bddManager->nodeManagerArray[0];
  hashTable->requestNodeList = Cal_Nil(CalRequestNode_t);
  return hashTable;
}


void
CalHashTableOneQuit(
  CalHashTable_t * hashTable)
{
  CalBddNode_t *ptr, *next, *node;
  int i;
  if(hashTable == Cal_Nil(CalHashTable_t))return;
  for(i = 0; i < hashTable->numBins; i++){
    ptr = hashTable->bins[i];
    while(ptr != Cal_Nil(CalBddNode_t)){
      next = CalBddNodeGetNextBddNode(ptr);
      node = CalBddNodeGetElseBddNode(ptr);
      CalNodeManagerFreeNode(hashTable->nodeManager, node);
      CalNodeManagerFreeNode(hashTable->nodeManager, ptr);
      ptr = next;
    }
  }
  Cal_MemFree(hashTable->bins);
  Cal_MemFree(hashTable);
}


void
CalHashTableOneInsert(CalHashTable_t * hashTable, Cal_Bdd_t  keyBdd,
                      char * valuePtr)
{
  int hashValue;
  CalBddNode_t *bddNode, *dataPtr;

  hashValue = HashTableOneDoHash(hashTable, keyBdd);
  hashTable->numEntries++;
  if(hashTable->numEntries >= hashTable->maxCapacity){
    HashTableOneRehash(hashTable, 1);
    hashValue = HashTableOneDoHash(hashTable, keyBdd);
  }
  CalNodeManagerAllocNode(hashTable->nodeManager, dataPtr);
  memcpy(dataPtr, valuePtr, (size_t)hashTable->bddId);
  CalNodeManagerAllocNode(hashTable->nodeManager, bddNode);
  CalBddNodePutThenBdd(bddNode, keyBdd);
  CalBddNodePutElseBddNode(bddNode, dataPtr);
  CalBddNodePutNextBddNode(bddNode, hashTable->bins[hashValue]);
  hashTable->bins[hashValue] = bddNode;
}

int
CalHashTableOneLookup(CalHashTable_t * hashTable, Cal_Bdd_t  keyBdd,
                      char ** valuePtrPtr)
{
  CalBddNode_t *ptr;
  Cal_Bdd_t tmpBdd;
  int hashValue;
  
  hashValue = HashTableOneDoHash(hashTable, keyBdd);
  ptr = hashTable->bins[hashValue];
  while(ptr != Cal_Nil(CalBddNode_t)){
    CalBddNodeGetThenBdd(ptr, tmpBdd);
    if(CalBddIsEqual(keyBdd, tmpBdd)){
      if(valuePtrPtr){
        *valuePtrPtr = (char *)CalBddNodeGetElseBddNode(ptr);
      }
      return 1;
    }
    ptr = CalBddNodeGetNextBddNode(ptr);
  }
  if(valuePtrPtr){
    *valuePtrPtr = Cal_Nil(char);
  }
  return 0;
}
/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/

static void
HashTableOneRehash(
  CalHashTable_t * hashTable,
  int  grow)
{
  CalBddNode_t *ptr, *next;
  CalBddNode_t **oldBins = hashTable->bins;
  int i, hashValue;
  int oldNumBins = hashTable->numBins;
  Cal_Bdd_t keyBdd;

  if(grow){
    hashTable->sizeIndex++;
  }
  else{
    if (hashTable->sizeIndex <= HASH_TABLE_DEFAULT_SIZE_INDEX){/* No need to rehash */
      return;
    }
    hashTable->sizeIndex--;
  }

  hashTable->numBins = TABLE_SIZE(hashTable->sizeIndex);
  hashTable->maxCapacity = hashTable->numBins * HASH_TABLE_DEFAULT_MAX_DENSITY;
  hashTable->bins = Cal_MemAlloc(CalBddNode_t *, hashTable->numBins);
  if(hashTable->bins == Cal_Nil(CalBddNode_t *)){
    CalBddFatalMessage("out of memory");
  }
  for(i = 0; i < hashTable->numBins; i++){
    hashTable->bins[i] = Cal_Nil(CalBddNode_t);
  }

  for(i = 0; i < oldNumBins; i++){
    ptr = oldBins[i];
    while(ptr != Cal_Nil(CalBddNode_t)){
      next = CalBddNodeGetNextBddNode(ptr);
      CalBddNodeGetThenBdd(ptr, keyBdd);
      hashValue = HashTableOneDoHash(hashTable, keyBdd);
      CalBddNodePutNextBddNode(ptr, hashTable->bins[hashValue]);
      hashTable->bins[hashValue] = ptr;
      ptr = next;
    }
  }
  Cal_MemFree(oldBins);
}

---