Robust/src/Runtime/SimpleHash.c

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