#include "chash.h"
-#define INLINE inline __attribute__((always_inline))
void crehash(ctable_t *table) {
cResize(table, table->size);
ctable->mask = (size << 2)-1;
ctable->numelements = 0; // Initial number of elements in the hash
ctable->loadfactor = loadfactor;
+ ctable->resize=loadfactor*size;
ctable->listhead=NULL;
return ctable;
}
//Store objects and their pointers into hash
-unsigned int cInsert(ctable_t *table, unsigned int key, void *val) {
+INLINE void cInsert(ctable_t *table, unsigned int key, void *val) {
unsigned int newsize;
int index;
cnode_t *ptr, *node;
- if(table->numelements > (table->loadfactor * table->size)) {
- //Resize
- newsize = table->size << 1;
- cResize(table,newsize);
+ ptr = &table->table[(key & table->mask)>>2];
+ if (ptr->key==0) {
+ ptr->key=key;
+ ptr->val=val;
+ ptr->lnext=table->listhead;
+ table->listhead=ptr;
+ return;
}
- ptr = table->table;
+ cnode_t *tmp=malloc(sizeof(cnode_t));
+ tmp->next=ptr->next;
+ ptr->next=tmp;
+ tmp->key=key;
+ tmp->val=val;
+ tmp->lnext=table->listhead;
+ table->listhead=tmp;
+
table->numelements++;
- index =(key & table->mask)>>2;
- if(ptr[index].next == NULL && ptr[index].key == 0) { // Insert at the first position in the hashtable
- ptr[index].key = key;
- ptr[index].val = val;
- } else { // Insert in the beginning of linked list
- if ((node = calloc(1, sizeof(cnode_t))) == NULL) {
- printf("Calloc error %s, %d\n", __FILE__, __LINE__);
- return 1;
- }
- node->key = key;
- node->val = val;
- node->next = ptr[index].next;
- node->lnext=table->listhead;
- table->listhead=node;
- ptr[index].next = node;
+ if(table->numelements > table->resize) {
+ newsize = table->size << 1;
+ cResize(table,newsize);
}
- return 0;
}
// Search for an address for a given oid
}
unsigned int cResize(ctable_t *table, unsigned int newsize) {
- cnode_t *node, *ptr, *curr, *next; // 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
- int i,index;
- cnode_t *newnode;
+ int i;
cnode_t *last=NULL;
+ int mask=(newsize<<2)-1;
+ int oldsize = table->size;
+ cnode_t *ptr = table->table;
+ cnode_t * ntable=calloc(newsize, sizeof(cnode_t));
- ptr = table->table;
- oldsize = table->size;
-
- if((node = calloc(newsize, sizeof(cnode_t))) == NULL) {
- printf("Calloc error %s %d\n", __FILE__, __LINE__);
- return 1;
- }
-
- table->table = node; //Update the global hashtable upon resize()
+ table->table = ntable;
table->size = newsize;
- table->mask = (newsize << 2)-1;
- table->numelements = 0;
-
- 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->key == 0) { //Exit inner loop if there the first element for a given bin/index is NULL
- break; //key = val =0 for element if not present within the hash table
- }
- next = curr->next;
-
- index =(curr->key & table->mask)>>2;
- // Insert into the new table
- if(table->table[index].next == NULL && table->table[index].key == 0) {
- table->table[index].key = curr->key;
- table->table[index].val = curr->val;
- table->numelements++;
- table->table[index].lnext=last;
- last=&table->table[index];
- } else {
- if((newnode = calloc(1, sizeof(cnode_t))) == NULL) {
- printf("Calloc error %s, %d\n", __FILE__, __LINE__);
- return 1;
- }
- newnode->key = curr->key;
- newnode->val = curr->val;
- newnode->next = table->table[index].next;
- table->table[index].next = newnode;
- table->numelements++;
+ table->mask = mask;
+ table->resize=newsize*table->loadfactor;
+
+ for(i = 0; i < oldsize; i++) {
+ int isfirst=1;
+ cnode_t * curr=&ptr[i];
+ if (curr->key==0)
+ continue;
+ while(curr!=NULL) {
+ cnode_t * next = curr->next;
+ int index =(curr->key & mask)>>2;
+ cnode_t * newnode=&ntable[index];
+
+ if(newnode->key==0) {
+ newnode->key=curr->key;
+ newnode->val=curr->val;
newnode->lnext=last;
last=newnode;
- }
-
- //free the linked list of chashlistnode_t if not the first element in the hash table
- if (isfirst != 1) {
+ } else {
+ cnode_t *tmp=malloc(sizeof(cnode_t));
+ tmp->next=newnode->next;
+ newnode->next=tmp;
+ tmp->key=curr->key;
+ tmp->val=curr->val;
+ tmp->lnext=last;
+ last=tmp;
+ }
+ if (isfirst) {
+ isfirst=0;
+ } else {
free(curr);
}
-
- isfirst = 0;
curr = next;
}
}
#include "runtime.h"
#include "structdefs.h"
#include <string.h>
+#include "Queue.h"
#ifdef DMALLOC
#include "dmalloc.h"
#endif
}
}
-void validitycheck(struct RuntimeHash *forward, struct RuntimeHash *reverse) {
+/*
+void validitycheck(struct ctable *forward, struct ctable *reverse) {
struct RuntimeIterator rit;
RuntimeHashiterator(forward, &rit);
while(RunhasNext(&rit)) {
}
}
}
+*/
-
-void ** makecheckpoint(int numparams, void ** srcpointer, struct RuntimeHash * forward, struct RuntimeHash * reverse) {
+void ** makecheckpoint(int numparams, void ** srcpointer, struct ctable * forward, struct ctable * reverse) {
#ifdef PRECISE_GC
void **newarray=cpmalloc(sizeof(void *)*numparams);
#else
void **newarray=RUNMALLOC(sizeof(void *)*numparams);
#endif
- struct RuntimeHash *todo=allocateRuntimeHash(100);
+ struct Queue *todo=createQueue();
int i;
for(i=0; i<numparams; i++) {
void * objptr=srcpointer[i];
- if (RuntimeHashcontainskey(forward, (int) objptr))
- RuntimeHashget(forward,(int) objptr,(int *) &newarray[i]);
+ void *dst;
+ if ((dst=cSearch(forward, (int) objptr))!=NULL)
+ newarray[i]=dst;
else {
void * copy=createcopy(objptr);
- RuntimeHashadd(forward, (int) objptr, (int)copy);
- RuntimeHashadd(reverse, (int) copy, (int) objptr);
- RuntimeHashadd(todo, (int) objptr, (int) objptr);
+ cInsert(forward, (int) objptr, copy);
+ cInsert(reverse, (int) copy, objptr);
+ addNewItem(todo, objptr);
newarray[i]=copy;
}
}
- while(RuntimeHashcountset(todo)!=0) {
- void * ptr=(void *) RuntimeHashfirstkey(todo);
+ while(!isEmpty(todo)) {
+ void * ptr=getItem(todo);
int type=((int *)ptr)[0];
- RuntimeHashremove(todo, (int) ptr, (int) ptr);
{
void *cpy;
unsigned int * pointer=NULL;
- RuntimeHashget(forward, (int) ptr, (int *) &cpy);
+ cpy=cSearch(forward, (unsigned int)ptr);
pointer=pointerarray[type];
#ifdef TASK
if (type==TAGTYPE) {
void *objptr=((struct ___TagDescriptor___*)ptr)->flagptr;
if (objptr!=NULL) {
- if (!RuntimeHashcontainskey(forward, (int) objptr)) {
+ void *dst;
+ if ((dst=cSearch(forward, (unsigned int)objptr))==NULL) {
void *copy=createcopy(objptr);
- RuntimeHashadd(forward, (int) objptr, (int) copy);
- RuntimeHashadd(reverse, (int) copy, (int) objptr);
- RuntimeHashadd(todo, (int) objptr, (int) objptr);
+ cInsert(forward, (int) objptr, copy);
+ cInsert(reverse, (int) copy, objptr);
+ addNewItem(todo, objptr);
((struct ___TagDescriptor___*)cpy)->flagptr=copy;
} else {
- RuntimeHashget(forward, (int) objptr, (int *) &(((struct ___TagDescriptor___*) cpy)->flagptr));
- }
+ ((struct ___TagDescriptor___*) cpy)->flagptr=dst;
}
- } else
+ }
+ } else
#endif
if (pointer==0) {
/* Array of primitives */
int length=ao->___length___;
int i;
for(i=0; i<length; i++) {
+ void *dst;
void *objptr=((void **)(((char *)&ao->___length___)+sizeof(int)))[i];
if (objptr==NULL) {
((void **)(((char *)&ao_cpy->___length___)+sizeof(int)))[i]=NULL;
- } else if (RuntimeHashcontainskey(forward, (int) objptr))
- RuntimeHashget(forward,(int) objptr,(int *) &((void **)(((char *)&ao_cpy->___length___)+sizeof(int)))[i]);
+ } else if ((dst=cSearch(forward, (int)objptr))!=NULL)
+ ((void **)(((char *)&ao_cpy->___length___)+sizeof(int)))[i]=dst;
else {
void * copy=createcopy(objptr);
- RuntimeHashadd(forward, (int) objptr, (int)copy);
- RuntimeHashadd(reverse, (int) copy, (int) objptr);
- RuntimeHashadd(todo, (int) objptr, (int) objptr);
+ cInsert(forward, (int) objptr, copy);
+ cInsert(reverse, (int) copy, objptr);
+ addNewItem(todo, objptr);
((void **)(((char *)&ao_cpy->___length___)+sizeof(int)))[i]=copy;
}
}
for(i=1; i<=size; i++) {
int offset=pointer[i];
void * objptr=*((void **)(((int)ptr)+offset));
+ void *dst;
if (objptr==NULL) {
*((void **)(((int)cpy)+offset))=NULL;
- } else if (RuntimeHashcontainskey(forward, (int) objptr))
- RuntimeHashget(forward, (int) objptr, (int *) &(((char *)cpy)[offset]));
+ } else if ((dst=cSearch(forward, (unsigned int)objptr))!=NULL)
+ *((void **) &(((char *)cpy)[offset]))=dst;
else {
void * copy=createcopy(objptr);
- RuntimeHashadd(forward, (int) objptr, (int) copy);
- RuntimeHashadd(reverse, (int) copy, (int) objptr);
- RuntimeHashadd(todo, (int) objptr, (int) objptr);
+ cInsert(forward, (int) objptr, copy);
+ cInsert(reverse, (int) copy, objptr);
+ addNewItem(todo, objptr);
*((void **)(((int)cpy)+offset))=copy;
}
}
}
}
}
- freeRuntimeHash(todo);
+ freeQueue(todo);
return newarray;
}
}
}
-void restorecheckpoint(int numparams, void ** original, void ** checkpoint, struct RuntimeHash *forward, struct RuntimeHash * reverse) {
- struct RuntimeHash *todo=allocateRuntimeHash(100);
- struct RuntimeHash *visited=allocateRuntimeHash(100);
+void restorecheckpoint(int numparams, void ** original, void ** checkpoint, struct ctable *forward, struct ctable * reverse) {
+ struct Queue *todo=createQueue();
+ struct ctable *visited=cCreate(256, 0.5);
int i;
for(i=0; i<numparams; i++) {
if (checkpoint[i]!=NULL) {
- RuntimeHashadd(todo, (int) checkpoint[i], (int) checkpoint[i]);
- RuntimeHashadd(visited, (int) checkpoint[i], (int) checkpoint[i]);
+ addNewItem(todo, checkpoint[i]);
+ cInsert(visited, (unsigned int) checkpoint[i], checkpoint[i]);
}
}
- while(RuntimeHashcountset(todo)!=0) {
- void * ptr=(void *) RuntimeHashfirstkey(todo);
+ while(!isEmpty(todo)) {
+ void * ptr=(void *) getItem(todo);
int type=((int *)ptr)[0];
- RuntimeHashremove(todo, (int) ptr, (int) ptr);
{
void *cpy;
unsigned int *pointer;
int size;
- RuntimeHashget(reverse, (int) ptr, (int *) &cpy);
+ cpy=cSearch(reverse, (int) ptr);
pointer=pointerarray[type];
size=classsize[type];
#ifdef TASK
void *objptr=((struct ___TagDescriptor___*)ptr)->flagptr;
memcpy(cpy, ptr, size);
if (objptr!=NULL) {
- if (!RuntimeHashcontainskey(visited, (int) objptr)) {
- RuntimeHashadd(visited, (int) objptr, (int) objptr);
- RuntimeHashadd(todo, (int) objptr, (int) objptr);
+ if (cSearch(visited, (unsigned int)objptr)==NULL) {
+ cInsert(visited, (int) objptr, objptr);
+ addNewItem(todo, objptr);
}
- RuntimeHashget(reverse, (int) objptr, (int *) &(((struct ___TagDescriptor___ *)cpy)->flagptr));
+ *((void **) &(((struct ___TagDescriptor___ *)cpy)->flagptr))=cSearch(reverse, (int) objptr);
}
} else
#endif
if (objptr==NULL)
((void **)(((char *)&ao_cpy->___length___)+sizeof(int)))[i]=NULL;
else {
- if (!RuntimeHashcontainskey(visited, (int) objptr)) {
- RuntimeHashadd(visited, (int) objptr, (int) objptr);
- RuntimeHashadd(todo, (int) objptr, (int) objptr);
+ if (cSearch(visited, (int) objptr)==NULL) {
+ cInsert(visited, (int) objptr, objptr);
+ addNewItem(todo, objptr);
}
- RuntimeHashget(reverse, (int) objptr, (int *) &((void **)(((char *)&ao_cpy->___length___)+sizeof(int)))[i]);
+ *((void **) &((void **)(((char *)&ao_cpy->___length___)+sizeof(int)))[i])=cSearch(reverse, (int) objptr);
}
}
} else {
if (objptr==NULL)
*((void **)(((int)cpy)+offset))=NULL;
else {
- if (!RuntimeHashcontainskey(visited, (int) objptr)) {
- RuntimeHashadd(visited, (int) objptr, (int) objptr);
- RuntimeHashadd(todo, (int) objptr, (int) objptr);
+ if (cSearch(visited, (int)objptr)==NULL) {
+ cInsert(visited, (int) objptr, objptr);
+ addNewItem(todo, objptr);
}
- RuntimeHashget(reverse, (int) objptr, (int *) &(((char *)cpy)[offset]));
+ *((void **) &(((char *)cpy)[offset]))=cSearch(reverse, (int) objptr);
}
}
if (hasflags[type]) {
}
}
}
- freeRuntimeHash(todo);
- freeRuntimeHash(visited);
+ freeQueue(todo);
+ cDelete(visited);
}