Robust/src/Runtime/SimpleHash.c

   1 #include "SimpleHash.h"
   2 #ifdef RAW
   3 #include <raw.h>
   4 #else
   5 #include <stdio.h>
   6 #endif
   7 #ifdef DMALLOC
   8 #include "dmalloc.h"
   9 #endif
  10
  11 /* SIMPLE HASH ********************************************************/
  12 struct RuntimeIterator* RuntimeHashcreateiterator(struct RuntimeHash * thisvar) {
  13     return allocateRuntimeIterator(thisvar->listhead);
  14 }
  15
  16 void RuntimeHashiterator(struct RuntimeHash *thisvar, struct RuntimeIterator * it) {
  17   it->cur=thisvar->listhead;
  18 }
  19
  20 struct RuntimeHash * noargallocateRuntimeHash() {
  21     return allocateRuntimeHash(100);
  22 }
  23
  24 struct RuntimeHash * allocateRuntimeHash(int size) {
  25     struct RuntimeHash *thisvar;//=(struct RuntimeHash *)RUNMALLOC(sizeof(struct RuntimeHash));
  26     if (size <= 0) {
  27 #ifdef RAW
  28                 raw_test_done(0xb001);
  29 #else
  30         printf("Negative Hashtable size Exception\n");
  31                 exit(-1);
  32 #endif
  33     }
  34         thisvar=(struct RuntimeHash *)RUNMALLOC(sizeof(struct RuntimeHash));
  35     thisvar->size = size;
  36     thisvar->bucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*size);
  37     /* Set allocation blocks*/
  38     thisvar->listhead=NULL;
  39     thisvar->listtail=NULL;
  40     /*Set data counts*/
  41     thisvar->numelements = 0;
  42     return thisvar;
  43 }
  44
  45 void freeRuntimeHash(struct RuntimeHash *thisvar) {
  46     struct RuntimeNode *ptr=thisvar->listhead;
  47     RUNFREE(thisvar->bucket);
  48     while(ptr) {
  49         struct RuntimeNode *next=ptr->lnext;
  50         RUNFREE(ptr);
  51         ptr=next;
  52     }
  53     RUNFREE(thisvar);
  54 }
  55
  56 inline int RuntimeHashcountset(struct RuntimeHash * thisvar) {
  57     return thisvar->numelements;
  58 }
  59
  60 int RuntimeHashfirstkey(struct RuntimeHash *thisvar) {
  61   struct RuntimeNode *ptr=thisvar->listhead;
  62   return ptr->key;
  63 }
  64
  65 int RuntimeHashremovekey(struct RuntimeHash *thisvar, int key) {
  66     unsigned int hashkey = (unsigned int)key % thisvar->size;
  67
  68     struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
  69     int i;
  70
  71     while (*ptr) {
  72         if ((*ptr)->key == key) {
  73           struct RuntimeNode *toremove=*ptr;
  74           *ptr=(*ptr)->next;
  75
  76           if (toremove->lprev!=NULL) {
  77             toremove->lprev->lnext=toremove->lnext;
  78           } else {
  79             thisvar->listhead=toremove->lnext;
  80           }
  81           if (toremove->lnext!=NULL) {
  82             toremove->lnext->lprev=toremove->lprev;
  83           } else{
  84             thisvar->listtail=toremove->lprev;
  85           }
  86           RUNFREE(toremove);
  87
  88           thisvar->numelements--;
  89           return 1;
  90         }
  91         ptr = &((*ptr)->next);
  92     }
  93
  94     return 0;
  95 }
  96
  97 int RuntimeHashremove(struct RuntimeHash *thisvar, int key, int data) {
  98     unsigned int hashkey = (unsigned int)key % thisvar->size;
  99
 100     struct RuntimeNode **ptr = &thisvar->bucket[hashkey];
 101     int i;
 102
 103     while (*ptr) {
 104         if ((*ptr)->key == key && (*ptr)->data == data) {
 105           struct RuntimeNode *toremove=*ptr;
 106           *ptr=(*ptr)->next;
 107
 108           if (toremove->lprev!=NULL) {
 109             toremove->lprev->lnext=toremove->lnext;
 110           } else {
 111             thisvar->listhead=toremove->lnext;
 112           }
 113           if (toremove->lnext!=NULL) {
 114             toremove->lnext->lprev=toremove->lprev;
 115           } else {
 116             thisvar->listtail=toremove->lprev;
 117           }
 118           RUNFREE(toremove);
 119
 120           thisvar->numelements--;
 121           return 1;
 122         }
 123         ptr = &((*ptr)->next);
 124     }
 125
 126     return 0;
 127 }
 128
 129 void RuntimeHashrehash(struct RuntimeHash * thisvar) {
 130   int newsize=thisvar->size;
 131   struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
 132   int i;
 133   for(i=thisvar->size-1;i>=0;i--) {
 134     struct RuntimeNode *ptr;
 135     for(ptr=thisvar->bucket[i];ptr!=NULL;) {
 136       struct RuntimeNode * nextptr=ptr->next;
 137       unsigned int newhashkey=(unsigned int)ptr->key % newsize;
 138       ptr->next=newbucket[newhashkey];
 139       newbucket[newhashkey]=ptr;
 140       ptr=nextptr;
 141     }
 142   }
 143   thisvar->size=newsize;
 144   RUNFREE(thisvar->bucket);
 145   thisvar->bucket=newbucket;
 146 }
 147
 148 int RuntimeHashadd(struct RuntimeHash * thisvar,int key, int data) {
 149   /* Rehash code */
 150   unsigned int hashkey;
 151   struct RuntimeNode **ptr;
 152
 153   if (thisvar->numelements>=thisvar->size) {
 154     int newsize=2*thisvar->size+1;
 155     struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
 156     int i;
 157     for(i=thisvar->size-1;i>=0;i--) {
 158         struct RuntimeNode *ptr;
 159         for(ptr=thisvar->bucket[i];ptr!=NULL;) {
 160             struct RuntimeNode * nextptr=ptr->next;
 161             unsigned int newhashkey=(unsigned int)ptr->key % newsize;
 162             ptr->next=newbucket[newhashkey];
 163             newbucket[newhashkey]=ptr;
 164             ptr=nextptr;
 165         }
 166     }
 167     thisvar->size=newsize;
 168     RUNFREE(thisvar->bucket);
 169     thisvar->bucket=newbucket;
 170   }
 171
 172   hashkey = (unsigned int)key % thisvar->size;
 173   ptr = &thisvar->bucket[hashkey];
 174
 175   /* check that thisvar key/object pair isn't already here */
 176   /* TBD can be optimized for set v. relation */
 177
 178   while (*ptr) {
 179     if ((*ptr)->key == key && (*ptr)->data == data) {
 180       return 0;
 181     }
 182     ptr = &((*ptr)->next);
 183   }
 184
 185   {
 186     struct RuntimeNode *node=RUNMALLOC(sizeof(struct RuntimeNode));
 187     node->data=data;
 188     node->key=key;
 189     node->next=(*ptr);
 190     *ptr=node;
 191     if (thisvar->listhead==NULL) {
 192       thisvar->listhead=node;
 193       thisvar->listtail=node;
 194       node->lnext=NULL;
 195       node->lprev=NULL;
 196     } else {
 197       node->lprev=NULL;
 198       node->lnext=thisvar->listhead;
 199       thisvar->listhead->lprev=node;
 200       thisvar->listhead=node;
 201     }
 202   }
 203
 204   thisvar->numelements++;
 205   return 1;
 206 }
 207
 208 #ifdef RAW
 209 int RuntimeHashadd_I(struct RuntimeHash * thisvar,int key, int data) {
 210   /* Rehash code */
 211   unsigned int hashkey;
 212   struct RuntimeNode **ptr;
 213
 214   if (thisvar->numelements>=thisvar->size) {
 215     int newsize=2*thisvar->size+1;
 216     struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC_I(sizeof(struct RuntimeNode *)*newsize);
 217     int i;
 218     for(i=thisvar->size-1;i>=0;i--) {
 219         struct RuntimeNode *ptr;
 220         for(ptr=thisvar->bucket[i];ptr!=NULL;) {
 221             struct RuntimeNode * nextptr=ptr->next;
 222             unsigned int newhashkey=(unsigned int)ptr->key % newsize;
 223             ptr->next=newbucket[newhashkey];
 224             newbucket[newhashkey]=ptr;
 225             ptr=nextptr;
 226         }
 227     }
 228     thisvar->size=newsize;
 229     RUNFREE(thisvar->bucket);
 230     thisvar->bucket=newbucket;
 231   }
 232
 233   hashkey = (unsigned int)key % thisvar->size;
 234   ptr = &thisvar->bucket[hashkey];
 235
 236   /* check that thisvar key/object pair isn't already here */
 237   /* TBD can be optimized for set v. relation */
 238
 239   while (*ptr) {
 240     if ((*ptr)->key == key && (*ptr)->data == data) {
 241       return 0;
 242     }
 243     ptr = &((*ptr)->next);
 244   }
 245
 246   {
 247     struct RuntimeNode *node=RUNMALLOC_I(sizeof(struct RuntimeNode));
 248     node->data=data;
 249     node->key=key;
 250     node->next=(*ptr);
 251     *ptr=node;
 252     if (thisvar->listhead==NULL) {
 253       thisvar->listhead=node;
 254       thisvar->listtail=node;
 255       node->lnext=NULL;
 256       node->lprev=NULL;
 257     } else {
 258       node->lprev=NULL;
 259       node->lnext=thisvar->listhead;
 260       thisvar->listhead->lprev=node;
 261       thisvar->listhead=node;
 262     }
 263   }
 264
 265   thisvar->numelements++;
 266   return 1;
 267 }
 268 #endif
 269
 270 bool RuntimeHashcontainskey(struct RuntimeHash *thisvar,int key) {
 271     unsigned int hashkey = (unsigned int)key % thisvar->size;
 272
 273     struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 274     while (ptr) {
 275         if (ptr->key == key) {
 276             /* we already have thisvar object
 277                stored in the hash so just return */
 278             return true;
 279         }
 280         ptr = ptr->next;
 281     }
 282     return false;
 283 }
 284
 285 bool RuntimeHashcontainskeydata(struct RuntimeHash *thisvar, int key, int data) {
 286     unsigned int hashkey = (unsigned int)key % thisvar->size;
 287
 288     struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 289     while (ptr) {
 290         if (ptr->key == key && ptr->data == data) {
 291             /* we already have thisvar object
 292                stored in the hash so just return*/
 293             return true;
 294         }
 295         ptr = ptr->next;
 296     }
 297     return false;
 298 }
 299
 300 int RuntimeHashcount(struct RuntimeHash *thisvar,int key) {
 301     unsigned int hashkey = (unsigned int)key % thisvar->size;
 302     int count = 0;
 303
 304     struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 305     while (ptr) {
 306         if (ptr->key == key) {
 307             count++;
 308         }
 309         ptr = ptr->next;
 310     }
 311     return count;
 312 }
 313
 314 struct RuntimeHash * RuntimeHashimageSet(struct RuntimeHash *thisvar, int key) {
 315   struct RuntimeHash * newset=allocateRuntimeHash(2*RuntimeHashcount(thisvar,key)+4);
 316   unsigned int hashkey = (unsigned int)key % thisvar->size;
 317
 318   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 319   while (ptr) {
 320     if (ptr->key == key) {
 321         RuntimeHashadd(newset,ptr->data,ptr->data);
 322     }
 323     ptr = ptr->next;
 324   }
 325   return newset;
 326 }
 327
 328 int RuntimeHashget(struct RuntimeHash *thisvar, int key, int *data) {
 329     unsigned int hashkey = (unsigned int)key % thisvar->size;
 330
 331     struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 332     while (ptr) {
 333         if (ptr->key == key) {
 334             *data = ptr->data;
 335             return 1; /* success */
 336         }
 337         ptr = ptr->next;
 338     }
 339
 340     return 0; /* failure */
 341 }
 342
 343 inline struct RuntimeIterator * noargallocateRuntimeIterator() {
 344     return (struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
 345 }
 346
 347 inline struct RuntimeIterator * allocateRuntimeIterator(struct RuntimeNode *start) {
 348     struct RuntimeIterator *thisvar=(struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
 349     thisvar->cur = start;
 350     return thisvar;
 351 }
 352
 353 inline int RunhasNext(struct RuntimeIterator *thisvar) {
 354   return (thisvar->cur!=NULL);
 355 }
 356
 357 inline int Runnext(struct RuntimeIterator *thisvar) {
 358   int curr=thisvar->cur->data;
 359   thisvar->cur=thisvar->cur->lnext;
 360   return curr;
 361 }
 362
 363 inline int Runkey(struct RuntimeIterator *thisvar) {
 364   return thisvar->cur->key;
 365 }