1 #include "SimpleHash.h"
11 /* SIMPLE HASH ********************************************************/
12 struct RuntimeIterator* RuntimeHashcreateiterator(struct RuntimeHash * thisvar) {
13 return allocateRuntimeIterator(thisvar->listhead);
16 void RuntimeHashiterator(struct RuntimeHash *thisvar, struct RuntimeIterator * it) {
17 it->cur=thisvar->listhead;
20 struct RuntimeHash * noargallocateRuntimeHash() {
21 return allocateRuntimeHash(100);
24 struct RuntimeHash * allocateRuntimeHash(int size) {
25 struct RuntimeHash *thisvar;//=(struct RuntimeHash *)RUNMALLOC(sizeof(struct RuntimeHash));
28 raw_test_done(0xb001);
30 printf("Negative Hashtable size Exception\n");
34 thisvar=(struct RuntimeHash *)RUNMALLOC(sizeof(struct RuntimeHash));
36 thisvar->bucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*size);
37 /* Set allocation blocks*/
38 thisvar->listhead=NULL;
39 thisvar->listtail=NULL;
41 thisvar->numelements = 0;
45 void freeRuntimeHash(struct RuntimeHash *thisvar) {
46 struct RuntimeNode *ptr=thisvar->listhead;
47 RUNFREE(thisvar->bucket);
49 struct RuntimeNode *next=ptr->lnext;
56 inline int RuntimeHashcountset(struct RuntimeHash * thisvar) {
57 return thisvar->numelements;
60 int RuntimeHashfirstkey(struct RuntimeHash *thisvar) {
61 struct RuntimeNode *ptr=thisvar->listhead;
65 int RuntimeHashremovekey(struct RuntimeHash *thisvar, int key) {
66 unsigned int hashkey = (unsigned int)key % thisvar->size;
68 struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
72 if ((*ptr)->key == key) {
73 struct RuntimeNode *toremove=*ptr;
76 if (toremove->lprev!=NULL) {
77 toremove->lprev->lnext=toremove->lnext;
79 thisvar->listhead=toremove->lnext;
81 if (toremove->lnext!=NULL) {
82 toremove->lnext->lprev=toremove->lprev;
84 thisvar->listtail=toremove->lprev;
88 thisvar->numelements--;
91 ptr = &((*ptr)->next);
97 int RuntimeHashremove(struct RuntimeHash *thisvar, int key, int data) {
98 unsigned int hashkey = (unsigned int)key % thisvar->size;
100 struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
104 if ((*ptr)->key == key && (*ptr)->data == data) {
105 struct RuntimeNode *toremove=*ptr;
108 if (toremove->lprev!=NULL) {
109 toremove->lprev->lnext=toremove->lnext;
111 thisvar->listhead=toremove->lnext;
113 if (toremove->lnext!=NULL) {
114 toremove->lnext->lprev=toremove->lprev;
116 thisvar->listtail=toremove->lprev;
120 thisvar->numelements--;
123 ptr = &((*ptr)->next);
129 void RuntimeHashrehash(struct RuntimeHash * thisvar) {
130 int newsize=thisvar->size;
131 struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
133 for(i=thisvar->size-1;i>=0;i--) {
134 struct RuntimeNode *ptr;
135 for(ptr=thisvar->bucket[i];ptr!=NULL;) {
136 struct RuntimeNode * nextptr=ptr->next;
137 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
138 ptr->next=newbucket[newhashkey];
139 newbucket[newhashkey]=ptr;
143 thisvar->size=newsize;
144 RUNFREE(thisvar->bucket);
145 thisvar->bucket=newbucket;
148 int RuntimeHashadd(struct RuntimeHash * thisvar,int key, int data) {
150 unsigned int hashkey;
151 struct RuntimeNode **ptr;
153 if (thisvar->numelements>=thisvar->size) {
154 int newsize=2*thisvar->size+1;
155 struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
157 for(i=thisvar->size-1;i>=0;i--) {
158 struct RuntimeNode *ptr;
159 for(ptr=thisvar->bucket[i];ptr!=NULL;) {
160 struct RuntimeNode * nextptr=ptr->next;
161 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
162 ptr->next=newbucket[newhashkey];
163 newbucket[newhashkey]=ptr;
167 thisvar->size=newsize;
168 RUNFREE(thisvar->bucket);
169 thisvar->bucket=newbucket;
172 hashkey = (unsigned int)key % thisvar->size;
173 ptr = &thisvar->bucket[hashkey];
175 /* check that thisvar key/object pair isn't already here */
176 /* TBD can be optimized for set v. relation */
179 if ((*ptr)->key == key && (*ptr)->data == data) {
182 ptr = &((*ptr)->next);
186 struct RuntimeNode *node=RUNMALLOC(sizeof(struct RuntimeNode));
191 if (thisvar->listhead==NULL) {
192 thisvar->listhead=node;
193 thisvar->listtail=node;
198 node->lnext=thisvar->listhead;
199 thisvar->listhead->lprev=node;
200 thisvar->listhead=node;
204 thisvar->numelements++;
209 int RuntimeHashadd_I(struct RuntimeHash * thisvar,int key, int data) {
211 unsigned int hashkey;
212 struct RuntimeNode **ptr;
214 if (thisvar->numelements>=thisvar->size) {
215 int newsize=2*thisvar->size+1;
216 struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC_I(sizeof(struct RuntimeNode *)*newsize);
218 for(i=thisvar->size-1;i>=0;i--) {
219 struct RuntimeNode *ptr;
220 for(ptr=thisvar->bucket[i];ptr!=NULL;) {
221 struct RuntimeNode * nextptr=ptr->next;
222 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
223 ptr->next=newbucket[newhashkey];
224 newbucket[newhashkey]=ptr;
228 thisvar->size=newsize;
229 RUNFREE(thisvar->bucket);
230 thisvar->bucket=newbucket;
233 hashkey = (unsigned int)key % thisvar->size;
234 ptr = &thisvar->bucket[hashkey];
236 /* check that thisvar key/object pair isn't already here */
237 /* TBD can be optimized for set v. relation */
240 if ((*ptr)->key == key && (*ptr)->data == data) {
243 ptr = &((*ptr)->next);
247 struct RuntimeNode *node=RUNMALLOC_I(sizeof(struct RuntimeNode));
252 if (thisvar->listhead==NULL) {
253 thisvar->listhead=node;
254 thisvar->listtail=node;
259 node->lnext=thisvar->listhead;
260 thisvar->listhead->lprev=node;
261 thisvar->listhead=node;
265 thisvar->numelements++;
270 bool RuntimeHashcontainskey(struct RuntimeHash *thisvar,int key) {
271 unsigned int hashkey = (unsigned int)key % thisvar->size;
273 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
275 if (ptr->key == key) {
276 /* we already have thisvar object
277 stored in the hash so just return */
285 bool RuntimeHashcontainskeydata(struct RuntimeHash *thisvar, int key, int data) {
286 unsigned int hashkey = (unsigned int)key % thisvar->size;
288 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
290 if (ptr->key == key && ptr->data == data) {
291 /* we already have thisvar object
292 stored in the hash so just return*/
300 int RuntimeHashcount(struct RuntimeHash *thisvar,int key) {
301 unsigned int hashkey = (unsigned int)key % thisvar->size;
304 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
306 if (ptr->key == key) {
314 struct RuntimeHash * RuntimeHashimageSet(struct RuntimeHash *thisvar, int key) {
315 struct RuntimeHash * newset=allocateRuntimeHash(2*RuntimeHashcount(thisvar,key)+4);
316 unsigned int hashkey = (unsigned int)key % thisvar->size;
318 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
320 if (ptr->key == key) {
321 RuntimeHashadd(newset,ptr->data,ptr->data);
328 int RuntimeHashget(struct RuntimeHash *thisvar, int key, int *data) {
329 unsigned int hashkey = (unsigned int)key % thisvar->size;
331 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
333 if (ptr->key == key) {
335 return 1; /* success */
340 return 0; /* failure */
343 inline struct RuntimeIterator * noargallocateRuntimeIterator() {
344 return (struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
347 inline struct RuntimeIterator * allocateRuntimeIterator(struct RuntimeNode *start) {
348 struct RuntimeIterator *thisvar=(struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
349 thisvar->cur = start;
353 inline int RunhasNext(struct RuntimeIterator *thisvar) {
354 return (thisvar->cur!=NULL);
357 inline int Runnext(struct RuntimeIterator *thisvar) {
358 int curr=thisvar->cur->data;
359 thisvar->cur=thisvar->cur->lnext;
363 inline int Runkey(struct RuntimeIterator *thisvar) {
364 return thisvar->cur->key;