From e1ae8762bce3f1df594ae66842fa70fee0a555b8 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Wed, 22 Oct 2008 00:53:50 +0000 Subject: [PATCH] extra hash table implementation...might be worth trying --- Robust/src/Runtime/DSTM/interface/clookup2.c | 126 +++++++++++++++++++ Robust/src/Runtime/DSTM/interface/clookup2.h | 34 +++++ 2 files changed, 160 insertions(+) create mode 100644 Robust/src/Runtime/DSTM/interface/clookup2.c create mode 100644 Robust/src/Runtime/DSTM/interface/clookup2.h diff --git a/Robust/src/Runtime/DSTM/interface/clookup2.c b/Robust/src/Runtime/DSTM/interface/clookup2.c new file mode 100644 index 00000000..043d9744 --- /dev/null +++ b/Robust/src/Runtime/DSTM/interface/clookup2.c @@ -0,0 +1,126 @@ +#include "clookup2.h" +#define INLINE inline __attribute__((always_inline)) + +chashtable_t *chashCreate(unsigned int size, float loadfactor) { + chashtable_t *ctable; + struct chashentry *nodes; + int i; + + if((ctable = calloc(1, sizeof(chashtable_t))) == NULL) { + printf("Calloc error %s %d\n", __FILE__, __LINE__); + return NULL; + } + + // Allocate space for the hash table + if((nodes = calloc(size, sizeof(struct chashentry))) == NULL) { + printf("Calloc error %s %d\n", __FILE__, __LINE__); + free(ctable); + return NULL; + } + + ctable->table = nodes; + ctable->size = size; + ctable->mask = (size << 1)-1; + ctable->numelements = 0; // Initial number of elements in the hash + ctable->loadfactor = loadfactor; + ctable->capacity=ctable->loadfactor*ctable->size; + return ctable; +} + +//Finds the right bin in the hash table +static INLINE unsigned int chashFunction(chashtable_t *table, unsigned int key) { + return ( key & (table->mask))>>1; //throw away low order bit +} + +//Store objects and their pointers into hash +void chashInsert(chashtable_t *table, unsigned int key, void *val) { + unsigned int newsize; + unsigned int index; + struct chashentry *node; + + if(table->numelements > table->capacity) { + //Resize + newsize = table->size << 1; + chashResize(table,newsize); + } + index=(key &table->mask)>>1; + while(1) { + node = & table->table[index]; + if (node->ptr==NULL) { + node->ptr=val; + node->key=key; + return; + } + index++; + if (index==table->size) + index=0; + } +} + +// Search for an address for a given oid +INLINE void * chashSearch(chashtable_t *table, unsigned int key) { + //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE + unsigned int tmp=(key &table->mask)>>1; + struct chashentry *node; + unsigned int ckey; + while(1) { + node = & table->table[tmp]; + ckey=node->key; + if (ckey==key) + return node->ptr; + if (ckey==0) + return NULL; + tmp++; + if (tmp==table->size) + tmp=0; + } +} + +void chashResize(chashtable_t *table, unsigned int newsize) { + unsigned int oldsize=table->size; + struct chashentry *ptr= table->table; + struct chashentry *node= calloc(newsize, sizeof(struct chashentry)); + unsigned int mask; + unsigned int i; + struct chashentry *newnode; + unsigned int bin; + unsigned int key; + struct chashentry *curr; + + if(node == NULL) { + printf("Calloc error %s %d\n", __FILE__, __LINE__); + return; + } + + table->table = node; //Update the global hashtable upon resize() + table->size = newsize; + mask=table->mask = (newsize << 1)-1; + table->numelements = 0; + + for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table + curr=& ptr[i]; + key=curr->key; + if (key != 0) { + bin=(key&mask)>>1; + while(1) { + newnode= & table->table[bin]; + if (newnode->key==0) { + newnode->key=key; + newnode->ptr=curr->ptr; + break; + } + bin++; + if (bin==newsize) + bin=0; + } + + } + } + free(ptr); //Free the memory of the old hash table +} + +//Delete the entire hash table +void chashDelete(chashtable_t *ctable) { + free(ctable->table); + free(ctable); +} diff --git a/Robust/src/Runtime/DSTM/interface/clookup2.h b/Robust/src/Runtime/DSTM/interface/clookup2.h new file mode 100644 index 00000000..cafa0a72 --- /dev/null +++ b/Robust/src/Runtime/DSTM/interface/clookup2.h @@ -0,0 +1,34 @@ +#ifndef _CLOOKUP_H_ +#define _CLOOKUP_H_ + +#include +#include + +#define CLOADFACTOR 0.25 +#define CHASH_SIZE 1024 + +struct chashentry { + void * ptr; + unsigned int key; +}; + +typedef struct chashtable { + struct chashentry *table; + unsigned int size; + unsigned int mask; + unsigned int numelements; + unsigned int capacity; + float loadfactor; +} chashtable_t; + +/* Prototypes for hash*/ +chashtable_t *chashCreate(unsigned int size, float loadfactor); +static unsigned int chashFunction(chashtable_t *table, unsigned int key); +void chashInsert(chashtable_t *table, unsigned int key, void *val); +void *chashSearch(chashtable_t *table, unsigned int key); //returns val, NULL if not found +void chashResize(chashtable_t *table, unsigned int newsize); +void chashDelete(chashtable_t *table); +/* end hash */ + +#endif + -- 2.34.1