From 0507bf880d71e896359f6f7c55a38be441f0b464 Mon Sep 17 00:00:00 2001 From: adash Date: Thu, 8 Mar 2007 19:32:58 +0000 Subject: [PATCH] Tested functionality of llookup hash table with global hash table data structure TODO: implement pthread on hash table Added main() to test code --- Robust/src/Runtime/DSTM/interface/dstm.c | 185 +----------------- Robust/src/Runtime/DSTM/interface/dstm.h | 1 - Robust/src/Runtime/DSTM/interface/llookup.c | 149 ++++++++------ Robust/src/Runtime/DSTM/interface/llookup.h | 15 +- .../src/Runtime/DSTM/interface/testllookup.c | 42 ++++ 5 files changed, 138 insertions(+), 254 deletions(-) create mode 100644 Robust/src/Runtime/DSTM/interface/testllookup.c diff --git a/Robust/src/Runtime/DSTM/interface/dstm.c b/Robust/src/Runtime/DSTM/interface/dstm.c index 506dfd06..36c4b063 100644 --- a/Robust/src/Runtime/DSTM/interface/dstm.c +++ b/Robust/src/Runtime/DSTM/interface/dstm.c @@ -1,194 +1,19 @@ #include "dstm.h" -obj_store_t *obj_begin; // points to the first location of the object store linked list -//unsigned int hash_size; // number of entries in hash table - extern int classsize[]; -/* BEGIN - object store */ -// Initializes the pointers...currently invoked inside main() -void dstm_init(void) { - obj_begin = NULL; - return; -} -// Create a new object store of a given "size" as a linked list -void create_objstr(unsigned int size) { - obj_store_t *tmp, *ptr; - static int id = 0; // keeps track of which object store is it when there are more than one object store - - if ((tmp = (obj_store_t *) malloc(sizeof(obj_store_t))) < 0) { - printf("DSTM: Malloc error %s %d\n", __FILE__, __LINE__); - exit(-1); - } - if ((tmp->base = (char *) malloc(sizeof(char)*size)) < 0) { - printf("DSTM: Malloc error %s %d\n", __FILE__, __LINE__); - exit(-1); - } - tmp->size = size; - printf("The object store size is : %d\n", tmp->size); - tmp->top = tmp->base; - tmp->id = id++; - printf("The object store id is : %d\n", tmp->id); - tmp->next = obj_begin; //adds new object store to the linked list and updates obj_begin pointer to new object store node - obj_begin = tmp; - return; -} - -// Delete the object store numbered "id" -void delete_objstr(int id) { - //TODO Implement this along with garbage collector - return; -} - -obj_store_t *get_objstr_begin(void) { - return obj_begin; -} - -/* END object store */ - /* BEGIN object header */ + // Get a new object id -int get_newID(void) { - static int id = 0; - +unsigned int getNewOID(void) { + static int id = 1; return ++id; } -// Insert the object header and object into the object store -int insertObject(obj_header_t h) { - extern obj_addr_table_t mlut; //declared in the main mlut=>machine look up table - unsigned int left, req; // Keeps track of the space available in the current object store - obj_header_t *header; - - left = obj_begin->size - (obj_begin->top - obj_begin->base); - req = getObjSize(h) + sizeof(obj_header_t); - if (req < left) { - memcpy(obj_begin->top, &h, sizeof(obj_header_t)); - header = (obj_header_t *) obj_begin->top; - printf("The header points to : %d\n", header); - obj_begin->top = obj_begin->top + sizeof(obj_header_t) + getObjSize(h); //increment object store top when new object is inserted - printf("Top now points to :%d\n", obj_begin->top); - } else { - return -1; - } - printf("header: %d\n", header); - printf("The oid is : %d\n", h.oid); - addKey(h.oid, header, &mlut); //Update obj_addr_table - printf("Object id = %d\n",h.oid); - return 0; -} + // Get the size of the object for a given type -int getObjSize(obj_header_t h) { +unsigned int objSize(objheader_t *object) { return classsize[h.type]; } -// Initial object when it is created at first -void createObject(unsigned short type) { - obj_header_t h; - h.oid = get_newID(); - h.type = type; - h.version = 0; - h.rcount = 1; - h.status = CLEAN; - insertObject(h); -} /* END object header */ -/* BEGIN hash*/ -//obj_addr_table is a generic hash table structure -//hash is an array of pointers that point to the beginning of a obj_listnode_t DS -// "size" in hash table is the no of indices in the hash table and each index points to a pointer for an object_header -void createHash(obj_addr_table_t *table, int size, float loadfactor) { - int i; - - if ((table->hash = (obj_listnode_t **) malloc(sizeof(obj_listnode_t *)*size)) == NULL) { - printf("Malloc error %s %d\n", __FILE__, __LINE__); - exit(-1); - } - for (i = 0; i < size; i++) { // initialize the hash elements - table->hash[i] = NULL; - } - - table->size = size; - table->numelements = 0; - table->loadfactor = loadfactor; - - return; -} - -// Hash Resize -void resize(obj_addr_table_t * table){ - int newCapacity = 2*(table->size) + 1; - obj_listnode_t **old; - //if ((table->hash = (obj_listnode_t **) malloc(sizeof(obj_listnode_t *)*size)) == NULL) { -} - -// Hashing for the Key -int hashKey(unsigned int oid, obj_addr_table_t *table) { - // hash32shiftmult - int c2=0x27d4eb2d; // a prime or an odd constant - oid = (oid ^ 61) ^ (oid >> 16); - oid = oid + (oid << 3); - oid = oid ^ (oid >> 4); - oid = oid * c2; - oid = oid ^ (oid >> 15); - printf("The bucket number is %d\n", oid % (table->size)); - return (oid % (table->size)); -} - -//Add oid and its address to the new ob_listnode_t -void addKey(unsigned int oid, obj_header_t *ptr, obj_addr_table_t *table) { - int index; - obj_listnode_t *node; - - table->numelements++; - if(table->numelements > (table->loadfactor * table->size)){ - //TODO : check if table is nearly full and then resize - } - - index = hashKey(oid,table); - if ((node = (obj_listnode_t *) malloc(sizeof(obj_listnode_t))) == NULL) { - printf("Malloc error %s %d\n", __FILE__, __LINE__); - exit(-1); - } - node->oid = oid; - node->object = ptr; - node->next = table->hash[index]; - table->hash[index] = node; - return; -} -// Get the address of the object header for a given oid -obj_header_t *findKey(unsigned int oid, obj_addr_table_t *table) { - int index; - obj_listnode_t *ptr; - - index = hashKey(oid,table); - ptr = table->hash[index]; - while(ptr != NULL) { - if (ptr->oid == oid) { - return ptr->object; - } - ptr = ptr->next; - } - return NULL; -} -// Remove the pointer to the object header from a linked list of obj_listnode_t given an oid -int removeKey(unsigned int oid, obj_addr_table_t *table) { - int index; - obj_listnode_t *curr, *prev; // prev points to previous node and curr points to the node to be deleted - - index = hashKey(oid,table); - prev = curr = table->hash[index]; - for (; curr != NULL; curr = curr->next) { - if (curr->oid == oid) { // Find a match in the hash table - table->numelements--; - prev->next = curr->next; - if (table->hash[index] == curr) { // Special case when there is one element pointed by the hash table - table->hash[index] = NULL; - } - free(curr); - return 0; - } - prev = curr; - } - return -1; -} diff --git a/Robust/src/Runtime/DSTM/interface/dstm.h b/Robust/src/Runtime/DSTM/interface/dstm.h index 3b938a7f..9651f3dc 100644 --- a/Robust/src/Runtime/DSTM/interface/dstm.h +++ b/Robust/src/Runtime/DSTM/interface/dstm.h @@ -4,7 +4,6 @@ #include #include #include -#include "hashtable.h" enum status {CLEAN, DIRTY}; diff --git a/Robust/src/Runtime/DSTM/interface/llookup.c b/Robust/src/Runtime/DSTM/interface/llookup.c index 2ffb2c1d..f75b51be 100644 --- a/Robust/src/Runtime/DSTM/interface/llookup.c +++ b/Robust/src/Runtime/DSTM/interface/llookup.c @@ -1,136 +1,157 @@ +/************************************************************************************************ + IMP NOTE: + + All llookup hash function prototypes returns 0 or NULL when there is an error or else returns 1 + llookup hash is an array of lhashlistnode_t + oid = mid = 0 in a given lhashlistnode_t for each bin in the hash table ONLY if the entry is empty => + the OID's can be any unsigned int except 0 +***************************************************************************************************/ #include "llookup.h" +extern lhashtable_t llookup; //Global Hash table + // Creates a hash table with default size HASH_SIZE and an array of lhashlistnode_t -lhashtable_t lhashCreate(unsigned int size, float loadfactor) { - lhashtable_t newtable; +unsigned int lhashCreate(unsigned int size, float loadfactor) { lhashlistnode_t *nodes; + int i; + // Allocate space for the hash table if((nodes = calloc(HASH_SIZE, sizeof(lhashlistnode_t))) == NULL) { printf("Calloc error %s %d\n", __FILE__, __LINE__); - exit(-1); + return 0; } + for (i = 0; i < HASH_SIZE; i++) + nodes[i].next = NULL; - newtable.table = nodes; - newtable.size = size; - newtable.numelements = 0; // Initial list of elements in the hash - newtable.loadfactor = loadfactor; - - return newtable; + llookup.table = nodes; + llookup.size = size; + llookup.numelements = 0; // Initial number of elements in the hash + llookup.loadfactor = loadfactor; + return 1; } // Assign to oids to bins inside hash table -unsigned int lhashFunction(lhashtable_t table, unsigned int oid) { - return( oid % (table.size)); +unsigned int lhashFunction(unsigned int oid) { + return( oid % (llookup.size)); } // Insert oid and mid mapping into the hash table -void lhashInsert(lhashtable_t table, unsigned int oid, unsigned int mid) { +unsigned int lhashInsert(unsigned int oid, unsigned int mid) { unsigned int newsize; int index; lhashlistnode_t *ptr; lhashlistnode_t *node; - ptr = table.table; - table.numelements++; - if (table.numelements > (table.loadfactor * table.size)) { + if (llookup.numelements > (llookup.loadfactor * llookup.size)) { //Resize Table - newsize = 2 * table.size + 1; - lhashResize(table, newsize); + newsize = 2 * llookup.size + 1; + lhashResize(newsize); } + ptr = llookup.table; + llookup.numelements++; - index = lhashFunction(table, oid); - if(ptr[index].next == NULL) { // Insert at the first position + index = lhashFunction(oid); + if(ptr[index].next == NULL && ptr[index].oid == 0) { // Insert at the first position in the hashtable ptr[index].oid = oid; ptr[index].mid = mid; } else { // Insert in the linked list if ((node = calloc(1, sizeof(lhashlistnode_t))) == NULL) { printf("Calloc error %s, %d\n", __FILE__, __LINE__); - exit(-1); + return 0; } node->oid = oid; node->mid = mid; node->next = ptr[index].next; ptr[index].next = node; } + return 1; } // Search for a value in the hash table -int lhashSearch(lhashtable_t table, unsigned int oid) { +unsigned int lhashSearch(unsigned int oid) { int index; lhashlistnode_t *ptr; lhashlistnode_t *tmp; - ptr = table.table; // Address of the beginning of hash table - index = lhashFunction(table, oid); - tmp = ptr[index].next; + ptr = llookup.table; // Address of the beginning of hash table + index = lhashFunction(oid); + tmp = &ptr[index]; while(tmp != NULL) { if(tmp->oid == oid) { return tmp->mid; } tmp = tmp->next; } - return -1; + return 0; } // Remove an entry from the hash table -int lhashRemove(lhashtable_t table, unsigned int oid) { +unsigned int lhashRemove(unsigned int oid) { int index; - lhashlistnode_t *curr, *prev; + lhashlistnode_t *curr, *prev, *tmp; lhashlistnode_t *ptr; - ptr = table.table; - index = lhashFunction(table, oid); + ptr = llookup.table; + index = lhashFunction(oid); prev = curr = &ptr[index]; for (; curr != NULL; curr = curr->next) { if (curr->oid == oid) { // Find a match in the hash table - table.numelements--; - prev->next = curr->next; - if (curr == &ptr[index]) { - ptr[index].oid = 0; - ptr[index].mid = 0; - // TO DO: Delete the first element in the hash table + llookup.numelements--; // Decrement the number of elements in the global hashtable + if ((curr == &ptr[index]) && (curr->next == NULL)) { // Delete the first item inside the hashtable with no linked list of lhashlistnode_t + curr->oid = 0; + curr->mid = 0; + } else if ((curr == &ptr[index]) && (curr->next != NULL)) { //Delete the first item with a linked list of lhashlistnode_t connected + curr->oid = curr->next->oid; + curr->mid = curr->next->mid; + tmp = curr->next; + curr->next = curr->next->next; + free(tmp); + } else { // Regular delete from linked listed + prev->next = curr->next; + free(curr); } - free(curr); - return 0; + return 1; } prev = curr; } - return -1; + return 0; } // Resize table -void lhashResize(lhashtable_t table, unsigned int newsize) { - int i; +unsigned int lhashResize(unsigned int newsize) { + lhashlistnode_t *node, *curr, *next; // curr and next keep track of the current and the next lhashlistnodes in a linked list lhashtable_t oldtable; - lhashlistnode_t *ptr; - lhashlistnode_t *node; - lhashlistnode_t *new; - - oldtable.table = table.table; - oldtable.size = table.size; - oldtable.numelements = table.numelements; - oldtable.loadfactor = table.loadfactor; - ptr = oldtable.table; + int i, isfirst; // Keeps track of the first element in the lhashlistnode_t for each bin in hashtable - //Allocate new space + oldtable.table = llookup.table; // copy orginial lhashtable_t type to a new structure + oldtable.size = llookup.size; + oldtable.numelements = llookup.numelements; + oldtable.loadfactor = llookup.loadfactor; if((node = calloc(newsize, sizeof(lhashlistnode_t))) == NULL) { printf("Calloc error %s %d\n", __FILE__, __LINE__); - exit(-1); + return 0; } - - table.table = node; - table.numelements = 0; - for(i=0; i< oldtable.size ; i++) { //For each entry in the old hashtable insert - //the element into the new hash table - new = &ptr[i]; - while ( new != NULL) { - lhashInsert(table, new->oid, new->mid); - new = new->next; + llookup.table = node; //Update the global hashtable upon resize() + llookup.size = newsize; + llookup.numelements = 0; + + for(i = 0; i < oldtable.size; i++) { + curr = next = &oldtable.table[i]; + isfirst = 1; //isfirst = true by default + while (curr != NULL) { + if (curr->oid == 0) { //Exit inner loop if there the first element for a given bin/index is NULL + break; //oid = mid =0 for element if not present within the hash table + } + next = curr->next; + lhashInsert(curr->oid, curr->mid); //Call hashInsert into the new resized table + if (isfirst != 1) { + free(curr); //free the linked list of lhashlistnode_t if not the first element in the hash table + } + isfirst = 0; //set isFirst = false inside inner loop + curr = next; } } - free(oldtable.table); // Free the oldhash table - table.size = newsize; + free(oldtable.table); //free the copied hashtable calloc-ed + return 1; } - - diff --git a/Robust/src/Runtime/DSTM/interface/llookup.h b/Robust/src/Runtime/DSTM/interface/llookup.h index 4e6ad7d8..93612322 100644 --- a/Robust/src/Runtime/DSTM/interface/llookup.h +++ b/Robust/src/Runtime/DSTM/interface/llookup.h @@ -20,14 +20,11 @@ typedef struct hashtable { float loadfactor; } lhashtable_t; -/* Prototypes for hash*/ -lhashtable_t lhashCreate(unsigned int size, float loadfactor); -unsigned int lhashFunction(lhashtable_t table, unsigned int oid); -void lhashInsert(lhashtable_t table, unsigned int oid, unsigned int mid); -int lhashSearch(lhashtable_t table, unsigned int oid); //returns oid, -1 if not found -int lhashRemove(lhashtable_t table, unsigned int oid); //returns -1 if not found -void lhashResize(lhashtable_t table, unsigned int newsize); -/* end hash */ +unsigned int lhashCreate(unsigned int size, float loadfactor);// returns 1 for success and 0 for failure +unsigned int lhashFunction(unsigned int oid); // returns 1 for success and 0 for failure +unsigned int lhashInsert(unsigned int oid, unsigned int mid); // returns 1 for success and 0 for failure +unsigned int lhashSearch(unsigned int oid); //returns mid, 0 if not found +unsigned int lhashRemove(unsigned int oid); //returns 0 if not success +unsigned int lhashResize(unsigned int newsize); // returns 1 for success and 0 for failure #endif - diff --git a/Robust/src/Runtime/DSTM/interface/testllookup.c b/Robust/src/Runtime/DSTM/interface/testllookup.c new file mode 100644 index 00000000..3e5d480b --- /dev/null +++ b/Robust/src/Runtime/DSTM/interface/testllookup.c @@ -0,0 +1,42 @@ +#include +#include "llookup.h" + +lhashtable_t llookup; + +main() +{ + int i, mid; + + if (lhashCreate(10, 0.80) == 0) { + printf("lhashCreate error\n"); //creates hashtable + } + for (i = 1; i <= 10; i++) { // Checks the insert() and resize() + if (lhashInsert(10*i, i) == 0) + printf("lhashInsert error\n"); + } + + i = lhashRemove(10);//Delete first element in the hashtable + if(i == 0) + printf("lhashRemove error "); + + for (i = 1; i <=10; i++) { // Check if it can search for all oids in hash table + mid = lhashSearch(10*i); + if (mid != i) + printf("lhashSearch error - mid = %d\n", mid); + else + printf("lhashSearch oid = %d mid = %d\n",10*i, mid); + } + + i = lhashRemove(60); + if(i == 0) + printf("lhashRemove error "); + + for (i = 1; i <= 10; i++) { //Prints all left over elements inside hash after deletion and prints error if element not found in hash + mid = lhashSearch(10*i); + if (mid != i) + printf("lhashSearch error - mid = %d\n", mid); + else + printf("lhashSearch oid = %d mid = %d\n",10*i, mid); + } + +} -- 2.34.1