Robust/src/Runtime/ObjectHash.c

   1 #include "ObjectHash.h"
   2 #include <stdio.h>
   3 #ifdef DMALLOC
   4 #include "dmalloc.h"
   5 #endif
   6
   7 /* SIMPLE HASH ********************************************************/
   8 struct ObjectIterator* ObjectHashcreateiterator(struct ObjectHash * thisvar) {
   9     return allocateObjectIterator(thisvar->listhead);
  10 }
  11
  12 void ObjectHashiterator(struct ObjectHash *thisvar, struct ObjectIterator * it) {
  13   it->cur=thisvar->listhead;
  14 }
  15
  16 struct ObjectHash * noargallocateObjectHash() {
  17     return allocateObjectHash(100);
  18 }
  19
  20 struct ObjectHash * allocateObjectHash(int size) {
  21     struct ObjectHash *thisvar=(struct ObjectHash *)RUNMALLOC(sizeof(struct ObjectHash));
  22     if (size <= 0) {
  23         printf("Negative Hashtable size Exception\n");
  24         exit(-1);
  25     }
  26     thisvar->size = size;
  27     thisvar->bucket = (struct ObjectNode **) RUNMALLOC(sizeof(struct ObjectNode *)*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 freeObjectHash(struct ObjectHash *thisvar) {
  37     struct ObjectNode *ptr=thisvar->listhead;
  38     RUNFREE(thisvar->bucket);
  39     while(ptr) {
  40         struct ObjectNode *next=ptr->lnext;
  41         RUNFREE(ptr);
  42         ptr=next;
  43     }
  44     RUNFREE(thisvar);
  45 }
  46
  47 inline int ObjectHashcountset(struct ObjectHash * thisvar) {
  48     return thisvar->numelements;
  49 }
  50
  51 int ObjectHashfirstkey(struct ObjectHash *thisvar) {
  52   struct ObjectNode *ptr=thisvar->listhead;
  53   return ptr->key;
  54 }
  55
  56 int ObjectHashremove(struct ObjectHash *thisvar, int key) {
  57     unsigned int hashkey = (unsigned int)key % thisvar->size;
  58
  59     struct ObjectNode **ptr = &thisvar->bucket[hashkey];
  60     int i;
  61
  62     while (*ptr) {
  63       if ((*ptr)->key == key) {
  64           struct ObjectNode *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 void ObjectHashrehash(struct ObjectHash * thisvar) {
  87   int newsize=thisvar->size;
  88   struct ObjectNode ** newbucket = (struct ObjectNode **) RUNMALLOC(sizeof(struct ObjectNode *)*newsize);
  89   int i;
  90   for(i=thisvar->size-1;i>=0;i--) {
  91     struct ObjectNode *ptr;
  92     for(ptr=thisvar->bucket[i];ptr!=NULL;) {
  93       struct ObjectNode * nextptr=ptr->next;
  94       unsigned int newhashkey=(unsigned int)ptr->key % newsize;
  95       ptr->next=newbucket[newhashkey];
  96       newbucket[newhashkey]=ptr;
  97       ptr=nextptr;
  98     }
  99   }
 100   thisvar->size=newsize;
 101   RUNFREE(thisvar->bucket);
 102   thisvar->bucket=newbucket;
 103 }
 104
 105 int ObjectHashadd(struct ObjectHash * thisvar,int key, int data, int data2) {
 106   /* Rehash code */
 107   unsigned int hashkey;
 108   struct ObjectNode **ptr;
 109
 110   if (thisvar->numelements>=thisvar->size) {
 111     int newsize=2*thisvar->size+1;
 112     struct ObjectNode ** newbucket = (struct ObjectNode **) RUNMALLOC(sizeof(struct ObjectNode *)*newsize);
 113     int i;
 114     for(i=thisvar->size-1;i>=0;i--) {
 115         struct ObjectNode *ptr;
 116         for(ptr=thisvar->bucket[i];ptr!=NULL;) {
 117             struct ObjectNode * nextptr=ptr->next;
 118             unsigned int newhashkey=(unsigned int)ptr->key % newsize;
 119             ptr->next=newbucket[newhashkey];
 120             newbucket[newhashkey]=ptr;
 121             ptr=nextptr;
 122         }
 123     }
 124     thisvar->size=newsize;
 125     RUNFREE(thisvar->bucket);
 126     thisvar->bucket=newbucket;
 127   }
 128
 129   hashkey = (unsigned int)key % thisvar->size;
 130   ptr = &thisvar->bucket[hashkey];
 131
 132   {
 133     struct ObjectNode *node=RUNMALLOC(sizeof(struct ObjectNode));
 134     node->data=data;
 135     node->data2=data2;
 136     node->key=key;
 137     node->next=(*ptr);
 138     *ptr=node;
 139     if (thisvar->listhead==NULL) {
 140       thisvar->listhead=node;
 141       thisvar->listtail=node;
 142       node->lnext=NULL;
 143       node->lprev=NULL;
 144     } else {
 145       node->lprev=NULL;
 146       node->lnext=thisvar->listhead;
 147       thisvar->listhead->lprev=node;
 148       thisvar->listhead=node;
 149     }
 150   }
 151
 152   thisvar->numelements++;
 153   return 1;
 154 }
 155
 156 bool ObjectHashcontainskey(struct ObjectHash *thisvar,int key) {
 157     unsigned int hashkey = (unsigned int)key % thisvar->size;
 158
 159     struct ObjectNode *ptr = thisvar->bucket[hashkey];
 160     while (ptr) {
 161         if (ptr->key == key) {
 162             /* we already have thisvar object
 163                stored in the hash so just return */
 164             return true;
 165         }
 166         ptr = ptr->next;
 167     }
 168     return false;
 169 }
 170
 171 bool ObjectHashcontainskeydata(struct ObjectHash *thisvar, int key, int data) {
 172     unsigned int hashkey = (unsigned int)key % thisvar->size;
 173
 174     struct ObjectNode *ptr = thisvar->bucket[hashkey];
 175     while (ptr) {
 176         if (ptr->key == key && ptr->data == data) {
 177             /* we already have thisvar object
 178                stored in the hash so just return*/
 179             return true;
 180         }
 181         ptr = ptr->next;
 182     }
 183     return false;
 184 }
 185
 186 int ObjectHashcount(struct ObjectHash *thisvar,int key) {
 187     unsigned int hashkey = (unsigned int)key % thisvar->size;
 188     int count = 0;
 189
 190     struct ObjectNode *ptr = thisvar->bucket[hashkey];
 191     while (ptr) {
 192         if (ptr->key == key) {
 193             count++;
 194         }
 195         ptr = ptr->next;
 196     }
 197     return count;
 198 }
 199
 200 int ObjectHashget(struct ObjectHash *thisvar, int key, int *data, int *data2) {
 201     unsigned int hashkey = (unsigned int)key % thisvar->size;
 202
 203     struct ObjectNode *ptr = thisvar->bucket[hashkey];
 204     while (ptr) {
 205         if (ptr->key == key) {
 206             *data = ptr->data;
 207             *data2 = ptr->data2;
 208             return 1; /* success */
 209         }
 210         ptr = ptr->next;
 211     }
 212
 213     return 0; /* failure */
 214 }
 215
 216 inline struct ObjectIterator * noargallocateObjectIterator() {
 217     return (struct ObjectIterator*)RUNMALLOC(sizeof(struct ObjectIterator));
 218 }
 219
 220 inline struct ObjectIterator * allocateObjectIterator(struct ObjectNode *start) {
 221     struct ObjectIterator *thisvar=(struct ObjectIterator*)RUNMALLOC(sizeof(struct ObjectIterator));
 222     thisvar->cur = start;
 223     return thisvar;
 224 }
 225
 226 inline int ObjhasNext(struct ObjectIterator *thisvar) {
 227   return (thisvar->cur!=NULL);
 228 }
 229
 230 inline int Objnext(struct ObjectIterator *thisvar) {
 231   int curr=thisvar->cur->data;
 232   thisvar->cur=thisvar->cur->next;
 233 }
 234
 235 inline int Objkey(struct ObjectIterator *thisvar) {
 236   return thisvar->cur->key;
 237 }