1 #include "SimpleHash.h"
7 /* SIMPLE HASH ********************************************************/
8 struct RuntimeIterator* RuntimeHashcreateiterator(struct RuntimeHash * thisvar) {
9 return allocateRuntimeIterator(thisvar->listhead);
12 void RuntimeHashiterator(struct RuntimeHash *thisvar, struct RuntimeIterator * it) {
13 it->cur=thisvar->listhead;
16 struct RuntimeHash * noargallocateRuntimeHash() {
17 return allocateRuntimeHash(100);
20 struct RuntimeHash * allocateRuntimeHash(int size) {
21 struct RuntimeHash *thisvar=(struct RuntimeHash *)RUNMALLOC(sizeof(struct RuntimeHash));
23 printf("Negative Hashtable size Exception\n");
27 thisvar->bucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*size);
28 /* Set allocation blocks*/
29 thisvar->listhead=NULL;
30 thisvar->listtail=NULL;
32 thisvar->numelements = 0;
36 void freeRuntimeHash(struct RuntimeHash *thisvar) {
37 struct RuntimeNode *ptr=thisvar->listhead;
38 RUNFREE(thisvar->bucket);
40 struct RuntimeNode *next=ptr->lnext;
47 inline int RuntimeHashcountset(struct RuntimeHash * thisvar) {
48 return thisvar->numelements;
51 int RuntimeHashfirstkey(struct RuntimeHash *thisvar) {
52 struct RuntimeNode *ptr=thisvar->listhead;
56 int RuntimeHashremove(struct RuntimeHash *thisvar, int key, int data) {
57 unsigned int hashkey = (unsigned int)key % thisvar->size;
59 struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
63 if ((*ptr)->key == key && (*ptr)->data == data) {
64 struct RuntimeNode *toremove=*ptr;
67 if (toremove->lprev!=NULL)
68 toremove->lprev->lnext=toremove->lnext;
70 thisvar->listhead=toremove->lnext;
71 if (toremove->lnext!=NULL)
72 toremove->lnext->lprev=toremove->lprev;
74 thisvar->listtail=toremove->lprev;
77 thisvar->numelements--;
80 ptr = &((*ptr)->next);
86 void RuntimeHashrehash(struct RuntimeHash * thisvar) {
87 int newsize=thisvar->size;
88 struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
90 for(i=thisvar->size-1;i>=0;i--) {
91 struct RuntimeNode *ptr;
92 for(ptr=thisvar->bucket[i];ptr!=NULL;) {
93 struct RuntimeNode * nextptr=ptr->next;
94 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
95 ptr->next=newbucket[newhashkey];
96 newbucket[newhashkey]=ptr;
100 thisvar->size=newsize;
101 RUNFREE(thisvar->bucket);
102 thisvar->bucket=newbucket;
105 int RuntimeHashadd(struct RuntimeHash * thisvar,int key, int data) {
107 unsigned int hashkey;
108 struct RuntimeNode **ptr;
110 if (thisvar->numelements>=thisvar->size) {
111 int newsize=2*thisvar->size+1;
112 struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
114 for(i=thisvar->size-1;i>=0;i--) {
115 struct RuntimeNode *ptr;
116 for(ptr=thisvar->bucket[i];ptr!=NULL;) {
117 struct RuntimeNode * nextptr=ptr->next;
118 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
119 ptr->next=newbucket[newhashkey];
120 newbucket[newhashkey]=ptr;
124 thisvar->size=newsize;
125 RUNFREE(thisvar->bucket);
126 thisvar->bucket=newbucket;
129 hashkey = (unsigned int)key % thisvar->size;
130 ptr = &thisvar->bucket[hashkey];
132 /* check that thisvar key/object pair isn't already here */
133 /* TBD can be optimized for set v. relation */
136 if ((*ptr)->key == key && (*ptr)->data == data) {
139 ptr = &((*ptr)->next);
143 struct RuntimeNode *node=RUNMALLOC(sizeof(struct RuntimeNode));
148 if (thisvar->listhead==NULL) {
149 thisvar->listhead=node;
150 thisvar->listtail=node;
155 node->lnext=thisvar->listhead;
156 thisvar->listhead->lprev=node;
157 thisvar->listhead=node;
161 thisvar->numelements++;
165 bool RuntimeHashcontainskey(struct RuntimeHash *thisvar,int key) {
166 unsigned int hashkey = (unsigned int)key % thisvar->size;
168 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
170 if (ptr->key == key) {
171 /* we already have thisvar object
172 stored in the hash so just return */
180 bool RuntimeHashcontainskeydata(struct RuntimeHash *thisvar, int key, int data) {
181 unsigned int hashkey = (unsigned int)key % thisvar->size;
183 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
185 if (ptr->key == key && ptr->data == data) {
186 /* we already have thisvar object
187 stored in the hash so just return*/
195 int RuntimeHashcount(struct RuntimeHash *thisvar,int key) {
196 unsigned int hashkey = (unsigned int)key % thisvar->size;
199 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
201 if (ptr->key == key) {
209 struct RuntimeHash * RuntimeHashimageSet(struct RuntimeHash *thisvar, int key) {
210 struct RuntimeHash * newset=allocateRuntimeHash(2*RuntimeHashcount(thisvar,key)+4);
211 unsigned int hashkey = (unsigned int)key % thisvar->size;
213 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
215 if (ptr->key == key) {
216 RuntimeHashadd(newset,ptr->data,ptr->data);
223 int RuntimeHashget(struct RuntimeHash *thisvar, int key, int *data) {
224 unsigned int hashkey = (unsigned int)key % thisvar->size;
226 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
228 if (ptr->key == key) {
230 return 1; /* success */
235 return 0; /* failure */
238 inline struct RuntimeIterator * noargallocateRuntimeIterator() {
239 return (struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
242 inline struct RuntimeIterator * allocateRuntimeIterator(struct RuntimeNode *start) {
243 struct RuntimeIterator *thisvar=(struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
244 thisvar->cur = start;
248 inline int RunhasNext(struct RuntimeIterator *thisvar) {
249 return (thisvar->cur!=NULL);
252 inline int Runnext(struct RuntimeIterator *thisvar) {
253 int curr=thisvar->cur->data;
254 thisvar->cur=thisvar->cur->next;
257 inline int Runkey(struct RuntimeIterator *thisvar) {
258 return thisvar->cur->key;