Back to index

tetex-bin  3.0
GHash.cc
Go to the documentation of this file.
00001 //========================================================================
00002 //
00003 // GHash.cc
00004 //
00005 // Copyright 2001-2003 Glyph & Cog, LLC
00006 //
00007 //========================================================================
00008 
00009 #include <aconf.h>
00010 
00011 #ifdef USE_GCC_PRAGMAS
00012 #pragma implementation
00013 #endif
00014 
00015 #include "gmem.h"
00016 #include "GString.h"
00017 #include "GHash.h"
00018 
00019 //------------------------------------------------------------------------
00020 
00021 struct GHashBucket {
00022   GString *key;
00023   union {
00024     void *p;
00025     int i;
00026   } val;
00027   GHashBucket *next;
00028 };
00029 
00030 struct GHashIter {
00031   int h;
00032   GHashBucket *p;
00033 };
00034 
00035 //------------------------------------------------------------------------
00036 
00037 GHash::GHash(GBool deleteKeysA) {
00038   int h;
00039 
00040   deleteKeys = deleteKeysA;
00041   size = 7;
00042   tab = (GHashBucket **)gmalloc(size * sizeof(GHashBucket *));
00043   for (h = 0; h < size; ++h) {
00044     tab[h] = NULL;
00045   }
00046   len = 0;
00047 }
00048 
00049 GHash::~GHash() {
00050   GHashBucket *p;
00051   int h;
00052 
00053   for (h = 0; h < size; ++h) {
00054     while (tab[h]) {
00055       p = tab[h];
00056       tab[h] = p->next;
00057       if (deleteKeys) {
00058        delete p->key;
00059       }
00060       delete p;
00061     }
00062   }
00063   gfree(tab);
00064 }
00065 
00066 void GHash::add(GString *key, void *val) {
00067   GHashBucket *p;
00068   int h;
00069 
00070   // expand the table if necessary
00071   if (len >= size) {
00072     expand();
00073   }
00074 
00075   // add the new symbol
00076   p = new GHashBucket;
00077   p->key = key;
00078   p->val.p = val;
00079   h = hash(key);
00080   p->next = tab[h];
00081   tab[h] = p;
00082   ++len;
00083 }
00084 
00085 void GHash::add(GString *key, int val) {
00086   GHashBucket *p;
00087   int h;
00088 
00089   // expand the table if necessary
00090   if (len >= size) {
00091     expand();
00092   }
00093 
00094   // add the new symbol
00095   p = new GHashBucket;
00096   p->key = key;
00097   p->val.i = val;
00098   h = hash(key);
00099   p->next = tab[h];
00100   tab[h] = p;
00101   ++len;
00102 }
00103 
00104 void *GHash::lookup(GString *key) {
00105   GHashBucket *p;
00106   int h;
00107 
00108   if (!(p = find(key, &h))) {
00109     return NULL;
00110   }
00111   return p->val.p;
00112 }
00113 
00114 int GHash::lookupInt(GString *key) {
00115   GHashBucket *p;
00116   int h;
00117 
00118   if (!(p = find(key, &h))) {
00119     return 0;
00120   }
00121   return p->val.i;
00122 }
00123 
00124 void *GHash::lookup(char *key) {
00125   GHashBucket *p;
00126   int h;
00127 
00128   if (!(p = find(key, &h))) {
00129     return NULL;
00130   }
00131   return p->val.p;
00132 }
00133 
00134 int GHash::lookupInt(char *key) {
00135   GHashBucket *p;
00136   int h;
00137 
00138   if (!(p = find(key, &h))) {
00139     return 0;
00140   }
00141   return p->val.i;
00142 }
00143 
00144 void *GHash::remove(GString *key) {
00145   GHashBucket *p;
00146   GHashBucket **q;
00147   void *val;
00148   int h;
00149 
00150   if (!(p = find(key, &h))) {
00151     return NULL;
00152   }
00153   q = &tab[h];
00154   while (*q != p) {
00155     q = &((*q)->next);
00156   }
00157   *q = p->next;
00158   if (deleteKeys) {
00159     delete p->key;
00160   }
00161   val = p->val.p;
00162   delete p;
00163   --len;
00164   return val;
00165 }
00166 
00167 int GHash::removeInt(GString *key) {
00168   GHashBucket *p;
00169   GHashBucket **q;
00170   int val;
00171   int h;
00172 
00173   if (!(p = find(key, &h))) {
00174     return 0;
00175   }
00176   q = &tab[h];
00177   while (*q != p) {
00178     q = &((*q)->next);
00179   }
00180   *q = p->next;
00181   if (deleteKeys) {
00182     delete p->key;
00183   }
00184   val = p->val.i;
00185   delete p;
00186   --len;
00187   return val;
00188 }
00189 
00190 void *GHash::remove(char *key) {
00191   GHashBucket *p;
00192   GHashBucket **q;
00193   void *val;
00194   int h;
00195 
00196   if (!(p = find(key, &h))) {
00197     return NULL;
00198   }
00199   q = &tab[h];
00200   while (*q != p) {
00201     q = &((*q)->next);
00202   }
00203   *q = p->next;
00204   if (deleteKeys) {
00205     delete p->key;
00206   }
00207   val = p->val.p;
00208   delete p;
00209   --len;
00210   return val;
00211 }
00212 
00213 int GHash::removeInt(char *key) {
00214   GHashBucket *p;
00215   GHashBucket **q;
00216   int val;
00217   int h;
00218 
00219   if (!(p = find(key, &h))) {
00220     return 0;
00221   }
00222   q = &tab[h];
00223   while (*q != p) {
00224     q = &((*q)->next);
00225   }
00226   *q = p->next;
00227   if (deleteKeys) {
00228     delete p->key;
00229   }
00230   val = p->val.i;
00231   delete p;
00232   --len;
00233   return val;
00234 }
00235 
00236 void GHash::startIter(GHashIter **iter) {
00237   *iter = new GHashIter;
00238   (*iter)->h = -1;
00239   (*iter)->p = NULL;
00240 }
00241 
00242 GBool GHash::getNext(GHashIter **iter, GString **key, void **val) {
00243   if (!*iter) {
00244     return gFalse;
00245   }
00246   if ((*iter)->p) {
00247     (*iter)->p = (*iter)->p->next;
00248   }
00249   while (!(*iter)->p) {
00250     if (++(*iter)->h == size) {
00251       delete *iter;
00252       *iter = NULL;
00253       return gFalse;
00254     }
00255     (*iter)->p = tab[(*iter)->h];
00256   }
00257   *key = (*iter)->p->key;
00258   *val = (*iter)->p->val.p;
00259   return gTrue;
00260 }
00261 
00262 GBool GHash::getNext(GHashIter **iter, GString **key, int *val) {
00263   if (!*iter) {
00264     return gFalse;
00265   }
00266   if ((*iter)->p) {
00267     (*iter)->p = (*iter)->p->next;
00268   }
00269   while (!(*iter)->p) {
00270     if (++(*iter)->h == size) {
00271       delete *iter;
00272       *iter = NULL;
00273       return gFalse;
00274     }
00275     (*iter)->p = tab[(*iter)->h];
00276   }
00277   *key = (*iter)->p->key;
00278   *val = (*iter)->p->val.i;
00279   return gTrue;
00280 }
00281 
00282 void GHash::killIter(GHashIter **iter) {
00283   delete *iter;
00284   *iter = NULL;
00285 }
00286 
00287 void GHash::expand() {
00288   GHashBucket **oldTab;
00289   GHashBucket *p;
00290   int oldSize, h, i;
00291 
00292   oldSize = size;
00293   oldTab = tab;
00294   size = 2*size + 1;
00295   tab = (GHashBucket **)gmalloc(size * sizeof(GHashBucket *));
00296   for (h = 0; h < size; ++h) {
00297     tab[h] = NULL;
00298   }
00299   for (i = 0; i < oldSize; ++i) {
00300     while (oldTab[i]) {
00301       p = oldTab[i];
00302       oldTab[i] = oldTab[i]->next;
00303       h = hash(p->key);
00304       p->next = tab[h];
00305       tab[h] = p;
00306     }
00307   }
00308   gfree(oldTab);
00309 }
00310 
00311 GHashBucket *GHash::find(GString *key, int *h) {
00312   GHashBucket *p;
00313 
00314   *h = hash(key);
00315   for (p = tab[*h]; p; p = p->next) {
00316     if (!p->key->cmp(key)) {
00317       return p;
00318     }
00319   }
00320   return NULL;
00321 }
00322 
00323 GHashBucket *GHash::find(char *key, int *h) {
00324   GHashBucket *p;
00325 
00326   *h = hash(key);
00327   for (p = tab[*h]; p; p = p->next) {
00328     if (!p->key->cmp(key)) {
00329       return p;
00330     }
00331   }
00332   return NULL;
00333 }
00334 
00335 int GHash::hash(GString *key) {
00336   char *p;
00337   unsigned int h;
00338   int i;
00339 
00340   h = 0;
00341   for (p = key->getCString(), i = 0; i < key->getLength(); ++p, ++i) {
00342     h = 17 * h + (int)(*p & 0xff);
00343   }
00344   return (int)(h % size);
00345 }
00346 
00347 int GHash::hash(char *key) {
00348   char *p;
00349   unsigned int h;
00350 
00351   h = 0;
00352   for (p = key; *p; ++p) {
00353     h = 17 * h + (int)(*p & 0xff);
00354   }
00355   return (int)(h % size);
00356 }