From 51dd0d8be22f286010302057980ecd23704d0dd6 Mon Sep 17 00:00:00 2001 From: stephey Date: Sat, 19 Mar 2011 23:47:41 +0000 Subject: [PATCH] Updated hashRCR and Queue_RCR to conform with new standards (i.e. storing both a ptr and a state). Fixed a bug in Queue_RCR where the first dequeue is a null.... Don't know how that could have been overlooked for so long and not cause an error... --- Robust/src/Runtime/oooJava/Queue_RCR.c | 45 +-- Robust/src/Runtime/oooJava/Queue_RCR.h | 17 +- Robust/src/Runtime/oooJava/hashRCR.c | 435 +++++++++++++------------ Robust/src/Runtime/oooJava/hashRCR.h | 91 +++--- 4 files changed, 293 insertions(+), 295 deletions(-) diff --git a/Robust/src/Runtime/oooJava/Queue_RCR.c b/Robust/src/Runtime/oooJava/Queue_RCR.c index ae8f197c..745861ac 100644 --- a/Robust/src/Runtime/oooJava/Queue_RCR.c +++ b/Robust/src/Runtime/oooJava/Queue_RCR.c @@ -7,39 +7,40 @@ __thread struct RCRQueue myRCRQueue; void resetRCRQueue() { myRCRQueue.head = 0; myRCRQueue.tail = 0; + myRCRQueue.length = 0; } -//0 would mean sucess +//0 would mean success //1 would mean fail -//since if we reach SIZE, we will stop operation, it doesn't matter -//that we overwrite the element in the queue -int enqueueRCRQueue(void * ptr) { - unsigned int head=myRCRQueue.head+1; - if (head&SIZE) - head=0; - - if (head==myRCRQueue.tail) - return 1; - - myRCRQueue.elements[head] = ptr; - myRCRQueue.head=head; +int enqueueRCRQueue(void * ptr, int traverserState) { + if (myRCRQueue.length & SIZE) + return 1; + + myRCRQueue.length++; + myRCRQueue.elements[myRCRQueue.head].object = ptr; + myRCRQueue.elements[myRCRQueue.head].traverserState = traverserState; + myRCRQueue.head++; + + if (myRCRQueue.head&SIZE) + myRCRQueue.head=0; + + return 0; } -void * dequeueRCRQueue() { - if(myRCRQueue.head==myRCRQueue.tail) +RCRQueueEntry * dequeueRCRQueue() { + if(!myRCRQueue.length) return NULL; - unsigned int tail=myRCRQueue.tail; - void * ptr = myRCRQueue.elements[tail]; - tail++; - if(tail & SIZE) - tail = 0; - myRCRQueue.tail=tail; + + myRCRQueue.length--; + void * ptr = &myRCRQueue.elements[myRCRQueue.tail++]; + if(myRCRQueue.tail & SIZE) + myRCRQueue.tail = 0; return ptr; } int isEmptyRCRQueue() { - return myRCRQueue.head=myRCRQueue.tail; + return !myRCRQueue.length; } diff --git a/Robust/src/Runtime/oooJava/Queue_RCR.h b/Robust/src/Runtime/oooJava/Queue_RCR.h index 38806463..fa91cbca 100644 --- a/Robust/src/Runtime/oooJava/Queue_RCR.h +++ b/Robust/src/Runtime/oooJava/Queue_RCR.h @@ -5,21 +5,20 @@ //SIZE is used as mask to check overflow #define SIZE 16384 -struct RCRQueue { - void * elements[SIZE]; - unsigned int head; - unsigned int tail; -}; - - typedef struct RCRQueueEntry_t { void* object; int traverserState; } RCRQueueEntry; +struct RCRQueue { + RCRQueueEntry elements[SIZE]; + unsigned int head; + unsigned int tail; + unsigned int length; +}; -int enqueueRCRQueue(void * ptr); -void * dequeueRCRQueue(); +int enqueueRCRQueue(void * ptr, int traverserState); +RCRQueueEntry * dequeueRCRQueue(); void resetRCRQueue(); int isEmptyRCRQueue(); int getSizeRCRQueue(); diff --git a/Robust/src/Runtime/oooJava/hashRCR.c b/Robust/src/Runtime/oooJava/hashRCR.c index f3d62d67..fc4b98cb 100644 --- a/Robust/src/Runtime/oooJava/hashRCR.c +++ b/Robust/src/Runtime/oooJava/hashRCR.c @@ -1,216 +1,219 @@ -#include "hashRCR.h" -#include -#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&&tmpptrkey=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->numarray[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" +#include +#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&&tmpptrobject=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 * objectPtr, int traverserState) { + dchashlistnode_t *ptr; + + if (unlikely(objectPtr==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)objectPtr)&dc_c_mask)>>SHIFTBITS]; + if(likely(ptr->object==0)) { + ptr->object=objectPtr; + ptr->traverserState = traverserState; + 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->object == objectPtr && search->traverserState == traverserState) { + return 0; + } + search=search->next; + } while(search != NULL); + + dc_c_numelements++; + if (dc_c_structs->numarray[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->object = objectPtr; + node->traverserState=traverserState; + 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->object) == 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->object == 0) { + tmp->object = key; + tmp->traverserState = curr->traverserState; + 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 * objectPtr, int traverserState) { + //REMOVE HASH FUNCTION CALL TO MAKE SURE IT IS INLINED HERE + dchashlistnode_t *node = &dc_c_table[(((unsigned INTPTR)objectPtr) & dc_c_mask)>>SHIFTBITS]; + + do { + if(node->object == objectPtr && node->traverserState == traverserState) { + return 1; + } + node = node->next; + } while(node != NULL); + + return 0; +} diff --git a/Robust/src/Runtime/oooJava/hashRCR.h b/Robust/src/Runtime/oooJava/hashRCR.h index 646e6296..cab493b0 100644 --- a/Robust/src/Runtime/oooJava/hashRCR.h +++ b/Robust/src/Runtime/oooJava/hashRCR.h @@ -1,48 +1,43 @@ -#ifndef _HASHRCR_H_ -#define _HASHRCR_H_ - -#include -#include - -#ifndef INTPTR -#ifdef BIT64 -#define INTPTR long -#else -#define INTPTR int -#endif -#endif - -//TODO consider changing loadfactor? -#define CLOADFACTOR 0.25 -#define CHASH_SIZE 1024 - -#define INLINE inline __attribute__((always_inline)) - -//TODO consider changing names to avoid conflicts -extern __thread unsigned int dc_c_size; -extern __thread unsigned INTPTR dc_c_mask; -extern __thread unsigned int dc_c_numelements; -extern __thread unsigned int dc_c_threshold; -extern __thread double dc_c_loadfactor; - -typedef struct dchashlistnode { - void * key; - struct dchashlistnode *next; - struct dchashlistnode *lnext; -} dchashlistnode_t; - -#define NUMDCLIST 250 -typedef struct dclist { - struct dchashlistnode array[NUMDCLIST]; - int num; - struct dclist *next; -} dcliststruct_t; - - -void hashRCRCreate(unsigned int size, double loadfactor); -int hashRCRInsert(void * key); -int hashRCRSearch(void * key); -unsigned int hashRCRResize(unsigned int newsize); -void hashRCRDelete(); -void hashRCRreset(); -#endif +#ifndef _HASHRCR_H_ +#define _HASHRCR_H_ + +#include +#include + +#ifndef INTPTR +#ifdef BIT64 +#define INTPTR long +#else +#define INTPTR int +#endif +#endif + +#define INLINE inline __attribute__((always_inline)) + +extern __thread unsigned int dc_c_size; +extern __thread unsigned INTPTR dc_c_mask; +extern __thread unsigned int dc_c_numelements; +extern __thread unsigned int dc_c_threshold; +extern __thread double dc_c_loadfactor; + +typedef struct dchashlistnode { + void * object; + int traverserState; + struct dchashlistnode *next; + struct dchashlistnode *lnext; +} dchashlistnode_t; + +#define NUMDCLIST 250 +typedef struct dclist { + struct dchashlistnode array[NUMDCLIST]; + int num; + struct dclist *next; +} dcliststruct_t; + + +void hashRCRCreate(unsigned int size, double loadfactor); +INLINE int hashRCRSearch(void * objectPtr, int traverserState); +unsigned int hashRCRResize(unsigned int newsize); +void hashRCRDelete(); +void hashRCRreset(); +#endif -- 2.34.1