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