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 int WorkList::hasMoreElements() {
  83   //  return (ptr != 0);
  84   return ((head!=tail)||(headoffset!=tailoffset));
  85 }
  86
  87 int WorkList::getid() {
  88   return tail->data[tailoffset];
  89 }
  90
  91 int WorkList::gettype() {
  92   return tail->data[tailoffset+1];
  93 }
  94
  95 int WorkList::getlvalue() {
  96   return tail->data[tailoffset+2];
  97 }
  98
  99 int WorkList::getrvalue() {
 100   return tail->data[tailoffset+3];
 101 }
 102
 103 WorkList::~WorkList() {
 104   struct ListNode *ptr=tail;
 105   while(ptr) {
 106     struct ListNode *oldptr=ptr;
 107     ptr=ptr->next;
 108     free(oldptr);
 109   }
 110 }
 111
 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;
 118     ptr=ptr->next;
 119     free(oldptr);
 120   }
 121   tail=ptr;
 122   tailoffset=newoffset;
 123 }
 124
 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));
 128     headoffset=0;
 129     head=head->next;
 130     head->next=0;
 131   }
 132   head->data[headoffset++]=id;
 133   head->data[headoffset++]=type;
 134   head->data[headoffset++]=lvalue;
 135   head->data[headoffset++]=rvalue;
 136 }
 137
 138 /* SIMPLE HASH ********************************************************/
 139 SimpleIterator* SimpleHash::iterator() {
 140   return new SimpleIterator(listhead,listtail,tailindex/*,this*/);
 141 }
 142
 143 void SimpleHash::iterator(SimpleIterator & it) {
 144   //  it.table=this;
 145   it.cur=listhead;
 146   it.index=0;
 147   it.tailindex=tailindex;
 148   it.tail=listtail;
 149 }
 150
 151 SimpleHash::SimpleHash(int size) {
 152     if (size <= 0) {
 153         throw SimpleHashException();
 154     }
 155     this->size = size;
 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;
 160     this->tailindex=0;
 161     /*Set data counts*/
 162     this->numparents = 0;
 163     this->numchildren = 0;
 164     this->numelements = 0;
 165 }
 166
 167 SimpleHash::~SimpleHash() {
 168   free(bucket);
 169   struct ArraySimple *ptr=listhead;
 170   while(ptr) {
 171       struct ArraySimple *next=ptr->nextarray;
 172       free(ptr);
 173       ptr=next;
 174   }
 175 }
 176
 177 int SimpleHash::firstkey() {
 178   struct ArraySimple *ptr=listhead;
 179   int index=0;
 180   while((index==ARRAYSIZE)||!ptr->nodes[index].inuse) {
 181     if (index==ARRAYSIZE) {
 182       index=0;
 183       ptr=ptr->nextarray;
 184     } else
 185       index++;
 186   }
 187   return ptr->nodes[index].key;
 188 }
 189
 190 void SimpleHash::addParent(SimpleHash* parent) {
 191     parents[numparents++] = parent;
 192     parent->addChild(this);
 193 }
 194
 195 void SimpleHash::addChild(SimpleHash *child) {
 196   children[numchildren++]=child;
 197 }
 198
 199 int SimpleHash::remove(int key, int data) {
 200     unsigned int hashkey = (unsigned int)key % size;
 201
 202     struct SimpleNode **ptr = &bucket[hashkey];
 203
 204     for (int i = 0; i < numchildren; i++) {
 205       children[i]->remove(key, data);
 206     }
 207
 208     while (*ptr) {
 209         if ((*ptr)->key == key && (*ptr)->data == data) {
 210           struct SimpleNode *toremove=*ptr;
 211           *ptr=(*ptr)->next;
 212
 213           toremove->inuse=0; /* Marked as unused */
 214
 215           numelements--;
 216           return 1;
 217         }
 218         ptr = &((*ptr)->next);
 219     }
 220
 221     return 0;
 222 }
 223
 224
 225
 226 int SimpleHash::add(int key, int data) {
 227     unsigned int hashkey = (unsigned int)key % size;
 228
 229     struct SimpleNode **ptr = &bucket[hashkey];
 230
 231     /* check that this key/object pair isn't already here */
 232     // TBD can be optimized for set v. relation */
 233     while (*ptr) {
 234         if ((*ptr)->key == key && (*ptr)->data == data) {
 235             return 0;
 236         }
 237         ptr = &((*ptr)->next);
 238     }
 239     if (tailindex==ARRAYSIZE) {
 240       listtail->nextarray=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
 241       tailindex=0;
 242       listtail=listtail->nextarray;
 243     }
 244
 245     *ptr = &listtail->nodes[tailindex++];
 246     (*ptr)->key=key;
 247     (*ptr)->data=data;
 248     (*ptr)->inuse=1;
 249
 250     numelements++;
 251
 252     for (int i = 0; i < numparents; i++) {
 253         parents[i]->add(key, data);
 254     }
 255
 256     return 1;
 257 }
 258
 259 bool SimpleHash::contains(int key) {
 260     unsigned int hashkey = (unsigned int)key % size;
 261
 262     struct SimpleNode *ptr = bucket[hashkey];
 263     while (ptr) {
 264         if (ptr->key == key) {
 265             // we already have this object
 266             // stored in the hash so just return
 267             return true;
 268         }
 269         ptr = ptr->next;
 270     }
 271     return false;
 272 }
 273
 274 bool SimpleHash::contains(int key, int data) {
 275     unsigned int hashkey = (unsigned int)key % size;
 276
 277     struct SimpleNode *ptr = bucket[hashkey];
 278     while (ptr) {
 279         if (ptr->key == key && ptr->data == data) {
 280             // we already have this object
 281             // stored in the hash so just return
 282             return true;
 283         }
 284         ptr = ptr->next;
 285     }
 286     return false;
 287 }
 288
 289 int SimpleHash::count(int key) {
 290     unsigned int hashkey = (unsigned int)key % size;
 291     int count = 0;
 292
 293     struct SimpleNode *ptr = bucket[hashkey];
 294     while (ptr) {
 295         if (ptr->key == key) {
 296             count++;
 297         }
 298         ptr = ptr->next;
 299     }
 300     return count;
 301 }
 302
 303 int SimpleHash::get(int key, int&data) {
 304     unsigned int hashkey = (unsigned int)key % size;
 305
 306     struct SimpleNode *ptr = bucket[hashkey];
 307     while (ptr) {
 308         if (ptr->key == key) {
 309             data = ptr->data;
 310             return 1; // success
 311         }
 312         ptr = ptr->next;
 313     }
 314
 315     return 0; // failure
 316 }
 317
 318 int SimpleHash::countdata(int data) {
 319     int count = 0;
 320     struct ArraySimple *ptr = listhead;
 321     while(ptr) {
 322       if (ptr->nextarray) {
 323         for(int i=0;i<ARRAYSIZE;i++)
 324           if (ptr->nodes[i].data == data
 325               &&ptr->nodes[i].inuse) {
 326             count++;
 327           }
 328       } else {
 329         for(int i=0;i<tailindex;i++)
 330           if (ptr->nodes[i].data == data
 331               &&ptr->nodes[i].inuse) {
 332             count++;
 333           }
 334       }
 335       ptr = ptr->nextarray;
 336     }
 337     return count;
 338 }
 339
 340 SimpleHashException::SimpleHashException() {}
 341 // ************************************************************
 342
 343
 344 RepairHashNode::RepairHashNode(int setrelation, int rule, int lvalue, int rvalue, int data, int data2, int ismodify){
 345     this->setrelation = setrelation;
 346     this->lvalue=lvalue;
 347     this->rvalue=rvalue;
 348     this->data = data;
 349     this->data2 = data2;
 350     this->next = 0;
 351     this->lnext=0;
 352     this->rule=rule;
 353     this->ismodify=ismodify;
 354 }
 355
 356 // ************************************************************
 357
 358 RepairHash::RepairHash(int size) {
 359     if (size <= 0) {
 360         throw SimpleHashException();
 361     }
 362     this->size = size;
 363     this->bucket = new RepairHashNode* [size];
 364     for (int i=0;i<size;i++)
 365       bucket[i]=0;
 366     this->nodelist=0;
 367     this->numelements = 0;
 368 }
 369
 370 #define REPAIRSIZE 100
 371 RepairHash::RepairHash() {
 372     this->size = REPAIRSIZE;
 373     this->bucket = new RepairHashNode* [REPAIRSIZE];
 374     for (int i=0;i<REPAIRSIZE;i++)
 375       bucket[i]=0;
 376     this->nodelist=0;
 377     this->numelements = 0;
 378 }
 379
 380 RepairHash::~RepairHash() {
 381   delete [] this->bucket;
 382   RepairHashNode *ptr=nodelist;
 383   while(ptr) {
 384       RepairHashNode *next=ptr->lnext;
 385       delete ptr;
 386       ptr=next;
 387   }
 388 }
 389
 390 #define SETFLAG (1<<31)
 391
 392 int RepairHash::addset(int setv, int rule, int value, int data) {
 393   return addrelation(setv||SETFLAG, rule, value,0,data);
 394 }
 395
 396 int RepairHash::addrelation(int relation, int rule, int lvalue, int rvalue, int data) {
 397     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
 398
 399     RepairHashNode **ptr = &bucket[hashkey];
 400
 401     /* check that this key/object pair isn't already here */
 402     // TBD can be optimized for set v. relation */
 403     while (*ptr) {
 404         if ((*ptr)->setrelation == relation &&
 405             (*ptr)->rule==rule &&
 406             (*ptr)->lvalue==lvalue &&
 407             (*ptr)->rvalue==rvalue &&
 408             (*ptr)->data == data&&
 409             (*ptr)->data2 == 0) {
 410             return 0;
 411         }
 412         ptr = &((*ptr)->next);
 413     }
 414
 415     *ptr = new RepairHashNode(relation,rule,lvalue,rvalue, data,0,0);
 416     (*ptr)->lnext=nodelist;
 417     nodelist=*ptr;
 418     numelements++;
 419     return 1;
 420 }
 421
 422 int RepairHash::addrelation(int relation, int rule, int lvalue, int rvalue, int data, int data2) {
 423     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
 424
 425     RepairHashNode **ptr = &bucket[hashkey];
 426
 427     /* check that this key/object pair isn't already here */
 428     // TBD can be optimized for set v. relation */
 429     while (*ptr) {
 430         if ((*ptr)->setrelation == relation &&
 431             (*ptr)->rule==rule &&
 432             (*ptr)->lvalue==lvalue &&
 433             (*ptr)->rvalue==rvalue &&
 434             (*ptr)->data == data &&
 435             (*ptr)->data2 == data2) {
 436             return 0;
 437         }
 438         ptr = &((*ptr)->next);
 439     }
 440
 441     *ptr = new RepairHashNode(relation,rule,lvalue,rvalue, data,data2,1);
 442     (*ptr)->lnext=nodelist;
 443     nodelist=*ptr;
 444     numelements++;
 445     return 1;
 446 }
 447
 448 bool RepairHash::containsset(int setv, int rule, int value) {
 449   return containsrelation(setv||SETFLAG, rule, value,0);
 450 }
 451
 452 bool RepairHash::containsrelation(int relation, int rule, int lvalue, int rvalue) {
 453     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
 454
 455     RepairHashNode **ptr = &bucket[hashkey];
 456
 457     /* check that this key/object pair isn't already here */
 458     // TBD can be optimized for set v. relation */
 459     while (*ptr) {
 460         if ((*ptr)->setrelation == relation &&
 461             (*ptr)->rule==rule &&
 462             (*ptr)->lvalue==lvalue &&
 463             (*ptr)->rvalue==rvalue) {
 464             return true;
 465         }
 466         ptr = &((*ptr)->next);
 467     }
 468     return false;
 469 }
 470
 471 int RepairHash::getset(int setv, int rule, int value) {
 472   return getrelation(setv||SETFLAG, rule, value,0);
 473 }
 474
 475 int RepairHash::ismodify(int relation, int rule, int lvalue,int rvalue) {
 476     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
 477
 478     RepairHashNode **ptr = &bucket[hashkey];
 479
 480     /* check that this key/object pair isn't already here */
 481     // TBD can be optimized for set v. relation */
 482     while (*ptr) {
 483         if ((*ptr)->setrelation == relation &&
 484             (*ptr)->rule==rule &&
 485             (*ptr)->lvalue==lvalue &&
 486             (*ptr)->rvalue==rvalue) {
 487           return (*ptr)->ismodify;
 488         }
 489         ptr = &((*ptr)->next);
 490     }
 491     return 0;
 492 }
 493
 494 int RepairHash::getrelation2(int relation, int rule, int lvalue,int rvalue) {
 495     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
 496
 497     RepairHashNode **ptr = &bucket[hashkey];
 498
 499     /* check that this key/object pair isn't already here */
 500     // TBD can be optimized for set v. relation */
 501     while (*ptr) {
 502         if ((*ptr)->setrelation == relation &&
 503             (*ptr)->rule==rule &&
 504             (*ptr)->lvalue==lvalue &&
 505             (*ptr)->rvalue==rvalue) {
 506           return (*ptr)->data2;
 507         }
 508         ptr = &((*ptr)->next);
 509     }
 510     return 0;
 511 }
 512
 513 int RepairHash::getrelation(int relation, int rule, int lvalue,int rvalue) {
 514     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
 515
 516     RepairHashNode **ptr = &bucket[hashkey];
 517
 518     /* check that this key/object pair isn't already here */
 519     // TBD can be optimized for set v. relation */
 520     while (*ptr) {
 521         if ((*ptr)->setrelation == relation &&
 522             (*ptr)->rule==rule &&
 523             (*ptr)->lvalue==lvalue &&
 524             (*ptr)->rvalue==rvalue) {
 525           return (*ptr)->data;
 526         }
 527         ptr = &((*ptr)->next);
 528     }
 529     return 0;
 530 }