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 int WorkList::hasMoreElements() {
84 return ((head!=tail)||(headoffset!=tailoffset));
87 int WorkList::getid() {
88 return tail->data[tailoffset];
91 int WorkList::gettype() {
92 return tail->data[tailoffset+1];
95 int WorkList::getlvalue() {
96 return tail->data[tailoffset+2];
99 int WorkList::getrvalue() {
100 return tail->data[tailoffset+3];
103 WorkList::~WorkList() {
104 struct ListNode *ptr=tail;
106 struct ListNode *oldptr=ptr;
112 void WorkList::pop() {
113 int newoffset=tailoffset+4;
114 struct ListNode *ptr=tail;
115 if (newoffset>=WLISTSIZE) {
116 newoffset-=WLISTSIZE;
117 struct ListNode *oldptr=ptr;
122 tailoffset=newoffset;
125 void WorkList::add(int id,int type, int lvalue, int rvalue) {
126 if (headoffset==WLISTSIZE) {
127 head->next=(struct ListNode *)malloc(sizeof(struct ListNode));
132 head->data[headoffset++]=id;
133 head->data[headoffset++]=type;
134 head->data[headoffset++]=lvalue;
135 head->data[headoffset++]=rvalue;
138 /* SIMPLE HASH ********************************************************/
139 SimpleIterator* SimpleHash::iterator() {
140 return new SimpleIterator(listhead,listtail,tailindex/*,this*/);
143 void SimpleHash::iterator(SimpleIterator & it) {
147 it.tailindex=tailindex;
151 SimpleHash::SimpleHash(int size) {
153 throw SimpleHashException();
156 this->bucket = (struct SimpleNode **) calloc(sizeof(struct SimpleNode *)*size,1);
157 /* Set allocation blocks*/
158 this->listhead=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
159 this->listtail=this->listhead;
162 this->numparents = 0;
163 this->numchildren = 0;
164 this->numelements = 0;
167 SimpleHash::~SimpleHash() {
169 struct ArraySimple *ptr=listhead;
171 struct ArraySimple *next=ptr->nextarray;
177 int SimpleHash::firstkey() {
178 struct ArraySimple *ptr=listhead;
180 while((index==ARRAYSIZE)||!ptr->nodes[index].inuse) {
181 if (index==ARRAYSIZE) {
187 return ptr->nodes[index].key;
190 void SimpleHash::addParent(SimpleHash* parent) {
191 parents[numparents++] = parent;
192 parent->addChild(this);
195 void SimpleHash::addChild(SimpleHash *child) {
196 children[numchildren++]=child;
199 int SimpleHash::remove(int key, int data) {
200 unsigned int hashkey = (unsigned int)key % size;
202 struct SimpleNode **ptr = &bucket[hashkey];
204 for (int i = 0; i < numchildren; i++) {
205 children[i]->remove(key, data);
209 if ((*ptr)->key == key && (*ptr)->data == data) {
210 struct SimpleNode *toremove=*ptr;
213 toremove->inuse=0; /* Marked as unused */
218 ptr = &((*ptr)->next);
226 int SimpleHash::add(int key, int data) {
227 unsigned int hashkey = (unsigned int)key % size;
229 struct SimpleNode **ptr = &bucket[hashkey];
231 /* check that this key/object pair isn't already here */
232 // TBD can be optimized for set v. relation */
234 if ((*ptr)->key == key && (*ptr)->data == data) {
237 ptr = &((*ptr)->next);
239 if (tailindex==ARRAYSIZE) {
240 listtail->nextarray=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
242 listtail=listtail->nextarray;
245 *ptr = &listtail->nodes[tailindex++];
252 for (int i = 0; i < numparents; i++) {
253 parents[i]->add(key, data);
259 bool SimpleHash::contains(int key) {
260 unsigned int hashkey = (unsigned int)key % size;
262 struct SimpleNode *ptr = bucket[hashkey];
264 if (ptr->key == key) {
265 // we already have this object
266 // stored in the hash so just return
274 bool SimpleHash::contains(int key, int data) {
275 unsigned int hashkey = (unsigned int)key % size;
277 struct SimpleNode *ptr = bucket[hashkey];
279 if (ptr->key == key && ptr->data == data) {
280 // we already have this object
281 // stored in the hash so just return
289 int SimpleHash::count(int key) {
290 unsigned int hashkey = (unsigned int)key % size;
293 struct SimpleNode *ptr = bucket[hashkey];
295 if (ptr->key == key) {
303 int SimpleHash::get(int key, int&data) {
304 unsigned int hashkey = (unsigned int)key % size;
306 struct SimpleNode *ptr = bucket[hashkey];
308 if (ptr->key == key) {
318 int SimpleHash::countdata(int data) {
320 struct ArraySimple *ptr = listhead;
322 if (ptr->nextarray) {
323 for(int i=0;i<ARRAYSIZE;i++)
324 if (ptr->nodes[i].data == data
325 &&ptr->nodes[i].inuse) {
329 for(int i=0;i<tailindex;i++)
330 if (ptr->nodes[i].data == data
331 &&ptr->nodes[i].inuse) {
335 ptr = ptr->nextarray;
340 SimpleHashException::SimpleHashException() {}
341 // ************************************************************
344 RepairHashNode::RepairHashNode(int setrelation, int rule, int lvalue, int rvalue, int data, int data2){
345 this->setrelation = setrelation;
355 // ************************************************************
357 RepairHash::RepairHash(int size) {
359 throw SimpleHashException();
362 this->bucket = new RepairHashNode* [size];
363 for (int i=0;i<size;i++)
366 this->numelements = 0;
369 #define REPAIRSIZE 100
370 RepairHash::RepairHash() {
371 this->size = REPAIRSIZE;
372 this->bucket = new RepairHashNode* [REPAIRSIZE];
373 for (int i=0;i<REPAIRSIZE;i++)
376 this->numelements = 0;
379 RepairHash::~RepairHash() {
380 delete [] this->bucket;
381 RepairHashNode *ptr=nodelist;
383 RepairHashNode *next=ptr->lnext;
389 #define SETFLAG (1<<31)
391 int RepairHash::addset(int setv, int rule, int value, int data) {
392 return addrelation(setv||SETFLAG, rule, value,0,data);
395 int RepairHash::addrelation(int relation, int rule, int lvalue, int rvalue, int data) {
396 return addrelation(relation,rule,lvalue,rvalue,data, 0);
399 int RepairHash::addrelation(int relation, int rule, int lvalue, int rvalue, int data, int data2) {
400 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
402 RepairHashNode **ptr = &bucket[hashkey];
404 /* check that this key/object pair isn't already here */
405 // TBD can be optimized for set v. relation */
407 if ((*ptr)->setrelation == relation &&
408 (*ptr)->rule==rule &&
409 (*ptr)->lvalue==lvalue &&
410 (*ptr)->rvalue==rvalue &&
411 (*ptr)->data == data &&
412 (*ptr)->data2 == data2) {
415 ptr = &((*ptr)->next);
418 *ptr = new RepairHashNode(relation,rule,lvalue,rvalue, data,data2);
419 (*ptr)->lnext=nodelist;
425 bool RepairHash::containsset(int setv, int rule, int value) {
426 return containsrelation(setv||SETFLAG, rule, value,0);
429 bool RepairHash::containsrelation(int relation, int rule, int lvalue, int rvalue) {
430 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
432 RepairHashNode **ptr = &bucket[hashkey];
434 /* check that this key/object pair isn't already here */
435 // TBD can be optimized for set v. relation */
437 if ((*ptr)->setrelation == relation &&
438 (*ptr)->rule==rule &&
439 (*ptr)->lvalue==lvalue &&
440 (*ptr)->rvalue==rvalue) {
443 ptr = &((*ptr)->next);
448 int RepairHash::getset(int setv, int rule, int value) {
449 return getrelation(setv||SETFLAG, rule, value,0);
452 int RepairHash::getrelation2(int relation, int rule, int lvalue,int rvalue) {
453 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
455 RepairHashNode **ptr = &bucket[hashkey];
457 /* check that this key/object pair isn't already here */
458 // TBD can be optimized for set v. relation */
460 if ((*ptr)->setrelation == relation &&
461 (*ptr)->rule==rule &&
462 (*ptr)->lvalue==lvalue &&
463 (*ptr)->rvalue==rvalue) {
464 return (*ptr)->data2;
466 ptr = &((*ptr)->next);
470 int RepairHash::getrelation(int relation, int rule, int lvalue,int rvalue) {
471 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
473 RepairHashNode **ptr = &bucket[hashkey];
475 /* check that this key/object pair isn't already here */
476 // TBD can be optimized for set v. relation */
478 if ((*ptr)->setrelation == relation &&
479 (*ptr)->rule==rule &&
480 (*ptr)->lvalue==lvalue &&
481 (*ptr)->rvalue==rvalue) {
484 ptr = &((*ptr)->next);