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,this);
 141 }
 142
 143 void SimpleHash::iterator(SimpleIterator & it) {
 144   it.table=this;
 145   it.cur=listhead;
 146   it.index=0;
 147 }
 148
 149 SimpleHash::SimpleHash(int size) {
 150     if (size <= 0) {
 151         throw SimpleHashException();
 152     }
 153     this->size = size;
 154     this->bucket = (struct SimpleNode **) calloc(sizeof(struct SimpleNode *)*size,1);
 155     /* Set allocation blocks*/
 156     this->listhead=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
 157     this->listtail=this->listhead;
 158     this->tailindex=0;
 159     /*Set data counts*/
 160     this->numparents = 0;
 161     this->numchildren = 0;
 162     this->numelements = 0;
 163 }
 164
 165 SimpleHash::~SimpleHash() {
 166   free(bucket);
 167   struct ArraySimple *ptr=listhead;
 168   while(ptr) {
 169       struct ArraySimple *next=ptr->nextarray;
 170       free(ptr);
 171       ptr=next;
 172   }
 173 }
 174
 175 void SimpleHash::addParent(SimpleHash* parent) {
 176     parents[numparents++] = parent;
 177     parent->addChild(this);
 178 }
 179
 180 void SimpleHash::addChild(SimpleHash *child) {
 181   children[numchildren++]=child;
 182 }
 183
 184 int SimpleHash::remove(int key, int data) {
 185     unsigned int hashkey = (unsigned int)key % size;
 186
 187     struct SimpleNode **ptr = &bucket[hashkey];
 188
 189     for (int i = 0; i < numchildren; i++) {
 190       children[i]->remove(key, data);
 191     }
 192
 193     while (*ptr) {
 194         if ((*ptr)->key == key && (*ptr)->data == data) {
 195           struct SimpleNode *toremove=*ptr;
 196           *ptr=(*ptr)->next;
 197
 198           toremove->inuse=0; /* Marked as unused */
 199
 200           numelements--;
 201           return 1;
 202         }
 203         ptr = &((*ptr)->next);
 204     }
 205
 206     return 0;
 207 }
 208
 209
 210
 211 int SimpleHash::add(int key, int data) {
 212     unsigned int hashkey = (unsigned int)key % size;
 213
 214     struct SimpleNode **ptr = &bucket[hashkey];
 215
 216     /* check that this key/object pair isn't already here */
 217     // TBD can be optimized for set v. relation */
 218     while (*ptr) {
 219         if ((*ptr)->key == key && (*ptr)->data == data) {
 220             return 0;
 221         }
 222         ptr = &((*ptr)->next);
 223     }
 224     if (tailindex==ARRAYSIZE) {
 225       listtail->nextarray=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
 226       tailindex=0;
 227       listtail=listtail->nextarray;
 228     }
 229
 230     *ptr = &listtail->nodes[tailindex++];
 231     (*ptr)->key=key;
 232     (*ptr)->data=data;
 233     (*ptr)->inuse=1;
 234
 235     numelements++;
 236
 237     for (int i = 0; i < numparents; i++) {
 238         parents[i]->add(key, data);
 239     }
 240
 241     return 1;
 242 }
 243
 244 bool SimpleHash::contains(int key) {
 245     unsigned int hashkey = (unsigned int)key % size;
 246
 247     struct SimpleNode *ptr = bucket[hashkey];
 248     while (ptr) {
 249         if (ptr->key == key) {
 250             // we already have this object
 251             // stored in the hash so just return
 252             return true;
 253         }
 254         ptr = ptr->next;
 255     }
 256     return false;
 257 }
 258
 259 bool SimpleHash::contains(int key, int data) {
 260     unsigned int hashkey = (unsigned int)key % size;
 261
 262     struct SimpleNode *ptr = bucket[hashkey];
 263     while (ptr) {
 264         if (ptr->key == key && ptr->data == data) {
 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 int SimpleHash::count(int key) {
 275     unsigned int hashkey = (unsigned int)key % size;
 276     int count = 0;
 277
 278     struct SimpleNode *ptr = bucket[hashkey];
 279     while (ptr) {
 280         if (ptr->key == key) {
 281             count++;
 282         }
 283         ptr = ptr->next;
 284     }
 285     return count;
 286 }
 287
 288 int SimpleHash::get(int key, int&data) {
 289     unsigned int hashkey = (unsigned int)key % size;
 290
 291     struct SimpleNode *ptr = bucket[hashkey];
 292     while (ptr) {
 293         if (ptr->key == key) {
 294             data = ptr->data;
 295             return 1; // success
 296         }
 297         ptr = ptr->next;
 298     }
 299
 300     return 0; // failure
 301 }
 302
 303 int SimpleHash::countdata(int data) {
 304     int count = 0;
 305     struct ArraySimple *ptr = listhead;
 306     while(ptr) {
 307       if (ptr->nextarray) {
 308         for(int i=0;i<ARRAYSIZE;i++)
 309           if (ptr->nodes[i].data == data
 310               &&ptr->nodes[i].inuse) {
 311             count++;
 312           }
 313       } else {
 314         for(int i=0;i<tailindex;i++)
 315           if (ptr->nodes[i].data == data
 316               &&ptr->nodes[i].inuse) {
 317             count++;
 318           }
 319       }
 320       ptr = ptr->nextarray;
 321     }
 322     return count;
 323 }
 324
 325 SimpleHashException::SimpleHashException() {}
 326 // ************************************************************
 327
 328
 329 RepairHashNode::RepairHashNode(int setrelation, int rule, int lvalue, int rvalue, int data){
 330     this->setrelation = setrelation;
 331     this->lvalue=lvalue;
 332     this->rvalue=rvalue;
 333     this->data = data;
 334     this->next = 0;
 335     this->lnext=0;
 336     this->rule=rule;
 337 }
 338
 339 // ************************************************************
 340
 341 RepairHash::RepairHash(int size) {
 342     if (size <= 0) {
 343         throw SimpleHashException();
 344     }
 345     this->size = size;
 346     this->bucket = new RepairHashNode* [size];
 347     for (int i=0;i<size;i++)
 348       bucket[i]=0;
 349     this->nodelist=0;
 350     this->numelements = 0;
 351 }
 352
 353 RepairHash::RepairHash() {
 354   RepairHash(100);
 355 }
 356
 357 RepairHash::~RepairHash() {
 358   delete [] this->bucket;
 359   RepairHashNode *ptr=nodelist;
 360   while(ptr) {
 361       RepairHashNode *next=ptr->lnext;
 362       delete ptr;
 363       ptr=next;
 364   }
 365 }
 366
 367 #define SETFLAG (1<<31)
 368
 369 int RepairHash::addset(int setv, int rule, int value, int data) {
 370   return addrelation(setv||SETFLAG, rule, value,0,data);
 371 }
 372
 373 int RepairHash::addrelation(int relation, int rule, int lvalue, int rvalue, int data) {
 374     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
 375
 376     RepairHashNode **ptr = &bucket[hashkey];
 377
 378     /* check that this key/object pair isn't already here */
 379     // TBD can be optimized for set v. relation */
 380     while (*ptr) {
 381         if ((*ptr)->setrelation == relation &&
 382             (*ptr)->rule==rule &&
 383             (*ptr)->lvalue==lvalue &&
 384             (*ptr)->rvalue==rvalue &&
 385             (*ptr)->data == data) {
 386             return 0;
 387         }
 388         ptr = &((*ptr)->next);
 389     }
 390
 391     *ptr = new RepairHashNode(relation,rule,lvalue,rvalue, data);
 392     (*ptr)->lnext=nodelist;
 393     nodelist=*ptr;
 394     numelements++;
 395     return 1;
 396 }
 397
 398 bool RepairHash::containsset(int setv, int rule, int value) {
 399   return containsrelation(setv||SETFLAG, rule, value,0);
 400 }
 401
 402 bool RepairHash::containsrelation(int relation, int rule, int lvalue, int rvalue) {
 403     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
 404
 405     RepairHashNode **ptr = &bucket[hashkey];
 406
 407     /* check that this key/object pair isn't already here */
 408     // TBD can be optimized for set v. relation */
 409     while (*ptr) {
 410         if ((*ptr)->setrelation == relation &&
 411             (*ptr)->rule==rule &&
 412             (*ptr)->lvalue==lvalue &&
 413             (*ptr)->rvalue==rvalue) {
 414             return true;
 415         }
 416         ptr = &((*ptr)->next);
 417     }
 418     return false;
 419 }
 420
 421 int RepairHash::getset(int setv, int rule, int value) {
 422   return getrelation(setv||SETFLAG, rule, value,0);
 423 }
 424
 425 int RepairHash::getrelation(int relation, int rule, int lvalue,int rvalue) {
 426     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % size;
 427
 428     RepairHashNode **ptr = &bucket[hashkey];
 429
 430     /* check that this key/object pair isn't already here */
 431     // TBD can be optimized for set v. relation */
 432     while (*ptr) {
 433         if ((*ptr)->setrelation == relation &&
 434             (*ptr)->rule==rule &&
 435             (*ptr)->lvalue==lvalue &&
 436             (*ptr)->rvalue==rvalue) {
 437           return (*ptr)->data;
 438         }
 439         ptr = &((*ptr)->next);
 440     }
 441     return 0;
 442 }