07f8a12b97511c5eb7f77fdb46f22da89f462592
[repair.git] / Repair / RepairCompiler / MCC / Runtime / SimpleHash.cc
1 #include "SimpleHash.h"
2 #include <stdarg.h>
3 #include <stdlib.h>
4
5 /* LINKED HASH NODE ****************************************************/
6
7 LinkedHashNode::LinkedHashNode(int key, int data, LinkedHashNode *next) {
8     this->key = key;
9     this->data = data;
10     this->next = next;
11     this->lnext=0;
12     this->lprev=0;
13 }
14
15 LinkedHashNode::LinkedHashNode() {
16     this->key = -1;
17     this->data = -1;
18     this->next = 0;
19     this->lnext=0;
20     this->lprev=0;
21 }
22
23 /* SIMPLE LIST ****************************************************/
24
25 SimpleList::SimpleList() {
26     ptr = 0;
27     head.next = 0;
28 }
29
30 void SimpleList::reset() {
31   // ptr = head.next;
32   ptr = &head;
33 }
34
35 int SimpleList::hasMoreElements() {
36   //  return (ptr != 0);
37   return (ptr->next != 0);
38 }
39
40 int SimpleList::nextElement() {
41   ptr = ptr->next;
42   return ptr->data;
43
44   //int data = ptr->data;
45   //ptr = ptr->next;
46   //return data;
47 }
48
49 void SimpleList::add(int data) {
50     LinkedHashNode *cur = &head;
51     while (cur->next) {
52         cur = cur->next;
53         if (cur->data == data) {
54             return; // no duplicates
55         }
56     }
57     cur->next = new LinkedHashNode(0, data, 0);
58     return;
59 }
60
61 int SimpleList::contains(int data) {
62     LinkedHashNode *cur = &head;
63     while (cur->next) {
64         cur = cur->next;
65         if (cur->data == data) {
66             return 1; // found!
67         }
68     }
69     return 0;    
70 }
71
72 /* WORK LIST ****************************************************/
73
74 WorkList::WorkList() {
75   head=(struct ListNode *) malloc(sizeof(struct ListNode));
76   tail=head;
77   head->next=0;
78   headoffset=0;
79   tailoffset=0;
80 }
81
82 void WorkList::reset() {
83   head=tail;
84   headoffset=0;
85   tailoffset=0;
86 }
87
88 int WorkList::hasMoreElements() {
89   //  return (ptr != 0);
90   return ((head!=tail)||(headoffset!=tailoffset));
91 }
92
93 int WorkList::getid() {
94   return tail->data[tailoffset];
95 }
96
97 int WorkList::gettype() {
98   return tail->data[tailoffset+1];
99 }
100
101 int WorkList::getlvalue() {
102   return tail->data[tailoffset+2];
103 }
104
105 int WorkList::getrvalue() {
106   return tail->data[tailoffset+3];
107 }
108
109 WorkList::~WorkList() {
110   struct ListNode *ptr=tail;
111   while(ptr) {
112     struct ListNode *oldptr=ptr;
113     ptr=ptr->next;
114     free(oldptr);
115   }
116 }
117
118 void WorkList::pop() {
119   int newoffset=tailoffset+4;
120   struct ListNode *ptr=tail;
121   if (newoffset>=WLISTSIZE) {
122     newoffset-=WLISTSIZE;
123     struct ListNode *oldptr=ptr;
124     ptr=ptr->next;
125     free(oldptr);
126   }
127   tail=ptr;
128   tailoffset=newoffset;
129 }
130
131 void WorkList::add(int id,int type, int lvalue, int rvalue) {
132   if (headoffset==WLISTSIZE) {
133     if (head->next==0) {
134       head->next=(struct ListNode *)malloc(sizeof(struct ListNode));
135       head->next->next=0;
136     }
137     headoffset=0;
138     head=head->next;
139   }
140   head->data[headoffset++]=id;
141   head->data[headoffset++]=type;
142   head->data[headoffset++]=lvalue;
143   head->data[headoffset++]=rvalue;
144 }
145
146 /* SIMPLE HASH ********************************************************/
147 SimpleIterator* SimpleHash::iterator() {
148   return new SimpleIterator(listhead,listtail,tailindex/*,this*/);
149 }
150
151 void SimpleHash::iterator(SimpleIterator & it) {
152   //  it.table=this;
153   it.cur=listhead;
154   it.index=0;
155   it.tailindex=tailindex;
156   it.tail=listtail;
157 }
158
159 SimpleHash::SimpleHash(int size) {
160     if (size <= 0) {
161         throw SimpleHashException();
162     }
163     this->size = size;
164     this->bucket = (struct SimpleNode **) calloc(sizeof(struct SimpleNode *)*size,1);
165     /* Set allocation blocks*/
166     this->listhead=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
167     this->listtail=this->listhead;
168     this->tailindex=0;
169     /*Set data counts*/
170     this->numparents = 0;
171     this->numchildren = 0;
172     this->numelements = 0;
173 }
174
175 SimpleHash::~SimpleHash() {
176   free(bucket);
177   struct ArraySimple *ptr=listhead;
178   while(ptr) {
179       struct ArraySimple *next=ptr->nextarray;
180       free(ptr);
181       ptr=next;
182   }
183 }
184
185 int SimpleHash::firstkey() {
186   struct ArraySimple *ptr=listhead;
187   int index=0;
188   while((index==ARRAYSIZE)||!ptr->nodes[index].inuse) {
189     if (index==ARRAYSIZE) {
190       index=0;
191       ptr=ptr->nextarray;
192     } else
193       index++;
194   }
195   return ptr->nodes[index].key;
196 }
197
198 void SimpleHash::addParent(SimpleHash* parent) {
199     parents[numparents++] = parent;
200     parent->addChild(this);
201 }
202
203 void SimpleHash::addChild(SimpleHash *child) {
204   children[numchildren++]=child;
205 }
206
207 int SimpleHash::remove(int key, int data) {
208     unsigned int hashkey = (unsigned int)key % size;
209     
210     struct SimpleNode **ptr = &bucket[hashkey];
211
212     for (int i = 0; i < numchildren; i++) {
213       children[i]->remove(key, data);
214     }
215
216     while (*ptr) {
217         if ((*ptr)->key == key && (*ptr)->data == data) {
218           struct SimpleNode *toremove=*ptr;
219           *ptr=(*ptr)->next;
220
221           toremove->inuse=0; /* Marked as unused */
222
223           numelements--;
224           return 1;
225         }
226         ptr = &((*ptr)->next);
227     }
228
229     return 0;
230 }
231
232 void SimpleHash::addAll(SimpleHash * set) {
233   SimpleIterator it;
234   set->iterator(it);
235   while(it.hasNext()) {
236     int key=it.key();
237     int data=it.next();
238     add(key,data);
239   }
240 }
241
242 int SimpleHash::add(int key, int data) {
243   /* Rehash code */
244   if (numelements>=size) {
245     int newsize=2*size+1;
246     struct SimpleNode ** newbucket = (struct SimpleNode **) calloc(sizeof(struct SimpleNode *)*newsize,1);
247     for(int i=size-1;i>=0;i--) {
248       for(struct SimpleNode *ptr=bucket[i];ptr!=NULL;) {
249         struct SimpleNode * nextptr=ptr->next;
250         unsigned int newhashkey=(unsigned int)ptr->key % newsize;
251         ptr->next=newbucket[newhashkey];
252         newbucket[newhashkey]=ptr;
253         ptr=nextptr;
254       }
255     }
256     size=newsize;
257     free(bucket);
258     bucket=newbucket;
259   }
260
261   unsigned int hashkey = (unsigned int)key % size;
262   struct SimpleNode **ptr = &bucket[hashkey];
263   
264   /* check that this key/object pair isn't already here */
265   /* TBD can be optimized for set v. relation */
266
267   while (*ptr) {
268     if ((*ptr)->key == key && (*ptr)->data == data) {
269       return 0;
270     }
271     ptr = &((*ptr)->next);
272   }
273   if (tailindex==ARRAYSIZE) {
274     listtail->nextarray=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
275     tailindex=0;
276     listtail=listtail->nextarray;
277   }
278   
279   *ptr = &listtail->nodes[tailindex++];
280   (*ptr)->key=key;
281   (*ptr)->data=data;
282   (*ptr)->inuse=1;
283   
284   numelements++;
285   
286   for (int i = 0; i < numparents; i++) {
287     parents[i]->add(key, data);
288   }
289   return 1;
290 }
291
292 bool SimpleHash::contains(int key) {
293     unsigned int hashkey = (unsigned int)key % size;
294     
295     struct SimpleNode *ptr = bucket[hashkey];
296     while (ptr) {
297         if (ptr->key == key) {
298             // we already have this object 
299             // stored in the hash so just return
300             return true;
301         }
302         ptr = ptr->next;
303     }
304     return false;
305 }
306
307 bool SimpleHash::contains(int key, int data) {
308     unsigned int hashkey = (unsigned int)key % size;
309     
310     struct SimpleNode *ptr = bucket[hashkey];
311     while (ptr) {
312         if (ptr->key == key && ptr->data == data) {
313             // we already have this object 
314             // stored in the hash so just return
315             return true;
316         }
317         ptr = ptr->next;
318     }
319     return false;
320 }
321
322 int SimpleHash::count(int key) {
323     unsigned int hashkey = (unsigned int)key % size;
324     int count = 0;
325
326     struct SimpleNode *ptr = bucket[hashkey];
327     while (ptr) {
328         if (ptr->key == key) {
329             count++;
330         }
331         ptr = ptr->next;
332     }
333     return count;
334 }
335
336 SimpleHash * SimpleHash::imageSet(int key) {
337   SimpleHash * newset=new SimpleHash(2*count(key)+4);
338   unsigned int hashkey = (unsigned int)key % size;
339   
340   struct SimpleNode *ptr = bucket[hashkey];
341   while (ptr) {
342     if (ptr->key == key) {
343       newset->add(ptr->data,ptr->data);
344     }
345     ptr = ptr->next;
346   }
347   return newset;
348 }
349
350 int SimpleHash::get(int key, int&data) {
351     unsigned int hashkey = (unsigned int)key % size;
352     
353     struct SimpleNode *ptr = bucket[hashkey];
354     while (ptr) {
355         if (ptr->key == key) {
356             data = ptr->data;
357             return 1; // success
358         }
359         ptr = ptr->next;
360     }
361         
362     return 0; // failure
363 }
364
365 int SimpleHash::countdata(int data) {
366     int count = 0;
367     struct ArraySimple *ptr = listhead;
368     while(ptr) {
369       if (ptr->nextarray) {
370         for(int i=0;i<ARRAYSIZE;i++)
371           if (ptr->nodes[i].data == data
372               &&ptr->nodes[i].inuse) {
373             count++;
374           }
375       } else {
376         for(int i=0;i<tailindex;i++)
377           if (ptr->nodes[i].data == data
378               &&ptr->nodes[i].inuse) {
379             count++;
380           }
381       }
382       ptr = ptr->nextarray;
383     }
384     return count;
385 }
386
387 SimpleHashException::SimpleHashException() {}
388 // ************************************************************
389
390
391 RepairHashNode::RepairHashNode(int setrelation, int rule, int lvalue, int rvalue, int data, int data2, int ismodify){
392     this->setrelation = setrelation;
393     this->lvalue=lvalue;
394     this->rvalue=rvalue;
395     this->data = data;
396     this->data2 = data2;
397     this->next = 0;
398     this->lnext=0;
399     this->rule=rule;
400     this->ismodify=ismodify;
401 }
402
403 // ************************************************************
404
405 RepairHash::RepairHash(int size) {
406     if (size <= 0) {
407         throw SimpleHashException();
408     }
409     this->size = size;
410     this->bucket = new RepairHashNode* [size];
411     for (int i=0;i<size;i++)
412       bucket[i]=0;
413     this->nodelist=0;
414     this->numelements = 0;
415 }
416
417 #define REPAIRSIZE 100
418 RepairHash::RepairHash() {
419     this->size = REPAIRSIZE;
420     this->bucket = new RepairHashNode* [REPAIRSIZE];
421     for (int i=0;i<REPAIRSIZE;i++)
422       bucket[i]=0;
423     this->nodelist=0;
424     this->numelements = 0;
425 }
426
427 RepairHash::~RepairHash() {
428   delete [] this->bucket;
429   RepairHashNode *ptr=nodelist;
430   while(ptr) {
431       RepairHashNode *next=ptr->lnext;
432       delete ptr;
433       ptr=next;
434   }
435 }
436
437 #define SETFLAG (1<<31)
438
439 int RepairHash::addset(int setv, int rule, int value, int data) {
440   return addrelation(setv||SETFLAG, rule, value,0,data);
441 }
442
443 int RepairHash::addrelation(int relation, int rule, int lvalue, int rvalue, int data) {
444     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
445     
446     RepairHashNode **ptr = &bucket[hashkey];
447
448     /* check that this key/object pair isn't already here */
449     // TBD can be optimized for set v. relation */
450     while (*ptr) {
451         if ((*ptr)->setrelation == relation && 
452             (*ptr)->rule==rule &&
453             (*ptr)->lvalue==lvalue &&
454             (*ptr)->rvalue==rvalue &&
455             (*ptr)->data == data&&
456             (*ptr)->data2 == 0) {
457             return 0;
458         }
459         ptr = &((*ptr)->next);
460     }
461     
462     *ptr = new RepairHashNode(relation,rule,lvalue,rvalue, data,0,0);
463     (*ptr)->lnext=nodelist;
464     nodelist=*ptr;
465     numelements++;
466     return 1;
467 }
468
469 int RepairHash::addrelation(int relation, int rule, int lvalue, int rvalue, int data, int data2) {
470     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
471     
472     RepairHashNode **ptr = &bucket[hashkey];
473
474     /* check that this key/object pair isn't already here */
475     // TBD can be optimized for set v. relation */
476     while (*ptr) {
477         if ((*ptr)->setrelation == relation && 
478             (*ptr)->rule==rule &&
479             (*ptr)->lvalue==lvalue &&
480             (*ptr)->rvalue==rvalue &&
481             (*ptr)->data == data &&
482             (*ptr)->data2 == data2) {
483             return 0;
484         }
485         ptr = &((*ptr)->next);
486     }
487     
488     *ptr = new RepairHashNode(relation,rule,lvalue,rvalue, data,data2,1);
489     (*ptr)->lnext=nodelist;
490     nodelist=*ptr;
491     numelements++;
492     return 1;
493 }
494
495 bool RepairHash::containsset(int setv, int rule, int value) {
496   return containsrelation(setv||SETFLAG, rule, value,0);
497 }
498
499 bool RepairHash::containsrelation(int relation, int rule, int lvalue, int rvalue) {
500     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
501     
502     RepairHashNode **ptr = &bucket[hashkey];
503
504     /* check that this key/object pair isn't already here */
505     // TBD can be optimized for set v. relation */
506     while (*ptr) {
507         if ((*ptr)->setrelation == relation && 
508             (*ptr)->rule==rule &&
509             (*ptr)->lvalue==lvalue &&
510             (*ptr)->rvalue==rvalue) {
511             return true;
512         }
513         ptr = &((*ptr)->next);
514     }
515     return false;
516 }
517
518 int RepairHash::getset(int setv, int rule, int value) {
519   return getrelation(setv||SETFLAG, rule, value,0);
520 }
521
522 int RepairHash::ismodify(int relation, int rule, int lvalue,int rvalue) {
523     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
524     
525     RepairHashNode **ptr = &bucket[hashkey];
526
527     /* check that this key/object pair isn't already here */
528     // TBD can be optimized for set v. relation */
529     while (*ptr) {
530         if ((*ptr)->setrelation == relation && 
531             (*ptr)->rule==rule &&
532             (*ptr)->lvalue==lvalue &&
533             (*ptr)->rvalue==rvalue) {
534           return (*ptr)->ismodify;
535         }
536         ptr = &((*ptr)->next);
537     }
538     return 0;
539 }
540
541 int RepairHash::getrelation2(int relation, int rule, int lvalue,int rvalue) {
542     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
543     
544     RepairHashNode **ptr = &bucket[hashkey];
545
546     /* check that this key/object pair isn't already here */
547     // TBD can be optimized for set v. relation */
548     while (*ptr) {
549         if ((*ptr)->setrelation == relation && 
550             (*ptr)->rule==rule &&
551             (*ptr)->lvalue==lvalue &&
552             (*ptr)->rvalue==rvalue) {
553           return (*ptr)->data2;
554         }
555         ptr = &((*ptr)->next);
556     }
557     return 0;
558 }
559
560 int RepairHash::getrelation(int relation, int rule, int lvalue,int rvalue) {
561     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
562     
563     RepairHashNode **ptr = &bucket[hashkey];
564
565     /* check that this key/object pair isn't already here */
566     // TBD can be optimized for set v. relation */
567     while (*ptr) {
568         if ((*ptr)->setrelation == relation && 
569             (*ptr)->rule==rule &&
570             (*ptr)->lvalue==lvalue &&
571             (*ptr)->rvalue==rvalue) {
572           return (*ptr)->data;
573         }
574         ptr = &((*ptr)->next);
575     }
576     return 0;
577 }