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