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 RuntimeHashremovekey(struct RuntimeHash *thisvar, int key) {
57 unsigned int hashkey = (unsigned int)key % thisvar->size;
59 struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
63 if ((*ptr)->key == key) {
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 int RuntimeHashremove(struct RuntimeHash *thisvar, int key, int data) {
87 unsigned int hashkey = (unsigned int)key % thisvar->size;
89 struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
93 if ((*ptr)->key == key && (*ptr)->data == data) {
94 struct RuntimeNode *toremove=*ptr;
97 if (toremove->lprev!=NULL)
98 toremove->lprev->lnext=toremove->lnext;
100 thisvar->listhead=toremove->lnext;
101 if (toremove->lnext!=NULL)
102 toremove->lnext->lprev=toremove->lprev;
104 thisvar->listtail=toremove->lprev;
107 thisvar->numelements--;
110 ptr = &((*ptr)->next);
116 void RuntimeHashrehash(struct RuntimeHash * thisvar) {
117 int newsize=thisvar->size;
118 struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
120 for(i=thisvar->size-1;i>=0;i--) {
121 struct RuntimeNode *ptr;
122 for(ptr=thisvar->bucket[i];ptr!=NULL;) {
123 struct RuntimeNode * nextptr=ptr->next;
124 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
125 ptr->next=newbucket[newhashkey];
126 newbucket[newhashkey]=ptr;
130 thisvar->size=newsize;
131 RUNFREE(thisvar->bucket);
132 thisvar->bucket=newbucket;
135 int RuntimeHashadd(struct RuntimeHash * thisvar,int key, int data) {
137 unsigned int hashkey;
138 struct RuntimeNode **ptr;
140 if (thisvar->numelements>=thisvar->size) {
141 int newsize=2*thisvar->size+1;
142 struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
144 for(i=thisvar->size-1;i>=0;i--) {
145 struct RuntimeNode *ptr;
146 for(ptr=thisvar->bucket[i];ptr!=NULL;) {
147 struct RuntimeNode * nextptr=ptr->next;
148 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
149 ptr->next=newbucket[newhashkey];
150 newbucket[newhashkey]=ptr;
154 thisvar->size=newsize;
155 RUNFREE(thisvar->bucket);
156 thisvar->bucket=newbucket;
159 hashkey = (unsigned int)key % thisvar->size;
160 ptr = &thisvar->bucket[hashkey];
162 /* check that thisvar key/object pair isn't already here */
163 /* TBD can be optimized for set v. relation */
166 if ((*ptr)->key == key && (*ptr)->data == data) {
169 ptr = &((*ptr)->next);
173 struct RuntimeNode *node=RUNMALLOC(sizeof(struct RuntimeNode));
178 if (thisvar->listhead==NULL) {
179 thisvar->listhead=node;
180 thisvar->listtail=node;
185 node->lnext=thisvar->listhead;
186 thisvar->listhead->lprev=node;
187 thisvar->listhead=node;
191 thisvar->numelements++;
195 bool RuntimeHashcontainskey(struct RuntimeHash *thisvar,int key) {
196 unsigned int hashkey = (unsigned int)key % thisvar->size;
198 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
200 if (ptr->key == key) {
201 /* we already have thisvar object
202 stored in the hash so just return */
210 bool RuntimeHashcontainskeydata(struct RuntimeHash *thisvar, int key, int data) {
211 unsigned int hashkey = (unsigned int)key % thisvar->size;
213 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
215 if (ptr->key == key && ptr->data == data) {
216 /* we already have thisvar object
217 stored in the hash so just return*/
225 int RuntimeHashcount(struct RuntimeHash *thisvar,int key) {
226 unsigned int hashkey = (unsigned int)key % thisvar->size;
229 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
231 if (ptr->key == key) {
239 struct RuntimeHash * RuntimeHashimageSet(struct RuntimeHash *thisvar, int key) {
240 struct RuntimeHash * newset=allocateRuntimeHash(2*RuntimeHashcount(thisvar,key)+4);
241 unsigned int hashkey = (unsigned int)key % thisvar->size;
243 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
245 if (ptr->key == key) {
246 RuntimeHashadd(newset,ptr->data,ptr->data);
253 int RuntimeHashget(struct RuntimeHash *thisvar, int key, int *data) {
254 unsigned int hashkey = (unsigned int)key % thisvar->size;
256 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
258 if (ptr->key == key) {
260 return 1; /* success */
265 return 0; /* failure */
268 inline struct RuntimeIterator * noargallocateRuntimeIterator() {
269 return (struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
272 inline struct RuntimeIterator * allocateRuntimeIterator(struct RuntimeNode *start) {
273 struct RuntimeIterator *thisvar=(struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
274 thisvar->cur = start;
278 inline int RunhasNext(struct RuntimeIterator *thisvar) {
279 return (thisvar->cur!=NULL);
282 inline int Runnext(struct RuntimeIterator *thisvar) {
283 int curr=thisvar->cur->data;
284 thisvar->cur=thisvar->cur->lnext;
288 inline int Runkey(struct RuntimeIterator *thisvar) {
289 return thisvar->cur->key;