-#include "hashRCR.h"
-#include <strings.h>
-#define likely(x) __builtin_expect((x),1)
-#define unlikely(x) __builtin_expect((x),0)
-
-//Smallest Object Size with 1 ptr is 32bytes on on 64-bit machine and 24bytes on 32-bit machine
-#ifdef BIT64
-#define SHIFTBITS 5
-#else
-#define SHIFTBITS 4
-#endif
-
-__thread dchashlistnode_t *dc_c_table = NULL;
-__thread dchashlistnode_t *dc_c_list = NULL;
-__thread dcliststruct_t *dc_c_structs= NULL;
-__thread unsigned int dc_c_size;
-__thread unsigned INTPTR dc_c_mask;
-__thread unsigned int dc_c_numelements;
-__thread unsigned int dc_c_threshold;
-__thread double dc_c_loadfactor;
-
-void hashRCRCreate(unsigned int size, double loadfactor) {
- // Allocate space for the hash table
-
- dc_c_table = calloc(size, sizeof(dchashlistnode_t));
- dc_c_loadfactor = loadfactor;
- dc_c_size = size;
- dc_c_threshold=size*loadfactor;
- dc_c_mask = (size << SHIFTBITS)-1;
- dc_c_structs=calloc(1, sizeof(dcliststruct_t));
- dc_c_numelements = 0; // Initial number of elements in the hash
- dc_c_list=NULL;
-}
-
-void hashRCRreset() {
- if(dc_c_table == NULL) {
- hashRCRCreate(128, 0.75);
- }
-
- dchashlistnode_t *ptr = dc_c_table;
-
- if (dc_c_numelements<(dc_c_size>>SHIFTBITS)) {
- dchashlistnode_t *top=&ptr[dc_c_size];
- dchashlistnode_t *tmpptr=dc_c_list;
- while(tmpptr!=NULL) {
- dchashlistnode_t *next=tmpptr->lnext;
- if (tmpptr>=ptr&&tmpptr<top) {
- //zero in list
- tmpptr->key=NULL;
- tmpptr->next=NULL;
- }
- tmpptr=next;
- }
- } else {
- bzero(dc_c_table, sizeof(dchashlistnode_t)*dc_c_size);
- }
- while(dc_c_structs->next!=NULL) {
- dcliststruct_t *next=dc_c_structs->next;
- free(dc_c_structs);
- dc_c_structs=next;
- }
- dc_c_structs->num = 0;
- dc_c_numelements = 0;
- dc_c_list=NULL;
-}
-
-//Store objects and their pointers into hash
-//1 = add success
-//0 = object already exists / Add failed
-int hashRCRInsert(void * key) {
- dchashlistnode_t *ptr;
-
- if (unlikely(key==NULL)) {
- return 0;
- }
-
- if(unlikely(dc_c_numelements > dc_c_threshold)) {
- //Resize
- unsigned int newsize = dc_c_size << 1;
- hashRCRResize(newsize);
- }
- ptr = &dc_c_table[(((unsigned INTPTR)key)&dc_c_mask)>>SHIFTBITS];
- if(likely(ptr->key==0)) {
- ptr->key=key;
- ptr->lnext=dc_c_list;
- dc_c_list=ptr;
- dc_c_numelements++;
- } else { // Insert in the beginning of linked list
- dchashlistnode_t * node;
- dchashlistnode_t *search=ptr;
-
- //make sure it isn't here
- do {
- if(search->key == key) {
- return 0;
- }
- search=search->next;
- } while(search != NULL);
-
- dc_c_numelements++;
- if (dc_c_structs->num<NUMDCLIST) {
- node=&dc_c_structs->array[dc_c_structs->num];
- dc_c_structs->num++;
- } else {
- //get new list
- dcliststruct_t *tcl=calloc(1,sizeof(dcliststruct_t));
- tcl->next=dc_c_structs;
- dc_c_structs=tcl;
- node=&tcl->array[0];
- tcl->num=1;
- }
- node->key = key;
- node->next = ptr->next;
- ptr->next=node;
- node->lnext=dc_c_list;
- dc_c_list=node;
- }
-
- return 1;
-}
-
-
-unsigned int hashRCRResize(unsigned int newsize) {
- dchashlistnode_t *node, *ptr, *curr; // curr and next keep track of the current and the next chashlistnodes in a linked list
- unsigned int oldsize;
- int isfirst; // Keeps track of the first element in the chashlistnode_t for each bin in hashtable
- unsigned int i,index;
- unsigned int mask;
-
- ptr = dc_c_table;
- oldsize = dc_c_size;
- dc_c_list=NULL;
-
- if((node = calloc(newsize, sizeof(dchashlistnode_t))) == NULL) {
- printf("Calloc error %s %d\n", __FILE__, __LINE__);
- return 1;
- }
-
- dc_c_table = node; //Update the global hashtable upon resize()
- dc_c_size = newsize;
- dc_c_threshold = newsize * dc_c_loadfactor;
- mask=dc_c_mask = (newsize << SHIFTBITS)-1;
-
- for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table
- curr = &ptr[i];
- isfirst = 1;
- do { //Inner loop to go through linked lists
- void * key;
- dchashlistnode_t *tmp,*next;
-
- if ((key=curr->key) == 0) { //Exit inner loop if there the first element is 0
- break; //key = val =0 for element if not present within the hash table
- }
-
- index = (((unsigned INTPTR)key) & mask) >>SHIFTBITS;
- tmp=&node[index];
- next = curr->next;
- // Insert into the new table
- if(tmp->key == 0) {
- tmp->key = key;
- tmp->lnext=dc_c_list;
- dc_c_list=tmp;
- } /*
- NOTE: Add this case if you change this...
- This case currently never happens because of the way things rehash....
- else if (isfirst) {
- chashlistnode_t *newnode= calloc(1, sizeof(chashlistnode_t));
- newnode->key = curr->key;
- newnode->val = curr->val;
- newnode->next = tmp->next;
- tmp->next=newnode;
- } */
- else {
- curr->next=tmp->next;
- tmp->next=curr;
- curr->lnext=dc_c_list;
- dc_c_list=curr;
- }
-
- isfirst = 0;
- curr = next;
- } while(curr!=NULL);
- }
-
- free(ptr); //Free the memory of the old hash table
- return 0;
-}
-
-//Delete the entire hash table
-void hashRCRDelete() {
- dcliststruct_t *ptr=dc_c_structs;
- while(ptr!=NULL) {
- dcliststruct_t *next=ptr->next;
- free(ptr);
- ptr=next;
- }
- free(dc_c_table);
- dc_c_table=NULL;
- dc_c_structs=NULL;
- dc_c_list=NULL;
-}
-
-// Search for an address for a given Address
-INLINE int hashRCRSearch(void * key) {
- //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE
- dchashlistnode_t *node = &dc_c_table[(((unsigned INTPTR)key) & dc_c_mask)>>SHIFTBITS];
-
- do {
- if(node->key == key) {
- return 1;
- }
- node = node->next;
- } while(node != NULL);
-
- return 0;
-}
+#include "hashRCR.h"\r
+#include <strings.h>\r
+#define likely(x) __builtin_expect((x),1)\r
+#define unlikely(x) __builtin_expect((x),0)\r
+\r
+//Smallest Object Size with 1 ptr is 32bytes on on 64-bit machine and 24bytes on 32-bit machine\r
+#ifdef BIT64\r
+#define SHIFTBITS 5\r
+#else\r
+#define SHIFTBITS 4\r
+#endif\r
+\r
+__thread dchashlistnode_t *dc_c_table = NULL;\r
+__thread dchashlistnode_t *dc_c_list = NULL;\r
+__thread dcliststruct_t *dc_c_structs= NULL;\r
+__thread unsigned int dc_c_size;\r
+__thread unsigned INTPTR dc_c_mask;\r
+__thread unsigned int dc_c_numelements;\r
+__thread unsigned int dc_c_threshold;\r
+__thread double dc_c_loadfactor;\r
+\r
+void hashRCRCreate(unsigned int size, double loadfactor) {\r
+ // Allocate space for the hash table\r
+\r
+ dc_c_table = calloc(size, sizeof(dchashlistnode_t));\r
+ dc_c_loadfactor = loadfactor;\r
+ dc_c_size = size;\r
+ dc_c_threshold=size*loadfactor;\r
+ dc_c_mask = (size << SHIFTBITS)-1;\r
+ dc_c_structs=calloc(1, sizeof(dcliststruct_t));\r
+ dc_c_numelements = 0; // Initial number of elements in the hash\r
+ dc_c_list=NULL;\r
+}\r
+\r
+void hashRCRreset() {\r
+ if(dc_c_table == NULL) {\r
+ hashRCRCreate(128, 0.75);\r
+ }\r
+\r
+ dchashlistnode_t *ptr = dc_c_table;\r
+\r
+ if (dc_c_numelements<(dc_c_size>>SHIFTBITS)) {\r
+ dchashlistnode_t *top=&ptr[dc_c_size];\r
+ dchashlistnode_t *tmpptr=dc_c_list;\r
+ while(tmpptr!=NULL) {\r
+ dchashlistnode_t *next=tmpptr->lnext;\r
+ if (tmpptr>=ptr&&tmpptr<top) {\r
+ //zero in list\r
+ tmpptr->object=NULL;\r
+ tmpptr->next=NULL;\r
+ }\r
+ tmpptr=next;\r
+ }\r
+ } else {\r
+ bzero(dc_c_table, sizeof(dchashlistnode_t)*dc_c_size);\r
+ }\r
+ while(dc_c_structs->next!=NULL) {\r
+ dcliststruct_t *next=dc_c_structs->next;\r
+ free(dc_c_structs);\r
+ dc_c_structs=next;\r
+ }\r
+ dc_c_structs->num = 0;\r
+ dc_c_numelements = 0;\r
+ dc_c_list=NULL;\r
+}\r
+\r
+//Store objects and their pointers into hash\r
+//1 = add success\r
+//0 = object already exists / Add failed\r
+int hashRCRInsert(void * objectPtr, int traverserState) {\r
+ dchashlistnode_t *ptr;\r
+\r
+ if (unlikely(objectPtr==NULL)) {\r
+ return 0;\r
+ }\r
+\r
+ if(unlikely(dc_c_numelements > dc_c_threshold)) {\r
+ //Resize\r
+ unsigned int newsize = dc_c_size << 1;\r
+ hashRCRResize(newsize);\r
+ }\r
+ ptr = &dc_c_table[(((unsigned INTPTR)objectPtr)&dc_c_mask)>>SHIFTBITS];\r
+ if(likely(ptr->object==0)) {\r
+ ptr->object=objectPtr;\r
+ ptr->traverserState = traverserState;\r
+ ptr->lnext=dc_c_list;\r
+ dc_c_list=ptr;\r
+ dc_c_numelements++;\r
+ } else { // Insert in the beginning of linked list\r
+ dchashlistnode_t * node;\r
+ dchashlistnode_t *search=ptr;\r
+ \r
+ //make sure it isn't here\r
+ do {\r
+ if(search->object == objectPtr && search->traverserState == traverserState) {\r
+ return 0;\r
+ }\r
+ search=search->next;\r
+ } while(search != NULL);\r
+\r
+ dc_c_numelements++; \r
+ if (dc_c_structs->num<NUMDCLIST) {\r
+ node=&dc_c_structs->array[dc_c_structs->num];\r
+ dc_c_structs->num++;\r
+ } else {\r
+ //get new list\r
+ dcliststruct_t *tcl=calloc(1,sizeof(dcliststruct_t));\r
+ tcl->next=dc_c_structs;\r
+ dc_c_structs=tcl;\r
+ node=&tcl->array[0];\r
+ tcl->num=1;\r
+ }\r
+ node->object = objectPtr;\r
+ node->traverserState=traverserState;\r
+ node->next = ptr->next;\r
+ ptr->next=node;\r
+ node->lnext=dc_c_list;\r
+ dc_c_list=node;\r
+ }\r
+\r
+ return 1;\r
+}\r
+\r
+\r
+unsigned int hashRCRResize(unsigned int newsize) {\r
+ dchashlistnode_t *node, *ptr, *curr; // curr and next keep track of the current and the next chashlistnodes in a linked list\r
+ unsigned int oldsize;\r
+ int isfirst; // Keeps track of the first element in the chashlistnode_t for each bin in hashtable\r
+ unsigned int i,index;\r
+ unsigned int mask;\r
+\r
+ ptr = dc_c_table;\r
+ oldsize = dc_c_size;\r
+ dc_c_list=NULL;\r
+\r
+ if((node = calloc(newsize, sizeof(dchashlistnode_t))) == NULL) {\r
+ printf("Calloc error %s %d\n", __FILE__, __LINE__);\r
+ return 1;\r
+ }\r
+\r
+ dc_c_table = node; //Update the global hashtable upon resize()\r
+ dc_c_size = newsize;\r
+ dc_c_threshold = newsize * dc_c_loadfactor;\r
+ mask=dc_c_mask = (newsize << SHIFTBITS)-1;\r
+\r
+ for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table\r
+ curr = &ptr[i];\r
+ isfirst = 1;\r
+ do { //Inner loop to go through linked lists\r
+ void * key;\r
+ dchashlistnode_t *tmp,*next;\r
+\r
+ if ((key=curr->object) == 0) { //Exit inner loop if there the first element is 0\r
+ break; //key = val =0 for element if not present within the hash table\r
+ }\r
+\r
+ index = (((unsigned INTPTR)key) & mask) >>SHIFTBITS;\r
+ tmp=&node[index];\r
+ next = curr->next;\r
+ // Insert into the new table\r
+ if(tmp->object == 0) {\r
+ tmp->object = key;\r
+ tmp->traverserState = curr->traverserState;\r
+ tmp->lnext=dc_c_list;\r
+ dc_c_list=tmp;\r
+ } /*\r
+ NOTE: Add this case if you change this...\r
+ This case currently never happens because of the way things rehash....\r
+ else if (isfirst) {\r
+ chashlistnode_t *newnode= calloc(1, sizeof(chashlistnode_t));\r
+ newnode->key = curr->key;\r
+ newnode->val = curr->val;\r
+ newnode->next = tmp->next;\r
+ tmp->next=newnode;\r
+ } */\r
+ else {\r
+ curr->next=tmp->next;\r
+ tmp->next=curr;\r
+ curr->lnext=dc_c_list;\r
+ dc_c_list=curr;\r
+ }\r
+\r
+ isfirst = 0;\r
+ curr = next;\r
+ } while(curr!=NULL);\r
+ }\r
+\r
+ free(ptr); //Free the memory of the old hash table\r
+ return 0;\r
+}\r
+\r
+//Delete the entire hash table\r
+void hashRCRDelete() {\r
+ dcliststruct_t *ptr=dc_c_structs;\r
+ while(ptr!=NULL) {\r
+ dcliststruct_t *next=ptr->next;\r
+ free(ptr);\r
+ ptr=next;\r
+ }\r
+ free(dc_c_table);\r
+ dc_c_table=NULL;\r
+ dc_c_structs=NULL;\r
+ dc_c_list=NULL;\r
+}\r
+\r
+// Search for an address for a given Address\r
+INLINE int hashRCRSearch(void * objectPtr, int traverserState) {\r
+ //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE\r
+ dchashlistnode_t *node = &dc_c_table[(((unsigned INTPTR)objectPtr) & dc_c_mask)>>SHIFTBITS];\r
+ \r
+ do {\r
+ if(node->object == objectPtr && node->traverserState == traverserState) {\r
+ return 1;\r
+ }\r
+ node = node->next;\r
+ } while(node != NULL);\r
+\r
+ return 0;\r
+}\r
projects / IRC.git / blobdiff