1 #include "SimpleHash.h"
5 /* LINKED HASH NODE ****************************************************/
7 LinkedHashNode::LinkedHashNode(int key, int data, LinkedHashNode *next) {
15 LinkedHashNode::LinkedHashNode() {
23 /* SIMPLE LIST ****************************************************/
25 SimpleList::SimpleList() {
30 void SimpleList::reset() {
35 int SimpleList::hasMoreElements() {
37 return (ptr->next != 0);
40 int SimpleList::nextElement() {
44 //int data = ptr->data;
49 void SimpleList::add(int data) {
50 LinkedHashNode *cur = &head;
53 if (cur->data == data) {
54 return; // no duplicates
57 cur->next = new LinkedHashNode(0, data, 0);
61 int SimpleList::contains(int data) {
62 LinkedHashNode *cur = &head;
65 if (cur->data == data) {
72 /* WORK LIST ****************************************************/
74 WorkList::WorkList() {
75 head=(struct ListNode *) malloc(sizeof(struct ListNode));
82 void WorkList::reset() {
88 int WorkList::hasMoreElements() {
90 return ((head!=tail)||(headoffset!=tailoffset));
93 int WorkList::getid() {
94 return tail->data[tailoffset];
97 int WorkList::gettype() {
98 return tail->data[tailoffset+1];
101 int WorkList::getlvalue() {
102 return tail->data[tailoffset+2];
105 int WorkList::getrvalue() {
106 return tail->data[tailoffset+3];
109 WorkList::~WorkList() {
110 struct ListNode *ptr=tail;
112 struct ListNode *oldptr=ptr;
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;
128 tailoffset=newoffset;
131 void WorkList::add(int id,int type, int lvalue, int rvalue) {
132 if (headoffset==WLISTSIZE) {
134 head->next=(struct ListNode *)malloc(sizeof(struct ListNode));
140 head->data[headoffset++]=id;
141 head->data[headoffset++]=type;
142 head->data[headoffset++]=lvalue;
143 head->data[headoffset++]=rvalue;
146 /* SIMPLE HASH ********************************************************/
147 SimpleIterator* SimpleHash::iterator() {
148 return new SimpleIterator(listhead,listtail,tailindex/*,this*/);
151 void SimpleHash::iterator(SimpleIterator & it) {
155 it.tailindex=tailindex;
159 SimpleHash::SimpleHash(int size) {
161 throw SimpleHashException();
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;
170 this->numparents = 0;
171 this->numchildren = 0;
172 this->numelements = 0;
175 SimpleHash::~SimpleHash() {
177 struct ArraySimple *ptr=listhead;
179 struct ArraySimple *next=ptr->nextarray;
185 int SimpleHash::firstkey() {
186 struct ArraySimple *ptr=listhead;
188 while((index==ARRAYSIZE)||!ptr->nodes[index].inuse) {
189 if (index==ARRAYSIZE) {
195 return ptr->nodes[index].key;
198 void SimpleHash::addParent(SimpleHash* parent) {
199 parents[numparents++] = parent;
200 parent->addChild(this);
203 void SimpleHash::addChild(SimpleHash *child) {
204 children[numchildren++]=child;
207 int SimpleHash::remove(int key, int data) {
208 unsigned int hashkey = (unsigned int)key % size;
210 struct SimpleNode **ptr = &bucket[hashkey];
212 for (int i = 0; i < numchildren; i++) {
213 children[i]->remove(key, data);
217 if ((*ptr)->key == key && (*ptr)->data == data) {
218 struct SimpleNode *toremove=*ptr;
221 toremove->inuse=0; /* Marked as unused */
226 ptr = &((*ptr)->next);
232 void SimpleHash::addAll(SimpleHash * set) {
235 while(it.hasNext()) {
242 int SimpleHash::add(int key, int data) {
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;
261 unsigned int hashkey = (unsigned int)key % size;
262 struct SimpleNode **ptr = &bucket[hashkey];
264 /* check that this key/object pair isn't already here */
265 /* TBD can be optimized for set v. relation */
268 if ((*ptr)->key == key && (*ptr)->data == data) {
271 ptr = &((*ptr)->next);
273 if (tailindex==ARRAYSIZE) {
274 listtail->nextarray=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
276 listtail=listtail->nextarray;
279 *ptr = &listtail->nodes[tailindex++];
286 for (int i = 0; i < numparents; i++) {
287 parents[i]->add(key, data);
292 bool SimpleHash::contains(int key) {
293 unsigned int hashkey = (unsigned int)key % size;
295 struct SimpleNode *ptr = bucket[hashkey];
297 if (ptr->key == key) {
298 // we already have this object
299 // stored in the hash so just return
307 bool SimpleHash::contains(int key, int data) {
308 unsigned int hashkey = (unsigned int)key % size;
310 struct SimpleNode *ptr = bucket[hashkey];
312 if (ptr->key == key && ptr->data == data) {
313 // we already have this object
314 // stored in the hash so just return
322 int SimpleHash::count(int key) {
323 unsigned int hashkey = (unsigned int)key % size;
326 struct SimpleNode *ptr = bucket[hashkey];
328 if (ptr->key == key) {
336 SimpleHash * SimpleHash::imageSet(int key) {
337 SimpleHash * newset=new SimpleHash(2*count(key)+4);
338 unsigned int hashkey = (unsigned int)key % size;
340 struct SimpleNode *ptr = bucket[hashkey];
342 if (ptr->key == key) {
343 newset->add(ptr->data,ptr->data);
350 int SimpleHash::get(int key, int&data) {
351 unsigned int hashkey = (unsigned int)key % size;
353 struct SimpleNode *ptr = bucket[hashkey];
355 if (ptr->key == key) {
365 int SimpleHash::countdata(int data) {
367 struct ArraySimple *ptr = listhead;
369 if (ptr->nextarray) {
370 for(int i=0;i<ARRAYSIZE;i++)
371 if (ptr->nodes[i].data == data
372 &&ptr->nodes[i].inuse) {
376 for(int i=0;i<tailindex;i++)
377 if (ptr->nodes[i].data == data
378 &&ptr->nodes[i].inuse) {
382 ptr = ptr->nextarray;
387 SimpleHashException::SimpleHashException() {}
388 // ************************************************************
391 RepairHashNode::RepairHashNode(int setrelation, int rule, int lvalue, int rvalue, int data, int data2, int ismodify){
392 this->setrelation = setrelation;
400 this->ismodify=ismodify;
403 // ************************************************************
405 RepairHash::RepairHash(int size) {
407 throw SimpleHashException();
410 this->bucket = new RepairHashNode* [size];
411 for (int i=0;i<size;i++)
414 this->numelements = 0;
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++)
424 this->numelements = 0;
427 RepairHash::~RepairHash() {
428 delete [] this->bucket;
429 RepairHashNode *ptr=nodelist;
431 RepairHashNode *next=ptr->lnext;
437 #define SETFLAG (1<<31)
439 int RepairHash::addset(int setv, int rule, int value, int data) {
440 return addrelation(setv||SETFLAG, rule, value,0,data);
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;
446 RepairHashNode **ptr = &bucket[hashkey];
448 /* check that this key/object pair isn't already here */
449 // TBD can be optimized for set v. relation */
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) {
459 ptr = &((*ptr)->next);
462 *ptr = new RepairHashNode(relation,rule,lvalue,rvalue, data,0,0);
463 (*ptr)->lnext=nodelist;
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;
472 RepairHashNode **ptr = &bucket[hashkey];
474 /* check that this key/object pair isn't already here */
475 // TBD can be optimized for set v. relation */
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) {
485 ptr = &((*ptr)->next);
488 *ptr = new RepairHashNode(relation,rule,lvalue,rvalue, data,data2,1);
489 (*ptr)->lnext=nodelist;
495 bool RepairHash::containsset(int setv, int rule, int value) {
496 return containsrelation(setv||SETFLAG, rule, value,0);
499 bool RepairHash::containsrelation(int relation, int rule, int lvalue, int rvalue) {
500 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
502 RepairHashNode **ptr = &bucket[hashkey];
504 /* check that this key/object pair isn't already here */
505 // TBD can be optimized for set v. relation */
507 if ((*ptr)->setrelation == relation &&
508 (*ptr)->rule==rule &&
509 (*ptr)->lvalue==lvalue &&
510 (*ptr)->rvalue==rvalue) {
513 ptr = &((*ptr)->next);
518 int RepairHash::getset(int setv, int rule, int value) {
519 return getrelation(setv||SETFLAG, rule, value,0);
522 int RepairHash::ismodify(int relation, int rule, int lvalue,int rvalue) {
523 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
525 RepairHashNode **ptr = &bucket[hashkey];
527 /* check that this key/object pair isn't already here */
528 // TBD can be optimized for set v. relation */
530 if ((*ptr)->setrelation == relation &&
531 (*ptr)->rule==rule &&
532 (*ptr)->lvalue==lvalue &&
533 (*ptr)->rvalue==rvalue) {
534 return (*ptr)->ismodify;
536 ptr = &((*ptr)->next);
541 int RepairHash::getrelation2(int relation, int rule, int lvalue,int rvalue) {
542 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
544 RepairHashNode **ptr = &bucket[hashkey];
546 /* check that this key/object pair isn't already here */
547 // TBD can be optimized for set v. relation */
549 if ((*ptr)->setrelation == relation &&
550 (*ptr)->rule==rule &&
551 (*ptr)->lvalue==lvalue &&
552 (*ptr)->rvalue==rvalue) {
553 return (*ptr)->data2;
555 ptr = &((*ptr)->next);
560 int RepairHash::getrelation(int relation, int rule, int lvalue,int rvalue) {
561 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
563 RepairHashNode **ptr = &bucket[hashkey];
565 /* check that this key/object pair isn't already here */
566 // TBD can be optimized for set v. relation */
568 if ((*ptr)->setrelation == relation &&
569 (*ptr)->rule==rule &&
570 (*ptr)->lvalue==lvalue &&
571 (*ptr)->rvalue==rvalue) {
574 ptr = &((*ptr)->next);