Robust/src/Runtime/DSTM/interface/clookup2.c

   1 #include "clookup2.h"
   2 #define INLINE    inline __attribute__((always_inline))
   3
   4 chashtable_t *chashCreate(unsigned int size, float loadfactor) {
   5   chashtable_t *ctable;
   6   struct chashentry *nodes;
   7   int i;
   8
   9   if((ctable = calloc(1, sizeof(chashtable_t))) == NULL) {
  10     printf("Calloc error %s %d\n", __FILE__, __LINE__);
  11     return NULL;
  12   }
  13
  14   // Allocate space for the hash table
  15   if((nodes = calloc(size, sizeof(struct chashentry))) == NULL) {
  16     printf("Calloc error %s %d\n", __FILE__, __LINE__);
  17     free(ctable);
  18     return NULL;
  19   }
  20
  21   ctable->table = nodes;
  22   ctable->size = size;
  23   ctable->mask = (size << 1)-1;
  24   ctable->numelements = 0; // Initial number of elements in the hash
  25   ctable->loadfactor = loadfactor;
  26   ctable->capacity=ctable->loadfactor*ctable->size;
  27   return ctable;
  28 }
  29
  30 //Finds the right bin in the hash table
  31 static INLINE unsigned int chashFunction(chashtable_t *table, unsigned int key) {
  32   return ( key & (table->mask))>>1; //throw away low order bit
  33 }
  34
  35 //Store objects and their pointers into hash
  36 void chashInsert(chashtable_t *table, unsigned int key, void *val) {
  37   unsigned int newsize;
  38   unsigned int index;
  39   struct chashentry *node;
  40
  41   if(table->numelements > table->capacity) {
  42     //Resize
  43     newsize = table->size << 1;
  44     chashResize(table,newsize);
  45   }
  46   index=(key &table->mask)>>1;
  47   while(1) {
  48     node = & table->table[index];
  49     if (node->ptr==NULL) {
  50       node->ptr=val;
  51       node->key=key;
  52       return;
  53     }
  54     index++;
  55     if (index==table->size)
  56       index=0;
  57   }
  58 }
  59
  60 // Search for an address for a given oid
  61 INLINE void * chashSearch(chashtable_t *table, unsigned int key) {
  62   //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE
  63   unsigned int tmp=(key &table->mask)>>1;
  64   struct chashentry *node;
  65   unsigned int ckey;
  66   while(1) {
  67     node = & table->table[tmp];
  68     ckey=node->key;
  69     if (ckey==key)
  70       return node->ptr;
  71     if (ckey==0)
  72       return NULL;
  73     tmp++;
  74     if (tmp==table->size)
  75       tmp=0;
  76   }
  77 }
  78
  79 void chashResize(chashtable_t *table, unsigned int newsize) {
  80   unsigned int oldsize=table->size;
  81   struct chashentry *ptr= table->table;
  82   struct chashentry *node= calloc(newsize, sizeof(struct chashentry));
  83   unsigned int mask;
  84   unsigned int i;
  85   struct chashentry *newnode;
  86   unsigned int bin;
  87   unsigned int key;
  88   struct chashentry *curr;
  89
  90   if(node == NULL) {
  91     printf("Calloc error %s %d\n", __FILE__, __LINE__);
  92     return;
  93   }
  94
  95   table->table = node;          //Update the global hashtable upon resize()
  96   table->size = newsize;
  97   mask=table->mask = (newsize << 1)-1;
  98   table->numelements = 0;
  99
 100   for(i = 0; i < oldsize; i++) {                        //Outer loop for each bin in hash table
 101     curr=& ptr[i];
 102     key=curr->key;
 103     if (key != 0) {
 104       bin=(key&mask)>>1;
 105       while(1) {
 106         newnode= & table->table[bin];
 107         if (newnode->key==0) {
 108           newnode->key=key;
 109           newnode->ptr=curr->ptr;
 110           break;
 111         }
 112         bin++;
 113         if (bin==newsize)
 114           bin=0;
 115       }
 116
 117     }
 118   }
 119   free(ptr);            //Free the memory of the old hash table
 120 }
 121
 122 //Delete the entire hash table
 123 void chashDelete(chashtable_t *ctable) {
 124   free(ctable->table);
 125   free(ctable);
 126 }