pdf2swf/xpdf/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 **)gmalloc(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::lookup(GString *key) {
 105   GHashBucket *p;
 106   int h;
 107
 108   if (!(p = find(key, &h))) {
 109     return NULL;
 110   }
 111   return p->val.p;
 112 }
 113
 114 int GHash::lookupInt(GString *key) {
 115   GHashBucket *p;
 116   int h;
 117
 118   if (!(p = find(key, &h))) {
 119     return 0;
 120   }
 121   return p->val.i;
 122 }
 123
 124 void *GHash::lookup(char *key) {
 125   GHashBucket *p;
 126   int h;
 127
 128   if (!(p = find(key, &h))) {
 129     return NULL;
 130   }
 131   return p->val.p;
 132 }
 133
 134 int GHash::lookupInt(char *key) {
 135   GHashBucket *p;
 136   int h;
 137
 138   if (!(p = find(key, &h))) {
 139     return 0;
 140   }
 141   return p->val.i;
 142 }
 143
 144 void *GHash::remove(GString *key) {
 145   GHashBucket *p;
 146   GHashBucket **q;
 147   void *val;
 148   int h;
 149
 150   if (!(p = find(key, &h))) {
 151     return NULL;
 152   }
 153   q = &tab[h];
 154   while (*q != p) {
 155     q = &((*q)->next);
 156   }
 157   *q = p->next;
 158   if (deleteKeys) {
 159     delete p->key;
 160   }
 161   val = p->val.p;
 162   delete p;
 163   --len;
 164   return val;
 165 }
 166
 167 int GHash::removeInt(GString *key) {
 168   GHashBucket *p;
 169   GHashBucket **q;
 170   int val;
 171   int h;
 172
 173   if (!(p = find(key, &h))) {
 174     return 0;
 175   }
 176   q = &tab[h];
 177   while (*q != p) {
 178     q = &((*q)->next);
 179   }
 180   *q = p->next;
 181   if (deleteKeys) {
 182     delete p->key;
 183   }
 184   val = p->val.i;
 185   delete p;
 186   --len;
 187   return val;
 188 }
 189
 190 void *GHash::remove(char *key) {
 191   GHashBucket *p;
 192   GHashBucket **q;
 193   void *val;
 194   int h;
 195
 196   if (!(p = find(key, &h))) {
 197     return NULL;
 198   }
 199   q = &tab[h];
 200   while (*q != p) {
 201     q = &((*q)->next);
 202   }
 203   *q = p->next;
 204   if (deleteKeys) {
 205     delete p->key;
 206   }
 207   val = p->val.p;
 208   delete p;
 209   --len;
 210   return val;
 211 }
 212
 213 int GHash::removeInt(char *key) {
 214   GHashBucket *p;
 215   GHashBucket **q;
 216   int val;
 217   int h;
 218
 219   if (!(p = find(key, &h))) {
 220     return 0;
 221   }
 222   q = &tab[h];
 223   while (*q != p) {
 224     q = &((*q)->next);
 225   }
 226   *q = p->next;
 227   if (deleteKeys) {
 228     delete p->key;
 229   }
 230   val = p->val.i;
 231   delete p;
 232   --len;
 233   return val;
 234 }
 235
 236 void GHash::startIter(GHashIter **iter) {
 237   *iter = new GHashIter;
 238   (*iter)->h = -1;
 239   (*iter)->p = NULL;
 240 }
 241
 242 GBool GHash::getNext(GHashIter **iter, GString **key, void **val) {
 243   if (!*iter) {
 244     return gFalse;
 245   }
 246   if ((*iter)->p) {
 247     (*iter)->p = (*iter)->p->next;
 248   }
 249   while (!(*iter)->p) {
 250     if (++(*iter)->h == size) {
 251       delete *iter;
 252       *iter = NULL;
 253       return gFalse;
 254     }
 255     (*iter)->p = tab[(*iter)->h];
 256   }
 257   *key = (*iter)->p->key;
 258   *val = (*iter)->p->val.p;
 259   return gTrue;
 260 }
 261
 262 GBool GHash::getNext(GHashIter **iter, GString **key, int *val) {
 263   if (!*iter) {
 264     return gFalse;
 265   }
 266   if ((*iter)->p) {
 267     (*iter)->p = (*iter)->p->next;
 268   }
 269   while (!(*iter)->p) {
 270     if (++(*iter)->h == size) {
 271       delete *iter;
 272       *iter = NULL;
 273       return gFalse;
 274     }
 275     (*iter)->p = tab[(*iter)->h];
 276   }
 277   *key = (*iter)->p->key;
 278   *val = (*iter)->p->val.i;
 279   return gTrue;
 280 }
 281
 282 void GHash::killIter(GHashIter **iter) {
 283   delete *iter;
 284   *iter = NULL;
 285 }
 286
 287 void GHash::expand() {
 288   GHashBucket **oldTab;
 289   GHashBucket *p;
 290   int oldSize, h, i;
 291
 292   oldSize = size;
 293   oldTab = tab;
 294   size = 2*size + 1;
 295   tab = (GHashBucket **)gmalloc(size * sizeof(GHashBucket *));
 296   for (h = 0; h < size; ++h) {
 297     tab[h] = NULL;
 298   }
 299   for (i = 0; i < oldSize; ++i) {
 300     while (oldTab[i]) {
 301       p = oldTab[i];
 302       oldTab[i] = oldTab[i]->next;
 303       h = hash(p->key);
 304       p->next = tab[h];
 305       tab[h] = p;
 306     }
 307   }
 308   gfree(oldTab);
 309 }
 310
 311 GHashBucket *GHash::find(GString *key, int *h) {
 312   GHashBucket *p;
 313
 314   *h = hash(key);
 315   for (p = tab[*h]; p; p = p->next) {
 316     if (!p->key->cmp(key)) {
 317       return p;
 318     }
 319   }
 320   return NULL;
 321 }
 322
 323 GHashBucket *GHash::find(char *key, int *h) {
 324   GHashBucket *p;
 325
 326   *h = hash(key);
 327   for (p = tab[*h]; p; p = p->next) {
 328     if (!p->key->cmp(key)) {
 329       return p;
 330     }
 331   }
 332   return NULL;
 333 }
 334
 335 int GHash::hash(GString *key) {
 336   char *p;
 337   unsigned int h;
 338   int i;
 339
 340   h = 0;
 341   for (p = key->getCString(), i = 0; i < key->getLength(); ++p, ++i) {
 342     h = 17 * h + (int)(*p & 0xff);
 343   }
 344   return (int)(h % size);
 345 }
 346
 347 int GHash::hash(char *key) {
 348   char *p;
 349   unsigned int h;
 350
 351   h = 0;
 352   for (p = key; *p; ++p) {
 353     h = 17 * h + (int)(*p & 0xff);
 354   }
 355   return (int)(h % size);
 356 }