1 #include "SimpleHash.h"
4 /* LINKED HASH NODE ****************************************************/
6 struct LinkedHashNode * allocateLinkedHashNode(int key, int data, struct LinkedHashNode *next) {
7 struct LinkedHashNode *thisvar=(struct LinkedHashNode *)malloc(sizeof(struct LinkedHashNode));
16 struct LinkedHashNode * noargallocateLinkedHashNode() {
17 struct LinkedHashNode *thisvar=(struct LinkedHashNode *)malloc(sizeof(struct LinkedHashNode));
26 /* SIMPLE LIST ****************************************************/
28 struct SimpleList * allocateSimpleList() {
29 struct SimpleList *thisvar=(struct SimpleList *)malloc(sizeof(struct SimpleList));
31 thisvar->head.next = 0;
35 void SimpleListreset(struct SimpleList *thisvar) {
36 thisvar->ptr = &thisvar->head;
39 int SimpleListhasMoreElements(struct SimpleList *thisvar) {
40 return (thisvar->ptr->next != 0);
43 int SimpleListnextElement(struct SimpleList *thisvar) {
44 thisvar->ptr = thisvar->ptr->next;
45 return thisvar->ptr->data;
48 void SimpleListadd(struct SimpleList *thisvar,int data) {
49 struct LinkedHashNode *cur = &thisvar->head;
52 if (cur->data == data) {
53 return; /* no duplicates */
56 cur->next = allocateLinkedHashNode(0, data, 0);
60 int SimpleListcontains(struct SimpleList *thisvar,int data) {
61 struct LinkedHashNode *cur = &thisvar->head;
64 if (cur->data == data) {
65 return 1; /* found! */
71 /* WORK LIST ****************************************************/
73 struct WorkList * allocateWorkList() {
74 struct WorkList *thisvar=(struct WorkList *)malloc(sizeof(struct WorkList));
75 thisvar->head=(struct ListNode *) malloc(sizeof(struct ListNode));
76 thisvar->tail=thisvar->head;
77 thisvar->head->next=0;
78 thisvar->headoffset=0;
79 thisvar->tailoffset=0;
83 void WorkListreset(struct WorkList *thisvar) {
84 thisvar->head=thisvar->tail;
85 thisvar->headoffset=0;
86 thisvar->tailoffset=0;
89 int WorkListhasMoreElements(struct WorkList *thisvar) {
90 return ((thisvar->head!=thisvar->tail)||(thisvar->headoffset!=thisvar->tailoffset));
93 int WorkListgetid(struct WorkList *thisvar) {
94 return thisvar->tail->data[thisvar->tailoffset];
97 int WorkListgettype(struct WorkList *thisvar) {
98 return thisvar->tail->data[thisvar->tailoffset+1];
101 int WorkListgetlvalue(struct WorkList *thisvar) {
102 return thisvar->tail->data[thisvar->tailoffset+2];
105 int WorkListgetrvalue(struct WorkList *thisvar) {
106 return thisvar->tail->data[thisvar->tailoffset+3];
109 void freeWorkList(struct WorkList *thisvar) {
110 struct ListNode *ptr=thisvar->tail;
112 struct ListNode *oldptr=ptr;
119 void WorkListpop(struct WorkList *thisvar) {
120 int newoffset=thisvar->tailoffset+4;
121 struct ListNode *ptr=thisvar->tail;
122 if (newoffset>=WLISTSIZE) {
123 if (newoffset!=WLISTSIZE||thisvar->head!=thisvar->tail) {
124 struct ListNode *oldptr=ptr;
125 newoffset-=WLISTSIZE;
131 thisvar->tailoffset=newoffset;
134 void WorkListadd(struct WorkList *thisvar, int id,int type, int lvalue, int rvalue) {
135 if (thisvar->headoffset==WLISTSIZE) {
136 if (thisvar->head->next==0) {
137 thisvar->head->next=(struct ListNode *)malloc(sizeof(struct ListNode));
138 thisvar->head->next->next=0;
140 thisvar->headoffset=0;
141 thisvar->head=thisvar->head->next;
142 if (thisvar->tailoffset==WLISTSIZE) { /* roll the tail over also */
143 thisvar->tailoffset=0;
144 thisvar->tail=thisvar->tail->next;
147 thisvar->head->data[thisvar->headoffset++]=id;
148 thisvar->head->data[thisvar->headoffset++]=type;
149 thisvar->head->data[thisvar->headoffset++]=lvalue;
150 thisvar->head->data[thisvar->headoffset++]=rvalue;
153 /* SIMPLE HASH ********************************************************/
154 struct SimpleIterator* SimpleHashcreateiterator(struct SimpleHash * thisvar) {
155 return allocateSimpleIterator(thisvar->listhead,thisvar->listtail,thisvar->tailindex/*,thisvar*/);
158 void SimpleHashiterator(struct SimpleHash *thisvar, struct SimpleIterator * it) {
159 it->cur=thisvar->listhead;
161 it->tailindex=thisvar->tailindex;
162 it->tail=thisvar->listtail;
165 struct SimpleHash * noargallocateSimpleHash() {
166 return allocateSimpleHash(100);
169 struct SimpleHash * allocateSimpleHash(int size) {
170 struct SimpleHash *thisvar=(struct SimpleHash *)malloc(sizeof(struct SimpleHash));
172 printf("Negative Hashtable size Exception\n");
175 thisvar->size = size;
176 thisvar->bucket = (struct SimpleNode **) calloc(sizeof(struct SimpleNode *)*size,1);
177 /* Set allocation blocks*/
178 thisvar->listhead=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
179 thisvar->listtail=thisvar->listhead;
180 thisvar->tailindex=0;
182 thisvar->numparents = 0;
183 thisvar->numchildren = 0;
184 thisvar->numelements = 0;
188 void freeSimpleHash(struct SimpleHash *thisvar) {
189 struct ArraySimple *ptr=thisvar->listhead;
190 free(thisvar->bucket);
192 struct ArraySimple *next=ptr->nextarray;
199 inline int SimpleHashcountset(struct SimpleHash * thisvar) {
200 return thisvar->numelements;
203 int SimpleHashfirstkey(struct SimpleHash *thisvar) {
204 struct ArraySimple *ptr=thisvar->listhead;
206 while((index==ARRAYSIZE)||!ptr->nodes[index].inuse) {
207 if (index==ARRAYSIZE) {
213 return ptr->nodes[index].key;
216 void SimpleHashaddParent(struct SimpleHash *thisvar,struct SimpleHash* parent) {
217 thisvar->parents[thisvar->numparents++] = parent;
218 SimpleHashaddChild(parent,thisvar);
221 void SimpleHashaddChild(struct SimpleHash *thisvar, struct SimpleHash *child) {
222 thisvar->children[thisvar->numchildren++]=child;
225 int SimpleHashremove(struct SimpleHash *thisvar, int key, int data) {
226 unsigned int hashkey = (unsigned int)key % thisvar->size;
228 struct SimpleNode **ptr = &thisvar->bucket[hashkey];
230 for (i = 0; i < thisvar->numchildren; i++) {
231 SimpleHashremove(thisvar->children[i], key, data);
235 if ((*ptr)->key == key && (*ptr)->data == data) {
236 struct SimpleNode *toremove=*ptr;
239 toremove->inuse=0; /* Marked as unused */
241 thisvar->numelements--;
244 ptr = &((*ptr)->next);
250 void SimpleHashaddAll(struct SimpleHash *thisvar, struct SimpleHash * set) {
251 struct SimpleIterator it;
252 SimpleHashiterator(set, &it);
253 while(hasNext(&it)) {
256 SimpleHashadd(thisvar,keyv,data);
260 int SimpleHashadd(struct SimpleHash * thisvar,int key, int data) {
262 unsigned int hashkey;
263 struct SimpleNode **ptr;
265 if (thisvar->numelements>=thisvar->size) {
266 int newsize=2*thisvar->size+1;
267 struct SimpleNode ** newbucket = (struct SimpleNode **) calloc(sizeof(struct SimpleNode *)*newsize,1);
269 for(i=thisvar->size-1;i>=0;i--) {
270 struct SimpleNode *ptr;
271 for(ptr=thisvar->bucket[i];ptr!=NULL;) {
272 struct SimpleNode * nextptr=ptr->next;
273 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
274 ptr->next=newbucket[newhashkey];
275 newbucket[newhashkey]=ptr;
279 thisvar->size=newsize;
280 free(thisvar->bucket);
281 thisvar->bucket=newbucket;
284 hashkey = (unsigned int)key % thisvar->size;
285 ptr = &thisvar->bucket[hashkey];
287 /* check that thisvar key/object pair isn't already here */
288 /* TBD can be optimized for set v. relation */
291 if ((*ptr)->key == key && (*ptr)->data == data) {
294 ptr = &((*ptr)->next);
296 if (thisvar->tailindex==ARRAYSIZE) {
297 thisvar->listtail->nextarray=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
298 thisvar->tailindex=0;
299 thisvar->listtail=thisvar->listtail->nextarray;
302 *ptr = &thisvar->listtail->nodes[thisvar->tailindex++];
307 thisvar->numelements++;
310 for (i = 0; i < thisvar->numparents; i++) {
311 SimpleHashadd(thisvar->parents[i], key, data);
317 bool SimpleHashcontainskey(struct SimpleHash *thisvar,int key) {
318 unsigned int hashkey = (unsigned int)key % thisvar->size;
320 struct SimpleNode *ptr = thisvar->bucket[hashkey];
322 if (ptr->key == key) {
323 /* we already have thisvar object
324 stored in the hash so just return */
332 bool SimpleHashcontainskeydata(struct SimpleHash *thisvar, int key, int data) {
333 unsigned int hashkey = (unsigned int)key % thisvar->size;
335 struct SimpleNode *ptr = thisvar->bucket[hashkey];
337 if (ptr->key == key && ptr->data == data) {
338 /* we already have thisvar object
339 stored in the hash so just return*/
347 int SimpleHashcount(struct SimpleHash *thisvar,int key) {
348 unsigned int hashkey = (unsigned int)key % thisvar->size;
351 struct SimpleNode *ptr = thisvar->bucket[hashkey];
353 if (ptr->key == key) {
361 struct SimpleHash * SimpleHashimageSet(struct SimpleHash *thisvar, int key) {
362 struct SimpleHash * newset=allocateSimpleHash(2*SimpleHashcount(thisvar,key)+4);
363 unsigned int hashkey = (unsigned int)key % thisvar->size;
365 struct SimpleNode *ptr = thisvar->bucket[hashkey];
367 if (ptr->key == key) {
368 SimpleHashadd(newset,ptr->data,ptr->data);
375 int SimpleHashget(struct SimpleHash *thisvar, int key, int *data) {
376 unsigned int hashkey = (unsigned int)key % thisvar->size;
378 struct SimpleNode *ptr = thisvar->bucket[hashkey];
380 if (ptr->key == key) {
382 return 1; /* success */
387 return 0; /* failure */
390 int SimpleHashcountdata(struct SimpleHash *thisvar,int data) {
392 struct ArraySimple *ptr = thisvar->listhead;
394 if (ptr->nextarray) {
396 for(i=0;i<ARRAYSIZE;i++)
397 if (ptr->nodes[i].data == data
398 &&ptr->nodes[i].inuse) {
403 for(i=0;i<thisvar->tailindex;i++)
404 if (ptr->nodes[i].data == data
405 &&ptr->nodes[i].inuse) {
409 ptr = ptr->nextarray;
414 struct RepairHashNode * allocateRepairHashNode(int setrelation, int rule, int lvalue, int rvalue, int data, int data2, int ismodify){
415 struct RepairHashNode * thisvar=(struct RepairHashNode *)malloc(sizeof(struct RepairHashNode));
416 thisvar->setrelation = setrelation;
417 thisvar->lvalue=lvalue;
418 thisvar->rvalue=rvalue;
419 thisvar->data = data;
420 thisvar->data2 = data2;
424 thisvar->ismodify=ismodify;
428 struct RepairHash * allocateRepairHash(int size) {
429 struct RepairHash *thisvar=(struct RepairHash*)malloc(sizeof(struct RepairHash));
431 printf("Negative size for RepairHash\n");
435 thisvar->size = size;
436 thisvar->bucket = (struct RepairHashNode **) calloc(1,sizeof(struct RepairHashNode*)*size);
438 thisvar->numelements = 0;
442 #define REPAIRSIZE 100
443 struct RepairHash * noargallocateRepairHash() {
444 return allocateRepairHash(REPAIRSIZE);
447 void freeRepairHash(struct RepairHash *thisvar) {
448 struct RepairHashNode *ptr=thisvar->nodelist;
449 free(thisvar->bucket);
451 struct RepairHashNode *next=ptr->lnext;
458 #define SETFLAG (1<<31)
460 int RepairHashaddset(struct RepairHash *thisvar, int setv, int rule, int value, int data) {
461 return RepairHashaddrelation(thisvar, setv||SETFLAG, rule, value,0,data);
464 int RepairHashaddrelation(struct RepairHash *thisvar, int relation, int rule, int lvalue, int rvalue, int data) {
465 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
467 struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
469 /* check that thisvar key/object pair isn't already here */
470 /* TBD can be optimized for set v. relation */
472 if ((*ptr)->setrelation == relation &&
473 (*ptr)->rule==rule &&
474 (*ptr)->lvalue==lvalue &&
475 (*ptr)->rvalue==rvalue &&
476 (*ptr)->data == data&&
477 (*ptr)->data2 == 0) {
480 ptr = &((*ptr)->next);
483 *ptr = allocateRepairHashNode(relation,rule,lvalue,rvalue, data,0,0);
484 (*ptr)->lnext=thisvar->nodelist;
485 thisvar->nodelist=*ptr;
486 thisvar->numelements++;
490 int RepairHashaddrelation2(struct RepairHash *thisvar, int relation, int rule, int lvalue, int rvalue, int data, int data2) {
491 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
493 struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
495 /* check that thisvar key/object pair isn't already here */
496 /* TBD can be optimized for set v. relation */
498 if ((*ptr)->setrelation == relation &&
499 (*ptr)->rule==rule &&
500 (*ptr)->lvalue==lvalue &&
501 (*ptr)->rvalue==rvalue &&
502 (*ptr)->data == data &&
503 (*ptr)->data2 == data2) {
506 ptr = &((*ptr)->next);
509 *ptr = allocateRepairHashNode(relation,rule,lvalue,rvalue, data,data2,1);
510 (*ptr)->lnext=thisvar->nodelist;
511 thisvar->nodelist=*ptr;
512 thisvar->numelements++;
516 bool RepairHashcontainsset(struct RepairHash *thisvar, int setv, int rule, int value) {
517 return RepairHashcontainsrelation(thisvar, setv||SETFLAG, rule, value,0);
520 bool RepairHashcontainsrelation(struct RepairHash *thisvar, int relation, int rule, int lvalue, int rvalue) {
521 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
523 struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
525 /* check that thisvar key/object pair isn't already here */
526 /* TBD can be optimized for set v. relation */
528 if ((*ptr)->setrelation == relation &&
529 (*ptr)->rule==rule &&
530 (*ptr)->lvalue==lvalue &&
531 (*ptr)->rvalue==rvalue) {
534 ptr = &((*ptr)->next);
539 int RepairHashgetset(struct RepairHash *thisvar, int setv, int rule, int value) {
540 return RepairHashgetrelation(thisvar, setv||SETFLAG, rule, value,0);
543 int RepairHashismodify(struct RepairHash *thisvar, int relation, int rule, int lvalue,int rvalue) {
544 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
546 struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
548 /* check that thisvar key/object pair isn't already here */
549 /* TBD can be optimized for set v. relation */
551 if ((*ptr)->setrelation == relation &&
552 (*ptr)->rule==rule &&
553 (*ptr)->lvalue==lvalue &&
554 (*ptr)->rvalue==rvalue) {
555 return (*ptr)->ismodify;
557 ptr = &((*ptr)->next);
562 int RepairHashgetrelation2(struct RepairHash *thisvar, int relation, int rule, int lvalue,int rvalue) {
563 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
565 struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
567 /* check that thisvar key/object pair isn't already here */
568 /* TBD can be optimized for set v. relation */
570 if ((*ptr)->setrelation == relation &&
571 (*ptr)->rule==rule &&
572 (*ptr)->lvalue==lvalue &&
573 (*ptr)->rvalue==rvalue) {
574 return (*ptr)->data2;
576 ptr = &((*ptr)->next);
581 int RepairHashgetrelation(struct RepairHash *thisvar, int relation, int rule, int lvalue,int rvalue) {
582 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
584 struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
586 /* check that this key/object pair isn't already here */
587 /* TBD can be optimized for set v. relation */
589 if ((*ptr)->setrelation == relation &&
590 (*ptr)->rule==rule &&
591 (*ptr)->lvalue==lvalue &&
592 (*ptr)->rvalue==rvalue) {
595 ptr = &((*ptr)->next);
600 inline struct SimpleIterator * noargallocateSimpleIterator() {
601 return (struct SimpleIterator*)malloc(sizeof(struct SimpleIterator));
604 inline struct SimpleIterator * allocateSimpleIterator(struct ArraySimple *start, struct ArraySimple *tl, int tlindex) {
605 struct SimpleIterator *thisvar=(struct SimpleIterator*)malloc(sizeof(struct SimpleIterator));
606 thisvar->cur = start;
608 thisvar->tailindex=tlindex;
613 inline int hasNext(struct SimpleIterator *thisvar) {
614 if (thisvar->cur==thisvar->tail &&
615 thisvar->index==thisvar->tailindex)
617 while((thisvar->index==ARRAYSIZE)||!thisvar->cur->nodes[thisvar->index].inuse) {
618 if (thisvar->index==ARRAYSIZE) {
620 thisvar->cur=thisvar->cur->nextarray;
624 if (thisvar->cur->nodes[thisvar->index].inuse)
630 inline int next(struct SimpleIterator *thisvar) {
631 return thisvar->cur->nodes[thisvar->index++].data;
634 inline int key(struct SimpleIterator *thisvar) {
635 return thisvar->cur->nodes[thisvar->index].key;