From dffd32beee08600ed251e3ba266d5daeb5f617d0 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Fri, 25 Aug 2006 08:48:33 +0000 Subject: [PATCH] add generichashtable --- Robust/src/Runtime/GenericHashtable.c | 202 ++++++++++++++++++++++++++ Robust/src/Runtime/GenericHashtable.h | 51 +++++++ Robust/src/Runtime/runtime.c | 31 ++++ Robust/src/Runtime/runtime.h | 9 ++ 4 files changed, 293 insertions(+) create mode 100755 Robust/src/Runtime/GenericHashtable.c create mode 100755 Robust/src/Runtime/GenericHashtable.h diff --git a/Robust/src/Runtime/GenericHashtable.c b/Robust/src/Runtime/GenericHashtable.c new file mode 100755 index 00000000..8c24e05d --- /dev/null +++ b/Robust/src/Runtime/GenericHashtable.c @@ -0,0 +1,202 @@ +#include +#include +#include +#include +#include +#include +#include "GenericHashtable.h" +#include "mem.h" +//#include "dmalloc.h" + +int genputtable(struct genhashtable *ht, void * key, void * object) { + unsigned int bin=genhashfunction(ht,key); + struct genpointerlist * newptrlist=(struct genpointerlist *) RUNMALLOC(sizeof(struct genpointerlist)); + newptrlist->src=key; + newptrlist->object=object; + newptrlist->next=ht->bins[bin]; + newptrlist->inext=NULL; + /* maintain linked list of ht entries for iteration*/ + if (ht->last==NULL) { + ht->last=newptrlist; + ht->list=newptrlist; + newptrlist->iprev=NULL; + } else { + ht->last->inext=newptrlist; + newptrlist->iprev=ht->last; + ht->last=newptrlist; + } + ht->bins[bin]=newptrlist; + ht->counter++; + if(ht->counter>ht->currentsize&&ht->currentsize!=MAXINT) { + /* Expand hashtable */ + long newcurrentsize=(ht->currentsize<(MAXINT/2))?ht->currentsize*2:MAXINT; + long oldcurrentsize=ht->currentsize; + struct genpointerlist **newbins=(struct genpointerlist **) RUNMALLOC(sizeof (struct genpointerlist *)*newcurrentsize); + struct genpointerlist **oldbins=ht->bins; + long j,i; + for(j=0;jcurrentsize=newcurrentsize; + for(i=0;isrc); + struct genpointerlist *nextptr=tmpptr->next; + tmpptr->next=newbins[hashcode]; + newbins[hashcode]=tmpptr; + tmpptr=nextptr; + } + } + ht->bins=newbins; + RUNFREE(oldbins); + } + return 1; +} + +int hashsize(struct genhashtable *ht) { + return ht->counter; +} + +void * gengettable(struct genhashtable *ht, void * key) { + struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)]; + while(ptr!=NULL) { + if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key))) + return ptr->object; + ptr=ptr->next; + } + printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p\n",key); + return NULL; +} + +void * getnext(struct genhashtable *ht, void * key) { + struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)]; + while(ptr!=NULL) { + if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key))) + if (ptr->inext!=NULL) { + return ptr->inext->src; + } else + return NULL; + ptr=ptr->next; + } + printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p...\n Likely concurrent removal--bad user!!!\n",key); + return NULL; +} + +int gencontains(struct genhashtable *ht, void * key) { + struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)]; + //printf("In gencontains2\n");fflush(NULL); + while(ptr!=NULL) { + if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key))) + return 1; + ptr=ptr->next; + } + return 0; +} + + +void genfreekey(struct genhashtable *ht, void * key) { + struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)]; + + if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key))) { + ht->bins[genhashfunction(ht,key)]=ptr->next; + + if (ptr==ht->last) + ht->last=ptr->iprev; + + if (ptr==ht->list) + ht->list=ptr->inext; + + if (ptr->iprev!=NULL) + ptr->iprev->inext=ptr->inext; + if (ptr->inext!=NULL) + ptr->inext->iprev=ptr->iprev; + + RUNFREE(ptr); + ht->counter--; + return; + } + while(ptr->next!=NULL) { + if (((ht->comp_function==NULL)&&(ptr->next->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->next->src,key))) { + struct genpointerlist *tmpptr=ptr->next; + ptr->next=tmpptr->next; + if (tmpptr==ht->list) + ht->list=tmpptr->inext; + if (tmpptr==ht->last) + ht->last=tmpptr->iprev; + if (tmpptr->iprev!=NULL) + tmpptr->iprev->inext=tmpptr->inext; + if (tmpptr->inext!=NULL) + tmpptr->inext->iprev=tmpptr->iprev; + RUNFREE(tmpptr); + ht->counter--; + return; + } + ptr=ptr->next; + } + printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p\n",key); +} + +unsigned int genhashfunction(struct genhashtable *ht, void * key) { + if (ht->hash_function==NULL) + return ((long unsigned int)key) % ht->currentsize; + else + return ((*ht->hash_function)(key)) % ht->currentsize; +} + +struct genhashtable * genallocatehashtable(unsigned int (*hash_function)(void *),int (*comp_function)(void *, void *)) { + struct genhashtable *ght=(struct genhashtable *) RUNMALLOC(sizeof(struct genhashtable)); + struct genpointerlist **gpl=(struct genpointerlist **) RUNMALLOC(sizeof(struct genpointerlist *)*geninitialnumbins); + int i; + for(i=0;ihash_function=hash_function; + ght->comp_function=comp_function; + ght->currentsize=geninitialnumbins; + ght->bins=gpl; + ght->counter=0; + ght->list=NULL; + ght->last=NULL; + return ght; +} + +void genfreehashtable(struct genhashtable * ht) { + int i; + for (i=0;icurrentsize;i++) { + if (ht->bins[i]!=NULL) { + struct genpointerlist *genptr=ht->bins[i]; + while(genptr!=NULL) { + struct genpointerlist *tmpptr=genptr->next; + RUNFREE(genptr); + genptr=tmpptr; + } + } + } + RUNFREE(ht->bins); + RUNFREE(ht); +} + +struct geniterator * gengetiterator(struct genhashtable *ht) { + struct geniterator *gi=(struct geniterator*)RUNMALLOC(sizeof(struct geniterator)); + gi->ptr=ht->list; + return gi; +} + +void * gennext(struct geniterator *it) { + struct genpointerlist *curr=it->ptr; + if (curr==NULL) + return NULL; + if (it->finished&&(curr->inext==NULL)) + return NULL; + if (it->finished) { + it->ptr=curr->inext; + return it->ptr->src; + } + if(curr->inext!=NULL) + it->ptr=curr->inext; + else + it->finished=1; /* change offsetting scheme */ + return curr->src; +} + +void genfreeiterator(struct geniterator *it) { + RUNFREE(it); +} diff --git a/Robust/src/Runtime/GenericHashtable.h b/Robust/src/Runtime/GenericHashtable.h new file mode 100755 index 00000000..eb7d9846 --- /dev/null +++ b/Robust/src/Runtime/GenericHashtable.h @@ -0,0 +1,51 @@ +// implements a generic hash table + +#ifndef GENHASHTABLE +#define GENHASHTABLE +#define geninitialnumbins 10 +#define bool int + +struct genhashtable { + unsigned int (*hash_function)(void *); + int (*comp_function)(void *,void *); + struct genpointerlist ** bins; + long counter; + int currentsize; + struct genpointerlist *list; + struct genpointerlist *last; +}; + + +struct genpointerlist { + void * src; + void * object; + struct genpointerlist * next; + + struct genpointerlist * inext; + struct genpointerlist * iprev; +}; + + +struct geniterator { + struct genpointerlist * ptr; + bool finished; +}; + +struct genhashtable * genallocatehashtable(unsigned int (*hash_function)(void *),int (*comp_function)(void *,void *)); +void genfreehashtable(struct genhashtable * ht); + +void * getnext(struct genhashtable *,void *); +int genputtable(struct genhashtable *, void *, void *); +void * gengettable(struct genhashtable *, void *); +int gencontains(struct genhashtable *, void *); +unsigned int genhashfunction(struct genhashtable *,void *); + +int hashsize(struct genhashtable * ht); +void genfreekey(struct genhashtable *ht, void *); +struct geniterator * gengetiterator(struct genhashtable *ht); +void * gennext(struct geniterator *it); +void genfreeiterator(struct geniterator *it); +#endif + + + diff --git a/Robust/src/Runtime/runtime.c b/Robust/src/Runtime/runtime.c index 7353d931..4d62b52a 100644 --- a/Robust/src/Runtime/runtime.c +++ b/Robust/src/Runtime/runtime.c @@ -18,6 +18,7 @@ jmp_buf error_handler; #include "Queue.h" #include "SimpleHash.h" #include "task.h" +#include "GenericHashtable.h" struct SimpleHash * activetasks; struct parameterwrapper * objectqueues[NUMCLASSES]; @@ -46,6 +47,25 @@ int main(int argc, char **argv) { executetasks(); } +int hashCodeftd(struct failedtaskdescriptor *ftd) { + int hash=ftd->task; + int i; + for(i=0;inumParameters;i++) { + hash^=(int)parameterArray[i]; + } + return hash; +} + +int compareftd(struct failedtaskdescriptor *ftd1, failedtaskdescriptor *ftd2) { + int i; + if (ftd1->task!=ftd2->task) + return 0; + for(i=0;inumParameters;i++) + if (ftd1->parameterArray[i]!=ftd2->parameterArray[i]) + return 0; + return 1; +} + void flagorand(void * ptr, int ormask, int andmask) { int flag=((int *)ptr)[1]; struct QueueItem *flagptr=(struct QueueItem *)(((int*)ptr)[2]); @@ -96,6 +116,8 @@ void myhandler(int sig, struct __siginfo *info, void *uap) { void executetasks() { void * pointerarray[MAXTASKPARAMS]; + struct genhashtable * failedtasks=genallocatehashtable(&hashCodeftd, &compareftd); + /* Set up signal handlers */ struct sigaction sig; sig.sa_sigaction=&myhandler; @@ -129,6 +151,15 @@ void executetasks() { void ** checkpoint=makecheckpoint(task->numParameters, pointerarray, forward, reverse); if (setjmp(error_handler)) { /* Recover */ + struct failedtaskdescriptor *ftd=RUNMALLOC(sizeof(struct failedtaskdescriptor)); + int h; + ftd->task=task; + ftd->numParameters=task->numParameters; + ftd->parameterArray=RUNMALLOC(task->numParameters*sizeof(void *)); + for(j=0;jnumParameters;j++) { + ftd->parameterArray[j]=pointerarray[j]; + } + genputtable(failedtasks,ftd,ftd); restorecheckpoint(task->numParameters, pointerarray, checkpoint, forward, reverse); /* TODO: REMOVE TASK FROM QUEUE */ } else { diff --git a/Robust/src/Runtime/runtime.h b/Robust/src/Runtime/runtime.h index e17e18a5..a82ca495 100644 --- a/Robust/src/Runtime/runtime.h +++ b/Robust/src/Runtime/runtime.h @@ -23,6 +23,15 @@ struct parameterwrapper { int * intarray; struct taskdescriptor * task; }; + +struct failedtaskdescriptor { + struct taskdescriptor * task; + int numParameters; + void ** parameterArray; +}; + +int hashCodeftd(struct failedtaskdescriptor *); +int compareftd(struct failedtaskdescriptor *, failedtaskdescriptor *); #endif #endif -- 2.34.1