Rev 1892 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
1892 | serge | 1 | /* cairo - a vector graphics library with display and print output |
2 | * |
||
3 | * Copyright © 2004 Red Hat, Inc. |
||
4 | * Copyright © 2005 Red Hat, Inc. |
||
5 | * |
||
6 | * This library is free software; you can redistribute it and/or |
||
7 | * modify it either under the terms of the GNU Lesser General Public |
||
8 | * License version 2.1 as published by the Free Software Foundation |
||
9 | * (the "LGPL") or, at your option, under the terms of the Mozilla |
||
10 | * Public License Version 1.1 (the "MPL"). If you do not alter this |
||
11 | * notice, a recipient may use your version of this file under either |
||
12 | * the MPL or the LGPL. |
||
13 | * |
||
14 | * You should have received a copy of the LGPL along with this library |
||
15 | * in the file COPYING-LGPL-2.1; if not, write to the Free Software |
||
16 | * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA |
||
17 | * You should have received a copy of the MPL along with this library |
||
18 | * in the file COPYING-MPL-1.1 |
||
19 | * |
||
20 | * The contents of this file are subject to the Mozilla Public License |
||
21 | * Version 1.1 (the "License"); you may not use this file except in |
||
22 | * compliance with the License. You may obtain a copy of the License at |
||
23 | * http://www.mozilla.org/MPL/ |
||
24 | * |
||
25 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY |
||
26 | * OF ANY KIND, either express or implied. See the LGPL or the MPL for |
||
27 | * the specific language governing rights and limitations. |
||
28 | * |
||
29 | * The Original Code is the cairo graphics library. |
||
30 | * |
||
31 | * The Initial Developer of the Original Code is Red Hat, Inc. |
||
32 | * |
||
33 | * Contributor(s): |
||
34 | * Keith Packard |
||
35 | * Graydon Hoare |
||
36 | * Carl Worth |
||
37 | */ |
||
38 | |||
39 | #include "cairoint.h" |
||
40 | #include "cairo-error-private.h" |
||
41 | |||
42 | /* |
||
43 | * An entry can be in one of three states: |
||
44 | * |
||
45 | * FREE: Entry has never been used, terminates all searches. |
||
46 | * Appears in the table as a %NULL pointer. |
||
47 | * |
||
48 | * DEAD: Entry had been live in the past. A dead entry can be reused |
||
49 | * but does not terminate a search for an exact entry. |
||
50 | * Appears in the table as a pointer to DEAD_ENTRY. |
||
51 | * |
||
52 | * LIVE: Entry is currently being used. |
||
53 | * Appears in the table as any non-%NULL, non-DEAD_ENTRY pointer. |
||
54 | */ |
||
55 | |||
56 | #define DEAD_ENTRY ((cairo_hash_entry_t *) 0x1) |
||
57 | |||
58 | #define ENTRY_IS_FREE(entry) ((entry) == NULL) |
||
59 | #define ENTRY_IS_DEAD(entry) ((entry) == DEAD_ENTRY) |
||
60 | #define ENTRY_IS_LIVE(entry) ((entry) > DEAD_ENTRY) |
||
61 | |||
3959 | Serge | 62 | /* |
63 | * This table is open-addressed with double hashing. Each table size |
||
64 | * is a prime and it makes for the "first" hash modulus; a second |
||
65 | * prime (2 less than the first prime) serves as the "second" hash |
||
66 | * modulus, which is smaller and thus guarantees a complete |
||
67 | * permutation of table indices. |
||
1892 | serge | 68 | * |
3959 | Serge | 69 | * Hash tables are rehashed in order to keep between 12.5% and 50% |
70 | * entries in the hash table alive and at least 25% free. When table |
||
71 | * size is changed, the new table has about 25% live elements. |
||
1892 | serge | 72 | * |
3959 | Serge | 73 | * The free entries guarantee an expected constant-time lookup. |
74 | * Doubling/halving the table in the described fashion guarantees |
||
75 | * amortized O(1) insertion/removal. |
||
1892 | serge | 76 | * |
77 | * This structure, and accompanying table, is borrowed/modified from the |
||
78 | * file xserver/render/glyph.c in the freedesktop.org x server, with |
||
79 | * permission (and suggested modification of doubling sizes) by Keith |
||
80 | * Packard. |
||
81 | */ |
||
82 | |||
3959 | Serge | 83 | static const unsigned long hash_table_sizes[] = { |
84 | 43, |
||
85 | 73, |
||
86 | 151, |
||
87 | 283, |
||
88 | 571, |
||
89 | 1153, |
||
90 | 2269, |
||
91 | 4519, |
||
92 | 9013, |
||
93 | 18043, |
||
94 | 36109, |
||
95 | 72091, |
||
96 | 144409, |
||
97 | 288361, |
||
98 | 576883, |
||
99 | 1153459, |
||
100 | 2307163, |
||
101 | 4613893, |
||
102 | 9227641, |
||
103 | 18455029, |
||
104 | 36911011, |
||
105 | 73819861, |
||
106 | 147639589, |
||
107 | 295279081, |
||
108 | 590559793 |
||
1892 | serge | 109 | }; |
110 | |||
111 | struct _cairo_hash_table { |
||
112 | cairo_hash_keys_equal_func_t keys_equal; |
||
113 | |||
3959 | Serge | 114 | cairo_hash_entry_t *cache[32]; |
115 | |||
116 | const unsigned long *table_size; |
||
1892 | serge | 117 | cairo_hash_entry_t **entries; |
118 | |||
119 | unsigned long live_entries; |
||
3959 | Serge | 120 | unsigned long free_entries; |
1892 | serge | 121 | unsigned long iterating; /* Iterating, no insert, no resize */ |
122 | }; |
||
123 | |||
124 | /** |
||
3959 | Serge | 125 | * _cairo_hash_table_uid_keys_equal: |
126 | * @key_a: the first key to be compared |
||
127 | * @key_b: the second key to be compared |
||
128 | * |
||
129 | * Provides a #cairo_hash_keys_equal_func_t which always returns |
||
130 | * %TRUE. This is useful to create hash tables using keys whose hash |
||
131 | * completely describes the key, because in this special case |
||
132 | * comparing the hashes is sufficient to guarantee that the keys are |
||
133 | * equal. |
||
134 | * |
||
135 | * Return value: %TRUE. |
||
136 | **/ |
||
137 | static cairo_bool_t |
||
138 | _cairo_hash_table_uid_keys_equal (const void *key_a, const void *key_b) |
||
139 | { |
||
140 | return TRUE; |
||
141 | } |
||
142 | |||
143 | /** |
||
1892 | serge | 144 | * _cairo_hash_table_create: |
145 | * @keys_equal: a function to return %TRUE if two keys are equal |
||
146 | * |
||
147 | * Creates a new hash table which will use the keys_equal() function |
||
148 | * to compare hash keys. Data is provided to the hash table in the |
||
149 | * form of user-derived versions of #cairo_hash_entry_t. A hash entry |
||
150 | * must be able to hold both a key (including a hash code) and a |
||
151 | * value. Sometimes only the key will be necessary, (as in |
||
152 | * _cairo_hash_table_remove), and other times both a key and a value |
||
153 | * will be necessary, (as in _cairo_hash_table_insert). |
||
154 | * |
||
3959 | Serge | 155 | * If @keys_equal is %NULL, two keys will be considered equal if and |
156 | * only if their hashes are equal. |
||
157 | * |
||
1892 | serge | 158 | * See #cairo_hash_entry_t for more details. |
159 | * |
||
160 | * Return value: the new hash table or %NULL if out of memory. |
||
161 | **/ |
||
162 | cairo_hash_table_t * |
||
163 | _cairo_hash_table_create (cairo_hash_keys_equal_func_t keys_equal) |
||
164 | { |
||
165 | cairo_hash_table_t *hash_table; |
||
166 | |||
167 | hash_table = malloc (sizeof (cairo_hash_table_t)); |
||
168 | if (unlikely (hash_table == NULL)) { |
||
169 | _cairo_error_throw (CAIRO_STATUS_NO_MEMORY); |
||
170 | return NULL; |
||
171 | } |
||
172 | |||
3959 | Serge | 173 | if (keys_equal == NULL) |
174 | hash_table->keys_equal = _cairo_hash_table_uid_keys_equal; |
||
175 | else |
||
176 | hash_table->keys_equal = keys_equal; |
||
1892 | serge | 177 | |
3959 | Serge | 178 | memset (&hash_table->cache, 0, sizeof (hash_table->cache)); |
179 | hash_table->table_size = &hash_table_sizes[0]; |
||
1892 | serge | 180 | |
3959 | Serge | 181 | hash_table->entries = calloc (*hash_table->table_size, |
182 | sizeof (cairo_hash_entry_t *)); |
||
1892 | serge | 183 | if (unlikely (hash_table->entries == NULL)) { |
184 | _cairo_error_throw (CAIRO_STATUS_NO_MEMORY); |
||
185 | free (hash_table); |
||
186 | return NULL; |
||
187 | } |
||
188 | |||
189 | hash_table->live_entries = 0; |
||
3959 | Serge | 190 | hash_table->free_entries = *hash_table->table_size; |
1892 | serge | 191 | hash_table->iterating = 0; |
192 | |||
193 | return hash_table; |
||
194 | } |
||
195 | |||
196 | /** |
||
197 | * _cairo_hash_table_destroy: |
||
198 | * @hash_table: an empty hash table to destroy |
||
199 | * |
||
200 | * Immediately destroys the given hash table, freeing all resources |
||
201 | * associated with it. |
||
202 | * |
||
203 | * WARNING: The hash_table must have no live entries in it before |
||
204 | * _cairo_hash_table_destroy is called. It is a fatal error otherwise, |
||
205 | * and this function will halt. The rationale for this behavior is to |
||
206 | * avoid memory leaks and to avoid needless complication of the API |
||
207 | * with destroy notifiy callbacks. |
||
208 | * |
||
209 | * WARNING: The hash_table must have no running iterators in it when |
||
210 | * _cairo_hash_table_destroy is called. It is a fatal error otherwise, |
||
211 | * and this function will halt. |
||
212 | **/ |
||
213 | void |
||
214 | _cairo_hash_table_destroy (cairo_hash_table_t *hash_table) |
||
215 | { |
||
216 | /* The hash table must be empty. Otherwise, halt. */ |
||
217 | assert (hash_table->live_entries == 0); |
||
218 | /* No iterators can be running. Otherwise, halt. */ |
||
219 | assert (hash_table->iterating == 0); |
||
220 | |||
221 | free (hash_table->entries); |
||
222 | free (hash_table); |
||
223 | } |
||
224 | |||
225 | static cairo_hash_entry_t ** |
||
226 | _cairo_hash_table_lookup_unique_key (cairo_hash_table_t *hash_table, |
||
227 | cairo_hash_entry_t *key) |
||
228 | { |
||
229 | unsigned long table_size, i, idx, step; |
||
230 | cairo_hash_entry_t **entry; |
||
231 | |||
3959 | Serge | 232 | table_size = *hash_table->table_size; |
1892 | serge | 233 | idx = key->hash % table_size; |
234 | |||
235 | entry = &hash_table->entries[idx]; |
||
236 | if (! ENTRY_IS_LIVE (*entry)) |
||
237 | return entry; |
||
238 | |||
239 | i = 1; |
||
3959 | Serge | 240 | step = 1 + key->hash % (table_size - 2); |
1892 | serge | 241 | do { |
242 | idx += step; |
||
243 | if (idx >= table_size) |
||
244 | idx -= table_size; |
||
245 | |||
246 | entry = &hash_table->entries[idx]; |
||
247 | if (! ENTRY_IS_LIVE (*entry)) |
||
248 | return entry; |
||
249 | } while (++i < table_size); |
||
250 | |||
251 | ASSERT_NOT_REACHED; |
||
252 | return NULL; |
||
253 | } |
||
254 | |||
255 | /** |
||
3959 | Serge | 256 | * _cairo_hash_table_manage: |
1892 | serge | 257 | * @hash_table: a hash table |
258 | * |
||
259 | * Resize the hash table if the number of entries has gotten much |
||
260 | * bigger or smaller than the ideal number of entries for the current |
||
3959 | Serge | 261 | * size and guarantee some free entries to be used as lookup |
262 | * termination points. |
||
1892 | serge | 263 | * |
264 | * Return value: %CAIRO_STATUS_SUCCESS if successful or |
||
265 | * %CAIRO_STATUS_NO_MEMORY if out of memory. |
||
266 | **/ |
||
267 | static cairo_status_t |
||
3959 | Serge | 268 | _cairo_hash_table_manage (cairo_hash_table_t *hash_table) |
1892 | serge | 269 | { |
270 | cairo_hash_table_t tmp; |
||
271 | unsigned long new_size, i; |
||
272 | |||
3959 | Serge | 273 | /* Keep between 12.5% and 50% entries in the hash table alive and |
274 | * at least 25% free. */ |
||
275 | unsigned long live_high = *hash_table->table_size >> 1; |
||
276 | unsigned long live_low = live_high >> 2; |
||
277 | unsigned long free_low = live_high >> 1; |
||
1892 | serge | 278 | |
279 | tmp = *hash_table; |
||
280 | |||
3959 | Serge | 281 | if (hash_table->live_entries > live_high) |
1892 | serge | 282 | { |
3959 | Serge | 283 | tmp.table_size = hash_table->table_size + 1; |
1892 | serge | 284 | /* This code is being abused if we can't make a table big enough. */ |
3959 | Serge | 285 | assert (tmp.table_size - hash_table_sizes < |
286 | ARRAY_LENGTH (hash_table_sizes)); |
||
1892 | serge | 287 | } |
3959 | Serge | 288 | else if (hash_table->live_entries < live_low) |
1892 | serge | 289 | { |
290 | /* Can't shrink if we're at the smallest size */ |
||
3959 | Serge | 291 | if (hash_table->table_size == &hash_table_sizes[0]) |
292 | tmp.table_size = hash_table->table_size; |
||
293 | else |
||
294 | tmp.table_size = hash_table->table_size - 1; |
||
1892 | serge | 295 | } |
296 | |||
3959 | Serge | 297 | if (tmp.table_size == hash_table->table_size && |
298 | hash_table->free_entries > free_low) |
||
299 | { |
||
300 | /* The number of live entries is within the desired bounds |
||
301 | * (we're not going to resize the table) and we have enough |
||
302 | * free entries. Do nothing. */ |
||
303 | return CAIRO_STATUS_SUCCESS; |
||
304 | } |
||
305 | |||
306 | new_size = *tmp.table_size; |
||
1892 | serge | 307 | tmp.entries = calloc (new_size, sizeof (cairo_hash_entry_t*)); |
308 | if (unlikely (tmp.entries == NULL)) |
||
309 | return _cairo_error (CAIRO_STATUS_NO_MEMORY); |
||
310 | |||
3959 | Serge | 311 | for (i = 0; i < *hash_table->table_size; ++i) { |
1892 | serge | 312 | if (ENTRY_IS_LIVE (hash_table->entries[i])) { |
313 | *_cairo_hash_table_lookup_unique_key (&tmp, hash_table->entries[i]) |
||
314 | = hash_table->entries[i]; |
||
315 | } |
||
316 | } |
||
317 | |||
318 | free (hash_table->entries); |
||
319 | hash_table->entries = tmp.entries; |
||
3959 | Serge | 320 | hash_table->table_size = tmp.table_size; |
321 | hash_table->free_entries = new_size - hash_table->live_entries; |
||
1892 | serge | 322 | |
323 | return CAIRO_STATUS_SUCCESS; |
||
324 | } |
||
325 | |||
326 | /** |
||
327 | * _cairo_hash_table_lookup: |
||
328 | * @hash_table: a hash table |
||
329 | * @key: the key of interest |
||
330 | * |
||
331 | * Performs a lookup in @hash_table looking for an entry which has a |
||
332 | * key that matches @key, (as determined by the keys_equal() function |
||
333 | * passed to _cairo_hash_table_create). |
||
334 | * |
||
335 | * Return value: the matching entry, of %NULL if no match was found. |
||
336 | **/ |
||
337 | void * |
||
338 | _cairo_hash_table_lookup (cairo_hash_table_t *hash_table, |
||
339 | cairo_hash_entry_t *key) |
||
340 | { |
||
341 | cairo_hash_entry_t *entry; |
||
342 | unsigned long table_size, i, idx, step; |
||
3959 | Serge | 343 | unsigned long hash = key->hash; |
1892 | serge | 344 | |
3959 | Serge | 345 | entry = hash_table->cache[hash & 31]; |
346 | if (entry && entry->hash == hash && hash_table->keys_equal (key, entry)) |
||
347 | return entry; |
||
1892 | serge | 348 | |
3959 | Serge | 349 | table_size = *hash_table->table_size; |
350 | idx = hash % table_size; |
||
351 | |||
1892 | serge | 352 | entry = hash_table->entries[idx]; |
353 | if (ENTRY_IS_LIVE (entry)) { |
||
3959 | Serge | 354 | if (entry->hash == hash && hash_table->keys_equal (key, entry)) |
355 | goto insert_cache; |
||
1892 | serge | 356 | } else if (ENTRY_IS_FREE (entry)) |
357 | return NULL; |
||
358 | |||
359 | i = 1; |
||
3959 | Serge | 360 | step = 1 + hash % (table_size - 2); |
1892 | serge | 361 | do { |
362 | idx += step; |
||
363 | if (idx >= table_size) |
||
364 | idx -= table_size; |
||
365 | |||
366 | entry = hash_table->entries[idx]; |
||
367 | if (ENTRY_IS_LIVE (entry)) { |
||
3959 | Serge | 368 | if (entry->hash == hash && hash_table->keys_equal (key, entry)) |
369 | goto insert_cache; |
||
1892 | serge | 370 | } else if (ENTRY_IS_FREE (entry)) |
371 | return NULL; |
||
372 | } while (++i < table_size); |
||
373 | |||
3959 | Serge | 374 | ASSERT_NOT_REACHED; |
1892 | serge | 375 | return NULL; |
3959 | Serge | 376 | |
377 | insert_cache: |
||
378 | hash_table->cache[hash & 31] = entry; |
||
379 | return entry; |
||
1892 | serge | 380 | } |
381 | |||
382 | /** |
||
383 | * _cairo_hash_table_random_entry: |
||
384 | * @hash_table: a hash table |
||
385 | * @predicate: a predicate function. |
||
386 | * |
||
387 | * Find a random entry in the hash table satisfying the given |
||
388 | * @predicate. |
||
389 | * |
||
390 | * We use the same algorithm as the lookup algorithm to walk over the |
||
391 | * entries in the hash table in a pseudo-random order. Walking |
||
392 | * linearly would favor entries following gaps in the hash table. We |
||
393 | * could also call rand() repeatedly, which works well for almost-full |
||
394 | * tables, but degrades when the table is almost empty, or predicate |
||
395 | * returns %TRUE for most entries. |
||
396 | * |
||
397 | * Return value: a random live entry or %NULL if there are no entries |
||
398 | * that match the given predicate. In particular, if predicate is |
||
399 | * %NULL, a %NULL return value indicates that the table is empty. |
||
400 | **/ |
||
401 | void * |
||
402 | _cairo_hash_table_random_entry (cairo_hash_table_t *hash_table, |
||
403 | cairo_hash_predicate_func_t predicate) |
||
404 | { |
||
405 | cairo_hash_entry_t *entry; |
||
406 | unsigned long hash; |
||
407 | unsigned long table_size, i, idx, step; |
||
408 | |||
409 | assert (predicate != NULL); |
||
410 | |||
3959 | Serge | 411 | table_size = *hash_table->table_size; |
1892 | serge | 412 | hash = rand (); |
413 | idx = hash % table_size; |
||
414 | |||
415 | entry = hash_table->entries[idx]; |
||
416 | if (ENTRY_IS_LIVE (entry) && predicate (entry)) |
||
417 | return entry; |
||
418 | |||
419 | i = 1; |
||
3959 | Serge | 420 | step = 1 + hash % (table_size - 2); |
1892 | serge | 421 | do { |
422 | idx += step; |
||
423 | if (idx >= table_size) |
||
424 | idx -= table_size; |
||
425 | |||
426 | entry = hash_table->entries[idx]; |
||
427 | if (ENTRY_IS_LIVE (entry) && predicate (entry)) |
||
428 | return entry; |
||
429 | } while (++i < table_size); |
||
430 | |||
431 | return NULL; |
||
432 | } |
||
433 | |||
434 | /** |
||
435 | * _cairo_hash_table_insert: |
||
436 | * @hash_table: a hash table |
||
437 | * @key_and_value: an entry to be inserted |
||
438 | * |
||
439 | * Insert the entry #key_and_value into the hash table. |
||
440 | * |
||
441 | * WARNING: There must not be an existing entry in the hash table |
||
442 | * with a matching key. |
||
443 | * |
||
444 | * WARNING: It is a fatal error to insert an element while |
||
445 | * an iterator is running |
||
446 | * |
||
447 | * Instead of using insert to replace an entry, consider just editing |
||
448 | * the entry obtained with _cairo_hash_table_lookup. Or if absolutely |
||
449 | * necessary, use _cairo_hash_table_remove first. |
||
450 | * |
||
451 | * Return value: %CAIRO_STATUS_SUCCESS if successful or |
||
452 | * %CAIRO_STATUS_NO_MEMORY if insufficient memory is available. |
||
453 | **/ |
||
454 | cairo_status_t |
||
455 | _cairo_hash_table_insert (cairo_hash_table_t *hash_table, |
||
456 | cairo_hash_entry_t *key_and_value) |
||
457 | { |
||
3959 | Serge | 458 | cairo_hash_entry_t **entry; |
1892 | serge | 459 | cairo_status_t status; |
460 | |||
461 | /* Insert is illegal while an iterator is running. */ |
||
462 | assert (hash_table->iterating == 0); |
||
463 | |||
3959 | Serge | 464 | status = _cairo_hash_table_manage (hash_table); |
465 | if (unlikely (status)) |
||
1892 | serge | 466 | return status; |
467 | |||
3959 | Serge | 468 | entry = _cairo_hash_table_lookup_unique_key (hash_table, key_and_value); |
1892 | serge | 469 | |
3959 | Serge | 470 | if (ENTRY_IS_FREE (*entry)) |
471 | hash_table->free_entries--; |
||
472 | |||
473 | *entry = key_and_value; |
||
474 | hash_table->cache[key_and_value->hash & 31] = key_and_value; |
||
475 | hash_table->live_entries++; |
||
476 | |||
1892 | serge | 477 | return CAIRO_STATUS_SUCCESS; |
478 | } |
||
479 | |||
480 | static cairo_hash_entry_t ** |
||
481 | _cairo_hash_table_lookup_exact_key (cairo_hash_table_t *hash_table, |
||
482 | cairo_hash_entry_t *key) |
||
483 | { |
||
484 | unsigned long table_size, i, idx, step; |
||
485 | cairo_hash_entry_t **entry; |
||
486 | |||
3959 | Serge | 487 | table_size = *hash_table->table_size; |
1892 | serge | 488 | idx = key->hash % table_size; |
489 | |||
490 | entry = &hash_table->entries[idx]; |
||
491 | if (*entry == key) |
||
492 | return entry; |
||
493 | |||
494 | i = 1; |
||
3959 | Serge | 495 | step = 1 + key->hash % (table_size - 2); |
1892 | serge | 496 | do { |
497 | idx += step; |
||
498 | if (idx >= table_size) |
||
499 | idx -= table_size; |
||
500 | |||
501 | entry = &hash_table->entries[idx]; |
||
502 | if (*entry == key) |
||
503 | return entry; |
||
504 | } while (++i < table_size); |
||
505 | |||
506 | ASSERT_NOT_REACHED; |
||
507 | return NULL; |
||
508 | } |
||
509 | /** |
||
510 | * _cairo_hash_table_remove: |
||
511 | * @hash_table: a hash table |
||
512 | * @key: key of entry to be removed |
||
513 | * |
||
514 | * Remove an entry from the hash table which points to @key. |
||
515 | * |
||
516 | * Return value: %CAIRO_STATUS_SUCCESS if successful or |
||
517 | * %CAIRO_STATUS_NO_MEMORY if out of memory. |
||
518 | **/ |
||
519 | void |
||
520 | _cairo_hash_table_remove (cairo_hash_table_t *hash_table, |
||
521 | cairo_hash_entry_t *key) |
||
522 | { |
||
523 | *_cairo_hash_table_lookup_exact_key (hash_table, key) = DEAD_ENTRY; |
||
524 | hash_table->live_entries--; |
||
3959 | Serge | 525 | hash_table->cache[key->hash & 31] = NULL; |
1892 | serge | 526 | |
527 | /* Check for table resize. Don't do this when iterating as this will |
||
528 | * reorder elements of the table and cause the iteration to potentially |
||
529 | * skip some elements. */ |
||
530 | if (hash_table->iterating == 0) { |
||
531 | /* This call _can_ fail, but only in failing to allocate new |
||
532 | * memory to shrink the hash table. It does leave the table in a |
||
533 | * consistent state, and we've already succeeded in removing the |
||
534 | * entry, so we don't examine the failure status of this call. */ |
||
3959 | Serge | 535 | _cairo_hash_table_manage (hash_table); |
1892 | serge | 536 | } |
537 | } |
||
538 | |||
539 | /** |
||
540 | * _cairo_hash_table_foreach: |
||
541 | * @hash_table: a hash table |
||
542 | * @hash_callback: function to be called for each live entry |
||
543 | * @closure: additional argument to be passed to @hash_callback |
||
544 | * |
||
545 | * Call @hash_callback for each live entry in the hash table, in a |
||
546 | * non-specified order. |
||
547 | * |
||
548 | * Entries in @hash_table may be removed by code executed from @hash_callback. |
||
549 | * |
||
550 | * Entries may not be inserted to @hash_table, nor may @hash_table |
||
551 | * be destroyed by code executed from @hash_callback. The relevant |
||
552 | * functions will halt in these cases. |
||
553 | **/ |
||
554 | void |
||
555 | _cairo_hash_table_foreach (cairo_hash_table_t *hash_table, |
||
556 | cairo_hash_callback_func_t hash_callback, |
||
557 | void *closure) |
||
558 | { |
||
559 | unsigned long i; |
||
560 | cairo_hash_entry_t *entry; |
||
561 | |||
562 | /* Mark the table for iteration */ |
||
563 | ++hash_table->iterating; |
||
3959 | Serge | 564 | for (i = 0; i < *hash_table->table_size; i++) { |
1892 | serge | 565 | entry = hash_table->entries[i]; |
566 | if (ENTRY_IS_LIVE(entry)) |
||
567 | hash_callback (entry, closure); |
||
568 | } |
||
569 | /* If some elements were deleted during the iteration, |
||
570 | * the table may need resizing. Just do this every time |
||
571 | * as the check is inexpensive. |
||
572 | */ |
||
573 | if (--hash_table->iterating == 0) { |
||
574 | /* Should we fail to shrink the hash table, it is left unaltered, |
||
575 | * and we don't need to propagate the error status. */ |
||
3959 | Serge | 576 | _cairo_hash_table_manage (hash_table); |
1892 | serge | 577 | } |
578 | }>>>>>> |