Line data Source code
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 <keithp@keithp.com>
35 : * Graydon Hoare <graydon@redhat.com>
36 : * Carl Worth <cworth@cworth.org>
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 :
62 : /* We expect keys will not be destroyed frequently, so our table does not
63 : * contain any explicit shrinking code nor any chain-coalescing code for
64 : * entries randomly deleted by memory pressure (except during rehashing, of
65 : * course). These assumptions are potentially bad, but they make the
66 : * implementation straightforward.
67 : *
68 : * Revisit later if evidence appears that we're using excessive memory from
69 : * a mostly-dead table.
70 : *
71 : * This table is open-addressed with double hashing. Each table size is a
72 : * prime chosen to be a little more than double the high water mark for a
73 : * given arrangement, so the tables should remain < 50% full. The table
74 : * size makes for the "first" hash modulus; a second prime (2 less than the
75 : * first prime) serves as the "second" hash modulus, which is co-prime and
76 : * thus guarantees a complete permutation of table indices.
77 : *
78 : * This structure, and accompanying table, is borrowed/modified from the
79 : * file xserver/render/glyph.c in the freedesktop.org x server, with
80 : * permission (and suggested modification of doubling sizes) by Keith
81 : * Packard.
82 : */
83 :
84 : typedef struct _cairo_hash_table_arrangement {
85 : unsigned long high_water_mark;
86 : unsigned long size;
87 : unsigned long rehash;
88 : } cairo_hash_table_arrangement_t;
89 :
90 : static const cairo_hash_table_arrangement_t hash_table_arrangements [] = {
91 : { 16, 43, 41 },
92 : { 32, 73, 71 },
93 : { 64, 151, 149 },
94 : { 128, 283, 281 },
95 : { 256, 571, 569 },
96 : { 512, 1153, 1151 },
97 : { 1024, 2269, 2267 },
98 : { 2048, 4519, 4517 },
99 : { 4096, 9013, 9011 },
100 : { 8192, 18043, 18041 },
101 : { 16384, 36109, 36107 },
102 : { 32768, 72091, 72089 },
103 : { 65536, 144409, 144407 },
104 : { 131072, 288361, 288359 },
105 : { 262144, 576883, 576881 },
106 : { 524288, 1153459, 1153457 },
107 : { 1048576, 2307163, 2307161 },
108 : { 2097152, 4613893, 4613891 },
109 : { 4194304, 9227641, 9227639 },
110 : { 8388608, 18455029, 18455027 },
111 : { 16777216, 36911011, 36911009 },
112 : { 33554432, 73819861, 73819859 },
113 : { 67108864, 147639589, 147639587 },
114 : { 134217728, 295279081, 295279079 },
115 : { 268435456, 590559793, 590559791 }
116 : };
117 :
118 : #define NUM_HASH_TABLE_ARRANGEMENTS ARRAY_LENGTH (hash_table_arrangements)
119 :
120 : struct _cairo_hash_table {
121 : cairo_hash_keys_equal_func_t keys_equal;
122 :
123 : const cairo_hash_table_arrangement_t *arrangement;
124 : cairo_hash_entry_t **entries;
125 :
126 : unsigned long live_entries;
127 : unsigned long iterating; /* Iterating, no insert, no resize */
128 : };
129 :
130 : /**
131 : * _cairo_hash_table_create:
132 : * @keys_equal: a function to return %TRUE if two keys are equal
133 : *
134 : * Creates a new hash table which will use the keys_equal() function
135 : * to compare hash keys. Data is provided to the hash table in the
136 : * form of user-derived versions of #cairo_hash_entry_t. A hash entry
137 : * must be able to hold both a key (including a hash code) and a
138 : * value. Sometimes only the key will be necessary, (as in
139 : * _cairo_hash_table_remove), and other times both a key and a value
140 : * will be necessary, (as in _cairo_hash_table_insert).
141 : *
142 : * See #cairo_hash_entry_t for more details.
143 : *
144 : * Return value: the new hash table or %NULL if out of memory.
145 : **/
146 : cairo_hash_table_t *
147 19 : _cairo_hash_table_create (cairo_hash_keys_equal_func_t keys_equal)
148 : {
149 : cairo_hash_table_t *hash_table;
150 :
151 19 : hash_table = malloc (sizeof (cairo_hash_table_t));
152 19 : if (unlikely (hash_table == NULL)) {
153 0 : _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
154 0 : return NULL;
155 : }
156 :
157 19 : hash_table->keys_equal = keys_equal;
158 :
159 19 : hash_table->arrangement = &hash_table_arrangements[0];
160 :
161 19 : hash_table->entries = calloc (hash_table->arrangement->size,
162 : sizeof(cairo_hash_entry_t *));
163 19 : if (unlikely (hash_table->entries == NULL)) {
164 0 : _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
165 0 : free (hash_table);
166 0 : return NULL;
167 : }
168 :
169 19 : hash_table->live_entries = 0;
170 19 : hash_table->iterating = 0;
171 :
172 19 : return hash_table;
173 : }
174 :
175 : /**
176 : * _cairo_hash_table_destroy:
177 : * @hash_table: an empty hash table to destroy
178 : *
179 : * Immediately destroys the given hash table, freeing all resources
180 : * associated with it.
181 : *
182 : * WARNING: The hash_table must have no live entries in it before
183 : * _cairo_hash_table_destroy is called. It is a fatal error otherwise,
184 : * and this function will halt. The rationale for this behavior is to
185 : * avoid memory leaks and to avoid needless complication of the API
186 : * with destroy notifiy callbacks.
187 : *
188 : * WARNING: The hash_table must have no running iterators in it when
189 : * _cairo_hash_table_destroy is called. It is a fatal error otherwise,
190 : * and this function will halt.
191 : **/
192 : void
193 0 : _cairo_hash_table_destroy (cairo_hash_table_t *hash_table)
194 : {
195 : /* The hash table must be empty. Otherwise, halt. */
196 0 : assert (hash_table->live_entries == 0);
197 : /* No iterators can be running. Otherwise, halt. */
198 0 : assert (hash_table->iterating == 0);
199 :
200 0 : free (hash_table->entries);
201 0 : hash_table->entries = NULL;
202 :
203 0 : free (hash_table);
204 0 : }
205 :
206 : static cairo_hash_entry_t **
207 252 : _cairo_hash_table_lookup_unique_key (cairo_hash_table_t *hash_table,
208 : cairo_hash_entry_t *key)
209 : {
210 : unsigned long table_size, i, idx, step;
211 : cairo_hash_entry_t **entry;
212 :
213 252 : table_size = hash_table->arrangement->size;
214 252 : idx = key->hash % table_size;
215 :
216 252 : entry = &hash_table->entries[idx];
217 252 : if (! ENTRY_IS_LIVE (*entry))
218 241 : return entry;
219 :
220 11 : i = 1;
221 11 : step = key->hash % hash_table->arrangement->rehash;
222 11 : if (step == 0)
223 0 : step = 1;
224 : do {
225 19 : idx += step;
226 19 : if (idx >= table_size)
227 1 : idx -= table_size;
228 :
229 19 : entry = &hash_table->entries[idx];
230 19 : if (! ENTRY_IS_LIVE (*entry))
231 11 : return entry;
232 8 : } while (++i < table_size);
233 :
234 0 : ASSERT_NOT_REACHED;
235 0 : return NULL;
236 : }
237 :
238 : /**
239 : * _cairo_hash_table_resize:
240 : * @hash_table: a hash table
241 : *
242 : * Resize the hash table if the number of entries has gotten much
243 : * bigger or smaller than the ideal number of entries for the current
244 : * size.
245 : *
246 : * Return value: %CAIRO_STATUS_SUCCESS if successful or
247 : * %CAIRO_STATUS_NO_MEMORY if out of memory.
248 : **/
249 : static cairo_status_t
250 156 : _cairo_hash_table_resize (cairo_hash_table_t *hash_table)
251 : {
252 : cairo_hash_table_t tmp;
253 : unsigned long new_size, i;
254 :
255 : /* This keeps the hash table between 25% and 50% full. */
256 156 : unsigned long high = hash_table->arrangement->high_water_mark;
257 156 : unsigned long low = high >> 2;
258 :
259 156 : if (hash_table->live_entries >= low && hash_table->live_entries <= high)
260 115 : return CAIRO_STATUS_SUCCESS;
261 :
262 41 : tmp = *hash_table;
263 :
264 41 : if (hash_table->live_entries > high)
265 : {
266 5 : tmp.arrangement = hash_table->arrangement + 1;
267 : /* This code is being abused if we can't make a table big enough. */
268 5 : assert (tmp.arrangement - hash_table_arrangements <
269 : NUM_HASH_TABLE_ARRANGEMENTS);
270 : }
271 : else /* hash_table->live_entries < low */
272 : {
273 : /* Can't shrink if we're at the smallest size */
274 36 : if (hash_table->arrangement == &hash_table_arrangements[0])
275 36 : return CAIRO_STATUS_SUCCESS;
276 0 : tmp.arrangement = hash_table->arrangement - 1;
277 : }
278 :
279 5 : new_size = tmp.arrangement->size;
280 5 : tmp.entries = calloc (new_size, sizeof (cairo_hash_entry_t*));
281 5 : if (unlikely (tmp.entries == NULL))
282 0 : return _cairo_error (CAIRO_STATUS_NO_MEMORY);
283 :
284 250 : for (i = 0; i < hash_table->arrangement->size; ++i) {
285 245 : if (ENTRY_IS_LIVE (hash_table->entries[i])) {
286 96 : *_cairo_hash_table_lookup_unique_key (&tmp, hash_table->entries[i])
287 96 : = hash_table->entries[i];
288 : }
289 : }
290 :
291 5 : free (hash_table->entries);
292 5 : hash_table->entries = tmp.entries;
293 5 : hash_table->arrangement = tmp.arrangement;
294 :
295 5 : return CAIRO_STATUS_SUCCESS;
296 : }
297 :
298 : /**
299 : * _cairo_hash_table_lookup:
300 : * @hash_table: a hash table
301 : * @key: the key of interest
302 : *
303 : * Performs a lookup in @hash_table looking for an entry which has a
304 : * key that matches @key, (as determined by the keys_equal() function
305 : * passed to _cairo_hash_table_create).
306 : *
307 : * Return value: the matching entry, of %NULL if no match was found.
308 : **/
309 : void *
310 358 : _cairo_hash_table_lookup (cairo_hash_table_t *hash_table,
311 : cairo_hash_entry_t *key)
312 : {
313 : cairo_hash_entry_t *entry;
314 : unsigned long table_size, i, idx, step;
315 :
316 358 : table_size = hash_table->arrangement->size;
317 358 : idx = key->hash % table_size;
318 :
319 358 : entry = hash_table->entries[idx];
320 358 : if (ENTRY_IS_LIVE (entry)) {
321 216 : if (hash_table->keys_equal (key, entry))
322 206 : return entry;
323 142 : } else if (ENTRY_IS_FREE (entry))
324 142 : return NULL;
325 :
326 10 : i = 1;
327 10 : step = key->hash % hash_table->arrangement->rehash;
328 10 : if (step == 0)
329 0 : step = 1;
330 : do {
331 18 : idx += step;
332 18 : if (idx >= table_size)
333 1 : idx -= table_size;
334 :
335 18 : entry = hash_table->entries[idx];
336 18 : if (ENTRY_IS_LIVE (entry)) {
337 11 : if (hash_table->keys_equal (key, entry))
338 3 : return entry;
339 7 : } else if (ENTRY_IS_FREE (entry))
340 7 : return NULL;
341 8 : } while (++i < table_size);
342 :
343 0 : return NULL;
344 : }
345 :
346 : /**
347 : * _cairo_hash_table_random_entry:
348 : * @hash_table: a hash table
349 : * @predicate: a predicate function.
350 : *
351 : * Find a random entry in the hash table satisfying the given
352 : * @predicate.
353 : *
354 : * We use the same algorithm as the lookup algorithm to walk over the
355 : * entries in the hash table in a pseudo-random order. Walking
356 : * linearly would favor entries following gaps in the hash table. We
357 : * could also call rand() repeatedly, which works well for almost-full
358 : * tables, but degrades when the table is almost empty, or predicate
359 : * returns %TRUE for most entries.
360 : *
361 : * Return value: a random live entry or %NULL if there are no entries
362 : * that match the given predicate. In particular, if predicate is
363 : * %NULL, a %NULL return value indicates that the table is empty.
364 : **/
365 : void *
366 0 : _cairo_hash_table_random_entry (cairo_hash_table_t *hash_table,
367 : cairo_hash_predicate_func_t predicate)
368 : {
369 : cairo_hash_entry_t *entry;
370 : unsigned long hash;
371 : unsigned long table_size, i, idx, step;
372 :
373 0 : assert (predicate != NULL);
374 :
375 0 : table_size = hash_table->arrangement->size;
376 0 : hash = rand ();
377 0 : idx = hash % table_size;
378 :
379 0 : entry = hash_table->entries[idx];
380 0 : if (ENTRY_IS_LIVE (entry) && predicate (entry))
381 0 : return entry;
382 :
383 0 : i = 1;
384 0 : step = hash % hash_table->arrangement->rehash;
385 0 : if (step == 0)
386 0 : step = 1;
387 : do {
388 0 : idx += step;
389 0 : if (idx >= table_size)
390 0 : idx -= table_size;
391 :
392 0 : entry = hash_table->entries[idx];
393 0 : if (ENTRY_IS_LIVE (entry) && predicate (entry))
394 0 : return entry;
395 0 : } while (++i < table_size);
396 :
397 0 : return NULL;
398 : }
399 :
400 : /**
401 : * _cairo_hash_table_insert:
402 : * @hash_table: a hash table
403 : * @key_and_value: an entry to be inserted
404 : *
405 : * Insert the entry #key_and_value into the hash table.
406 : *
407 : * WARNING: There must not be an existing entry in the hash table
408 : * with a matching key.
409 : *
410 : * WARNING: It is a fatal error to insert an element while
411 : * an iterator is running
412 : *
413 : * Instead of using insert to replace an entry, consider just editing
414 : * the entry obtained with _cairo_hash_table_lookup. Or if absolutely
415 : * necessary, use _cairo_hash_table_remove first.
416 : *
417 : * Return value: %CAIRO_STATUS_SUCCESS if successful or
418 : * %CAIRO_STATUS_NO_MEMORY if insufficient memory is available.
419 : **/
420 : cairo_status_t
421 156 : _cairo_hash_table_insert (cairo_hash_table_t *hash_table,
422 : cairo_hash_entry_t *key_and_value)
423 : {
424 : cairo_status_t status;
425 :
426 : /* Insert is illegal while an iterator is running. */
427 156 : assert (hash_table->iterating == 0);
428 :
429 156 : hash_table->live_entries++;
430 156 : status = _cairo_hash_table_resize (hash_table);
431 156 : if (unlikely (status)) {
432 : /* abort the insert... */
433 0 : hash_table->live_entries--;
434 0 : return status;
435 : }
436 :
437 156 : *_cairo_hash_table_lookup_unique_key (hash_table,
438 156 : key_and_value) = key_and_value;
439 :
440 156 : return CAIRO_STATUS_SUCCESS;
441 : }
442 :
443 : static cairo_hash_entry_t **
444 0 : _cairo_hash_table_lookup_exact_key (cairo_hash_table_t *hash_table,
445 : cairo_hash_entry_t *key)
446 : {
447 : unsigned long table_size, i, idx, step;
448 : cairo_hash_entry_t **entry;
449 :
450 0 : table_size = hash_table->arrangement->size;
451 0 : idx = key->hash % table_size;
452 :
453 0 : entry = &hash_table->entries[idx];
454 0 : if (*entry == key)
455 0 : return entry;
456 :
457 0 : i = 1;
458 0 : step = key->hash % hash_table->arrangement->rehash;
459 0 : if (step == 0)
460 0 : step = 1;
461 : do {
462 0 : idx += step;
463 0 : if (idx >= table_size)
464 0 : idx -= table_size;
465 :
466 0 : entry = &hash_table->entries[idx];
467 0 : if (*entry == key)
468 0 : return entry;
469 0 : } while (++i < table_size);
470 :
471 0 : ASSERT_NOT_REACHED;
472 0 : return NULL;
473 : }
474 : /**
475 : * _cairo_hash_table_remove:
476 : * @hash_table: a hash table
477 : * @key: key of entry to be removed
478 : *
479 : * Remove an entry from the hash table which points to @key.
480 : *
481 : * Return value: %CAIRO_STATUS_SUCCESS if successful or
482 : * %CAIRO_STATUS_NO_MEMORY if out of memory.
483 : **/
484 : void
485 0 : _cairo_hash_table_remove (cairo_hash_table_t *hash_table,
486 : cairo_hash_entry_t *key)
487 : {
488 0 : *_cairo_hash_table_lookup_exact_key (hash_table, key) = DEAD_ENTRY;
489 0 : hash_table->live_entries--;
490 :
491 : /* Check for table resize. Don't do this when iterating as this will
492 : * reorder elements of the table and cause the iteration to potentially
493 : * skip some elements. */
494 0 : if (hash_table->iterating == 0) {
495 : /* This call _can_ fail, but only in failing to allocate new
496 : * memory to shrink the hash table. It does leave the table in a
497 : * consistent state, and we've already succeeded in removing the
498 : * entry, so we don't examine the failure status of this call. */
499 0 : _cairo_hash_table_resize (hash_table);
500 : }
501 0 : }
502 :
503 : /**
504 : * _cairo_hash_table_foreach:
505 : * @hash_table: a hash table
506 : * @hash_callback: function to be called for each live entry
507 : * @closure: additional argument to be passed to @hash_callback
508 : *
509 : * Call @hash_callback for each live entry in the hash table, in a
510 : * non-specified order.
511 : *
512 : * Entries in @hash_table may be removed by code executed from @hash_callback.
513 : *
514 : * Entries may not be inserted to @hash_table, nor may @hash_table
515 : * be destroyed by code executed from @hash_callback. The relevant
516 : * functions will halt in these cases.
517 : **/
518 : void
519 0 : _cairo_hash_table_foreach (cairo_hash_table_t *hash_table,
520 : cairo_hash_callback_func_t hash_callback,
521 : void *closure)
522 : {
523 : unsigned long i;
524 : cairo_hash_entry_t *entry;
525 :
526 : /* Mark the table for iteration */
527 0 : ++hash_table->iterating;
528 0 : for (i = 0; i < hash_table->arrangement->size; i++) {
529 0 : entry = hash_table->entries[i];
530 0 : if (ENTRY_IS_LIVE(entry))
531 0 : hash_callback (entry, closure);
532 : }
533 : /* If some elements were deleted during the iteration,
534 : * the table may need resizing. Just do this every time
535 : * as the check is inexpensive.
536 : */
537 0 : if (--hash_table->iterating == 0) {
538 : /* Should we fail to shrink the hash table, it is left unaltered,
539 : * and we don't need to propagate the error status. */
540 0 : _cairo_hash_table_resize (hash_table);
541 : }
542 0 : }
|
