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));
81 int WorkList::hasMoreElements() {
83 return ((head!=tail)||(headoffset!=tailoffset));
86 int WorkList::getid() {
87 return tail->data[tailoffset];
90 int WorkList::gettype() {
91 return tail->data[tailoffset+1];
94 int WorkList::getlvalue() {
95 return tail->data[tailoffset+2];
98 int WorkList::getrvalue() {
99 return tail->data[tailoffset+3];
102 WorkList::~WorkList() {
103 struct ListNode *ptr=tail;
105 struct ListNode *oldptr=ptr;
111 void WorkList::pop() {
112 int newoffset=tailoffset+4;
113 struct ListNode *ptr=tail;
114 if (newoffset>=WLISTSIZE) {
115 newoffset-=WLISTSIZE;
116 struct ListNode *oldptr=ptr;
121 tailoffset=newoffset;
124 void WorkList::add(int id,int type, int lvalue, int rvalue) {
125 if (headoffset==WLISTSIZE) {
126 head->next=(struct ListNode *)malloc(sizeof(struct ListNode));
130 head->data[headoffset++]=id;
131 head->data[headoffset++]=type;
132 head->data[headoffset++]=lvalue;
133 head->data[headoffset++]=rvalue;
136 /* SIMPLE HASH ********************************************************/
137 SimpleIterator* SimpleHash::iterator() {
138 return new SimpleIterator(listhead,this);
141 void SimpleHash::iterator(SimpleIterator & it) {
147 SimpleHash::SimpleHash(int size) {
149 throw SimpleHashException();
152 this->bucket = (struct SimpleNode **) calloc(sizeof(struct SimpleNode *)*size,1);
153 /* Set allocation blocks*/
154 this->listhead=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
155 this->listtail=this->listhead;
158 this->numparents = 0;
159 this->numchildren = 0;
160 this->numelements = 0;
163 SimpleHash::~SimpleHash() {
165 struct ArraySimple *ptr=listhead;
167 struct ArraySimple *next=ptr->nextarray;
173 void SimpleHash::addParent(SimpleHash* parent) {
174 parents[numparents++] = parent;
175 parent->addChild(this);
178 void SimpleHash::addChild(SimpleHash *child) {
179 children[numchildren++]=child;
182 int SimpleHash::remove(int key, int data) {
183 unsigned int hashkey = (unsigned int)key % size;
185 struct SimpleNode **ptr = &bucket[hashkey];
187 for (int i = 0; i < numchildren; i++) {
188 children[i]->remove(key, data);
192 if ((*ptr)->key == key && (*ptr)->data == data) {
193 struct SimpleNode *toremove=*ptr;
196 toremove->inuse=0; /* Marked as unused */
201 ptr = &((*ptr)->next);
209 int SimpleHash::add(int key, int data) {
210 unsigned int hashkey = (unsigned int)key % size;
212 struct SimpleNode **ptr = &bucket[hashkey];
214 /* check that this key/object pair isn't already here */
215 // TBD can be optimized for set v. relation */
217 if ((*ptr)->key == key && (*ptr)->data == data) {
220 ptr = &((*ptr)->next);
222 if (tailindex==ARRAYSIZE) {
223 listtail->nextarray=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
225 listtail=listtail->nextarray;
228 *ptr = &listtail->nodes[tailindex++];
235 for (int i = 0; i < numparents; i++) {
236 parents[i]->add(key, data);
242 bool SimpleHash::contains(int key) {
243 unsigned int hashkey = (unsigned int)key % size;
245 struct SimpleNode *ptr = bucket[hashkey];
247 if (ptr->key == key) {
248 // we already have this object
249 // stored in the hash so just return
257 bool SimpleHash::contains(int key, int data) {
258 unsigned int hashkey = (unsigned int)key % size;
260 struct SimpleNode *ptr = bucket[hashkey];
262 if (ptr->key == key && ptr->data == data) {
263 // we already have this object
264 // stored in the hash so just return
272 int SimpleHash::count(int key) {
273 unsigned int hashkey = (unsigned int)key % size;
276 struct SimpleNode *ptr = bucket[hashkey];
278 if (ptr->key == key) {
286 int SimpleHash::get(int key, int&data) {
287 unsigned int hashkey = (unsigned int)key % size;
289 struct SimpleNode *ptr = bucket[hashkey];
291 if (ptr->key == key) {
301 int SimpleHash::countdata(int data) {
303 struct ArraySimple *ptr = listhead;
305 if (ptr->nextarray) {
306 for(int i=0;i<ARRAYSIZE;i++)
307 if (ptr->nodes[i].data == data
308 &&ptr->nodes[i].inuse) {
312 for(int i=0;i<tailindex;i++)
313 if (ptr->nodes[i].data == data
314 &&ptr->nodes[i].inuse) {
318 ptr = ptr->nextarray;
323 SimpleHashException::SimpleHashException() {}
324 // ************************************************************
327 RepairHashNode::RepairHashNode(int setrelation, int rule, int lvalue, int rvalue, int data){
328 this->setrelation = setrelation;
337 // ************************************************************
339 RepairHash::RepairHash(int size) {
341 throw SimpleHashException();
344 this->bucket = new RepairHashNode* [size];
345 for (int i=0;i<size;i++)
348 this->numelements = 0;
351 RepairHash::RepairHash() {
355 RepairHash::~RepairHash() {
356 delete [] this->bucket;
357 RepairHashNode *ptr=nodelist;
359 RepairHashNode *next=ptr->lnext;
365 #define SETFLAG (1<<31)
367 int RepairHash::addset(int setv, int rule, int value, int data) {
368 return addrelation(setv||SETFLAG, rule, value,0,data);
371 int RepairHash::addrelation(int relation, int rule, int lvalue, int rvalue, int data) {
372 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
374 RepairHashNode **ptr = &bucket[hashkey];
376 /* check that this key/object pair isn't already here */
377 // TBD can be optimized for set v. relation */
379 if ((*ptr)->setrelation == relation &&
380 (*ptr)->rule==rule &&
381 (*ptr)->lvalue==lvalue &&
382 (*ptr)->rvalue==rvalue &&
383 (*ptr)->data == data) {
386 ptr = &((*ptr)->next);
389 *ptr = new RepairHashNode(relation,rule,lvalue,rvalue, data);
390 (*ptr)->lnext=nodelist;
396 bool RepairHash::containsset(int setv, int rule, int value) {
397 return containsrelation(setv||SETFLAG, rule, value,0);
400 bool RepairHash::containsrelation(int relation, int rule, int lvalue, int rvalue) {
401 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
403 RepairHashNode **ptr = &bucket[hashkey];
405 /* check that this key/object pair isn't already here */
406 // TBD can be optimized for set v. relation */
408 if ((*ptr)->setrelation == relation &&
409 (*ptr)->rule==rule &&
410 (*ptr)->lvalue==lvalue &&
411 (*ptr)->rvalue==rvalue) {
414 ptr = &((*ptr)->next);
419 int RepairHash::getset(int setv, int rule, int value) {
420 return getrelation(setv||SETFLAG, rule, value,0);
423 int RepairHash::getrelation(int relation, int rule, int lvalue,int rvalue) {
424 unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
426 RepairHashNode **ptr = &bucket[hashkey];
428 /* check that this key/object pair isn't already here */
429 // TBD can be optimized for set v. relation */
431 if ((*ptr)->setrelation == relation &&
432 (*ptr)->rule==rule &&
433 (*ptr)->lvalue==lvalue &&
434 (*ptr)->rvalue==rvalue) {
437 ptr = &((*ptr)->next);