filters

GHash.cc

00001 //========================================================================
00002 //
00003 // GHash.cc
00004 //
00005 // Copyright 2001-2002 Glyph & Cog, LLC
00006 //
00007 //========================================================================
00008 
00009 #include <aconf.h>
00010 
00011 
00012 #include "gmem.h"
00013 #include "GString.h"
00014 #include "GHash.h"
00015 
00016 //------------------------------------------------------------------------
00017 
00018 struct GHashBucket {
00019   GString *key;
00020   void *val;
00021   GHashBucket *next;
00022 };
00023 
00024 struct GHashIter {
00025   int h;
00026   GHashBucket *p;
00027 };
00028 
00029 //------------------------------------------------------------------------
00030 
00031 GHash::GHash(GBool deleteKeysA) {
00032   int h;
00033 
00034   deleteKeys = deleteKeysA;
00035   size = 7;
00036   tab = (GHashBucket **)gmalloc(size * sizeof(GHashBucket *));
00037   for (h = 0; h < size; ++h) {
00038     tab[h] = NULL;
00039   }
00040   len = 0;
00041 }
00042 
00043 GHash::~GHash() {
00044   GHashBucket *p;
00045   int h;
00046 
00047   for (h = 0; h < size; ++h) {
00048     while (tab[h]) {
00049       p = tab[h];
00050       tab[h] = p->next;
00051       if (deleteKeys) {
00052     delete p->key;
00053       }
00054       delete p;
00055     }
00056   }
00057   gfree(tab);
00058 }
00059 
00060 void GHash::add(GString *key, void *val) {
00061   GHashBucket **oldTab;
00062   GHashBucket *p;
00063   int oldSize, i, h;
00064 
00065   // expand the table if necessary
00066   if (len >= size) {
00067     oldSize = size;
00068     oldTab = tab;
00069     size = 2*size + 1;
00070     tab = (GHashBucket **)gmalloc(size * sizeof(GHashBucket *));
00071     for (h = 0; h < size; ++h) {
00072       tab[h] = NULL;
00073     }
00074     for (i = 0; i < oldSize; ++i) {
00075       while (oldTab[i]) {
00076     p = oldTab[i];
00077     oldTab[i] = oldTab[i]->next;
00078     h = hash(p->key);
00079     p->next = tab[h];
00080     tab[h] = p;
00081       }
00082     }
00083     gfree(oldTab);
00084   }
00085 
00086   // add the new symbol
00087   p = new GHashBucket;
00088   p->key = key;
00089   p->val = val;
00090   h = hash(key);
00091   p->next = tab[h];
00092   tab[h] = p;
00093   ++len;
00094 }
00095 
00096 void *GHash::lookup(const GString *key) {
00097   GHashBucket *p;
00098   int h;
00099 
00100   if (!(p = find(key, &h))) {
00101     return NULL;
00102   }
00103   return p->val;
00104 }
00105 
00106 void *GHash::lookup(const char *key) {
00107   GHashBucket *p;
00108   int h;
00109 
00110   if (!(p = find(key, &h))) {
00111     return NULL;
00112   }
00113   return p->val;
00114 }
00115 
00116 void *GHash::remove(const GString *key) {
00117   GHashBucket *p;
00118   GHashBucket **q;
00119   void *val;
00120   int h;
00121 
00122   if (!(p = find(key, &h))) {
00123     return NULL;
00124   }
00125   q = &tab[h];
00126   while (*q != p) {
00127     q = &((*q)->next);
00128   }
00129   *q = p->next;
00130   if (deleteKeys) {
00131     delete p->key;
00132   }
00133   val = p->val;
00134   delete p;
00135   --len;
00136   return val;
00137 }
00138 
00139 void *GHash::remove(const char *key) {
00140   GHashBucket *p;
00141   GHashBucket **q;
00142   void *val;
00143   int h;
00144 
00145   if (!(p = find(key, &h))) {
00146     return NULL;
00147   }
00148   q = &tab[h];
00149   while (*q != p) {
00150     q = &((*q)->next);
00151   }
00152   *q = p->next;
00153   if (deleteKeys) {
00154     delete p->key;
00155   }
00156   val = p->val;
00157   delete p;
00158   --len;
00159   return val;
00160 }
00161 
00162 void GHash::startIter(GHashIter **iter) {
00163   *iter = new GHashIter;
00164   (*iter)->h = -1;
00165   (*iter)->p = NULL;
00166 }
00167 
00168 GBool GHash::getNext(GHashIter **iter, GString **key, void **val) {
00169   if (!*iter) {
00170     return gFalse;
00171   }
00172   if ((*iter)->p) {
00173     (*iter)->p = (*iter)->p->next;
00174   }
00175   while (!(*iter)->p) {
00176     if (++(*iter)->h == size) {
00177       delete *iter;
00178       *iter = NULL;
00179       return gFalse;
00180     }
00181     (*iter)->p = tab[(*iter)->h];
00182   }
00183   *key = (*iter)->p->key;
00184   *val = (*iter)->p->val;
00185   return gTrue;
00186 }
00187 
00188 void GHash::killIter(GHashIter **iter) {
00189   delete *iter;
00190   *iter = NULL;
00191 }
00192 
00193 GHashBucket *GHash::find(const GString *key, int *h) {
00194   GHashBucket *p;
00195 
00196   *h = hash(key);
00197   for (p = tab[*h]; p; p = p->next) {
00198     if (!p->key->cmp(key)) {
00199       return p;
00200     }
00201   }
00202   return NULL;
00203 }
00204 
00205 GHashBucket *GHash::find(const char *key, int *h) {
00206   GHashBucket *p;
00207 
00208   *h = hash(key);
00209   for (p = tab[*h]; p; p = p->next) {
00210     if (!p->key->cmp(key)) {
00211       return p;
00212     }
00213   }
00214   return NULL;
00215 }
00216 
00217 int GHash::hash(const GString *key) {
00218   const char *p;
00219   unsigned int h;
00220   int i;
00221 
00222   h = 0;
00223   for (p = key->getCString(), i = 0; i < key->getLength(); ++p, ++i) {
00224     h = 17 * h + (int)(*p & 0xff);
00225   }
00226   return (int)(h % size);
00227 }
00228 
00229 int GHash::hash(const char *key) {
00230   const char *p;
00231   unsigned int h;
00232 
00233   h = 0;
00234   for (p = key; *p; ++p) {
00235     h = 17 * h + (int)(*p & 0xff);
00236   }
00237   return (int)(h % size);
00238 }
KDE Home | KDE Accessibility Home | Description of Access Keys