pdf2swf/xpdf/GHash.cc

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