Repair/RepairCompiler/MCC/CRuntime/SimpleHash.c

   1 #include "SimpleHash.h"
   2 #include <stdio.h>
   3
   4 /* LINKED HASH NODE ****************************************************/
   5
   6 struct LinkedHashNode * allocateLinkedHashNode(int key, int data, struct LinkedHashNode *next) {
   7     struct LinkedHashNode *thisvar=(struct LinkedHashNode *)malloc(sizeof(struct LinkedHashNode));
   8     thisvar->key = key;
   9     thisvar->data = data;
  10     thisvar->next = next;
  11     thisvar->lnext=0;
  12     thisvar->lprev=0;
  13     return thisvar;
  14 }
  15
  16 struct LinkedHashNode * noargallocateLinkedHashNode() {
  17     struct LinkedHashNode *thisvar=(struct LinkedHashNode *)malloc(sizeof(struct LinkedHashNode));
  18     thisvar->key = -1;
  19     thisvar->data = -1;
  20     thisvar->next = 0;
  21     thisvar->lnext=0;
  22     thisvar->lprev=0;
  23     return thisvar;
  24 }
  25
  26 /* SIMPLE LIST ****************************************************/
  27
  28 struct SimpleList * allocateSimpleList() {
  29     struct SimpleList *thisvar=(struct SimpleList *)malloc(sizeof(struct SimpleList));
  30     thisvar->ptr = 0;
  31     thisvar->head.next = 0;
  32     return thisvar;
  33 }
  34
  35 void SimpleListreset(struct SimpleList *thisvar) {
  36     thisvar->ptr = &thisvar->head;
  37 }
  38
  39 int SimpleListhasMoreElements(struct SimpleList *thisvar) {
  40     return (thisvar->ptr->next != 0);
  41 }
  42
  43 int SimpleListnextElement(struct SimpleList *thisvar) {
  44   thisvar->ptr = thisvar->ptr->next;
  45   return thisvar->ptr->data;
  46 }
  47
  48 void SimpleListadd(struct SimpleList *thisvar,int data) {
  49     struct LinkedHashNode *cur = &thisvar->head;
  50     while (cur->next) {
  51         cur = cur->next;
  52         if (cur->data == data) {
  53             return; /* no duplicates */
  54         }
  55     }
  56     cur->next = allocateLinkedHashNode(0, data, 0);
  57     return;
  58 }
  59
  60 int SimpleListcontains(struct SimpleList *thisvar,int data) {
  61     struct LinkedHashNode *cur = &thisvar->head;
  62     while (cur->next) {
  63         cur = cur->next;
  64         if (cur->data == data) {
  65             return 1; /* found! */
  66         }
  67     }
  68     return 0;
  69 }
  70
  71 /* WORK LIST ****************************************************/
  72
  73 struct WorkList * allocateWorkList() {
  74     struct WorkList *thisvar=(struct WorkList *)malloc(sizeof(struct WorkList));
  75     thisvar->head=(struct ListNode *) malloc(sizeof(struct ListNode));
  76     thisvar->tail=thisvar->head;
  77     thisvar->head->next=0;
  78     thisvar->headoffset=0;
  79     thisvar->tailoffset=0;
  80     return thisvar;
  81 }
  82
  83 void WorkListreset(struct WorkList *thisvar) {
  84     thisvar->head=thisvar->tail;
  85     thisvar->headoffset=0;
  86     thisvar->tailoffset=0;
  87 }
  88
  89 int WorkListhasMoreElements(struct WorkList *thisvar) {
  90   return ((thisvar->head!=thisvar->tail)||(thisvar->headoffset!=thisvar->tailoffset));
  91 }
  92
  93 int WorkListgetid(struct WorkList *thisvar) {
  94   return thisvar->tail->data[thisvar->tailoffset];
  95 }
  96
  97 int WorkListgettype(struct WorkList *thisvar) {
  98   return thisvar->tail->data[thisvar->tailoffset+1];
  99 }
 100
 101 int WorkListgetlvalue(struct WorkList *thisvar) {
 102   return thisvar->tail->data[thisvar->tailoffset+2];
 103 }
 104
 105 int WorkListgetrvalue(struct WorkList *thisvar) {
 106   return thisvar->tail->data[thisvar->tailoffset+3];
 107 }
 108
 109 void freeWorkList(struct WorkList *thisvar) {
 110   struct ListNode *ptr=thisvar->tail;
 111   while(ptr) {
 112     struct ListNode *oldptr=ptr;
 113     ptr=ptr->next;
 114     free(oldptr);
 115   }
 116   free(thisvar);
 117 }
 118
 119 void WorkListpop(struct WorkList *thisvar) {
 120   int newoffset=thisvar->tailoffset+4;
 121   struct ListNode *ptr=thisvar->tail;
 122   if (newoffset>=WLISTSIZE) {
 123     if (newoffset!=WLISTSIZE||thisvar->head!=thisvar->tail) {
 124       struct ListNode *oldptr=ptr;
 125       newoffset-=WLISTSIZE;
 126       ptr=ptr->next;
 127       free(oldptr);
 128     }
 129   }
 130   thisvar->tail=ptr;
 131   thisvar->tailoffset=newoffset;
 132 }
 133
 134 void WorkListadd(struct WorkList *thisvar, int id,int type, int lvalue, int rvalue) {
 135   if (thisvar->headoffset==WLISTSIZE) {
 136     if (thisvar->head->next==0) {
 137       thisvar->head->next=(struct ListNode *)malloc(sizeof(struct ListNode));
 138       thisvar->head->next->next=0;
 139     }
 140     thisvar->headoffset=0;
 141     thisvar->head=thisvar->head->next;
 142     if (thisvar->tailoffset==WLISTSIZE) { /* roll the tail over also */
 143         thisvar->tailoffset=0;
 144         thisvar->tail=thisvar->tail->next;
 145     }
 146   }
 147   thisvar->head->data[thisvar->headoffset++]=id;
 148   thisvar->head->data[thisvar->headoffset++]=type;
 149   thisvar->head->data[thisvar->headoffset++]=lvalue;
 150   thisvar->head->data[thisvar->headoffset++]=rvalue;
 151 }
 152
 153 /* SIMPLE HASH ********************************************************/
 154 struct SimpleIterator* createiterator(struct SimpleHash * thisvar) {
 155     return allocateSimpleIterator(thisvar->listhead,thisvar->listtail,thisvar->tailindex/*,thisvar*/);
 156 }
 157
 158 void iterator(struct SimpleHash *thisvar, struct SimpleIterator * it) {
 159   it->cur=thisvar->listhead;
 160   it->index=0;
 161   it->tailindex=thisvar->tailindex;
 162   it->tail=thisvar->listtail;
 163 }
 164
 165 struct SimpleHash * noargallocateSimpleHash() {
 166     return allocateSimpleHash(100);
 167 }
 168
 169 struct SimpleHash * allocateSimpleHash(int size) {
 170     struct SimpleHash *thisvar=(struct SimpleHash *)malloc(sizeof(struct SimpleHash));
 171     if (size <= 0) {
 172         printf("Negative Hashtable size Exception\n");
 173         exit(-1);
 174     }
 175     thisvar->size = size;
 176     thisvar->bucket = (struct SimpleNode **) calloc(sizeof(struct SimpleNode *)*size,1);
 177     /* Set allocation blocks*/
 178     thisvar->listhead=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
 179     thisvar->listtail=thisvar->listhead;
 180     thisvar->tailindex=0;
 181     /*Set data counts*/
 182     thisvar->numparents = 0;
 183     thisvar->numchildren = 0;
 184     thisvar->numelements = 0;
 185     return thisvar;
 186 }
 187
 188 void freeSimpleHash(struct SimpleHash *thisvar) {
 189     struct ArraySimple *ptr=thisvar->listhead;
 190     free(thisvar->bucket);
 191     while(ptr) {
 192         struct ArraySimple *next=ptr->nextarray;
 193         free(ptr);
 194         ptr=next;
 195     }
 196     free(thisvar);
 197 }
 198
 199 int SimpleHashfirstkey(struct SimpleHash *thisvar) {
 200   struct ArraySimple *ptr=thisvar->listhead;
 201   int index=0;
 202   while((index==ARRAYSIZE)||!ptr->nodes[index].inuse) {
 203     if (index==ARRAYSIZE) {
 204       index=0;
 205       ptr=ptr->nextarray;
 206     } else
 207       index++;
 208   }
 209   return ptr->nodes[index].key;
 210 }
 211
 212 void SimpleHashaddParent(struct SimpleHash *thisvar,struct SimpleHash* parent) {
 213     thisvar->parents[thisvar->numparents++] = parent;
 214     SimpleHashaddChild(parent,thisvar);
 215 }
 216
 217 void SimpleHashaddChild(struct SimpleHash *thisvar, struct SimpleHash *child) {
 218     thisvar->children[thisvar->numchildren++]=child;
 219 }
 220
 221 int SimpleHashremove(struct SimpleHash *thisvar, int key, int data) {
 222     unsigned int hashkey = (unsigned int)key % thisvar->size;
 223
 224     struct SimpleNode **ptr = &thisvar->bucket[hashkey];
 225     int i;
 226     for (i = 0; i < thisvar->numchildren; i++) {
 227         SimpleHashremove(thisvar->children[i], key, data);
 228     }
 229
 230     while (*ptr) {
 231         if ((*ptr)->key == key && (*ptr)->data == data) {
 232           struct SimpleNode *toremove=*ptr;
 233           *ptr=(*ptr)->next;
 234
 235           toremove->inuse=0; /* Marked as unused */
 236
 237           thisvar->numelements--;
 238           return 1;
 239         }
 240         ptr = &((*ptr)->next);
 241     }
 242
 243     return 0;
 244 }
 245
 246 void SimpleHashaddAll(struct SimpleHash *thisvar, struct SimpleHash * set) {
 247     struct SimpleIterator it;
 248     SimpleHashiterator(set, &it);
 249     while(hasNext(&it)) {
 250         int keyv=key(&it);
 251         int data=next(&it);
 252         SimpleHashadd(thisvar,keyv,data);
 253     }
 254 }
 255
 256 int SimpleHashadd(struct SimpleHash * thisvar,int key, int data) {
 257   /* Rehash code */
 258   unsigned int hashkey;
 259   struct SimpleNode **ptr;
 260
 261   if (thisvar->numelements>=thisvar->size) {
 262     int newsize=2*thisvar->size+1;
 263     struct SimpleNode ** newbucket = (struct SimpleNode **) calloc(sizeof(struct SimpleNode *)*newsize,1);
 264     int i;
 265     for(i=thisvar->size-1;i>=0;i--) {
 266         struct SimpleNode *ptr;
 267         for(ptr=thisvar->bucket[i];ptr!=NULL;) {
 268             struct SimpleNode * nextptr=ptr->next;
 269             unsigned int newhashkey=(unsigned int)ptr->key % newsize;
 270             ptr->next=newbucket[newhashkey];
 271             newbucket[newhashkey]=ptr;
 272             ptr=nextptr;
 273         }
 274     }
 275     thisvar->size=newsize;
 276     free(thisvar->bucket);
 277     thisvar->bucket=newbucket;
 278   }
 279
 280   hashkey = (unsigned int)key % thisvar->size;
 281   ptr = &thisvar->bucket[hashkey];
 282
 283   /* check that thisvar key/object pair isn't already here */
 284   /* TBD can be optimized for set v. relation */
 285
 286   while (*ptr) {
 287     if ((*ptr)->key == key && (*ptr)->data == data) {
 288       return 0;
 289     }
 290     ptr = &((*ptr)->next);
 291   }
 292   if (thisvar->tailindex==ARRAYSIZE) {
 293     thisvar->listtail->nextarray=(struct ArraySimple *) calloc(sizeof(struct ArraySimple),1);
 294     thisvar->tailindex=0;
 295     thisvar->listtail=thisvar->listtail->nextarray;
 296   }
 297
 298   *ptr = &thisvar->listtail->nodes[thisvar->tailindex++];
 299   (*ptr)->key=key;
 300   (*ptr)->data=data;
 301   (*ptr)->inuse=1;
 302
 303   thisvar->numelements++;
 304   {
 305       int i;
 306       for (i = 0; i < thisvar->numparents; i++) {
 307           SimpleHashadd(thisvar->parents[i], key, data);
 308       }
 309   }
 310   return 1;
 311 }
 312
 313 bool SimpleHashcontainskey(struct SimpleHash *thisvar,int key) {
 314     unsigned int hashkey = (unsigned int)key % thisvar->size;
 315
 316     struct SimpleNode *ptr = thisvar->bucket[hashkey];
 317     while (ptr) {
 318         if (ptr->key == key) {
 319             /* we already have thisvar object
 320                stored in the hash so just return */
 321             return true;
 322         }
 323         ptr = ptr->next;
 324     }
 325     return false;
 326 }
 327
 328 bool SimpleHashcontainskeydata(struct SimpleHash *thisvar, int key, int data) {
 329     unsigned int hashkey = (unsigned int)key % thisvar->size;
 330
 331     struct SimpleNode *ptr = thisvar->bucket[hashkey];
 332     while (ptr) {
 333         if (ptr->key == key && ptr->data == data) {
 334             /* we already have thisvar object
 335                stored in the hash so just return*/
 336             return true;
 337         }
 338         ptr = ptr->next;
 339     }
 340     return false;
 341 }
 342
 343 int SimpleHashcount(struct SimpleHash *thisvar,int key) {
 344     unsigned int hashkey = (unsigned int)key % thisvar->size;
 345     int count = 0;
 346
 347     struct SimpleNode *ptr = thisvar->bucket[hashkey];
 348     while (ptr) {
 349         if (ptr->key == key) {
 350             count++;
 351         }
 352         ptr = ptr->next;
 353     }
 354     return count;
 355 }
 356
 357 struct SimpleHash * SimpleHashimageSet(struct SimpleHash *thisvar, int key) {
 358   struct SimpleHash * newset=allocateSimpleHash(2*SimpleHashcount(thisvar,key)+4);
 359   unsigned int hashkey = (unsigned int)key % thisvar->size;
 360
 361   struct SimpleNode *ptr = thisvar->bucket[hashkey];
 362   while (ptr) {
 363     if (ptr->key == key) {
 364         SimpleHashadd(newset,ptr->data,ptr->data);
 365     }
 366     ptr = ptr->next;
 367   }
 368   return newset;
 369 }
 370
 371 int SimpleHashget(struct SimpleHash *thisvar, int key, int *data) {
 372     unsigned int hashkey = (unsigned int)key % thisvar->size;
 373
 374     struct SimpleNode *ptr = thisvar->bucket[hashkey];
 375     while (ptr) {
 376         if (ptr->key == key) {
 377             *data = ptr->data;
 378             return 1; /* success */
 379         }
 380         ptr = ptr->next;
 381     }
 382
 383     return 0; /* failure */
 384 }
 385
 386 int SimpleHashcountdata(struct SimpleHash *thisvar,int data) {
 387     int count = 0;
 388     struct ArraySimple *ptr = thisvar->listhead;
 389     while(ptr) {
 390       if (ptr->nextarray) {
 391           int i;
 392           for(i=0;i<ARRAYSIZE;i++)
 393               if (ptr->nodes[i].data == data
 394                   &&ptr->nodes[i].inuse) {
 395                   count++;
 396               }
 397       } else {
 398           int i;
 399           for(i=0;i<thisvar->tailindex;i++)
 400               if (ptr->nodes[i].data == data
 401                   &&ptr->nodes[i].inuse) {
 402                   count++;
 403               }
 404       }
 405       ptr = ptr->nextarray;
 406     }
 407     return count;
 408 }
 409
 410 struct RepairHashNode * allocateRepairHashNode(int setrelation, int rule, int lvalue, int rvalue, int data, int data2, int ismodify){
 411     struct RepairHashNode * thisvar=(struct RepairHashNode *)malloc(sizeof(struct RepairHashNode));
 412     thisvar->setrelation = setrelation;
 413     thisvar->lvalue=lvalue;
 414     thisvar->rvalue=rvalue;
 415     thisvar->data = data;
 416     thisvar->data2 = data2;
 417     thisvar->next = 0;
 418     thisvar->lnext=0;
 419     thisvar->rule=rule;
 420     thisvar->ismodify=ismodify;
 421     return thisvar;
 422 }
 423
 424 struct RepairHash * allocateRepairHash(int size) {
 425     struct RepairHash *thisvar=(struct RepairHash*)malloc(sizeof(struct RepairHash));
 426     if (size <= 0) {
 427         printf("Negative size for RepairHash\n");
 428         exit(-1);
 429     }
 430
 431     thisvar->size = size;
 432     thisvar->bucket = (struct RepairHashNode **) calloc(1,sizeof(struct RepairHashNode*)*size);
 433     thisvar->nodelist=0;
 434     thisvar->numelements = 0;
 435     return thisvar;
 436 }
 437
 438 #define REPAIRSIZE 100
 439 struct RepairHash * noargallocateRepairHash() {
 440     return allocateRepairHash(REPAIRSIZE);
 441 }
 442
 443 void freeRepairHash(struct RepairHash *thisvar) {
 444   struct RepairHashNode *ptr=thisvar->nodelist;
 445   free(thisvar->bucket);
 446   while(ptr) {
 447       struct RepairHashNode *next=ptr->lnext;
 448       free(ptr);
 449       ptr=next;
 450   }
 451   free(thisvar);
 452 }
 453
 454 #define SETFLAG (1<<31)
 455
 456 int addset(struct RepairHash *thisvar, int setv, int rule, int value, int data) {
 457   return addrelation(thisvar, setv||SETFLAG, rule, value,0,data);
 458 }
 459
 460 int addrelation(struct RepairHash *thisvar, int relation, int rule, int lvalue, int rvalue, int data) {
 461     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
 462
 463     struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
 464
 465     /* check that thisvar key/object pair isn't already here */
 466     /* TBD can be optimized for set v. relation */
 467     while (*ptr) {
 468         if ((*ptr)->setrelation == relation &&
 469             (*ptr)->rule==rule &&
 470             (*ptr)->lvalue==lvalue &&
 471             (*ptr)->rvalue==rvalue &&
 472             (*ptr)->data == data&&
 473             (*ptr)->data2 == 0) {
 474             return 0;
 475         }
 476         ptr = &((*ptr)->next);
 477     }
 478
 479     *ptr = allocateRepairHashNode(relation,rule,lvalue,rvalue, data,0,0);
 480     (*ptr)->lnext=thisvar->nodelist;
 481     thisvar->nodelist=*ptr;
 482     thisvar->numelements++;
 483     return 1;
 484 }
 485
 486 int addrelation2(struct RepairHash *thisvar, int relation, int rule, int lvalue, int rvalue, int data, int data2) {
 487     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
 488
 489     struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
 490
 491     /* check that thisvar key/object pair isn't already here */
 492     /* TBD can be optimized for set v. relation */
 493     while (*ptr) {
 494         if ((*ptr)->setrelation == relation &&
 495             (*ptr)->rule==rule &&
 496             (*ptr)->lvalue==lvalue &&
 497             (*ptr)->rvalue==rvalue &&
 498             (*ptr)->data == data &&
 499             (*ptr)->data2 == data2) {
 500             return 0;
 501         }
 502         ptr = &((*ptr)->next);
 503     }
 504
 505     *ptr = allocateRepairHashNode(relation,rule,lvalue,rvalue, data,data2,1);
 506     (*ptr)->lnext=thisvar->nodelist;
 507     thisvar->nodelist=*ptr;
 508     thisvar->numelements++;
 509     return 1;
 510 }
 511
 512 bool containsset(struct RepairHash *thisvar, int setv, int rule, int value) {
 513   return containsrelation(thisvar, setv||SETFLAG, rule, value,0);
 514 }
 515
 516 bool containsrelation(struct RepairHash *thisvar, int relation, int rule, int lvalue, int rvalue) {
 517     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
 518
 519     struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
 520
 521     /* check that thisvar key/object pair isn't already here */
 522     /*  TBD can be optimized for set v. relation */
 523     while (*ptr) {
 524         if ((*ptr)->setrelation == relation &&
 525             (*ptr)->rule==rule &&
 526             (*ptr)->lvalue==lvalue &&
 527             (*ptr)->rvalue==rvalue) {
 528             return true;
 529         }
 530         ptr = &((*ptr)->next);
 531     }
 532     return false;
 533 }
 534
 535 int getset(struct RepairHash *thisvar, int setv, int rule, int value) {
 536   return getrelation(thisvar, setv||SETFLAG, rule, value,0);
 537 }
 538
 539 int ismodify(struct RepairHash *thisvar, int relation, int rule, int lvalue,int rvalue) {
 540     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
 541
 542     struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
 543
 544     /* check that thisvar key/object pair isn't already here */
 545     /* TBD can be optimized for set v. relation */
 546     while (*ptr) {
 547         if ((*ptr)->setrelation == relation &&
 548             (*ptr)->rule==rule &&
 549             (*ptr)->lvalue==lvalue &&
 550             (*ptr)->rvalue==rvalue) {
 551           return (*ptr)->ismodify;
 552         }
 553         ptr = &((*ptr)->next);
 554     }
 555     return 0;
 556 }
 557
 558 int getrelation2(struct RepairHash *thisvar, int relation, int rule, int lvalue,int rvalue) {
 559     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
 560
 561     struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
 562
 563     /* check that thisvar key/object pair isn't already here */
 564     /* TBD can be optimized for set v. relation */
 565     while (*ptr) {
 566         if ((*ptr)->setrelation == relation &&
 567             (*ptr)->rule==rule &&
 568             (*ptr)->lvalue==lvalue &&
 569             (*ptr)->rvalue==rvalue) {
 570           return (*ptr)->data2;
 571         }
 572         ptr = &((*ptr)->next);
 573     }
 574     return 0;
 575 }
 576
 577 int getrelation(struct RepairHash *thisvar, int relation, int rule, int lvalue,int rvalue) {
 578     unsigned int hashkey = ((unsigned int)(relation ^ rule ^ lvalue ^ rvalue)) % thisvar->size;
 579
 580     struct RepairHashNode **ptr = &thisvar->bucket[hashkey];
 581
 582     /* check that this key/object pair isn't already here */
 583     /* TBD can be optimized for set v. relation */
 584     while (*ptr) {
 585         if ((*ptr)->setrelation == relation &&
 586             (*ptr)->rule==rule &&
 587             (*ptr)->lvalue==lvalue &&
 588             (*ptr)->rvalue==rvalue) {
 589           return (*ptr)->data;
 590         }
 591         ptr = &((*ptr)->next);
 592     }
 593     return 0;
 594 }