1 #include "SimpleHash.h"
3 #include "runtime_arch.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));
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];
71 if ((*ptr)->key == key) {
72 struct RuntimeNode *toremove=*ptr;
75 if (toremove->lprev!=NULL) {
76 toremove->lprev->lnext=toremove->lnext;
78 thisvar->listhead=toremove->lnext;
80 if (toremove->lnext!=NULL) {
81 toremove->lnext->lprev=toremove->lprev;
83 thisvar->listtail=toremove->lprev;
87 thisvar->numelements--;
90 ptr = &((*ptr)->next);
96 int RuntimeHashremove(struct RuntimeHash *thisvar, int key, int data) {
97 unsigned int hashkey = (unsigned int)key % thisvar->size;
99 struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
102 if ((*ptr)->key == key && (*ptr)->data == data) {
103 struct RuntimeNode *toremove=*ptr;
106 if (toremove->lprev!=NULL) {
107 toremove->lprev->lnext=toremove->lnext;
109 thisvar->listhead=toremove->lnext;
111 if (toremove->lnext!=NULL) {
112 toremove->lnext->lprev=toremove->lprev;
114 thisvar->listtail=toremove->lprev;
118 thisvar->numelements--;
121 ptr = &((*ptr)->next);
127 void RuntimeHashrehash(struct RuntimeHash * thisvar) {
128 int newsize=thisvar->size;
129 struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
131 for(i=thisvar->size-1; i>=0; i--) {
132 struct RuntimeNode *ptr;
133 for(ptr=thisvar->bucket[i]; ptr!=NULL;) {
134 struct RuntimeNode * nextptr=ptr->next;
135 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
136 ptr->next=newbucket[newhashkey];
137 newbucket[newhashkey]=ptr;
141 thisvar->size=newsize;
142 RUNFREE(thisvar->bucket);
143 thisvar->bucket=newbucket;
146 int RuntimeHashadd(struct RuntimeHash * thisvar,int key, int data) {
148 unsigned int hashkey;
149 struct RuntimeNode **ptr;
151 if (thisvar->numelements>=thisvar->size) {
152 int newsize=2*thisvar->size+1;
153 struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
155 for(i=thisvar->size-1; i>=0; i--) {
156 struct RuntimeNode *ptr;
157 for(ptr=thisvar->bucket[i]; ptr!=NULL;) {
158 struct RuntimeNode * nextptr=ptr->next;
159 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
160 ptr->next=newbucket[newhashkey];
161 newbucket[newhashkey]=ptr;
165 thisvar->size=newsize;
166 RUNFREE(thisvar->bucket);
167 thisvar->bucket=newbucket;
170 hashkey = (unsigned int)key % thisvar->size;
171 ptr = &thisvar->bucket[hashkey];
173 /* check that thisvar key/object pair isn't already here */
174 /* TBD can be optimized for set v. relation */
177 if ((*ptr)->key == key && (*ptr)->data == data) {
180 ptr = &((*ptr)->next);
184 struct RuntimeNode *node=RUNMALLOC(sizeof(struct RuntimeNode));
189 if (thisvar->listhead==NULL) {
190 thisvar->listhead=node;
191 thisvar->listtail=node;
196 node->lnext=thisvar->listhead;
197 thisvar->listhead->lprev=node;
198 thisvar->listhead=node;
202 thisvar->numelements++;
207 struct RuntimeHash * allocateRuntimeHash_I(int size) {
208 struct RuntimeHash *thisvar; //=(struct RuntimeHash *)RUNMALLOC(sizeof(struct RuntimeHash));
213 printf("Negative Hashtable size Exception\n");
217 thisvar=(struct RuntimeHash *)RUNMALLOC_I(sizeof(struct RuntimeHash));
218 thisvar->size = size;
219 thisvar->bucket = (struct RuntimeNode **) RUNMALLOC_I(sizeof(struct RuntimeNode *)*size);
220 /* Set allocation blocks*/
221 thisvar->listhead=NULL;
222 thisvar->listtail=NULL;
224 thisvar->numelements = 0;
228 int RuntimeHashadd_I(struct RuntimeHash * thisvar,int key, int data) {
230 unsigned int hashkey;
231 struct RuntimeNode **ptr;
233 if (thisvar->numelements>=thisvar->size) {
234 int newsize=2*thisvar->size+1;
235 struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC_I(sizeof(struct RuntimeNode *)*newsize);
237 for(i=thisvar->size-1; i>=0; i--) {
238 struct RuntimeNode *ptr;
239 for(ptr=thisvar->bucket[i]; ptr!=NULL;) {
240 struct RuntimeNode * nextptr=ptr->next;
241 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
242 ptr->next=newbucket[newhashkey];
243 newbucket[newhashkey]=ptr;
247 thisvar->size=newsize;
248 RUNFREE(thisvar->bucket);
249 thisvar->bucket=newbucket;
252 hashkey = (unsigned int)key % thisvar->size;
253 ptr = &thisvar->bucket[hashkey];
255 /* check that thisvar key/object pair isn't already here */
256 /* TBD can be optimized for set v. relation */
259 if ((*ptr)->key == key && (*ptr)->data == data) {
262 ptr = &((*ptr)->next);
266 struct RuntimeNode *node=RUNMALLOC_I(sizeof(struct RuntimeNode));
271 if (thisvar->listhead==NULL) {
272 thisvar->listhead=node;
273 thisvar->listtail=node;
278 node->lnext=thisvar->listhead;
279 thisvar->listhead->lprev=node;
280 thisvar->listhead=node;
284 thisvar->numelements++;
289 bool RuntimeHashcontainskey(struct RuntimeHash *thisvar,int key) {
290 unsigned int hashkey = (unsigned int)key % thisvar->size;
292 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
294 if (ptr->key == key) {
295 /* we already have thisvar object
296 stored in the hash so just return */
304 bool RuntimeHashcontainskeydata(struct RuntimeHash *thisvar, int key, int data) {
305 unsigned int hashkey = (unsigned int)key % thisvar->size;
307 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
309 if (ptr->key == key && ptr->data == data) {
310 /* we already have thisvar object
311 stored in the hash so just return*/
319 int RuntimeHashcount(struct RuntimeHash *thisvar,int key) {
320 unsigned int hashkey = (unsigned int)key % thisvar->size;
323 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
325 if (ptr->key == key) {
333 struct RuntimeHash * RuntimeHashimageSet(struct RuntimeHash *thisvar, int key) {
334 struct RuntimeHash * newset=allocateRuntimeHash(2*RuntimeHashcount(thisvar,key)+4);
335 unsigned int hashkey = (unsigned int)key % thisvar->size;
337 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
339 if (ptr->key == key) {
340 RuntimeHashadd(newset,ptr->data,ptr->data);
347 int RuntimeHashget(struct RuntimeHash *thisvar, int key, int *data) {
348 unsigned int hashkey = (unsigned int)key % thisvar->size;
350 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
352 if (ptr->key == key) {
354 return 1; /* success */
359 return 0; /* failure */
362 inline struct RuntimeIterator * noargallocateRuntimeIterator() {
363 return (struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
366 inline struct RuntimeIterator * allocateRuntimeIterator(struct RuntimeNode *start) {
367 struct RuntimeIterator *thisvar=(struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
368 thisvar->cur = start;
372 inline int RunhasNext(struct RuntimeIterator *thisvar) {
373 return (thisvar->cur!=NULL);
376 inline int Runnext(struct RuntimeIterator *thisvar) {
377 int curr=thisvar->cur->data;
378 thisvar->cur=thisvar->cur->lnext;
382 inline int Runkey(struct RuntimeIterator *thisvar) {
383 return thisvar->cur->key;