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