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* createiterator(struct SimpleHash * thisvar) {
155 return allocateSimpleIterator(thisvar->listhead,thisvar->listtail,thisvar->tailindex/*,thisvar*/);
158 void iterator(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 int SimpleHashfirstkey(struct SimpleHash *thisvar) {
200 struct ArraySimple *ptr=thisvar->listhead;
202 while((index==ARRAYSIZE)||!ptr->nodes[index].inuse) {
203 if (index==ARRAYSIZE) {
209 return ptr->nodes[index].key;
212 void SimpleHashaddParent(struct SimpleHash *thisvar,struct SimpleHash* parent) {
213 thisvar->parents[thisvar->numparents++] = parent;
214 SimpleHashaddChild(parent,thisvar);
217 void SimpleHashaddChild(struct SimpleHash *thisvar, struct SimpleHash *child) {
218 thisvar->children[thisvar->numchildren++]=child;
221 int SimpleHashremove(struct SimpleHash *thisvar, int key, int data) {
222 unsigned int hashkey = (unsigned int)key % thisvar->size;
224 struct SimpleNode **ptr = &thisvar->bucket[hashkey];
226 for (i = 0; i < thisvar->numchildren; i++) {
227 SimpleHashremove(thisvar->children[i], key, data);
231 if ((*ptr)->key == key && (*ptr)->data == data) {
232 struct SimpleNode *toremove=*ptr;
235 toremove->inuse=0; /* Marked as unused */
237 thisvar->numelements--;
240 ptr = &((*ptr)->next);
246 void SimpleHashaddAll(struct SimpleHash *thisvar, struct SimpleHash * set) {
247 struct SimpleIterator it;
248 SimpleHashiterator(set, &it);
249 while(hasNext(&it)) {
252 SimpleHashadd(thisvar,keyv,data);
256 int SimpleHashadd(struct SimpleHash * thisvar,int key, int data) {
258 unsigned int hashkey;
259 struct SimpleNode **ptr;
261 if (thisvar->numelements>=thisvar->size) {
262 int newsize=2*thisvar->size+1;
263 struct SimpleNode ** newbucket = (struct SimpleNode **) calloc(sizeof(struct SimpleNode *)*newsize,1);
265 for(i=thisvar->size-1;i>=0;i--) {
266 struct SimpleNode *ptr;
267 for(ptr=thisvar->bucket[i];ptr!=NULL;) {
268 struct SimpleNode * nextptr=ptr->next;
269 unsigned int newhashkey=(unsigned int)ptr->key % newsize;
270 ptr->next=newbucket[newhashkey];
271 newbucket[newhashkey]=ptr;
275 thisvar->size=newsize;
276 free(thisvar->bucket);
277 thisvar->bucket=newbucket;
280 hashkey = (unsigned int)key % thisvar->size;
281 ptr = &thisvar->bucket[hashkey];
283 /* check that thisvar key/object pair isn't already here */
284 /* TBD can be optimized for set v. relation */
287 if ((*ptr)->key == key && (*ptr)->data == data) {
290 ptr = &((*ptr)->next);
292 if (thisvar->tailindex==ARRAYSIZE) {
293 thisvar->listtail->nextarray=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
294 thisvar->tailindex=0;
295 thisvar->listtail=thisvar->listtail->nextarray;
298 *ptr = &thisvar->listtail->nodes[thisvar->tailindex++];
303 thisvar->numelements++;
306 for (i = 0; i < thisvar->numparents; i++) {
307 SimpleHashadd(thisvar->parents[i], key, data);
313 bool SimpleHashcontainskey(struct SimpleHash *thisvar,int key) {
314 unsigned int hashkey = (unsigned int)key % thisvar->size;
316 struct SimpleNode *ptr = thisvar->bucket[hashkey];
318 if (ptr->key == key) {
319 /* we already have thisvar object
320 stored in the hash so just return */
328 bool SimpleHashcontainskeydata(struct SimpleHash *thisvar, int key, int data) {
329 unsigned int hashkey = (unsigned int)key % thisvar->size;
331 struct SimpleNode *ptr = thisvar->bucket[hashkey];
333 if (ptr->key == key && ptr->data == data) {
334 /* we already have thisvar object
335 stored in the hash so just return*/
343 int SimpleHashcount(struct SimpleHash *thisvar,int key) {
344 unsigned int hashkey = (unsigned int)key % thisvar->size;
347 struct SimpleNode *ptr = thisvar->bucket[hashkey];
349 if (ptr->key == key) {
357 struct SimpleHash * SimpleHashimageSet(struct SimpleHash *thisvar, int key) {
358 struct SimpleHash * newset=allocateSimpleHash(2*SimpleHashcount(thisvar,key)+4);
359 unsigned int hashkey = (unsigned int)key % thisvar->size;
361 struct SimpleNode *ptr = thisvar->bucket[hashkey];
363 if (ptr->key == key) {
364 SimpleHashadd(newset,ptr->data,ptr->data);
371 int SimpleHashget(struct SimpleHash *thisvar, int key, int *data) {
372 unsigned int hashkey = (unsigned int)key % thisvar->size;
374 struct SimpleNode *ptr = thisvar->bucket[hashkey];
376 if (ptr->key == key) {
378 return 1; /* success */
383 return 0; /* failure */
386 int SimpleHashcountdata(struct SimpleHash *thisvar,int data) {
388 struct ArraySimple *ptr = thisvar->listhead;
390 if (ptr->nextarray) {
392 for(i=0;i<ARRAYSIZE;i++)
393 if (ptr->nodes[i].data == data
394 &&ptr->nodes[i].inuse) {
399 for(i=0;i<thisvar->tailindex;i++)
400 if (ptr->nodes[i].data == data
401 &&ptr->nodes[i].inuse) {
405 ptr = ptr->nextarray;
410 struct RepairHashNode * allocateRepairHashNode(int setrelation, int rule, int lvalue, int rvalue, int data, int data2, int ismodify){
411 struct RepairHashNode * thisvar=(struct RepairHashNode *)malloc(sizeof(struct RepairHashNode));
412 thisvar->setrelation = setrelation;
413 thisvar->lvalue=lvalue;
414 thisvar->rvalue=rvalue;
415 thisvar->data = data;
416 thisvar->data2 = data2;
420 thisvar->ismodify=ismodify;
424 struct RepairHash * allocateRepairHash(int size) {
425 struct RepairHash *thisvar=(struct RepairHash*)malloc(sizeof(struct RepairHash));
427 printf("Negative size for RepairHash\n");
431 thisvar->size = size;
432 thisvar->bucket = (struct RepairHashNode **) calloc(1,sizeof(struct RepairHashNode*)*size);
434 thisvar->numelements = 0;
438 #define REPAIRSIZE 100
439 struct RepairHash * noargallocateRepairHash() {
440 return allocateRepairHash(REPAIRSIZE);
443 void freeRepairHash(struct RepairHash *thisvar) {
444 struct RepairHashNode *ptr=thisvar->nodelist;
445 free(thisvar->bucket);
447 struct RepairHashNode *next=ptr->lnext;
454 #define SETFLAG (1<<31)
456 int addset(struct RepairHash *thisvar, int setv, int rule, int value, int data) {
457 return addrelation(thisvar, setv||SETFLAG, rule, value,0,data);
460 int addrelation(struct RepairHash *thisvar, int relation, int rule, int lvalue, int rvalue, int data) {
461 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
463 struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
465 /* check that thisvar key/object pair isn't already here */
466 /* TBD can be optimized for set v. relation */
468 if ((*ptr)->setrelation == relation &&
469 (*ptr)->rule==rule &&
470 (*ptr)->lvalue==lvalue &&
471 (*ptr)->rvalue==rvalue &&
472 (*ptr)->data == data&&
473 (*ptr)->data2 == 0) {
476 ptr = &((*ptr)->next);
479 *ptr = allocateRepairHashNode(relation,rule,lvalue,rvalue, data,0,0);
480 (*ptr)->lnext=thisvar->nodelist;
481 thisvar->nodelist=*ptr;
482 thisvar->numelements++;
486 int addrelation2(struct RepairHash *thisvar, int relation, int rule, int lvalue, int rvalue, int data, int data2) {
487 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
489 struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
491 /* check that thisvar key/object pair isn't already here */
492 /* TBD can be optimized for set v. relation */
494 if ((*ptr)->setrelation == relation &&
495 (*ptr)->rule==rule &&
496 (*ptr)->lvalue==lvalue &&
497 (*ptr)->rvalue==rvalue &&
498 (*ptr)->data == data &&
499 (*ptr)->data2 == data2) {
502 ptr = &((*ptr)->next);
505 *ptr = allocateRepairHashNode(relation,rule,lvalue,rvalue, data,data2,1);
506 (*ptr)->lnext=thisvar->nodelist;
507 thisvar->nodelist=*ptr;
508 thisvar->numelements++;
512 bool containsset(struct RepairHash *thisvar, int setv, int rule, int value) {
513 return containsrelation(thisvar, setv||SETFLAG, rule, value,0);
516 bool containsrelation(struct RepairHash *thisvar, int relation, int rule, int lvalue, int rvalue) {
517 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
519 struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
521 /* check that thisvar key/object pair isn't already here */
522 /* TBD can be optimized for set v. relation */
524 if ((*ptr)->setrelation == relation &&
525 (*ptr)->rule==rule &&
526 (*ptr)->lvalue==lvalue &&
527 (*ptr)->rvalue==rvalue) {
530 ptr = &((*ptr)->next);
535 int getset(struct RepairHash *thisvar, int setv, int rule, int value) {
536 return getrelation(thisvar, setv||SETFLAG, rule, value,0);
539 int ismodify(struct RepairHash *thisvar, int relation, int rule, int lvalue,int rvalue) {
540 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
542 struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
544 /* check that thisvar key/object pair isn't already here */
545 /* TBD can be optimized for set v. relation */
547 if ((*ptr)->setrelation == relation &&
548 (*ptr)->rule==rule &&
549 (*ptr)->lvalue==lvalue &&
550 (*ptr)->rvalue==rvalue) {
551 return (*ptr)->ismodify;
553 ptr = &((*ptr)->next);
558 int getrelation2(struct RepairHash *thisvar, int relation, int rule, int lvalue,int rvalue) {
559 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
561 struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
563 /* check that thisvar key/object pair isn't already here */
564 /* TBD can be optimized for set v. relation */
566 if ((*ptr)->setrelation == relation &&
567 (*ptr)->rule==rule &&
568 (*ptr)->lvalue==lvalue &&
569 (*ptr)->rvalue==rvalue) {
570 return (*ptr)->data2;
572 ptr = &((*ptr)->next);
577 int getrelation(struct RepairHash *thisvar, int relation, int rule, int lvalue,int rvalue) {
578 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
580 struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
582 /* check that this key/object pair isn't already here */
583 /* TBD can be optimized for set v. relation */
585 if ((*ptr)->setrelation == relation &&
586 (*ptr)->rule==rule &&
587 (*ptr)->lvalue==lvalue &&
588 (*ptr)->rvalue==rvalue) {
591 ptr = &((*ptr)->next);