filters
GHash.cc00001
00002
00003
00004
00005
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
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
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 }
|