1 #include "SimpleHash.h"
4 /* SIMPLE HASH ********************************************************/
5 struct SimpleIterator* SimpleHashcreateiterator(struct SimpleHash * thisvar) {
6 return allocateSimpleIterator(thisvar->listhead,thisvar->listtail,thisvar->tailindex/*,thisvar*/);
9 void SimpleHashiterator(struct SimpleHash *thisvar, struct SimpleIterator * it) {
10 it->cur=thisvar->listhead;
12 it->tailindex=thisvar->tailindex;
13 it->tail=thisvar->listtail;
16 struct SimpleHash * noargallocateSimpleHash() {
17 return allocateSimpleHash(100);
20 struct SimpleHash * allocateSimpleHash(int size) {
21 struct SimpleHash *thisvar=(struct SimpleHash *)RUNMALLOC(sizeof(struct SimpleHash));
23 printf("Negative Hashtable size Exception\n");
27 thisvar->bucket = (struct SimpleNode **) RUNMALLOC(sizeof(struct SimpleNode *)*size);
28 /* Set allocation blocks*/
29 thisvar->listhead=(struct ArraySimple *) RUNMALLOC(sizeof(struct ArraySimple));
30 thisvar->listtail=thisvar->listhead;
33 thisvar->numelements = 0;
37 void freeSimpleHash(struct SimpleHash *thisvar) {
38 struct ArraySimple *ptr=thisvar->listhead;
39 RUNFREE(thisvar->bucket);
41 struct ArraySimple *next=ptr->nextarray;
48 inline int SimpleHashcountset(struct SimpleHash * thisvar) {
49 return thisvar->numelements;
52 int SimpleHashfirstkey(struct SimpleHash *thisvar) {
53 struct ArraySimple *ptr=thisvar->listhead;
55 while((index==ARRAYSIZE)||!ptr->nodes[index].inuse) {
56 if (index==ARRAYSIZE) {
62 return ptr->nodes[index].key;
65 int SimpleHashremove(struct SimpleHash *thisvar, int key, int data) {
66 unsigned int hashkey = (unsigned int)key % thisvar->size;
68 struct SimpleNode **ptr = &thisvar->bucket[hashkey];
72 if ((*ptr)->key == key && (*ptr)->data == data) {
73 struct SimpleNode *toremove=*ptr;
76 toremove->inuse=0; /* Marked as unused */
78 thisvar->numelements--;
81 ptr = &((*ptr)->next);
87 void SimpleHashaddAll(struct SimpleHash *thisvar, struct SimpleHash * set) {
88 struct SimpleIterator it;
89 SimpleHashiterator(set, &it);
93 SimpleHashadd(thisvar,keyv,data);
97 int SimpleHashadd(struct SimpleHash * thisvar,int key, int data) {
100 struct SimpleNode **ptr;
102 if (thisvar->numelements>=thisvar->size) {
103 int newsize=2*thisvar->size+1;
104 struct SimpleNode ** newbucket = (struct SimpleNode **) RUNMALLOC(sizeof(struct SimpleNode *)*newsize);
106 for(i=thisvar->size-1;i>=0;i--) {
107 struct SimpleNode *ptr;
108 for(ptr=thisvar->bucket[i];ptr!=NULL;) {
109 struct SimpleNode * 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 ArraySimple *) RUNMALLOC(sizeof(struct ArraySimple));
135 thisvar->tailindex=0;
136 thisvar->listtail=thisvar->listtail->nextarray;
139 *ptr = &thisvar->listtail->nodes[thisvar->tailindex++];
144 thisvar->numelements++;
148 bool SimpleHashcontainskey(struct SimpleHash *thisvar,int key) {
149 unsigned int hashkey = (unsigned int)key % thisvar->size;
151 struct SimpleNode *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 SimpleHashcontainskeydata(struct SimpleHash *thisvar, int key, int data) {
164 unsigned int hashkey = (unsigned int)key % thisvar->size;
166 struct SimpleNode *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 SimpleHashcount(struct SimpleHash *thisvar,int key) {
179 unsigned int hashkey = (unsigned int)key % thisvar->size;
182 struct SimpleNode *ptr = thisvar->bucket[hashkey];
184 if (ptr->key == key) {
192 struct SimpleHash * SimpleHashimageSet(struct SimpleHash *thisvar, int key) {
193 struct SimpleHash * newset=allocateSimpleHash(2*SimpleHashcount(thisvar,key)+4);
194 unsigned int hashkey = (unsigned int)key % thisvar->size;
196 struct SimpleNode *ptr = thisvar->bucket[hashkey];
198 if (ptr->key == key) {
199 SimpleHashadd(newset,ptr->data,ptr->data);
206 int SimpleHashget(struct SimpleHash *thisvar, int key, int *data) {
207 unsigned int hashkey = (unsigned int)key % thisvar->size;
209 struct SimpleNode *ptr = thisvar->bucket[hashkey];
211 if (ptr->key == key) {
213 return 1; /* success */
218 return 0; /* failure */
221 int SimpleHashcountdata(struct SimpleHash *thisvar,int data) {
223 struct ArraySimple *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 SimpleIterator * noargallocateSimpleIterator() {
246 return (struct SimpleIterator*)RUNMALLOC(sizeof(struct SimpleIterator));
249 inline struct SimpleIterator * allocateSimpleIterator(struct ArraySimple *start, struct ArraySimple *tl, int tlindex) {
250 struct SimpleIterator *thisvar=(struct SimpleIterator*)RUNMALLOC(sizeof(struct SimpleIterator));
251 thisvar->cur = start;
253 thisvar->tailindex=tlindex;
258 inline int hasNext(struct SimpleIterator *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 next(struct SimpleIterator *thisvar) {
276 return thisvar->cur->nodes[thisvar->index++].data;
279 inline int key(struct SimpleIterator *thisvar) {
280 return thisvar->cur->nodes[thisvar->index].key;