1 #include "SimpleHash.h"
4 /* SIMPLE HASH ********************************************************/
5 struct RuntimeIterator* RuntimeHashcreateiterator(struct RuntimeHash * thisvar) {
6 return allocateRuntimeIterator(thisvar->listhead);
9 void RuntimeHashiterator(struct RuntimeHash *thisvar, struct RuntimeIterator * it) {
10 it->cur=thisvar->listhead;
13 struct RuntimeHash * noargallocateRuntimeHash() {
14 return allocateRuntimeHash(100);
17 struct RuntimeHash * allocateRuntimeHash(int size) {
18 struct RuntimeHash *thisvar=(struct RuntimeHash *)RUNMALLOC(sizeof(struct RuntimeHash));
20 printf("Negative Hashtable size Exception\n");
24 thisvar->bucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*size);
25 /* Set allocation blocks*/
26 thisvar->listhead=NULL;
27 thisvar->listtail=NULL;
29 thisvar->numelements = 0;
33 void freeRuntimeHash(struct RuntimeHash *thisvar) {
34 struct RuntimeNode *ptr=thisvar->listhead;
35 RUNFREE(thisvar->bucket);
37 struct RuntimeNode *next=ptr->next;
44 inline int RuntimeHashcountset(struct RuntimeHash * thisvar) {
45 return thisvar->numelements;
48 int RuntimeHashfirstkey(struct RuntimeHash *thisvar) {
49 struct RuntimeNode *ptr=thisvar->listhead;
53 int RuntimeHashremove(struct RuntimeHash *thisvar, int key, int data) {
54 unsigned int hashkey = (unsigned int)key % thisvar->size;
56 struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
60 if ((*ptr)->key == key && (*ptr)->data == data) {
61 struct RuntimeNode *toremove=*ptr;
64 if (toremove->lprev!=NULL)
65 toremove->lprev->lnext=toremove->lnext;
67 thisvar->listhead=toremove->lnext;
68 if (toremove->lnext!=NULL)
69 toremove->lnext->lprev=toremove->lprev;
71 thisvar->listtail=toremove->lprev;
74 thisvar->numelements--;
77 ptr = &((*ptr)->next);
83 int RuntimeHashadd(struct RuntimeHash * thisvar,int key, int data) {
86 struct RuntimeNode **ptr;
88 if (thisvar->numelements>=thisvar->size) {
89 int newsize=2*thisvar->size+1;
90 struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
92 for(i=thisvar->size-1;i>=0;i--) {
93 struct RuntimeNode *ptr;
94 for(ptr=thisvar->bucket[i];ptr!=NULL;) {
95 struct RuntimeNode * nextptr=ptr->next;
96 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
97 ptr->next=newbucket[newhashkey];
98 newbucket[newhashkey]=ptr;
102 thisvar->size=newsize;
103 RUNFREE(thisvar->bucket);
104 thisvar->bucket=newbucket;
107 hashkey = (unsigned int)key % thisvar->size;
108 ptr = &thisvar->bucket[hashkey];
110 /* check that thisvar key/object pair isn't already here */
111 /* TBD can be optimized for set v. relation */
114 if ((*ptr)->key == key && (*ptr)->data == data) {
117 ptr = &((*ptr)->next);
121 struct RuntimeNode *node=RUNMALLOC(sizeof(struct RuntimeNode));
126 if (thisvar->listhead==NULL) {
127 thisvar->listhead=node;
128 thisvar->listtail=node;
133 node->lnext=thisvar->listhead;
134 thisvar->listhead->lprev=node;
135 thisvar->listhead=node;
139 thisvar->numelements++;
143 bool RuntimeHashcontainskey(struct RuntimeHash *thisvar,int key) {
144 unsigned int hashkey = (unsigned int)key % thisvar->size;
146 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
148 if (ptr->key == key) {
149 /* we already have thisvar object
150 stored in the hash so just return */
158 bool RuntimeHashcontainskeydata(struct RuntimeHash *thisvar, int key, int data) {
159 unsigned int hashkey = (unsigned int)key % thisvar->size;
161 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
163 if (ptr->key == key && ptr->data == data) {
164 /* we already have thisvar object
165 stored in the hash so just return*/
173 int RuntimeHashcount(struct RuntimeHash *thisvar,int key) {
174 unsigned int hashkey = (unsigned int)key % thisvar->size;
177 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
179 if (ptr->key == key) {
187 struct RuntimeHash * RuntimeHashimageSet(struct RuntimeHash *thisvar, int key) {
188 struct RuntimeHash * newset=allocateRuntimeHash(2*RuntimeHashcount(thisvar,key)+4);
189 unsigned int hashkey = (unsigned int)key % thisvar->size;
191 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
193 if (ptr->key == key) {
194 RuntimeHashadd(newset,ptr->data,ptr->data);
201 int RuntimeHashget(struct RuntimeHash *thisvar, int key, int *data) {
202 unsigned int hashkey = (unsigned int)key % thisvar->size;
204 struct RuntimeNode *ptr = thisvar->bucket[hashkey];
206 if (ptr->key == key) {
208 return 1; /* success */
213 return 0; /* failure */
216 inline struct RuntimeIterator * noargallocateRuntimeIterator() {
217 return (struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
220 inline struct RuntimeIterator * allocateRuntimeIterator(struct RuntimeNode *start) {
221 struct RuntimeIterator *thisvar=(struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
222 thisvar->cur = start;
226 inline int RunhasNext(struct RuntimeIterator *thisvar) {
227 return (thisvar->cur!=NULL);
230 inline int Runnext(struct RuntimeIterator *thisvar) {
231 int curr=thisvar->cur->data;
232 thisvar->cur=thisvar->cur->next;
235 inline int Runkey(struct RuntimeIterator *thisvar) {
236 return thisvar->cur->key;