Robust/src/Runtime/SimpleHash.c

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