author | sandman <sandman> | 2002-04-13 00:47:20 (UTC) |
---|---|---|
committer | sandman <sandman> | 2002-04-13 00:47:20 (UTC) |
commit | 98a1e3f36567639344f12932b629e526a8783aa8 (patch) (unidiff) | |
tree | 0433d296857faceeafc54f7deabddb621f45a933 /noncore/unsupported/qpdf/goo/GHash.cc | |
parent | 7e31b1fba119f69929d6744d7295555ff1727f4f (diff) | |
download | opie-98a1e3f36567639344f12932b629e526a8783aa8.zip opie-98a1e3f36567639344f12932b629e526a8783aa8.tar.gz opie-98a1e3f36567639344f12932b629e526a8783aa8.tar.bz2 |
CVS import of QPdf
Diffstat (limited to 'noncore/unsupported/qpdf/goo/GHash.cc') (more/less context) (ignore whitespace changes)
-rw-r--r-- | noncore/unsupported/qpdf/goo/GHash.cc | 240 |
1 files changed, 240 insertions, 0 deletions
diff --git a/noncore/unsupported/qpdf/goo/GHash.cc b/noncore/unsupported/qpdf/goo/GHash.cc new file mode 100644 index 0000000..9ef6bb1 --- a/dev/null +++ b/noncore/unsupported/qpdf/goo/GHash.cc | |||
@@ -0,0 +1,240 @@ | |||
1 | //======================================================================== | ||
2 | // | ||
3 | // GHash.cc | ||
4 | // | ||
5 | // Copyright 2001 Derek B. Noonburg | ||
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 | } | ||