Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/source/fitz/hash.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 // Copyright (C) 2004-2021 Artifex Software, Inc.
2 //
3 // This file is part of MuPDF.
4 //
5 // MuPDF is free software: you can redistribute it and/or modify it under the
6 // terms of the GNU Affero General Public License as published by the Free
7 // Software Foundation, either version 3 of the License, or (at your option)
8 // any later version.
9 //
10 // MuPDF is distributed in the hope that it will be useful, but WITHOUT ANY
11 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12 // FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
13 // details.
14 //
15 // You should have received a copy of the GNU Affero General Public License
16 // along with MuPDF. If not, see <https://www.gnu.org/licenses/agpl-3.0.en.html>
17 //
18 // Alternative licensing terms are available from the licensor.
19 // For commercial licensing, see <https://www.artifex.com/> or contact
20 // Artifex Software, Inc., 39 Mesa Street, Suite 108A, San Francisco,
21 // CA 94129, USA, for further information.
22
23 #include "mupdf/fitz.h"
24
25 #include <string.h>
26 #include <assert.h>
27
28 /*
29 Simple hashtable with open addressing linear probe.
30 Unlike text book examples, removing entries works
31 correctly in this implementation, so it won't start
32 exhibiting bad behaviour if entries are inserted
33 and removed frequently.
34 */
35
36 typedef struct
37 {
38 unsigned char key[FZ_HASH_TABLE_KEY_LENGTH];
39 void *val;
40 } fz_hash_entry;
41
42 struct fz_hash_table
43 {
44 int keylen;
45 int size;
46 int load;
47 int lock; /* -1 or the lock used to protect this hash table */
48 fz_hash_table_drop_fn *drop_val;
49 fz_hash_entry *ents;
50 };
51
52 static unsigned hash(const unsigned char *s, int len)
53 {
54 unsigned val = 0;
55 int i;
56 for (i = 0; i < len; i++)
57 {
58 val += s[i];
59 val += (val << 10);
60 val ^= (val >> 6);
61 }
62 val += (val << 3);
63 val ^= (val >> 11);
64 val += (val << 15);
65 return val;
66 }
67
68 fz_hash_table *
69 fz_new_hash_table(fz_context *ctx, int initialsize, int keylen, int lock, fz_hash_table_drop_fn *drop_val)
70 {
71 fz_hash_table *table;
72
73 if (keylen > FZ_HASH_TABLE_KEY_LENGTH)
74 fz_throw(ctx, FZ_ERROR_ARGUMENT, "hash table key length too large");
75
76 table = fz_malloc_struct(ctx, fz_hash_table);
77 table->keylen = keylen;
78 table->size = initialsize;
79 table->load = 0;
80 table->lock = lock;
81 table->drop_val = drop_val;
82 fz_try(ctx)
83 {
84 table->ents = Memento_label(fz_malloc_array(ctx, table->size, fz_hash_entry), "hash_entries");
85 memset(table->ents, 0, sizeof(fz_hash_entry) * table->size);
86 }
87 fz_catch(ctx)
88 {
89 fz_free(ctx, table);
90 fz_rethrow(ctx);
91 }
92
93 return table;
94 }
95
96 void
97 fz_drop_hash_table(fz_context *ctx, fz_hash_table *table)
98 {
99 if (!table)
100 return;
101
102 if (table->drop_val)
103 {
104 int i, n = table->size;
105 for (i = 0; i < n; ++i)
106 {
107 void *v = table->ents[i].val;
108 if (v)
109 table->drop_val(ctx, v);
110 }
111 }
112
113 fz_free(ctx, table->ents);
114 fz_free(ctx, table);
115 }
116
117 static void *
118 do_hash_insert(fz_context *ctx, fz_hash_table *table, const void *key, void *val)
119 {
120 fz_hash_entry *ents;
121 unsigned size;
122 unsigned pos;
123
124 ents = table->ents;
125 size = table->size;
126 pos = hash(key, table->keylen) % size;
127
128 if (table->lock >= 0)
129 fz_assert_lock_held(ctx, table->lock);
130
131 while (1)
132 {
133 if (!ents[pos].val)
134 {
135 memcpy(ents[pos].key, key, table->keylen);
136 ents[pos].val = val;
137 table->load ++;
138 return NULL;
139 }
140
141 if (memcmp(key, ents[pos].key, table->keylen) == 0)
142 {
143 /* This is legal, but should rarely happen. */
144 return ents[pos].val;
145 }
146
147 pos = (pos + 1) % size;
148 }
149 }
150
151 /* Entered with the lock taken, held throughout and at exit, UNLESS the lock
152 * is the alloc lock in which case it may be momentarily dropped. */
153 static void
154 fz_resize_hash(fz_context *ctx, fz_hash_table *table, int newsize)
155 {
156 fz_hash_entry *oldents = table->ents;
157 fz_hash_entry *newents;
158 int oldsize = table->size;
159 int oldload = table->load;
160 int i;
161
162 if (newsize < oldload * 8 / 10)
163 {
164 fz_warn(ctx, "assert: resize hash too small");
165 return;
166 }
167
168 if (table->lock == FZ_LOCK_ALLOC)
169 fz_unlock(ctx, table->lock);
170 newents = Memento_label(fz_malloc_no_throw(ctx, newsize * sizeof (fz_hash_entry)), "hash_entries");
171 if (table->lock == FZ_LOCK_ALLOC)
172 fz_lock(ctx, table->lock);
173 if (table->lock >= 0)
174 {
175 if (table->size >= newsize)
176 {
177 /* Someone else fixed it before we could lock! */
178 if (table->lock == FZ_LOCK_ALLOC)
179 fz_unlock(ctx, table->lock);
180 fz_free(ctx, newents);
181 if (table->lock == FZ_LOCK_ALLOC)
182 fz_lock(ctx, table->lock);
183 return;
184 }
185 }
186 if (newents == NULL)
187 fz_throw(ctx, FZ_ERROR_SYSTEM, "hash table resize failed; out of memory (%d entries)", newsize);
188 table->ents = newents;
189 memset(table->ents, 0, sizeof(fz_hash_entry) * newsize);
190 table->size = newsize;
191 table->load = 0;
192
193 for (i = 0; i < oldsize; i++)
194 {
195 if (oldents[i].val)
196 {
197 do_hash_insert(ctx, table, oldents[i].key, oldents[i].val);
198 }
199 }
200
201 if (table->lock == FZ_LOCK_ALLOC)
202 fz_unlock(ctx, table->lock);
203 fz_free(ctx, oldents);
204 if (table->lock == FZ_LOCK_ALLOC)
205 fz_lock(ctx, table->lock);
206 }
207
208 void *
209 fz_hash_find(fz_context *ctx, fz_hash_table *table, const void *key)
210 {
211 fz_hash_entry *ents = table->ents;
212 unsigned size = table->size;
213 unsigned pos = hash(key, table->keylen) % size;
214
215 if (table->lock >= 0)
216 fz_assert_lock_held(ctx, table->lock);
217
218 while (1)
219 {
220 if (!ents[pos].val)
221 return NULL;
222
223 if (memcmp(key, ents[pos].key, table->keylen) == 0)
224 return ents[pos].val;
225
226 pos = (pos + 1) % size;
227 }
228 }
229
230 void *
231 fz_hash_insert(fz_context *ctx, fz_hash_table *table, const void *key, void *val)
232 {
233 if (table->load > table->size * 8 / 10)
234 fz_resize_hash(ctx, table, table->size * 2);
235 return do_hash_insert(ctx, table, key, val);
236 }
237
238 static void
239 do_removal(fz_context *ctx, fz_hash_table *table, unsigned hole)
240 {
241 fz_hash_entry *ents = table->ents;
242 unsigned size = table->size;
243 unsigned look, code;
244
245 if (table->lock >= 0)
246 fz_assert_lock_held(ctx, table->lock);
247
248 ents[hole].val = NULL;
249
250 look = hole + 1;
251 if (look == size)
252 look = 0;
253
254 while (ents[look].val)
255 {
256 code = hash(ents[look].key, table->keylen) % size;
257 if ((code <= hole && hole < look) ||
258 (look < code && code <= hole) ||
259 (hole < look && look < code))
260 {
261 ents[hole] = ents[look];
262 ents[look].val = NULL;
263 hole = look;
264 }
265
266 look++;
267 if (look == size)
268 look = 0;
269 }
270
271 table->load --;
272 }
273
274 void
275 fz_hash_remove(fz_context *ctx, fz_hash_table *table, const void *key)
276 {
277 fz_hash_entry *ents = table->ents;
278 unsigned size = table->size;
279 unsigned pos = hash(key, table->keylen) % size;
280
281 if (table->lock >= 0)
282 fz_assert_lock_held(ctx, table->lock);
283
284 while (1)
285 {
286 if (!ents[pos].val)
287 {
288 fz_warn(ctx, "assert: remove non-existent hash entry");
289 return;
290 }
291
292 if (memcmp(key, ents[pos].key, table->keylen) == 0)
293 {
294 do_removal(ctx, table, pos);
295 return;
296 }
297
298 pos++;
299 if (pos == size)
300 pos = 0;
301 }
302 }
303
304 void
305 fz_hash_for_each(fz_context *ctx, fz_hash_table *table, void *state, fz_hash_table_for_each_fn *callback)
306 {
307 int i;
308 for (i = 0; i < table->size; ++i)
309 if (table->ents[i].val)
310 callback(ctx, state, table->ents[i].key, table->keylen, table->ents[i].val);
311 }
312
313 void
314 fz_hash_filter(fz_context *ctx, fz_hash_table *table, void *state, fz_hash_table_filter_fn *callback)
315 {
316 int i;
317 restart:
318 for (i = 0; i < table->size; ++i)
319 {
320 if (table->ents[i].val)
321 {
322 if (callback(ctx, state, table->ents[i].key, table->keylen, table->ents[i].val))
323 {
324 do_removal(ctx, table, i);
325 goto restart; /* we may have moved some slots around, so just restart the scan */
326 }
327 }
328 }
329 }