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 /*
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.
68 *
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.
72 *
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.
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
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
109 };
110
111 struct _cairo_hash_table {
112 cairo_hash_keys_equal_func_t keys_equal;
113
114 cairo_hash_entry_t *cache[32];
115
116 const unsigned long *table_size;
117 cairo_hash_entry_t **entries;
118
119 unsigned long live_entries;
120 unsigned long free_entries;
121 unsigned long iterating; /* Iterating, no insert, no resize */
122 };
123
124 /**
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
_cairo_hash_table_uid_keys_equal(const void * key_a,const void * key_b)138 _cairo_hash_table_uid_keys_equal (const void *key_a, const void *key_b)
139 {
140 return TRUE;
141 }
142
143 /**
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 *
155 * If @keys_equal is %NULL, two keys will be considered equal if and
156 * only if their hashes are equal.
157 *
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 *
_cairo_hash_table_create(cairo_hash_keys_equal_func_t keys_equal)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 = _cairo_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
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;
177
178 memset (&hash_table->cache, 0, sizeof (hash_table->cache));
179 hash_table->table_size = &hash_table_sizes[0];
180
181 hash_table->entries = calloc (*hash_table->table_size,
182 sizeof (cairo_hash_entry_t *));
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;
190 hash_table->free_entries = *hash_table->table_size;
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 notify 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
_cairo_hash_table_destroy(cairo_hash_table_t * hash_table)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 **
_cairo_hash_table_lookup_unique_key(cairo_hash_table_t * hash_table,cairo_hash_entry_t * key)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
232 table_size = *hash_table->table_size;
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;
240 step = 1 + key->hash % (table_size - 2);
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 /**
256 * _cairo_hash_table_manage:
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
261 * size and guarantee some free entries to be used as lookup
262 * termination points.
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
_cairo_hash_table_manage(cairo_hash_table_t * hash_table)268 _cairo_hash_table_manage (cairo_hash_table_t *hash_table)
269 {
270 cairo_hash_table_t tmp;
271 unsigned long new_size, i;
272
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;
278
279 tmp = *hash_table;
280
281 if (hash_table->live_entries > live_high)
282 {
283 tmp.table_size = hash_table->table_size + 1;
284 /* This code is being abused if we can't make a table big enough. */
285 assert (tmp.table_size - hash_table_sizes <
286 ARRAY_LENGTH (hash_table_sizes));
287 }
288 else if (hash_table->live_entries < live_low)
289 {
290 /* Can't shrink if we're at the smallest size */
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;
295 }
296
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;
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
311 for (i = 0; i < *hash_table->table_size; ++i) {
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;
320 hash_table->table_size = tmp.table_size;
321 hash_table->free_entries = new_size - hash_table->live_entries;
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 *
_cairo_hash_table_lookup(cairo_hash_table_t * hash_table,cairo_hash_entry_t * key)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;
343 unsigned long hash = key->hash;
344
345 entry = hash_table->cache[hash & 31];
346 if (entry && entry->hash == hash && hash_table->keys_equal (key, entry))
347 return entry;
348
349 table_size = *hash_table->table_size;
350 idx = hash % table_size;
351
352 entry = hash_table->entries[idx];
353 if (ENTRY_IS_LIVE (entry)) {
354 if (entry->hash == hash && hash_table->keys_equal (key, entry))
355 goto insert_cache;
356 } else if (ENTRY_IS_FREE (entry))
357 return NULL;
358
359 i = 1;
360 step = 1 + hash % (table_size - 2);
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)) {
368 if (entry->hash == hash && hash_table->keys_equal (key, entry))
369 goto insert_cache;
370 } else if (ENTRY_IS_FREE (entry))
371 return NULL;
372 } while (++i < table_size);
373
374 ASSERT_NOT_REACHED;
375 return NULL;
376
377 insert_cache:
378 hash_table->cache[hash & 31] = entry;
379 return entry;
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 *
_cairo_hash_table_random_entry(cairo_hash_table_t * hash_table,cairo_hash_predicate_func_t predicate)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
411 table_size = *hash_table->table_size;
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;
420 step = 1 + hash % (table_size - 2);
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
_cairo_hash_table_insert(cairo_hash_table_t * hash_table,cairo_hash_entry_t * key_and_value)455 _cairo_hash_table_insert (cairo_hash_table_t *hash_table,
456 cairo_hash_entry_t *key_and_value)
457 {
458 cairo_hash_entry_t **entry;
459 cairo_status_t status;
460
461 /* Insert is illegal while an iterator is running. */
462 assert (hash_table->iterating == 0);
463
464 status = _cairo_hash_table_manage (hash_table);
465 if (unlikely (status))
466 return status;
467
468 entry = _cairo_hash_table_lookup_unique_key (hash_table, key_and_value);
469
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
477 return CAIRO_STATUS_SUCCESS;
478 }
479
480 static cairo_hash_entry_t **
_cairo_hash_table_lookup_exact_key(cairo_hash_table_t * hash_table,cairo_hash_entry_t * key)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
487 table_size = *hash_table->table_size;
488 idx = key->hash % table_size;
489
490 entry = &hash_table->entries[idx];
491 if (*entry == key)
492 return entry;
493
494 i = 1;
495 step = 1 + key->hash % (table_size - 2);
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
_cairo_hash_table_remove(cairo_hash_table_t * hash_table,cairo_hash_entry_t * key)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--;
525 hash_table->cache[key->hash & 31] = NULL;
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. */
535 _cairo_hash_table_manage (hash_table);
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
_cairo_hash_table_foreach(cairo_hash_table_t * hash_table,cairo_hash_callback_func_t hash_callback,void * closure)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;
564 for (i = 0; i < *hash_table->table_size; i++) {
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. */
576 _cairo_hash_table_manage (hash_table);
577 }
578 }
579