Robust/src/Runtime/oooJava/hashRCR.c

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