From 18b206a1cd05e86bf872d975ca13030edc33f490 Mon Sep 17 00:00:00 2001 From: adash Date: Fri, 9 Mar 2007 04:30:02 +0000 Subject: [PATCH] Modify return statements, declare llookup in .c file, modify the lhashResize(), get rid of extraneous initializations --- Robust/src/Runtime/DSTM/interface/llookup.c | 107 +++++++++++------- .../src/Runtime/DSTM/interface/testllookup.c | 23 ++-- 2 files changed, 75 insertions(+), 55 deletions(-) diff --git a/Robust/src/Runtime/DSTM/interface/llookup.c b/Robust/src/Runtime/DSTM/interface/llookup.c index f75b51be..d43457b2 100644 --- a/Robust/src/Runtime/DSTM/interface/llookup.c +++ b/Robust/src/Runtime/DSTM/interface/llookup.c @@ -1,14 +1,13 @@ /************************************************************************************************ IMP NOTE: - - All llookup hash function prototypes returns 0 or NULL when there is an error or else returns 1 + All llookup hash function prototypes returns 0 on sucess and 1 otherwise 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 +lhashtable_t llookup; //Global Hash table // Creates a hash table with default size HASH_SIZE and an array of lhashlistnode_t unsigned int lhashCreate(unsigned int size, float loadfactor) { @@ -18,16 +17,14 @@ unsigned int lhashCreate(unsigned int size, float loadfactor) { // Allocate space for the hash table if((nodes = calloc(HASH_SIZE, sizeof(lhashlistnode_t))) == NULL) { printf("Calloc error %s %d\n", __FILE__, __LINE__); - return 0; + return 1; } - for (i = 0; i < HASH_SIZE; i++) - nodes[i].next = NULL; llookup.table = nodes; llookup.size = size; llookup.numelements = 0; // Initial number of elements in the hash llookup.loadfactor = loadfactor; - return 1; + return 0; } // Assign to oids to bins inside hash table @@ -39,8 +36,7 @@ unsigned int lhashFunction(unsigned int oid) { unsigned int lhashInsert(unsigned int oid, unsigned int mid) { unsigned int newsize; int index; - lhashlistnode_t *ptr; - lhashlistnode_t *node; + lhashlistnode_t *ptr, *node; if (llookup.numelements > (llookup.loadfactor * llookup.size)) { //Resize Table @@ -57,30 +53,29 @@ unsigned int lhashInsert(unsigned int oid, unsigned int mid) { } else { // Insert in the linked list if ((node = calloc(1, sizeof(lhashlistnode_t))) == NULL) { printf("Calloc error %s, %d\n", __FILE__, __LINE__); - return 0; + return 1; } node->oid = oid; node->mid = mid; node->next = ptr[index].next; ptr[index].next = node; } - return 1; + return 0; } -// Search for a value in the hash table +// Return mid for a given oid in the hash table unsigned int lhashSearch(unsigned int oid) { int index; - lhashlistnode_t *ptr; - lhashlistnode_t *tmp; + lhashlistnode_t *ptr, *node; 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; + node = &ptr[index]; + while(node != NULL) { + if(node->oid == oid) { + return node->mid; } - tmp = tmp->next; + node = node->next; } return 0; } @@ -88,12 +83,12 @@ unsigned int lhashSearch(unsigned int oid) { // Remove an entry from the hash table unsigned int lhashRemove(unsigned int oid) { int index; - lhashlistnode_t *curr, *prev, *tmp; - lhashlistnode_t *ptr; + lhashlistnode_t *curr, *prev; + lhashlistnode_t *ptr, *node; ptr = llookup.table; index = lhashFunction(oid); - prev = curr = &ptr[index]; + curr = &ptr[index]; for (; curr != NULL; curr = curr->next) { if (curr->oid == oid) { // Find a match in the hash table @@ -104,54 +99,78 @@ unsigned int lhashRemove(unsigned int oid) { } 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; + node = curr->next; curr->next = curr->next->next; - free(tmp); + free(node); } else { // Regular delete from linked listed prev->next = curr->next; free(curr); } - return 1; + return 0; } prev = curr; } - return 0; + return 1; } // Resize table 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; - int i, isfirst; // Keeps track of the first element in the lhashlistnode_t for each bin in hashtable - - 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; + lhashlistnode_t *node, *ptr, *curr, *next; // curr and next keep track of the current and the next lhashlistnodes in a linked list + unsigned int oldsize; + int isfirst; // Keeps track of the first element in the lhashlistnode_t for each bin in hashtable + int i,index; + lhashlistnode_t *newnode; + + ptr = llookup.table; + oldsize = llookup.size; + if((node = calloc(newsize, sizeof(lhashlistnode_t))) == NULL) { printf("Calloc error %s %d\n", __FILE__, __LINE__); - return 0; + return 1; } + 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) { + for(i = 0; i < oldsize; i++) { //Outer loop for each bin in hash table + curr = &ptr[i]; + isfirst = 1; + while (curr != NULL) { //Inner loop to go through linked lists 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 + + index = lhashFunction(curr->oid); + // Insert into the new table + if(ptr[index].next == NULL && ptr[index].oid == 0) { + ptr[index].oid = curr->oid; + ptr[index].mid = curr->mid; + llookup.numelements++; + }else { + if((newnode = calloc(1, sizeof(lhashlistnode_t))) == NULL) { + printf("Calloc error %s, %d\n", __FILE__, __LINE__); + return 1; + } + newnode->oid = curr->oid; + newnode->mid = curr->mid; + newnode->next = ptr[index].next; + ptr[index].next = newnode; + llookup.numelements++; + } + + //free the linked list of lhashlistnode_t if not the first element in the hash table if (isfirst != 1) { - free(curr); //free the linked list of lhashlistnode_t if not the first element in the hash table + free(curr); } - isfirst = 0; //set isFirst = false inside inner loop + + isfirst = 0; curr = next; + } } - free(oldtable.table); //free the copied hashtable calloc-ed - return 1; + + free(ptr); //Free the memory of the old hash table + return 0; } diff --git a/Robust/src/Runtime/DSTM/interface/testllookup.c b/Robust/src/Runtime/DSTM/interface/testllookup.c index 3e5d480b..80f6333e 100644 --- a/Robust/src/Runtime/DSTM/interface/testllookup.c +++ b/Robust/src/Runtime/DSTM/interface/testllookup.c @@ -1,25 +1,24 @@ #include #include "llookup.h" - -lhashtable_t llookup; +extern lhashtable_t llookup; main() { int i, mid; - if (lhashCreate(10, 0.80) == 0) { + if (lhashCreate(10, 0.80) == 1) { printf("lhashCreate error\n"); //creates hashtable } - for (i = 1; i <= 10; i++) { // Checks the insert() and resize() - if (lhashInsert(10*i, i) == 0) + for (i = 1; i <= 7; i++) { // Checks the insert() and resize() + if (lhashInsert(10*i, i) == 1) printf("lhashInsert error\n"); } - i = lhashRemove(10);//Delete first element in the hashtable - if(i == 0) + i = lhashRemove(60);//Delete first element in the hashtable + if(i == 1) printf("lhashRemove error "); - for (i = 1; i <=10; i++) { // Check if it can search for all oids in hash table + for (i = 1; i <=7; 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); @@ -27,11 +26,11 @@ main() printf("lhashSearch oid = %d mid = %d\n",10*i, mid); } - i = lhashRemove(60); - if(i == 0) + i = lhashRemove(30); + if(i == 1) 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 + for (i = 1; i <= 7; 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); @@ -39,4 +38,6 @@ main() printf("lhashSearch oid = %d mid = %d\n",10*i, mid); } + printf(" The total number of elements in table : %d\n", llookup.numelements); + } -- 2.34.1