pdf/goo/GHash.cc

   1 //========================================================================
   2 //
   3 // GHash.cc
   4 //
   5 // Copyright 2001-2002 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   void *val;
  24   GHashBucket *next;
  25 };
  26
  27 struct GHashIter {
  28   int h;
  29   GHashBucket *p;
  30 };
  31
  32 //------------------------------------------------------------------------
  33
  34 GHash::GHash(GBool deleteKeysA) {
  35   int h;
  36
  37   deleteKeys = deleteKeysA;
  38   size = 7;
  39   tab = (GHashBucket **)gmalloc(size * sizeof(GHashBucket *));
  40   for (h = 0; h < size; ++h) {
  41     tab[h] = NULL;
  42   }
  43   len = 0;
  44 }
  45
  46 GHash::~GHash() {
  47   GHashBucket *p;
  48   int h;
  49
  50   for (h = 0; h < size; ++h) {
  51     while (tab[h]) {
  52       p = tab[h];
  53       tab[h] = p->next;
  54       if (deleteKeys) {
  55         delete p->key;
  56       }
  57       delete p;
  58     }
  59   }
  60   gfree(tab);
  61 }
  62
  63 void GHash::add(GString *key, void *val) {
  64   GHashBucket **oldTab;
  65   GHashBucket *p;
  66   int oldSize, i, h;
  67
  68   // expand the table if necessary
  69   if (len >= size) {
  70     oldSize = size;
  71     oldTab = tab;
  72     size = 2*size + 1;
  73     tab = (GHashBucket **)gmalloc(size * sizeof(GHashBucket *));
  74     for (h = 0; h < size; ++h) {
  75       tab[h] = NULL;
  76     }
  77     for (i = 0; i < oldSize; ++i) {
  78       while (oldTab[i]) {
  79         p = oldTab[i];
  80         oldTab[i] = oldTab[i]->next;
  81         h = hash(p->key);
  82         p->next = tab[h];
  83         tab[h] = p;
  84       }
  85     }
  86     gfree(oldTab);
  87   }
  88
  89   // add the new symbol
  90   p = new GHashBucket;
  91   p->key = key;
  92   p->val = val;
  93   h = hash(key);
  94   p->next = tab[h];
  95   tab[h] = p;
  96   ++len;
  97 }
  98
  99 void *GHash::lookup(GString *key) {
 100   GHashBucket *p;
 101   int h;
 102
 103   if (!(p = find(key, &h))) {
 104     return NULL;
 105   }
 106   return p->val;
 107 }
 108
 109 void *GHash::lookup(char *key) {
 110   GHashBucket *p;
 111   int h;
 112
 113   if (!(p = find(key, &h))) {
 114     return NULL;
 115   }
 116   return p->val;
 117 }
 118
 119 void *GHash::remove(GString *key) {
 120   GHashBucket *p;
 121   GHashBucket **q;
 122   void *val;
 123   int h;
 124
 125   if (!(p = find(key, &h))) {
 126     return NULL;
 127   }
 128   q = &tab[h];
 129   while (*q != p) {
 130     q = &((*q)->next);
 131   }
 132   *q = p->next;
 133   if (deleteKeys) {
 134     delete p->key;
 135   }
 136   val = p->val;
 137   delete p;
 138   --len;
 139   return val;
 140 }
 141
 142 void *GHash::remove(char *key) {
 143   GHashBucket *p;
 144   GHashBucket **q;
 145   void *val;
 146   int h;
 147
 148   if (!(p = find(key, &h))) {
 149     return NULL;
 150   }
 151   q = &tab[h];
 152   while (*q != p) {
 153     q = &((*q)->next);
 154   }
 155   *q = p->next;
 156   if (deleteKeys) {
 157     delete p->key;
 158   }
 159   val = p->val;
 160   delete p;
 161   --len;
 162   return val;
 163 }
 164
 165 void GHash::startIter(GHashIter **iter) {
 166   *iter = new GHashIter;
 167   (*iter)->h = -1;
 168   (*iter)->p = NULL;
 169 }
 170
 171 GBool GHash::getNext(GHashIter **iter, GString **key, void **val) {
 172   if (!*iter) {
 173     return gFalse;
 174   }
 175   if ((*iter)->p) {
 176     (*iter)->p = (*iter)->p->next;
 177   }
 178   while (!(*iter)->p) {
 179     if (++(*iter)->h == size) {
 180       delete *iter;
 181       *iter = NULL;
 182       return gFalse;
 183     }
 184     (*iter)->p = tab[(*iter)->h];
 185   }
 186   *key = (*iter)->p->key;
 187   *val = (*iter)->p->val;
 188   return gTrue;
 189 }
 190
 191 void GHash::killIter(GHashIter **iter) {
 192   delete *iter;
 193   *iter = NULL;
 194 }
 195
 196 GHashBucket *GHash::find(GString *key, int *h) {
 197   GHashBucket *p;
 198
 199   *h = hash(key);
 200   for (p = tab[*h]; p; p = p->next) {
 201     if (!p->key->cmp(key)) {
 202       return p;
 203     }
 204   }
 205   return NULL;
 206 }
 207
 208 GHashBucket *GHash::find(char *key, int *h) {
 209   GHashBucket *p;
 210
 211   *h = hash(key);
 212   for (p = tab[*h]; p; p = p->next) {
 213     if (!p->key->cmp(key)) {
 214       return p;
 215     }
 216   }
 217   return NULL;
 218 }
 219
 220 int GHash::hash(GString *key) {
 221   char *p;
 222   unsigned int h;
 223   int i;
 224
 225   h = 0;
 226   for (p = key->getCString(), i = 0; i < key->getLength(); ++p, ++i) {
 227     h = 17 * h + (int)(*p & 0xff);
 228   }
 229   return (int)(h % size);
 230 }
 231
 232 int GHash::hash(char *key) {
 233   char *p;
 234   unsigned int h;
 235
 236   h = 0;
 237   for (p = key; *p; ++p) {
 238     h = 17 * h + (int)(*p & 0xff);
 239   }
 240   return (int)(h % size);
 241 }