Robust/src/Runtime/SimpleHash.c

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