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=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 }