Robust/src/Runtime/oooJava/hashRCR.c

   1 #include "hashRCR.h"
   2 #include <strings.h>
   3 #define likely(x) __builtin_expect((x),1)
   4 #define unlikely(x) __builtin_expect((x),0)
   5
   6 //Smallest Object Size with 1 ptr is 32bytes on on 64-bit machine and 24bytes on 32-bit machine
   7 #ifdef BIT64
   8 #define SHIFTBITS 5
   9 #else
  10 #define SHIFTBITS 4
  11 #endif
  12
  13 __thread dchashlistnode_t *dc_c_table = NULL;
  14 __thread dchashlistnode_t *dc_c_list = NULL;
  15 __thread dcliststruct_t *dc_c_structs= NULL;
  16 __thread unsigned int dc_c_size;
  17 __thread unsigned INTPTR dc_c_mask;
  18 __thread unsigned int dc_c_numelements;
  19 __thread unsigned int dc_c_threshold;
  20 __thread double dc_c_loadfactor;
  21
  22 void hashRCRCreate(unsigned int size, double loadfactor) {
  23   // Allocate space for the hash table
  24
  25   dc_c_table = calloc(size, sizeof(dchashlistnode_t));
  26   dc_c_loadfactor = loadfactor;
  27   dc_c_size = size;
  28   dc_c_threshold=size*loadfactor;
  29   dc_c_mask = (size << SHIFTBITS)-1;
  30   dc_c_structs=calloc(1, sizeof(dcliststruct_t));
  31   dc_c_numelements = 0; // Initial number of elements in the hash
  32   dc_c_list=NULL;
  33 }
  34
  35 void hashRCRreset() {
  36   if(dc_c_table == NULL) {
  37     hashRCRCreate(128, 0.75);
  38   }
  39
  40   dchashlistnode_t *ptr = dc_c_table;
  41
  42   if (dc_c_numelements<(dc_c_size>>SHIFTBITS)) {
  43     dchashlistnode_t *top=&ptr[dc_c_size];
  44     dchashlistnode_t *tmpptr=dc_c_list;
  45     while(tmpptr!=NULL) {
  46       dchashlistnode_t *next=tmpptr->lnext;
  47       if (tmpptr>=ptr&&tmpptr<top) {
  48         //zero in list
  49         tmpptr->key=NULL;
  50         tmpptr->next=NULL;
  51       }
  52       tmpptr=next;
  53     }
  54   } else {
  55     bzero(dc_c_table, sizeof(dchashlistnode_t)*dc_c_size);
  56   }
  57   while(dc_c_structs->next!=NULL) {
  58     dcliststruct_t *next=dc_c_structs->next;
  59     free(dc_c_structs);
  60     dc_c_structs=next;
  61   }
  62   dc_c_structs->num = 0;
  63   dc_c_numelements = 0;
  64   dc_c_list=NULL;
  65 }
  66
  67 //Store objects and their pointers into hash
  68 //1 = add success
  69 //0 = object already exists / Add failed
  70 int hashRCRInsert(void * key) {
  71   dchashlistnode_t *ptr;
  72
  73   if (unlikely(key==NULL)) {
  74     return 0;
  75   }
  76
  77   if(unlikely(dc_c_numelements > dc_c_threshold)) {
  78     //Resize
  79     unsigned int newsize = dc_c_size << 1;
  80     hashRCRResize(newsize);
  81   }
  82   ptr = &dc_c_table[(((unsigned INTPTR)key)&dc_c_mask)>>SHIFTBITS];
  83   if(likely(ptr->key==0)) {
  84     ptr->key=key;
  85     ptr->lnext=dc_c_list;
  86     dc_c_list=ptr;
  87     dc_c_numelements++;
  88   } else { // Insert in the beginning of linked list
  89     dchashlistnode_t * node;
  90     dchashlistnode_t *search=ptr;
  91
  92     //make sure it isn't here
  93     do {
  94       if(search->key == key) {
  95         return 0;
  96       }
  97       search=search->next;
  98     } while(search != NULL);
  99
 100     dc_c_numelements++;
 101     if (dc_c_structs->num<NUMDCLIST) {
 102       node=&dc_c_structs->array[dc_c_structs->num];
 103       dc_c_structs->num++;
 104     } else {
 105       //get new list
 106       dcliststruct_t *tcl=calloc(1,sizeof(dcliststruct_t));
 107       tcl->next=dc_c_structs;
 108       dc_c_structs=tcl;
 109       node=&tcl->array[0];
 110       tcl->num=1;
 111     }
 112     node->key = key;
 113     node->next = ptr->next;
 114     ptr->next=node;
 115     node->lnext=dc_c_list;
 116     dc_c_list=node;
 117   }
 118
 119   return 1;
 120 }
 121
 122
 123 unsigned int hashRCRResize(unsigned int newsize) {
 124   dchashlistnode_t *node, *ptr, *curr;    // curr and next keep track of the current and the next chashlistnodes in a linked list
 125   unsigned int oldsize;
 126   int isfirst;    // Keeps track of the first element in the chashlistnode_t for each bin in hashtable
 127   unsigned int i,index;
 128   unsigned int mask;
 129
 130   ptr = dc_c_table;
 131   oldsize = dc_c_size;
 132   dc_c_list=NULL;
 133
 134   if((node = calloc(newsize, sizeof(dchashlistnode_t))) == NULL) {
 135     printf("Calloc error %s %d\n", __FILE__, __LINE__);
 136     return 1;
 137   }
 138
 139   dc_c_table = node;          //Update the global hashtable upon resize()
 140   dc_c_size = newsize;
 141   dc_c_threshold = newsize * dc_c_loadfactor;
 142   mask=dc_c_mask = (newsize << SHIFTBITS)-1;
 143
 144   for(i = 0; i < oldsize; i++) {                        //Outer loop for each bin in hash table
 145     curr = &ptr[i];
 146     isfirst = 1;
 147     do {                      //Inner loop to go through linked lists
 148       void * key;
 149       dchashlistnode_t *tmp,*next;
 150
 151       if ((key=curr->key) == 0) {             //Exit inner loop if there the first element is 0
 152         break;                  //key = val =0 for element if not present within the hash table
 153       }
 154
 155       index = (((unsigned INTPTR)key) & mask) >>SHIFTBITS;
 156       tmp=&node[index];
 157       next = curr->next;
 158       // Insert into the new table
 159       if(tmp->key == 0) {
 160         tmp->key = key;
 161         tmp->lnext=dc_c_list;
 162         dc_c_list=tmp;
 163       } /*
 164           NOTE:  Add this case if you change this...
 165           This case currently never happens because of the way things rehash....
 166           else if (isfirst) {
 167           chashlistnode_t *newnode= calloc(1, sizeof(chashlistnode_t));
 168           newnode->key = curr->key;
 169           newnode->val = curr->val;
 170           newnode->next = tmp->next;
 171           tmp->next=newnode;
 172           } */
 173       else {
 174         curr->next=tmp->next;
 175         tmp->next=curr;
 176         curr->lnext=dc_c_list;
 177         dc_c_list=curr;
 178       }
 179
 180       isfirst = 0;
 181       curr = next;
 182     } while(curr!=NULL);
 183   }
 184
 185   free(ptr);            //Free the memory of the old hash table
 186   return 0;
 187 }
 188
 189 //Delete the entire hash table
 190 void hashRCRDelete() {
 191   dcliststruct_t *ptr=dc_c_structs;
 192   while(ptr!=NULL) {
 193     dcliststruct_t *next=ptr->next;
 194     free(ptr);
 195     ptr=next;
 196   }
 197   free(dc_c_table);
 198   dc_c_table=NULL;
 199   dc_c_structs=NULL;
 200   dc_c_list=NULL;
 201 }
 202
 203 // Search for an address for a given Address
 204 INLINE int hashRCRSearch(void * key) {
 205   //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE
 206   dchashlistnode_t *node = &dc_c_table[(((unsigned INTPTR)key) & dc_c_mask)>>SHIFTBITS];
 207
 208   do {
 209     if(node->key == key) {
 210       return 1;
 211     }
 212     node = node->next;
 213   } while(node != NULL);
 214
 215   return 0;
 216 }