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