#include "SimpleHash.h"
+#ifdef RAW
+#include <raw.h>
+#else
#include <stdio.h>
+#endif
+#ifdef DMALLOC
+#include "dmalloc.h"
+#endif
/* SIMPLE HASH ********************************************************/
-struct SimpleIterator* SimpleHashcreateiterator(struct SimpleHash * thisvar) {
- return allocateSimpleIterator(thisvar->listhead,thisvar->listtail,thisvar->tailindex/*,thisvar*/);
+struct RuntimeIterator* RuntimeHashcreateiterator(struct RuntimeHash * thisvar) {
+ return allocateRuntimeIterator(thisvar->listhead);
}
-void SimpleHashiterator(struct SimpleHash *thisvar, struct SimpleIterator * it) {
+void RuntimeHashiterator(struct RuntimeHash *thisvar, struct RuntimeIterator * it) {
it->cur=thisvar->listhead;
- it->index=0;
- it->tailindex=thisvar->tailindex;
- it->tail=thisvar->listtail;
}
-struct SimpleHash * noargallocateSimpleHash() {
- return allocateSimpleHash(100);
+struct RuntimeHash * noargallocateRuntimeHash() {
+ return allocateRuntimeHash(100);
}
-struct SimpleHash * allocateSimpleHash(int size) {
- struct SimpleHash *thisvar=(struct SimpleHash *)RUNMALLOC(sizeof(struct SimpleHash));
+struct RuntimeHash * allocateRuntimeHash(int size) {
+ struct RuntimeHash *thisvar;//=(struct RuntimeHash *)RUNMALLOC(sizeof(struct RuntimeHash));
if (size <= 0) {
+#ifdef RAW
+ raw_test_done(0xb001);
+#else
printf("Negative Hashtable size Exception\n");
- exit(-1);
+ exit(-1);
+#endif
}
+ thisvar=(struct RuntimeHash *)RUNMALLOC(sizeof(struct RuntimeHash));
thisvar->size = size;
- thisvar->bucket = (struct SimpleNode **) calloc(sizeof(struct SimpleNode *)*size,1);
+ thisvar->bucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*size);
/* Set allocation blocks*/
- thisvar->listhead=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
- thisvar->listtail=thisvar->listhead;
- thisvar->tailindex=0;
+ thisvar->listhead=NULL;
+ thisvar->listtail=NULL;
/*Set data counts*/
thisvar->numelements = 0;
return thisvar;
}
-void freeSimpleHash(struct SimpleHash *thisvar) {
- struct ArraySimple *ptr=thisvar->listhead;
+void freeRuntimeHash(struct RuntimeHash *thisvar) {
+ struct RuntimeNode *ptr=thisvar->listhead;
RUNFREE(thisvar->bucket);
while(ptr) {
- struct ArraySimple *next=ptr->nextarray;
+ struct RuntimeNode *next=ptr->lnext;
RUNFREE(ptr);
ptr=next;
}
RUNFREE(thisvar);
}
-inline int SimpleHashcountset(struct SimpleHash * thisvar) {
+inline int RuntimeHashcountset(struct RuntimeHash * thisvar) {
return thisvar->numelements;
}
-int SimpleHashfirstkey(struct SimpleHash *thisvar) {
- struct ArraySimple *ptr=thisvar->listhead;
- int index=0;
- while((index==ARRAYSIZE)||!ptr->nodes[index].inuse) {
- if (index==ARRAYSIZE) {
- index=0;
- ptr=ptr->nextarray;
- } else
- index++;
- }
- return ptr->nodes[index].key;
+int RuntimeHashfirstkey(struct RuntimeHash *thisvar) {
+ struct RuntimeNode *ptr=thisvar->listhead;
+ return ptr->key;
}
-int SimpleHashremove(struct SimpleHash *thisvar, int key, int data) {
+int RuntimeHashremovekey(struct RuntimeHash *thisvar, int key) {
unsigned int hashkey = (unsigned int)key % thisvar->size;
- struct SimpleNode **ptr = &thisvar->bucket[hashkey];
+ struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
+ int i;
+
+ while (*ptr) {
+ if ((*ptr)->key == key) {
+ struct RuntimeNode *toremove=*ptr;
+ *ptr=(*ptr)->next;
+
+ if (toremove->lprev!=NULL) {
+ toremove->lprev->lnext=toremove->lnext;
+ } else {
+ thisvar->listhead=toremove->lnext;
+ }
+ if (toremove->lnext!=NULL) {
+ toremove->lnext->lprev=toremove->lprev;
+ } else{
+ thisvar->listtail=toremove->lprev;
+ }
+ RUNFREE(toremove);
+
+ thisvar->numelements--;
+ return 1;
+ }
+ ptr = &((*ptr)->next);
+ }
+
+ return 0;
+}
+
+int RuntimeHashremove(struct RuntimeHash *thisvar, int key, int data) {
+ unsigned int hashkey = (unsigned int)key % thisvar->size;
+
+ struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
int i;
while (*ptr) {
if ((*ptr)->key == key && (*ptr)->data == data) {
- struct SimpleNode *toremove=*ptr;
+ struct RuntimeNode *toremove=*ptr;
*ptr=(*ptr)->next;
- toremove->inuse=0; /* Marked as unused */
+ if (toremove->lprev!=NULL) {
+ toremove->lprev->lnext=toremove->lnext;
+ } else {
+ thisvar->listhead=toremove->lnext;
+ }
+ if (toremove->lnext!=NULL) {
+ toremove->lnext->lprev=toremove->lprev;
+ } else {
+ thisvar->listtail=toremove->lprev;
+ }
+ RUNFREE(toremove);
thisvar->numelements--;
return 1;
return 0;
}
-void SimpleHashaddAll(struct SimpleHash *thisvar, struct SimpleHash * set) {
- struct SimpleIterator it;
- SimpleHashiterator(set, &it);
- while(hasNext(&it)) {
- int keyv=key(&it);
- int data=next(&it);
- SimpleHashadd(thisvar,keyv,data);
+void RuntimeHashrehash(struct RuntimeHash * thisvar) {
+ int newsize=thisvar->size;
+ struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
+ int i;
+ for(i=thisvar->size-1;i>=0;i--) {
+ struct RuntimeNode *ptr;
+ for(ptr=thisvar->bucket[i];ptr!=NULL;) {
+ struct RuntimeNode * nextptr=ptr->next;
+ unsigned int newhashkey=(unsigned int)ptr->key % newsize;
+ ptr->next=newbucket[newhashkey];
+ newbucket[newhashkey]=ptr;
+ ptr=nextptr;
}
+ }
+ thisvar->size=newsize;
+ RUNFREE(thisvar->bucket);
+ thisvar->bucket=newbucket;
}
-int SimpleHashadd(struct SimpleHash * thisvar,int key, int data) {
+int RuntimeHashadd(struct RuntimeHash * thisvar,int key, int data) {
/* Rehash code */
unsigned int hashkey;
- struct SimpleNode **ptr;
+ struct RuntimeNode **ptr;
if (thisvar->numelements>=thisvar->size) {
int newsize=2*thisvar->size+1;
- struct SimpleNode ** newbucket = (struct SimpleNode **) calloc(sizeof(struct SimpleNode *)*newsize,1);
+ struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
int i;
for(i=thisvar->size-1;i>=0;i--) {
- struct SimpleNode *ptr;
+ struct RuntimeNode *ptr;
for(ptr=thisvar->bucket[i];ptr!=NULL;) {
- struct SimpleNode * nextptr=ptr->next;
+ struct RuntimeNode * nextptr=ptr->next;
unsigned int newhashkey=(unsigned int)ptr->key % newsize;
ptr->next=newbucket[newhashkey];
newbucket[newhashkey]=ptr;
}
ptr = &((*ptr)->next);
}
- if (thisvar->tailindex==ARRAYSIZE) {
- thisvar->listtail->nextarray=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
- thisvar->tailindex=0;
- thisvar->listtail=thisvar->listtail->nextarray;
+
+ {
+ struct RuntimeNode *node=RUNMALLOC(sizeof(struct RuntimeNode));
+ node->data=data;
+ node->key=key;
+ node->next=(*ptr);
+ *ptr=node;
+ if (thisvar->listhead==NULL) {
+ thisvar->listhead=node;
+ thisvar->listtail=node;
+ node->lnext=NULL;
+ node->lprev=NULL;
+ } else {
+ node->lprev=NULL;
+ node->lnext=thisvar->listhead;
+ thisvar->listhead->lprev=node;
+ thisvar->listhead=node;
+ }
+ }
+
+ thisvar->numelements++;
+ return 1;
+}
+
+#ifdef RAW
+int RuntimeHashadd_I(struct RuntimeHash * thisvar,int key, int data) {
+ /* Rehash code */
+ unsigned int hashkey;
+ struct RuntimeNode **ptr;
+
+ if (thisvar->numelements>=thisvar->size) {
+ int newsize=2*thisvar->size+1;
+ struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC_I(sizeof(struct RuntimeNode *)*newsize);
+ int i;
+ for(i=thisvar->size-1;i>=0;i--) {
+ struct RuntimeNode *ptr;
+ for(ptr=thisvar->bucket[i];ptr!=NULL;) {
+ struct RuntimeNode * nextptr=ptr->next;
+ unsigned int newhashkey=(unsigned int)ptr->key % newsize;
+ ptr->next=newbucket[newhashkey];
+ newbucket[newhashkey]=ptr;
+ ptr=nextptr;
+ }
+ }
+ thisvar->size=newsize;
+ RUNFREE(thisvar->bucket);
+ thisvar->bucket=newbucket;
+ }
+
+ hashkey = (unsigned int)key % thisvar->size;
+ ptr = &thisvar->bucket[hashkey];
+
+ /* check that thisvar key/object pair isn't already here */
+ /* TBD can be optimized for set v. relation */
+
+ while (*ptr) {
+ if ((*ptr)->key == key && (*ptr)->data == data) {
+ return 0;
+ }
+ ptr = &((*ptr)->next);
}
- *ptr = &thisvar->listtail->nodes[thisvar->tailindex++];
- (*ptr)->key=key;
- (*ptr)->data=data;
- (*ptr)->inuse=1;
+ {
+ struct RuntimeNode *node=RUNMALLOC_I(sizeof(struct RuntimeNode));
+ node->data=data;
+ node->key=key;
+ node->next=(*ptr);
+ *ptr=node;
+ if (thisvar->listhead==NULL) {
+ thisvar->listhead=node;
+ thisvar->listtail=node;
+ node->lnext=NULL;
+ node->lprev=NULL;
+ } else {
+ node->lprev=NULL;
+ node->lnext=thisvar->listhead;
+ thisvar->listhead->lprev=node;
+ thisvar->listhead=node;
+ }
+ }
thisvar->numelements++;
return 1;
}
+#endif
-bool SimpleHashcontainskey(struct SimpleHash *thisvar,int key) {
+bool RuntimeHashcontainskey(struct RuntimeHash *thisvar,int key) {
unsigned int hashkey = (unsigned int)key % thisvar->size;
- struct SimpleNode *ptr = thisvar->bucket[hashkey];
+ struct RuntimeNode *ptr = thisvar->bucket[hashkey];
while (ptr) {
if (ptr->key == key) {
/* we already have thisvar object
return false;
}
-bool SimpleHashcontainskeydata(struct SimpleHash *thisvar, int key, int data) {
+bool RuntimeHashcontainskeydata(struct RuntimeHash *thisvar, int key, int data) {
unsigned int hashkey = (unsigned int)key % thisvar->size;
- struct SimpleNode *ptr = thisvar->bucket[hashkey];
+ struct RuntimeNode *ptr = thisvar->bucket[hashkey];
while (ptr) {
if (ptr->key == key && ptr->data == data) {
/* we already have thisvar object
return false;
}
-int SimpleHashcount(struct SimpleHash *thisvar,int key) {
+int RuntimeHashcount(struct RuntimeHash *thisvar,int key) {
unsigned int hashkey = (unsigned int)key % thisvar->size;
int count = 0;
- struct SimpleNode *ptr = thisvar->bucket[hashkey];
+ struct RuntimeNode *ptr = thisvar->bucket[hashkey];
while (ptr) {
if (ptr->key == key) {
count++;
return count;
}
-struct SimpleHash * SimpleHashimageSet(struct SimpleHash *thisvar, int key) {
- struct SimpleHash * newset=allocateSimpleHash(2*SimpleHashcount(thisvar,key)+4);
+struct RuntimeHash * RuntimeHashimageSet(struct RuntimeHash *thisvar, int key) {
+ struct RuntimeHash * newset=allocateRuntimeHash(2*RuntimeHashcount(thisvar,key)+4);
unsigned int hashkey = (unsigned int)key % thisvar->size;
- struct SimpleNode *ptr = thisvar->bucket[hashkey];
+ struct RuntimeNode *ptr = thisvar->bucket[hashkey];
while (ptr) {
if (ptr->key == key) {
- SimpleHashadd(newset,ptr->data,ptr->data);
+ RuntimeHashadd(newset,ptr->data,ptr->data);
}
ptr = ptr->next;
}
return newset;
}
-int SimpleHashget(struct SimpleHash *thisvar, int key, int *data) {
+int RuntimeHashget(struct RuntimeHash *thisvar, int key, int *data) {
unsigned int hashkey = (unsigned int)key % thisvar->size;
- struct SimpleNode *ptr = thisvar->bucket[hashkey];
+ struct RuntimeNode *ptr = thisvar->bucket[hashkey];
while (ptr) {
if (ptr->key == key) {
*data = ptr->data;
return 0; /* failure */
}
-int SimpleHashcountdata(struct SimpleHash *thisvar,int data) {
- int count = 0;
- struct ArraySimple *ptr = thisvar->listhead;
- while(ptr) {
- if (ptr->nextarray) {
- int i;
- for(i=0;i<ARRAYSIZE;i++)
- if (ptr->nodes[i].data == data
- &&ptr->nodes[i].inuse) {
- count++;
- }
- } else {
- int i;
- for(i=0;i<thisvar->tailindex;i++)
- if (ptr->nodes[i].data == data
- &&ptr->nodes[i].inuse) {
- count++;
- }
- }
- ptr = ptr->nextarray;
- }
- return count;
-}
-
-inline struct SimpleIterator * noargallocateSimpleIterator() {
- return (struct SimpleIterator*)RUNMALLOC(sizeof(struct SimpleIterator));
+inline struct RuntimeIterator * noargallocateRuntimeIterator() {
+ return (struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
}
-inline struct SimpleIterator * allocateSimpleIterator(struct ArraySimple *start, struct ArraySimple *tl, int tlindex) {
- struct SimpleIterator *thisvar=(struct SimpleIterator*)RUNMALLOC(sizeof(struct SimpleIterator));
+inline struct RuntimeIterator * allocateRuntimeIterator(struct RuntimeNode *start) {
+ struct RuntimeIterator *thisvar=(struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
thisvar->cur = start;
- thisvar->index=0;
- thisvar->tailindex=tlindex;
- thisvar->tail=tl;
return thisvar;
}
-inline int hasNext(struct SimpleIterator *thisvar) {
- if (thisvar->cur==thisvar->tail &&
- thisvar->index==thisvar->tailindex)
- return 0;
- while((thisvar->index==ARRAYSIZE)||!thisvar->cur->nodes[thisvar->index].inuse) {
- if (thisvar->index==ARRAYSIZE) {
- thisvar->index=0;
- thisvar->cur=thisvar->cur->nextarray;
- } else
- thisvar->index++;
- }
- if (thisvar->cur->nodes[thisvar->index].inuse)
- return 1;
- else
- return 0;
+inline int RunhasNext(struct RuntimeIterator *thisvar) {
+ return (thisvar->cur!=NULL);
}
-inline int next(struct SimpleIterator *thisvar) {
- return thisvar->cur->nodes[thisvar->index++].data;
+inline int Runnext(struct RuntimeIterator *thisvar) {
+ int curr=thisvar->cur->data;
+ thisvar->cur=thisvar->cur->lnext;
+ return curr;
}
-inline int key(struct SimpleIterator *thisvar) {
- return thisvar->cur->nodes[thisvar->index].key;
+inline int Runkey(struct RuntimeIterator *thisvar) {
+ return thisvar->cur->key;
}
projects / IRC.git / blobdiff