source/libs/poppler/poppler-src/goo/GooHash.cc

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