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 void RuntimeHashrehash(struct RuntimeHash * thisvar) {
  84   int newsize=thisvar->size;
  85   struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
  86   int i;
  87   for(i=thisvar->size-1;i>=0;i--) {
  88     struct RuntimeNode *ptr;
  89     for(ptr=thisvar->bucket[i];ptr!=NULL;) {
  90       struct RuntimeNode * nextptr=ptr->next;
  91       unsigned int newhashkey=(unsigned int)ptr->key % newsize;
  92       ptr->next=newbucket[newhashkey];
  93       newbucket[newhashkey]=ptr;
  94       ptr=nextptr;
  95     }
  96   }
  97   thisvar->size=newsize;
  98   RUNFREE(thisvar->bucket);
  99   thisvar->bucket=newbucket;
 100 }
 101
 102 int RuntimeHashadd(struct RuntimeHash * thisvar,int key, int data) {
 103   /* Rehash code */
 104   unsigned int hashkey;
 105   struct RuntimeNode **ptr;
 106
 107   if (thisvar->numelements>=thisvar->size) {
 108     int newsize=2*thisvar->size+1;
 109     struct RuntimeNode ** newbucket = (struct RuntimeNode **) RUNMALLOC(sizeof(struct RuntimeNode *)*newsize);
 110     int i;
 111     for(i=thisvar->size-1;i>=0;i--) {
 112         struct RuntimeNode *ptr;
 113         for(ptr=thisvar->bucket[i];ptr!=NULL;) {
 114             struct RuntimeNode * nextptr=ptr->next;
 115             unsigned int newhashkey=(unsigned int)ptr->key % newsize;
 116             ptr->next=newbucket[newhashkey];
 117             newbucket[newhashkey]=ptr;
 118             ptr=nextptr;
 119         }
 120     }
 121     thisvar->size=newsize;
 122     RUNFREE(thisvar->bucket);
 123     thisvar->bucket=newbucket;
 124   }
 125
 126   hashkey = (unsigned int)key % thisvar->size;
 127   ptr = &thisvar->bucket[hashkey];
 128
 129   /* check that thisvar key/object pair isn't already here */
 130   /* TBD can be optimized for set v. relation */
 131
 132   while (*ptr) {
 133     if ((*ptr)->key == key && (*ptr)->data == data) {
 134       return 0;
 135     }
 136     ptr = &((*ptr)->next);
 137   }
 138
 139   {
 140     struct RuntimeNode *node=RUNMALLOC(sizeof(struct RuntimeNode));
 141     node->data=data;
 142     node->key=key;
 143     node->next=(*ptr);
 144     *ptr=node;
 145     if (thisvar->listhead==NULL) {
 146       thisvar->listhead=node;
 147       thisvar->listtail=node;
 148       node->lnext=NULL;
 149       node->lprev=NULL;
 150     } else {
 151       node->lprev=NULL;
 152       node->lnext=thisvar->listhead;
 153       thisvar->listhead->lprev=node;
 154       thisvar->listhead=node;
 155     }
 156   }
 157
 158   thisvar->numelements++;
 159   return 1;
 160 }
 161
 162 bool RuntimeHashcontainskey(struct RuntimeHash *thisvar,int key) {
 163     unsigned int hashkey = (unsigned int)key % thisvar->size;
 164
 165     struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 166     while (ptr) {
 167         if (ptr->key == key) {
 168             /* we already have thisvar object
 169                stored in the hash so just return */
 170             return true;
 171         }
 172         ptr = ptr->next;
 173     }
 174     return false;
 175 }
 176
 177 bool RuntimeHashcontainskeydata(struct RuntimeHash *thisvar, int key, int data) {
 178     unsigned int hashkey = (unsigned int)key % thisvar->size;
 179
 180     struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 181     while (ptr) {
 182         if (ptr->key == key && ptr->data == data) {
 183             /* we already have thisvar object
 184                stored in the hash so just return*/
 185             return true;
 186         }
 187         ptr = ptr->next;
 188     }
 189     return false;
 190 }
 191
 192 int RuntimeHashcount(struct RuntimeHash *thisvar,int key) {
 193     unsigned int hashkey = (unsigned int)key % thisvar->size;
 194     int count = 0;
 195
 196     struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 197     while (ptr) {
 198         if (ptr->key == key) {
 199             count++;
 200         }
 201         ptr = ptr->next;
 202     }
 203     return count;
 204 }
 205
 206 struct RuntimeHash * RuntimeHashimageSet(struct RuntimeHash *thisvar, int key) {
 207   struct RuntimeHash * newset=allocateRuntimeHash(2*RuntimeHashcount(thisvar,key)+4);
 208   unsigned int hashkey = (unsigned int)key % thisvar->size;
 209
 210   struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 211   while (ptr) {
 212     if (ptr->key == key) {
 213         RuntimeHashadd(newset,ptr->data,ptr->data);
 214     }
 215     ptr = ptr->next;
 216   }
 217   return newset;
 218 }
 219
 220 int RuntimeHashget(struct RuntimeHash *thisvar, int key, int *data) {
 221     unsigned int hashkey = (unsigned int)key % thisvar->size;
 222
 223     struct RuntimeNode *ptr = thisvar->bucket[hashkey];
 224     while (ptr) {
 225         if (ptr->key == key) {
 226             *data = ptr->data;
 227             return 1; /* success */
 228         }
 229         ptr = ptr->next;
 230     }
 231
 232     return 0; /* failure */
 233 }
 234
 235 inline struct RuntimeIterator * noargallocateRuntimeIterator() {
 236     return (struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
 237 }
 238
 239 inline struct RuntimeIterator * allocateRuntimeIterator(struct RuntimeNode *start) {
 240     struct RuntimeIterator *thisvar=(struct RuntimeIterator*)RUNMALLOC(sizeof(struct RuntimeIterator));
 241     thisvar->cur = start;
 242     return thisvar;
 243 }
 244
 245 inline int RunhasNext(struct RuntimeIterator *thisvar) {
 246   return (thisvar->cur!=NULL);
 247 }
 248
 249 inline int Runnext(struct RuntimeIterator *thisvar) {
 250   int curr=thisvar->cur->data;
 251   thisvar->cur=thisvar->cur->next;
 252 }
 253
 254 inline int Runkey(struct RuntimeIterator *thisvar) {
 255   return thisvar->cur->key;
 256 }