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 *
_cairo_hash_table_create(cairo_hash_keys_equal_func_t keys_equal)147 _cairo_hash_table_create (cairo_hash_keys_equal_func_t keys_equal)
148 {
149 cairo_hash_table_t *hash_table;
150
151 hash_table = malloc (sizeof (cairo_hash_table_t));
152 if (unlikely (hash_table == NULL)) {
153 _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
154 return NULL;
155 }
156
157 hash_table->keys_equal = keys_equal;
158
159 hash_table->arrangement = &hash_table_arrangements[0];
160
161 hash_table->entries = calloc (hash_table->arrangement->size,
162 sizeof(cairo_hash_entry_t *));
163 if (unlikely (hash_table->entries == NULL)) {
164 _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
165 free (hash_table);
166 return NULL;
167 }
168
169 hash_table->live_entries = 0;
170 hash_table->iterating = 0;
171
172 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
_cairo_hash_table_destroy(cairo_hash_table_t * hash_table)193 _cairo_hash_table_destroy (cairo_hash_table_t *hash_table)
194 {
195 /* The hash table must be empty. Otherwise, halt. */
196 assert (hash_table->live_entries == 0);
197 /* No iterators can be running. Otherwise, halt. */
198 assert (hash_table->iterating == 0);
199
200 free (hash_table->entries);
201 hash_table->entries = NULL;
202
203 free (hash_table);
204 }
205
206 static cairo_hash_entry_t **
_cairo_hash_table_lookup_unique_key(cairo_hash_table_t * hash_table,cairo_hash_entry_t * key)207 _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 table_size = hash_table->arrangement->size;
214 idx = key->hash % table_size;
215
216 entry = &hash_table->entries[idx];
217 if (! ENTRY_IS_LIVE (*entry))
218 return entry;
219
220 i = 1;
221 step = key->hash % hash_table->arrangement->rehash;
222 if (step == 0)
223 step = 1;
224 do {
225 idx += step;
226 if (idx >= table_size)
227 idx -= table_size;
228
229 entry = &hash_table->entries[idx];
230 if (! ENTRY_IS_LIVE (*entry))
231 return entry;
232 } while (++i < table_size);
233
234 ASSERT_NOT_REACHED;
235 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
_cairo_hash_table_resize(cairo_hash_table_t * hash_table)250 _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 unsigned long high = hash_table->arrangement->high_water_mark;
257 unsigned long low = high >> 2;
258
259 if (hash_table->live_entries >= low && hash_table->live_entries <= high)
260 return CAIRO_STATUS_SUCCESS;
261
262 tmp = *hash_table;
263
264 if (hash_table->live_entries > high)
265 {
266 tmp.arrangement = hash_table->arrangement + 1;
267 /* This code is being abused if we can't make a table big enough. */
268 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 if (hash_table->arrangement == &hash_table_arrangements[0])
275 return CAIRO_STATUS_SUCCESS;
276 tmp.arrangement = hash_table->arrangement - 1;
277 }
278
279 new_size = tmp.arrangement->size;
280 tmp.entries = calloc (new_size, sizeof (cairo_hash_entry_t*));
281 if (unlikely (tmp.entries == NULL))
282 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
283
284 for (i = 0; i < hash_table->arrangement->size; ++i) {
285 if (ENTRY_IS_LIVE (hash_table->entries[i])) {
286 *_cairo_hash_table_lookup_unique_key (&tmp, hash_table->entries[i])
287 = hash_table->entries[i];
288 }
289 }
290
291 free (hash_table->entries);
292 hash_table->entries = tmp.entries;
293 hash_table->arrangement = tmp.arrangement;
294
295 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 *
_cairo_hash_table_lookup(cairo_hash_table_t * hash_table,cairo_hash_entry_t * key)310 _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 table_size = hash_table->arrangement->size;
317 idx = key->hash % table_size;
318
319 entry = hash_table->entries[idx];
320 if (ENTRY_IS_LIVE (entry)) {
321 if (hash_table->keys_equal (key, entry))
322 return entry;
323 } else if (ENTRY_IS_FREE (entry))
324 return NULL;
325
326 i = 1;
327 step = key->hash % hash_table->arrangement->rehash;
328 if (step == 0)
329 step = 1;
330 do {
331 idx += step;
332 if (idx >= table_size)
333 idx -= table_size;
334
335 entry = hash_table->entries[idx];
336 if (ENTRY_IS_LIVE (entry)) {
337 if (hash_table->keys_equal (key, entry))
338 return entry;
339 } else if (ENTRY_IS_FREE (entry))
340 return NULL;
341 } while (++i < table_size);
342
343 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 *
_cairo_hash_table_random_entry(cairo_hash_table_t * hash_table,cairo_hash_predicate_func_t predicate)366 _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 assert (predicate != NULL);
374
375 table_size = hash_table->arrangement->size;
376 hash = rand ();
377 idx = hash % table_size;
378
379 entry = hash_table->entries[idx];
380 if (ENTRY_IS_LIVE (entry) && predicate (entry))
381 return entry;
382
383 i = 1;
384 step = hash % hash_table->arrangement->rehash;
385 if (step == 0)
386 step = 1;
387 do {
388 idx += step;
389 if (idx >= table_size)
390 idx -= table_size;
391
392 entry = hash_table->entries[idx];
393 if (ENTRY_IS_LIVE (entry) && predicate (entry))
394 return entry;
395 } while (++i < table_size);
396
397 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
_cairo_hash_table_insert(cairo_hash_table_t * hash_table,cairo_hash_entry_t * key_and_value)421 _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 assert (hash_table->iterating == 0);
428
429 hash_table->live_entries++;
430 status = _cairo_hash_table_resize (hash_table);
431 if (unlikely (status)) {
432 /* abort the insert... */
433 hash_table->live_entries--;
434 return status;
435 }
436
437 *_cairo_hash_table_lookup_unique_key (hash_table,
438 key_and_value) = key_and_value;
439
440 return CAIRO_STATUS_SUCCESS;
441 }
442
443 static cairo_hash_entry_t **
_cairo_hash_table_lookup_exact_key(cairo_hash_table_t * hash_table,cairo_hash_entry_t * key)444 _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 table_size = hash_table->arrangement->size;
451 idx = key->hash % table_size;
452
453 entry = &hash_table->entries[idx];
454 if (*entry == key)
455 return entry;
456
457 i = 1;
458 step = key->hash % hash_table->arrangement->rehash;
459 if (step == 0)
460 step = 1;
461 do {
462 idx += step;
463 if (idx >= table_size)
464 idx -= table_size;
465
466 entry = &hash_table->entries[idx];
467 if (*entry == key)
468 return entry;
469 } while (++i < table_size);
470
471 ASSERT_NOT_REACHED;
472 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
_cairo_hash_table_remove(cairo_hash_table_t * hash_table,cairo_hash_entry_t * key)485 _cairo_hash_table_remove (cairo_hash_table_t *hash_table,
486 cairo_hash_entry_t *key)
487 {
488 *_cairo_hash_table_lookup_exact_key (hash_table, key) = DEAD_ENTRY;
489 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 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 _cairo_hash_table_resize (hash_table);
500 }
501 }
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
_cairo_hash_table_foreach(cairo_hash_table_t * hash_table,cairo_hash_callback_func_t hash_callback,void * closure)519 _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 ++hash_table->iterating;
528 for (i = 0; i < hash_table->arrangement->size; i++) {
529 entry = hash_table->entries[i];
530 if (ENTRY_IS_LIVE(entry))
531 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 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 _cairo_hash_table_resize (hash_table);
541 }
542 }
543