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