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

   1 #include "clookup.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, unsigned int i) {
  32   return ((key+i*331) & 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   struct chashentry *node = &table->table[(key & table->mask)>>1];
  38   unsigned int ne=table->numelements++;
  39   unsigned int i;
  40
  41   if (node->key==0) {
  42     node->ptr=val;
  43     node->key=key;
  44     return;
  45   }
  46
  47   if(ne > table->capacity) {
  48     //Resize
  49     unsigned int newsize = table->size << 1;
  50     chashResize(table,newsize);
  51     node = &table->table[(key & table->mask)>>1];
  52     if (node->key==0) {
  53       node->ptr=val;
  54       node->key=key;
  55       return;
  56     }
  57   }
  58
  59
  60   for(i=1; 1; i++) {
  61     node = &table->table[((key+i*331) & table->mask)>>1];
  62     if (node->key==0) {
  63       node->ptr=val;
  64       node->key=key;
  65       return;
  66     }
  67   }
  68 }
  69
  70 // Search for an address for a given oid
  71 INLINE void * chashSearch(chashtable_t *table, unsigned int key) {
  72   //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE
  73   struct chashentry *node=&table->table[(key & table->mask)>>1];
  74   unsigned int i,ckey;
  75
  76   if (node->key==key)
  77     return node->ptr;
  78   if (node->key==0)
  79     return NULL;
  80
  81   for(i=1; 1; i++) {
  82     node = &table->table[((key+i*331) & table->mask)>>1];
  83     ckey=node->key;
  84     if (ckey==key)
  85       return node->ptr;
  86     if (ckey==0)
  87       return NULL;
  88   }
  89 }
  90
  91 void chashResize(chashtable_t *table, unsigned int newsize) {
  92   unsigned int oldsize=table->size;
  93   struct chashentry *ptr= table->table;
  94   struct chashentry *node= calloc(newsize, sizeof(struct chashentry));
  95   unsigned int mask;
  96   unsigned int i;
  97   struct chashentry *newnode;
  98   unsigned int bin;
  99   unsigned int key;
 100   struct chashentry *curr;
 101
 102   if(node == NULL) {
 103     printf("Calloc error %s %d\n", __FILE__, __LINE__);
 104     return;
 105   }
 106   table->table = node;          //Update the global hashtable upon resize()
 107   table->size = newsize;
 108   table->capacity=table->loadfactor*table->size;
 109   mask=(table->mask = (newsize << 1)-1);
 110
 111   for(i = 0; i < oldsize; i++) {                        //Outer loop for each bin in hash table
 112     curr=&ptr[i];
 113     key=curr->key;
 114     if (key != 0) {
 115       newnode= &table->table[(key&mask)>>1];
 116       if (newnode->key==0) {
 117         newnode->key=key;
 118         newnode->ptr=curr->ptr;
 119         continue;
 120       }
 121
 122       for(bin=1; 1; bin++) {
 123         newnode = &table->table[((key+bin*331) & mask)>>1];
 124         if (newnode->key==0) {
 125           newnode->key=key;
 126           newnode->ptr=curr->ptr;
 127           break;
 128         }
 129       }
 130     }
 131   }
 132   free(ptr);            //Free the memory of the old hash table
 133 }
 134
 135 //Delete the entire hash table
 136 void chashDelete(chashtable_t *ctable) {
 137   free(ctable->table);
 138   free(ctable);
 139 }