#include "SimpleHash.h"
+#ifdef RAW
+#include <raw.h>
+#else
#include <stdio.h>
+#endif
+#ifdef DMALLOC
+#include "dmalloc.h"
+#endif
/* SIMPLE HASH ********************************************************/
struct RuntimeIterator* RuntimeHashcreateiterator(struct RuntimeHash * thisvar) {
- return allocateRuntimeIterator(thisvar->listhead,thisvar->listtail,thisvar->tailindex/*,thisvar*/);
+ return allocateRuntimeIterator(thisvar->listhead);
}
void RuntimeHashiterator(struct RuntimeHash *thisvar, struct RuntimeIterator * it) {
it->cur=thisvar->listhead;
- it->index=0;
- it->tailindex=thisvar->tailindex;
- it->tail=thisvar->listtail;
}
struct RuntimeHash * noargallocateRuntimeHash() {
}
struct RuntimeHash * allocateRuntimeHash(int size) {
- struct RuntimeHash *thisvar=(struct RuntimeHash *)RUNMALLOC(sizeof(struct RuntimeHash));
+ 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 RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*size);
/* Set allocation blocks*/
- thisvar->listhead=(struct ArrayRuntime *) RUNMALLOC(sizeof(struct ArrayRuntime));
- thisvar->listtail=thisvar->listhead;
- thisvar->tailindex=0;
+ thisvar->listhead=NULL;
+ thisvar->listtail=NULL;
/*Set data counts*/
thisvar->numelements = 0;
return thisvar;
}
void freeRuntimeHash(struct RuntimeHash *thisvar) {
- struct ArrayRuntime *ptr=thisvar->listhead;
+ struct RuntimeNode *ptr=thisvar->listhead;
RUNFREE(thisvar->bucket);
while(ptr) {
- struct ArrayRuntime *next=ptr->nextarray;
+ struct RuntimeNode *next=ptr->lnext;
RUNFREE(ptr);
ptr=next;
}
}
int RuntimeHashfirstkey(struct RuntimeHash *thisvar) {
- struct ArrayRuntime *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;
+ struct RuntimeNode *ptr=thisvar->listhead;
+ return ptr->key;
+}
+
+int RuntimeHashremovekey(struct RuntimeHash *thisvar, int key) {
+ unsigned int hashkey = (unsigned int)key % thisvar->size;
+
+ 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) {
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 RuntimeHashaddAll(struct RuntimeHash *thisvar, struct RuntimeHash * set) {
- struct RuntimeIterator it;
- RuntimeHashiterator(set, &it);
- while(RunhasNext(&it)) {
- int keyv=Runkey(&it);
- int data=Runnext(&it);
- RuntimeHashadd(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 RuntimeHashadd(struct RuntimeHash * thisvar,int key, int data) {
}
ptr = &((*ptr)->next);
}
- if (thisvar->tailindex==ARRAYSIZE) {
- thisvar->listtail->nextarray=(struct ArrayRuntime *) RUNMALLOC(sizeof(struct ArrayRuntime));
- 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;
+ }
}
- *ptr = &thisvar->listtail->nodes[thisvar->tailindex++];
- (*ptr)->key=key;
- (*ptr)->data=data;
- (*ptr)->inuse=1;
+ 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);
+ }
+
+ {
+ 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 RuntimeHashcontainskey(struct RuntimeHash *thisvar,int key) {
unsigned int hashkey = (unsigned int)key % thisvar->size;
return 0; /* failure */
}
-int RuntimeHashcountdata(struct RuntimeHash *thisvar,int data) {
- int count = 0;
- struct ArrayRuntime *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 RuntimeIterator * noargallocateRuntimeIterator() {
return (struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
}
-inline struct RuntimeIterator * allocateRuntimeIterator(struct ArrayRuntime *start, struct ArrayRuntime *tl, int tlindex) {
+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 RunhasNext(struct RuntimeIterator *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;
+ return (thisvar->cur!=NULL);
}
inline int Runnext(struct RuntimeIterator *thisvar) {
- return thisvar->cur->nodes[thisvar->index++].data;
+ int curr=thisvar->cur->data;
+ thisvar->cur=thisvar->cur->lnext;
+ return curr;
}
inline int Runkey(struct RuntimeIterator *thisvar) {
- return thisvar->cur->nodes[thisvar->index].key;
+ return thisvar->cur->key;
}
projects / IRC.git / blobdiff