apdf/goo/GHash.cc

   1 //========================================================================
   2 //
   3 // GHash.cc
   4 //
   5 // Copyright 2001-2003 Glyph & Cog, LLC
   6 //
   7 //========================================================================
   8
   9 #include <aconf.h>
  10
  11 #ifdef USE_GCC_PRAGMAS
  12 #pragma implementation
  13 #endif
  14
  15 #include "gmem.h"
  16 #include "GString.h"
  17 #include "GHash.h"
  18
  19 //------------------------------------------------------------------------
  20
  21 struct GHashBucket {
  22   GString *key;
  23   union {
  24     void *p;
  25     int i;
  26   } val;
  27   GHashBucket *next;
  28 };
  29
  30 struct GHashIter {
  31   int h;
  32   GHashBucket *p;
  33 };
  34
  35 //------------------------------------------------------------------------
  36
  37 GHash::GHash(GBool deleteKeysA) {
  38   int h;
  39
  40   deleteKeys = deleteKeysA;
  41   size = 7;
  42   tab = (GHashBucket **)gmallocn(size, sizeof(GHashBucket *));
  43   for (h = 0; h < size; ++h) {
  44     tab[h] = NULL;
  45   }
  46   len = 0;
  47 }
  48
  49 GHash::~GHash() {
  50   GHashBucket *p;
  51   int h;
  52
  53   for (h = 0; h < size; ++h) {
  54     while (tab[h]) {
  55       p = tab[h];
  56       tab[h] = p->next;
  57       if (deleteKeys) {
  58         delete p->key;
  59       }
  60       delete p;
  61     }
  62   }
  63   gfree(tab);
  64 }
  65
  66 void GHash::add(GString *key, void *val) {
  67   GHashBucket *p;
  68   int h;
  69
  70   // expand the table if necessary
  71   if (len >= size) {
  72     expand();
  73   }
  74
  75   // add the new symbol
  76   p = new GHashBucket;
  77   p->key = key;
  78   p->val.p = val;
  79   h = hash(key);
  80   p->next = tab[h];
  81   tab[h] = p;
  82   ++len;
  83 }
  84
  85 void GHash::add(GString *key, int val) {
  86   GHashBucket *p;
  87   int h;
  88
  89   // expand the table if necessary
  90   if (len >= size) {
  91     expand();
  92   }
  93
  94   // add the new symbol
  95   p = new GHashBucket;
  96   p->key = key;
  97   p->val.i = val;
  98   h = hash(key);
  99   p->next = tab[h];
 100   tab[h] = p;
 101   ++len;
 102 }
 103
 104 void GHash::replace(GString *key, void *val) {
 105   GHashBucket *p;
 106   int h;
 107
 108   if ((p = find(key, &h))) {
 109     p->val.p = val;
 110     delete key;
 111   } else {
 112     add(key, val);
 113   }
 114 }
 115
 116 void GHash::replace(GString *key, int val) {
 117   GHashBucket *p;
 118   int h;
 119
 120   if ((p = find(key, &h))) {
 121     p->val.i = val;
 122     delete key;
 123   } else {
 124     add(key, val);
 125   }
 126 }
 127
 128 void *GHash::lookup(GString *key) {
 129   GHashBucket *p;
 130   int h;
 131
 132   if (!(p = find(key, &h))) {
 133     return NULL;
 134   }
 135   return p->val.p;
 136 }
 137
 138 int GHash::lookupInt(GString *key) {
 139   GHashBucket *p;
 140   int h;
 141
 142   if (!(p = find(key, &h))) {
 143     return 0;
 144   }
 145   return p->val.i;
 146 }
 147
 148 void *GHash::lookup(char *key) {
 149   GHashBucket *p;
 150   int h;
 151
 152   if (!(p = find(key, &h))) {
 153     return NULL;
 154   }
 155   return p->val.p;
 156 }
 157
 158 int GHash::lookupInt(char *key) {
 159   GHashBucket *p;
 160   int h;
 161
 162   if (!(p = find(key, &h))) {
 163     return 0;
 164   }
 165   return p->val.i;
 166 }
 167
 168 void *GHash::remove(GString *key) {
 169   GHashBucket *p;
 170   GHashBucket **q;
 171   void *val;
 172   int h;
 173
 174   if (!(p = find(key, &h))) {
 175     return NULL;
 176   }
 177   q = &tab[h];
 178   while (*q != p) {
 179     q = &((*q)->next);
 180   }
 181   *q = p->next;
 182   if (deleteKeys) {
 183     delete p->key;
 184   }
 185   val = p->val.p;
 186   delete p;
 187   --len;
 188   return val;
 189 }
 190
 191 int GHash::removeInt(GString *key) {
 192   GHashBucket *p;
 193   GHashBucket **q;
 194   int val;
 195   int h;
 196
 197   if (!(p = find(key, &h))) {
 198     return 0;
 199   }
 200   q = &tab[h];
 201   while (*q != p) {
 202     q = &((*q)->next);
 203   }
 204   *q = p->next;
 205   if (deleteKeys) {
 206     delete p->key;
 207   }
 208   val = p->val.i;
 209   delete p;
 210   --len;
 211   return val;
 212 }
 213
 214 void *GHash::remove(char *key) {
 215   GHashBucket *p;
 216   GHashBucket **q;
 217   void *val;
 218   int h;
 219
 220   if (!(p = find(key, &h))) {
 221     return NULL;
 222   }
 223   q = &tab[h];
 224   while (*q != p) {
 225     q = &((*q)->next);
 226   }
 227   *q = p->next;
 228   if (deleteKeys) {
 229     delete p->key;
 230   }
 231   val = p->val.p;
 232   delete p;
 233   --len;
 234   return val;
 235 }
 236
 237 int GHash::removeInt(char *key) {
 238   GHashBucket *p;
 239   GHashBucket **q;
 240   int val;
 241   int h;
 242
 243   if (!(p = find(key, &h))) {
 244     return 0;
 245   }
 246   q = &tab[h];
 247   while (*q != p) {
 248     q = &((*q)->next);
 249   }
 250   *q = p->next;
 251   if (deleteKeys) {
 252     delete p->key;
 253   }
 254   val = p->val.i;
 255   delete p;
 256   --len;
 257   return val;
 258 }
 259
 260 void GHash::startIter(GHashIter **iter) {
 261   *iter = new GHashIter;
 262   (*iter)->h = -1;
 263   (*iter)->p = NULL;
 264 }
 265
 266 GBool GHash::getNext(GHashIter **iter, GString **key, void **val) {
 267   if (!*iter) {
 268     return gFalse;
 269   }
 270   if ((*iter)->p) {
 271     (*iter)->p = (*iter)->p->next;
 272   }
 273   while (!(*iter)->p) {
 274     if (++(*iter)->h == size) {
 275       delete *iter;
 276       *iter = NULL;
 277       return gFalse;
 278     }
 279     (*iter)->p = tab[(*iter)->h];
 280   }
 281   *key = (*iter)->p->key;
 282   *val = (*iter)->p->val.p;
 283   return gTrue;
 284 }
 285
 286 GBool GHash::getNext(GHashIter **iter, GString **key, int *val) {
 287   if (!*iter) {
 288     return gFalse;
 289   }
 290   if ((*iter)->p) {
 291     (*iter)->p = (*iter)->p->next;
 292   }
 293   while (!(*iter)->p) {
 294     if (++(*iter)->h == size) {
 295       delete *iter;
 296       *iter = NULL;
 297       return gFalse;
 298     }
 299     (*iter)->p = tab[(*iter)->h];
 300   }
 301   *key = (*iter)->p->key;
 302   *val = (*iter)->p->val.i;
 303   return gTrue;
 304 }
 305
 306 void GHash::killIter(GHashIter **iter) {
 307   delete *iter;
 308   *iter = NULL;
 309 }
 310
 311 void GHash::expand() {
 312   GHashBucket **oldTab;
 313   GHashBucket *p;
 314   int oldSize, h, i;
 315
 316   oldSize = size;
 317   oldTab = tab;
 318   size = 2*size + 1;
 319   tab = (GHashBucket **)gmallocn(size, sizeof(GHashBucket *));
 320   for (h = 0; h < size; ++h) {
 321     tab[h] = NULL;
 322   }
 323   for (i = 0; i < oldSize; ++i) {
 324     while (oldTab[i]) {
 325       p = oldTab[i];
 326       oldTab[i] = oldTab[i]->next;
 327       h = hash(p->key);
 328       p->next = tab[h];
 329       tab[h] = p;
 330     }
 331   }
 332   gfree(oldTab);
 333 }
 334
 335 GHashBucket *GHash::find(GString *key, int *h) {
 336   GHashBucket *p;
 337
 338   *h = hash(key);
 339   for (p = tab[*h]; p; p = p->next) {
 340     if (!p->key->cmp(key)) {
 341       return p;
 342     }
 343   }
 344   return NULL;
 345 }
 346
 347 GHashBucket *GHash::find(char *key, int *h) {
 348   GHashBucket *p;
 349
 350   *h = hash(key);
 351   for (p = tab[*h]; p; p = p->next) {
 352     if (!p->key->cmp(key)) {
 353       return p;
 354     }
 355   }
 356   return NULL;
 357 }
 358
 359 int GHash::hash(GString *key) {
 360   char *p;
 361   unsigned int h;
 362   int i;
 363
 364   h = 0;
 365   for (p = key->getCString(), i = 0; i < key->getLength(); ++p, ++i) {
 366     h = 17 * h + (int)(*p & 0xff);
 367   }
 368   return (int)(h % size);
 369 }
 370
 371 int GHash::hash(char *key) {
 372   char *p;
 373   unsigned int h;
 374
 375   h = 0;
 376   for (p = key; *p; ++p) {
 377     h = 17 * h + (int)(*p & 0xff);
 378   }
 379   return (int)(h % size);
 380 }