1#include "mupdf/fitz.h"
2#include "fitz-imp.h"
3
4#include <string.h>
5#include <assert.h>
6
7/*
8Simple hashtable with open addressing linear probe.
9Unlike text book examples, removing entries works
10correctly in this implementation, so it won't start
11exhibiting bad behaviour if entries are inserted
12and removed frequently.
13*/
14
15enum { MAX_KEY_LEN = 48 };
16typedef struct fz_hash_entry_s fz_hash_entry;
17
18struct fz_hash_entry_s
19{
20 unsigned char key[MAX_KEY_LEN];
21 void *val;
22};
23
24struct fz_hash_table_s
25{
26 int keylen;
27 int size;
28 int load;
29 int lock; /* -1 or the lock used to protect this hash table */
30 fz_hash_table_drop_fn *drop_val;
31 fz_hash_entry *ents;
32};
33
34static unsigned hash(const unsigned char *s, int len)
35{
36 unsigned val = 0;
37 int i;
38 for (i = 0; i < len; i++)
39 {
40 val += s[i];
41 val += (val << 10);
42 val ^= (val >> 6);
43 }
44 val += (val << 3);
45 val ^= (val >> 11);
46 val += (val << 15);
47 return val;
48}
49
50fz_hash_table *
51fz_new_hash_table(fz_context *ctx, int initialsize, int keylen, int lock, fz_hash_table_drop_fn *drop_val)
52{
53 fz_hash_table *table;
54
55 assert(keylen <= MAX_KEY_LEN);
56
57 table = fz_malloc_struct(ctx, fz_hash_table);
58 table->keylen = keylen;
59 table->size = initialsize;
60 table->load = 0;
61 table->lock = lock;
62 table->drop_val = drop_val;
63 fz_try(ctx)
64 {
65 table->ents = fz_malloc_array(ctx, table->size, fz_hash_entry);
66 memset(table->ents, 0, sizeof(fz_hash_entry) * table->size);
67 }
68 fz_catch(ctx)
69 {
70 fz_free(ctx, table);
71 fz_rethrow(ctx);
72 }
73
74 return table;
75}
76
77void
78fz_drop_hash_table(fz_context *ctx, fz_hash_table *table)
79{
80 if (!table)
81 return;
82
83 if (table->drop_val)
84 {
85 int i, n = table->size;
86 for (i = 0; i < n; ++i)
87 {
88 void *v = table->ents[i].val;
89 if (v)
90 table->drop_val(ctx, v);
91 }
92 }
93
94 fz_free(ctx, table->ents);
95 fz_free(ctx, table);
96}
97
98static void *
99do_hash_insert(fz_context *ctx, fz_hash_table *table, const void *key, void *val)
100{
101 fz_hash_entry *ents;
102 unsigned size;
103 unsigned pos;
104
105 ents = table->ents;
106 size = table->size;
107 pos = hash(key, table->keylen) % size;
108
109 if (table->lock >= 0)
110 fz_assert_lock_held(ctx, table->lock);
111
112 while (1)
113 {
114 if (!ents[pos].val)
115 {
116 memcpy(ents[pos].key, key, table->keylen);
117 ents[pos].val = val;
118 table->load ++;
119 return NULL;
120 }
121
122 if (memcmp(key, ents[pos].key, table->keylen) == 0)
123 {
124 /* This is legal, but should rarely happen. */
125 if (val != ents[pos].val)
126 fz_warn(ctx, "assert: overwrite hash slot with different value!");
127 else
128 fz_warn(ctx, "assert: overwrite hash slot with same value");
129 return ents[pos].val;
130 }
131
132 pos = (pos + 1) % size;
133 }
134}
135
136/* Entered with the lock taken, held throughout and at exit, UNLESS the lock
137 * is the alloc lock in which case it may be momentarily dropped. */
138static void
139fz_resize_hash(fz_context *ctx, fz_hash_table *table, int newsize)
140{
141 fz_hash_entry *oldents = table->ents;
142 fz_hash_entry *newents;
143 int oldsize = table->size;
144 int oldload = table->load;
145 int i;
146
147 if (newsize < oldload * 8 / 10)
148 {
149 fz_warn(ctx, "assert: resize hash too small");
150 return;
151 }
152
153 if (table->lock == FZ_LOCK_ALLOC)
154 fz_unlock(ctx, table->lock);
155 newents = fz_malloc_no_throw(ctx, newsize * sizeof (fz_hash_entry));
156 if (table->lock == FZ_LOCK_ALLOC)
157 fz_lock(ctx, table->lock);
158 if (table->lock >= 0)
159 {
160 if (table->size >= newsize)
161 {
162 /* Someone else fixed it before we could lock! */
163 if (table->lock == FZ_LOCK_ALLOC)
164 fz_unlock(ctx, table->lock);
165 fz_free(ctx, newents);
166 if (table->lock == FZ_LOCK_ALLOC)
167 fz_lock(ctx, table->lock);
168 return;
169 }
170 }
171 if (newents == NULL)
172 fz_throw(ctx, FZ_ERROR_GENERIC, "hash table resize failed; out of memory (%d entries)", newsize);
173 table->ents = newents;
174 memset(table->ents, 0, sizeof(fz_hash_entry) * newsize);
175 table->size = newsize;
176 table->load = 0;
177
178 for (i = 0; i < oldsize; i++)
179 {
180 if (oldents[i].val)
181 {
182 do_hash_insert(ctx, table, oldents[i].key, oldents[i].val);
183 }
184 }
185
186 if (table->lock == FZ_LOCK_ALLOC)
187 fz_unlock(ctx, table->lock);
188 fz_free(ctx, oldents);
189 if (table->lock == FZ_LOCK_ALLOC)
190 fz_lock(ctx, table->lock);
191}
192
193void *
194fz_hash_find(fz_context *ctx, fz_hash_table *table, const void *key)
195{
196 fz_hash_entry *ents = table->ents;
197 unsigned size = table->size;
198 unsigned pos = hash(key, table->keylen) % size;
199
200 if (table->lock >= 0)
201 fz_assert_lock_held(ctx, table->lock);
202
203 while (1)
204 {
205 if (!ents[pos].val)
206 return NULL;
207
208 if (memcmp(key, ents[pos].key, table->keylen) == 0)
209 return ents[pos].val;
210
211 pos = (pos + 1) % size;
212 }
213}
214
215void *
216fz_hash_insert(fz_context *ctx, fz_hash_table *table, const void *key, void *val)
217{
218 if (table->load > table->size * 8 / 10)
219 fz_resize_hash(ctx, table, table->size * 2);
220 return do_hash_insert(ctx, table, key, val);
221}
222
223static void
224do_removal(fz_context *ctx, fz_hash_table *table, const void *key, unsigned hole)
225{
226 fz_hash_entry *ents = table->ents;
227 unsigned size = table->size;
228 unsigned look, code;
229
230 if (table->lock >= 0)
231 fz_assert_lock_held(ctx, table->lock);
232
233 ents[hole].val = NULL;
234
235 look = hole + 1;
236 if (look == size)
237 look = 0;
238
239 while (ents[look].val)
240 {
241 code = hash(ents[look].key, table->keylen) % size;
242 if ((code <= hole && hole < look) ||
243 (look < code && code <= hole) ||
244 (hole < look && look < code))
245 {
246 ents[hole] = ents[look];
247 ents[look].val = NULL;
248 hole = look;
249 }
250
251 look++;
252 if (look == size)
253 look = 0;
254 }
255
256 table->load --;
257}
258
259void
260fz_hash_remove(fz_context *ctx, fz_hash_table *table, const void *key)
261{
262 fz_hash_entry *ents = table->ents;
263 unsigned size = table->size;
264 unsigned pos = hash(key, table->keylen) % size;
265
266 if (table->lock >= 0)
267 fz_assert_lock_held(ctx, table->lock);
268
269 while (1)
270 {
271 if (!ents[pos].val)
272 {
273 fz_warn(ctx, "assert: remove non-existent hash entry");
274 return;
275 }
276
277 if (memcmp(key, ents[pos].key, table->keylen) == 0)
278 {
279 do_removal(ctx, table, key, pos);
280 return;
281 }
282
283 pos++;
284 if (pos == size)
285 pos = 0;
286 }
287}
288
289void
290fz_hash_for_each(fz_context *ctx, fz_hash_table *table, void *state, fz_hash_table_for_each_fn *callback)
291{
292 int i;
293 for (i = 0; i < table->size; ++i)
294 if (table->ents[i].val)
295 callback(ctx, state, table->ents[i].key, table->keylen, table->ents[i].val);
296}
297