1 #include "SimpleHash.h"
3 #include "methodheaders.h"
4 #include "multicore_arch.h"
5 #include "runtime_arch.h"
13 /* SIMPLE HASH ********************************************************/
14 struct RuntimeIterator* RuntimeHashcreateiterator(struct RuntimeHash * thisvar) {
15 return allocateRuntimeIterator(thisvar->listhead);
18 void RuntimeHashiterator(struct RuntimeHash *thisvar, struct RuntimeIterator * it) {
19 it->cur=thisvar->listhead;
22 struct RuntimeHash * noargallocateRuntimeHash() {
23 return allocateRuntimeHash(100);
26 struct RuntimeHash * allocateRuntimeHash(int size) {
27 struct RuntimeHash *thisvar;
32 printf("Negative Hashtable size Exception\n");
36 thisvar=(struct RuntimeHash *)RUNMALLOC(sizeof(struct RuntimeHash));
38 thisvar->bucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*size);
39 /* Set allocation blocks*/
40 thisvar->listhead=NULL;
41 thisvar->listtail=NULL;
43 thisvar->numelements = 0;
47 void freeRuntimeHash(struct RuntimeHash *thisvar) {
48 struct RuntimeNode *ptr=thisvar->listhead;
49 RUNFREE(thisvar->bucket);
51 struct RuntimeNode *next=ptr->lnext;
58 inline int RuntimeHashcountset(struct RuntimeHash * thisvar) {
59 return thisvar->numelements;
62 int RuntimeHashfirstkey(struct RuntimeHash *thisvar) {
63 struct RuntimeNode *ptr=thisvar->listhead;
67 int RuntimeHashremovekey(struct RuntimeHash *thisvar, int key) {
68 unsigned int hashkey = (unsigned int)key % thisvar->size;
70 struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
73 if ((*ptr)->key == key) {
74 struct RuntimeNode *toremove=*ptr;
77 if (toremove->lprev!=NULL) {
78 toremove->lprev->lnext=toremove->lnext;
80 thisvar->listhead=toremove->lnext;
82 if (toremove->lnext!=NULL) {
83 toremove->lnext->lprev=toremove->lprev;
85 thisvar->listtail=toremove->lprev;
89 thisvar->numelements--;
92 ptr = &((*ptr)->next);
98 int RuntimeHashremove(struct RuntimeHash *thisvar, int key, int data) {
99 unsigned int hashkey = (unsigned int)key % thisvar->size;
101 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 struct RuntimeHash * allocateRuntimeHash_I(int size) {
210 struct RuntimeHash *thisvar;
215 printf("Negative Hashtable size Exception\n");
219 thisvar=(struct RuntimeHash *)RUNMALLOC_I(sizeof(struct RuntimeHash));
220 thisvar->size = size;
221 thisvar->bucket = (struct RuntimeNode **) RUNMALLOC_I(sizeof(struct RuntimeNode *)*size);
222 /* Set allocation blocks*/
223 thisvar->listhead=NULL;
224 thisvar->listtail=NULL;
226 thisvar->numelements = 0;
230 int RuntimeHashadd_I(struct RuntimeHash * thisvar,int key, int data) {
232 unsigned int hashkey;
233 struct RuntimeNode **ptr;
235 if (thisvar->numelements>=thisvar->size) {
236 int newsize=2*thisvar->size+1;
237 struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC_I(sizeof(struct RuntimeNode *)*newsize);
239 for(i=thisvar->size-1; i>=0; i--) {
240 struct RuntimeNode *ptr;
241 for(ptr=thisvar->bucket[i]; ptr!=NULL; ) {
242 struct RuntimeNode * nextptr=ptr->next;
243 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
244 ptr->next=newbucket[newhashkey];
245 newbucket[newhashkey]=ptr;
249 thisvar->size=newsize;
250 RUNFREE_I(thisvar->bucket);
251 thisvar->bucket=newbucket;
254 hashkey = (unsigned int)key % thisvar->size;
255 ptr = &thisvar->bucket[hashkey];
257 /* check that thisvar key/object pair isn't already here */
258 /* TBD can be optimized for set v. relation */
261 if ((*ptr)->key == key && (*ptr)->data == data) {
264 ptr = &((*ptr)->next);
268 struct RuntimeNode *node=RUNMALLOC_I(sizeof(struct RuntimeNode));
273 if (thisvar->listhead==NULL) {
274 thisvar->listhead=node;
275 thisvar->listtail=node;
280 node->lnext=thisvar->listhead;
281 thisvar->listhead->lprev=node;
282 thisvar->listhead=node;
286 thisvar->numelements++;
291 bool RuntimeHashcontainskey(struct RuntimeHash *thisvar,int key) {
292 unsigned int hashkey = (unsigned int)key % thisvar->size;
294 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
296 if (ptr->key == key) {
297 /* we already have thisvar object
298 stored in the hash so just return */
306 bool RuntimeHashcontainskeydata(struct RuntimeHash *thisvar, int key, int data) {
307 unsigned int hashkey = (unsigned int)key % thisvar->size;
309 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
311 if (ptr->key == key && ptr->data == data) {
312 /* we already have thisvar object
313 stored in the hash so just return*/
321 int RuntimeHashcount(struct RuntimeHash *thisvar,int key) {
322 unsigned int hashkey = (unsigned int)key % thisvar->size;
325 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
327 if (ptr->key == key) {
335 struct RuntimeHash * RuntimeHashimageSet(struct RuntimeHash *thisvar, int key) {
336 struct RuntimeHash * newset=allocateRuntimeHash(2*RuntimeHashcount(thisvar,key)+4);
337 unsigned int hashkey = (unsigned int)key % thisvar->size;
339 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
341 if (ptr->key == key) {
342 RuntimeHashadd(newset,ptr->data,ptr->data);
349 int RuntimeHashget(struct RuntimeHash *thisvar, int key, int *data) {
350 unsigned int hashkey = (unsigned int)key % thisvar->size;
352 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
354 if (ptr->key == key) {
356 return 1; /* success */
361 return 0; /* failure */
364 inline struct RuntimeIterator * noargallocateRuntimeIterator() {
365 return (struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
368 inline struct RuntimeIterator * allocateRuntimeIterator(struct RuntimeNode *start) {
369 struct RuntimeIterator *thisvar=(struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
370 thisvar->cur = start;
374 inline int RunhasNext(struct RuntimeIterator *thisvar) {
375 return (thisvar->cur!=NULL);
378 inline int Runnext(struct RuntimeIterator *thisvar) {
379 int curr=thisvar->cur->data;
380 thisvar->cur=thisvar->cur->lnext;
384 inline int Runkey(struct RuntimeIterator *thisvar) {
385 return thisvar->cur->key;