1 #include "SimpleHash.h"
4 /* SIMPLE HASH ********************************************************/
5 struct RuntimeIterator* RuntimeHashcreateiterator(struct RuntimeHash * thisvar) {
6 return allocateRuntimeIterator(thisvar->listhead,thisvar->listtail,thisvar->tailindex/*,thisvar*/);
9 void RuntimeHashiterator(struct RuntimeHash *thisvar, struct RuntimeIterator * it) {
10 it->cur=thisvar->listhead;
12 it->tailindex=thisvar->tailindex;
13 it->tail=thisvar->listtail;
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=(struct ArrayRuntime *) RUNMALLOC(sizeof(struct ArrayRuntime));
30 thisvar->listtail=thisvar->listhead;
33 thisvar->numelements = 0;
37 void freeRuntimeHash(struct RuntimeHash *thisvar) {
38 struct ArrayRuntime *ptr=thisvar->listhead;
39 RUNFREE(thisvar->bucket);
41 struct ArrayRuntime *next=ptr->nextarray;
48 inline int RuntimeHashcountset(struct RuntimeHash * thisvar) {
49 return thisvar->numelements;
52 int RuntimeHashfirstkey(struct RuntimeHash *thisvar) {
53 struct ArrayRuntime *ptr=thisvar->listhead;
55 while((index==ARRAYSIZE)||!ptr->nodes[index].inuse) {
56 if (index==ARRAYSIZE) {
62 return ptr->nodes[index].key;
65 int RuntimeHashremove(struct RuntimeHash *thisvar, int key, int data) {
66 unsigned int hashkey = (unsigned int)key % thisvar->size;
68 struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
72 if ((*ptr)->key == key && (*ptr)->data == data) {
73 struct RuntimeNode *toremove=*ptr;
76 toremove->inuse=0; /* Marked as unused */
78 thisvar->numelements--;
81 ptr = &((*ptr)->next);
87 void RuntimeHashaddAll(struct RuntimeHash *thisvar, struct RuntimeHash * set) {
88 struct RuntimeIterator it;
89 RuntimeHashiterator(set, &it);
90 while(RunhasNext(&it)) {
92 int data=Runnext(&it);
93 RuntimeHashadd(thisvar,keyv,data);
97 int RuntimeHashadd(struct RuntimeHash * thisvar,int key, int data) {
100 struct RuntimeNode **ptr;
102 if (thisvar->numelements>=thisvar->size) {
103 int newsize=2*thisvar->size+1;
104 struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
106 for(i=thisvar->size-1;i>=0;i--) {
107 struct RuntimeNode *ptr;
108 for(ptr=thisvar->bucket[i];ptr!=NULL;) {
109 struct RuntimeNode * nextptr=ptr->next;
110 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
111 ptr->next=newbucket[newhashkey];
112 newbucket[newhashkey]=ptr;
116 thisvar->size=newsize;
117 RUNFREE(thisvar->bucket);
118 thisvar->bucket=newbucket;
121 hashkey = (unsigned int)key % thisvar->size;
122 ptr = &thisvar->bucket[hashkey];
124 /* check that thisvar key/object pair isn't already here */
125 /* TBD can be optimized for set v. relation */
128 if ((*ptr)->key == key && (*ptr)->data == data) {
131 ptr = &((*ptr)->next);
133 if (thisvar->tailindex==ARRAYSIZE) {
134 thisvar->listtail->nextarray=(struct ArrayRuntime *) RUNMALLOC(sizeof(struct ArrayRuntime));
135 thisvar->tailindex=0;
136 thisvar->listtail=thisvar->listtail->nextarray;
139 *ptr = &thisvar->listtail->nodes[thisvar->tailindex++];
144 thisvar->numelements++;
148 bool RuntimeHashcontainskey(struct RuntimeHash *thisvar,int key) {
149 unsigned int hashkey = (unsigned int)key % thisvar->size;
151 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
153 if (ptr->key == key) {
154 /* we already have thisvar object
155 stored in the hash so just return */
163 bool RuntimeHashcontainskeydata(struct RuntimeHash *thisvar, int key, int data) {
164 unsigned int hashkey = (unsigned int)key % thisvar->size;
166 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
168 if (ptr->key == key && ptr->data == data) {
169 /* we already have thisvar object
170 stored in the hash so just return*/
178 int RuntimeHashcount(struct RuntimeHash *thisvar,int key) {
179 unsigned int hashkey = (unsigned int)key % thisvar->size;
182 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
184 if (ptr->key == key) {
192 struct RuntimeHash * RuntimeHashimageSet(struct RuntimeHash *thisvar, int key) {
193 struct RuntimeHash * newset=allocateRuntimeHash(2*RuntimeHashcount(thisvar,key)+4);
194 unsigned int hashkey = (unsigned int)key % thisvar->size;
196 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
198 if (ptr->key == key) {
199 RuntimeHashadd(newset,ptr->data,ptr->data);
206 int RuntimeHashget(struct RuntimeHash *thisvar, int key, int *data) {
207 unsigned int hashkey = (unsigned int)key % thisvar->size;
209 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
211 if (ptr->key == key) {
213 return 1; /* success */
218 return 0; /* failure */
221 int RuntimeHashcountdata(struct RuntimeHash *thisvar,int data) {
223 struct ArrayRuntime *ptr = thisvar->listhead;
225 if (ptr->nextarray) {
227 for(i=0;i<ARRAYSIZE;i++)
228 if (ptr->nodes[i].data == data
229 &&ptr->nodes[i].inuse) {
234 for(i=0;i<thisvar->tailindex;i++)
235 if (ptr->nodes[i].data == data
236 &&ptr->nodes[i].inuse) {
240 ptr = ptr->nextarray;
245 inline struct RuntimeIterator * noargallocateRuntimeIterator() {
246 return (struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
249 inline struct RuntimeIterator * allocateRuntimeIterator(struct ArrayRuntime *start, struct ArrayRuntime *tl, int tlindex) {
250 struct RuntimeIterator *thisvar=(struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
251 thisvar->cur = start;
253 thisvar->tailindex=tlindex;
258 inline int RunhasNext(struct RuntimeIterator *thisvar) {
259 if (thisvar->cur==thisvar->tail &&
260 thisvar->index==thisvar->tailindex)
262 while((thisvar->index==ARRAYSIZE)||!thisvar->cur->nodes[thisvar->index].inuse) {
263 if (thisvar->index==ARRAYSIZE) {
265 thisvar->cur=thisvar->cur->nextarray;
269 if (thisvar->cur->nodes[thisvar->index].inuse)
275 inline int Runnext(struct RuntimeIterator *thisvar) {
276 return thisvar->cur->nodes[thisvar->index++].data;
279 inline int Runkey(struct RuntimeIterator *thisvar) {
280 return thisvar->cur->nodes[thisvar->index].key;