2 #define INLINE inline __attribute__((always_inline))
4 chashtable_t *chashCreate(unsigned int size, float loadfactor) {
6 struct chashentry *nodes;
9 if((ctable = calloc(1, sizeof(chashtable_t))) == NULL) {
10 printf("Calloc error %s %d\n", __FILE__, __LINE__);
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__);
21 ctable->table = nodes;
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;
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
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++;
47 if(ne > table->capacity) {
49 unsigned int newsize = table->size << 1;
50 chashResize(table,newsize);
51 node = &table->table[(key & table->mask)>>1];
61 node = &table->table[((key+i*331) & table->mask)>>1];
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];
82 node = &table->table[((key+i*331) & table->mask)>>1];
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));
97 struct chashentry *newnode;
100 struct chashentry *curr;
103 printf("Calloc error %s %d\n", __FILE__, __LINE__);
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);
111 for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table
115 newnode= &table->table[(key&mask)>>1];
116 if (newnode->key==0) {
118 newnode->ptr=curr->ptr;
122 for(bin=1; 1; bin++) {
123 newnode = &table->table[((key+bin*331) & mask)>>1];
124 if (newnode->key==0) {
126 newnode->ptr=curr->ptr;
132 free(ptr); //Free the memory of the old hash table
135 //Delete the entire hash table
136 void chashDelete(chashtable_t *ctable) {