diff options
Diffstat (limited to 'src/cairo-hash.c')
| -rw-r--r-- | src/cairo-hash.c | 740 |
1 files changed, 380 insertions, 360 deletions
diff --git a/src/cairo-hash.c b/src/cairo-hash.c index e7547bc29..e44ab3025 100644 --- a/src/cairo-hash.c +++ b/src/cairo-hash.c @@ -1,6 +1,7 @@ /* cairo - a vector graphics library with display and print output * - * This file is Copyright © 2004 Red Hat, Inc. + * Copyright © 2004 Red Hat, Inc. + * Copyright © 2005 Red Hat, Inc. * * This library is free software; you can redistribute it and/or * modify it either under the terms of the GNU Lesser General Public @@ -30,61 +31,35 @@ * The Initial Developer of the Original Code is Red Hat, Inc. * * Contributor(s): - * Keith Packard + * Keith Packard <keithp@keithp.com> * Graydon Hoare <graydon@redhat.com> + * Carl Worth <cworth@cworth.org> */ #include "cairoint.h" -/* - * This structure, and accompanying table, is borrowed/modified from the - * file xserver/render/glyph.c in the freedesktop.org x server, with - * permission (and suggested modification of doubling sizes) by Keith - * Packard. +/* + * An entry can be in one of three states: + * + * FREE: Entry has never been used, terminates all searches. + * Appears in the table as a NULL pointer. + * + * DEAD: Entry had been live in the past. A dead entry can be reused + * but does not terminate a search for an exact entry. + * Appears in the table as a pointer to DEAD_ENTRY. + * + * LIVE: Entry is currently being used. + * Appears in the table as any non-NULL, non-DEAD_ENTRY pointer. */ -static const cairo_cache_arrangement_t cache_arrangements [] = { - { 16, 43, 41 }, - { 32, 73, 71 }, - { 64, 151, 149 }, - { 128, 283, 281 }, - { 256, 571, 569 }, - { 512, 1153, 1151 }, - { 1024, 2269, 2267 }, - { 2048, 4519, 4517 }, - { 4096, 9013, 9011 }, - { 8192, 18043, 18041 }, - { 16384, 36109, 36107 }, - { 32768, 72091, 72089 }, - { 65536, 144409, 144407 }, - { 131072, 288361, 288359 }, - { 262144, 576883, 576881 }, - { 524288, 1153459, 1153457 }, - { 1048576, 2307163, 2307161 }, - { 2097152, 4613893, 4613891 }, - { 4194304, 9227641, 9227639 }, - { 8388608, 18455029, 18455027 }, - { 16777216, 36911011, 36911009 }, - { 33554432, 73819861, 73819859 }, - { 67108864, 147639589, 147639587 }, - { 134217728, 295279081, 295279079 }, - { 268435456, 590559793, 590559791 } -}; +static cairo_hash_entry_t dead_entry = { 0 }; +#define DEAD_ENTRY (&dead_entry) -#define N_CACHE_SIZES (sizeof(cache_arrangements)/sizeof(cache_arrangements[0])) +#define ENTRY_IS_FREE(entry) ((entry) == NULL) +#define ENTRY_IS_DEAD(entry) ((entry) == DEAD_ENTRY) +#define ENTRY_IS_LIVE(entry) ((entry) && ! ENTRY_IS_DEAD(entry)) -/* - * Entries 'e' are poiners, in one of 3 states: - * - * e == NULL: The entry has never had anything put in it - * e != DEAD_ENTRY: The entry has an active value in it currently - * e == DEAD_ENTRY: The entry *had* a value in it at some point, but the - * entry has been killed. Lookups requesting free space can - * reuse these entries; lookups requesting a precise match - * should neither return these entries nor stop searching when - * seeing these entries. - * - * We expect keys will not be destroyed frequently, so our table does not +/* We expect keys will not be destroyed frequently, so our table does not * contain any explicit shrinking code nor any chain-coalescing code for * entries randomly deleted by memory pressure (except during rehashing, of * course). These assumptions are potentially bad, but they make the @@ -93,118 +68,196 @@ static const cairo_cache_arrangement_t cache_arrangements [] = { * Revisit later if evidence appears that we're using excessive memory from * a mostly-dead table. * - * Generally you do not need to worry about freeing cache entries; the - * cache will expire entries randomly as it experiences memory pressure. - * If max_memory is set, entries are not expired, and must be explicitely - * removed. - * * This table is open-addressed with double hashing. Each table size is a * prime chosen to be a little more than double the high water mark for a * given arrangement, so the tables should remain < 50% full. The table * size makes for the "first" hash modulus; a second prime (2 less than the * first prime) serves as the "second" hash modulus, which is co-prime and * thus guarantees a complete permutation of table indices. - * + * + * This structure, and accompanying table, is borrowed/modified from the + * file xserver/render/glyph.c in the freedesktop.org x server, with + * permission (and suggested modification of doubling sizes) by Keith + * Packard. */ -#define DEAD_ENTRY ((cairo_cache_entry_base_t *) 1) -#define NULL_ENTRY_P(cache, i) ((cache)->entries[i] == NULL) -#define DEAD_ENTRY_P(cache, i) ((cache)->entries[i] == DEAD_ENTRY) -#define LIVE_ENTRY_P(cache, i) \ - (!((NULL_ENTRY_P((cache),(i))) || (DEAD_ENTRY_P((cache),(i))))) - -#ifdef NDEBUG -#define _cache_sane_state(c) -#else -static void -_cache_sane_state (cairo_cache_t *cache) -{ - assert (cache != NULL); - assert (cache->entries != NULL); - assert (cache->backend != NULL); - assert (cache->arrangement != NULL); - /* Cannot check this, a single object may larger */ - /* assert (cache->used_memory <= cache->max_memory); */ - assert (cache->live_entries <= cache->arrangement->size); +typedef struct _cairo_hash_table_arrangement { + unsigned long high_water_mark; + unsigned long size; + unsigned long rehash; +} cairo_hash_table_arrangement_t; + +static const cairo_hash_table_arrangement_t hash_table_arrangements [] = { + { 16, 43, 41 }, + { 32, 73, 71 }, + { 64, 151, 149 }, + { 128, 283, 281 }, + { 256, 571, 569 }, + { 512, 1153, 1151 }, + { 1024, 2269, 2267 }, + { 2048, 4519, 4517 }, + { 4096, 9013, 9011 }, + { 8192, 18043, 18041 }, + { 16384, 36109, 36107 }, + { 32768, 72091, 72089 }, + { 65536, 144409, 144407 }, + { 131072, 288361, 288359 }, + { 262144, 576883, 576881 }, + { 524288, 1153459, 1153457 }, + { 1048576, 2307163, 2307161 }, + { 2097152, 4613893, 4613891 }, + { 4194304, 9227641, 9227639 }, + { 8388608, 18455029, 18455027 }, + { 16777216, 36911011, 36911009 }, + { 33554432, 73819861, 73819859 }, + { 67108864, 147639589, 147639587 }, + { 134217728, 295279081, 295279079 }, + { 268435456, 590559793, 590559791 } +}; + +#define NUM_HASH_TABLE_ARRANGEMENTS (sizeof(hash_table_arrangements)/sizeof(hash_table_arrangements[0])) + +struct _cairo_hash_table { + cairo_hash_keys_equal_func_t keys_equal; + + const cairo_hash_table_arrangement_t *arrangement; + cairo_hash_entry_t **entries; + + unsigned long live_entries; +}; + +/** + * _cairo_hash_table_create: + * @keys_equal: a function to return TRUE if two keys are equal + * + * Creates a new hash table which will use the keys_equal() function + * to compare hash keys. Data is provided to the hash table in the + * form of user-derived versions of cairo_hash_entry_t. A hash entry + * must be able to hold both a key (including a hash code) and a + * value. Sometimes only the key will be necessary, (as in + * _cairo_hash_table_remove), and other times both a key and a value + * will be necessary, (as in _cairo_hash_table_insert). + * + * See #cairo_hash_entry_t for more details. + * + * Return value: the new hash table or NULL if out of memory. + **/ +cairo_hash_table_t * +_cairo_hash_table_create (cairo_hash_keys_equal_func_t keys_equal) +{ + cairo_hash_table_t *hash_table; + + hash_table = malloc (sizeof (cairo_hash_table_t)); + if (hash_table == NULL) + return NULL; + + hash_table->keys_equal = keys_equal; + + hash_table->arrangement = &hash_table_arrangements[0]; + + hash_table->entries = calloc (hash_table->arrangement->size, + sizeof(cairo_hash_entry_t *)); + if (hash_table->entries == NULL) { + free (hash_table); + return NULL; + } + + hash_table->live_entries = 0; + + return hash_table; } -#endif -static void -_entry_destroy (cairo_cache_t *cache, unsigned long i) +/** + * _cairo_hash_table_destroy: + * @hash_table: an empty hash table to destroy + * + * Immediately destroys the given hash table, freeing all resources + * associated with it. + * + * WARNING: The hash_table must have no live entries in it before + * _cairo_hash_table_destroy is called. It is a fatal error otherwise, + * and this function will halt. The rationale for this behavior is to + * avoid memory leaks and to avoid needless complication of the API + * with destroy notifiy callbacks. + **/ +void +_cairo_hash_table_destroy (cairo_hash_table_t *hash_table) { - _cache_sane_state (cache); + if (hash_table == NULL) + return; - if (LIVE_ENTRY_P(cache, i)) - { - cairo_cache_entry_base_t *entry = cache->entries[i]; - assert(cache->live_entries > 0); - assert(cache->used_memory >= entry->memory); - - cache->live_entries--; - cache->used_memory -= entry->memory; - cache->backend->destroy_entry (cache, entry); - cache->entries[i] = DEAD_ENTRY; - } + /* The hash table must be empty. Otherwise, halt. */ + assert (hash_table->live_entries == 0); + + free (hash_table->entries); + hash_table->entries = NULL; + + free (hash_table); } -static cairo_cache_entry_base_t ** -_cache_lookup (cairo_cache_t *cache, - void *key, - int (*predicate)(void*,void*,void*)) +/** + * _cairo_hash_table_lookup_internal: + * + * @hash_table: a #cairo_hash_table_t to search + * @key: the key to search on + * @hash_code: the hash_code for @key + * @key_unique: If TRUE, then caller asserts that no key already + * exists that will compare equal to #key, so search can be + * optimized. If unsure, set to FALSE and the code will always work. + * + * Search the hashtable for a live entry for which + * hash_table->keys_equal returns true. If no such entry exists then + * return the first available (free or dead entry). + * + * If the key_unique flag is set, then the search will never call + * hash_table->keys_equal and will act as if it always returned + * false. This is useful as a performance optimization in special + * circumstances where the caller knows that there is no existing + * entry in the hash table with a matching key. + * + * Return value: The matching entry in the hash table (if + * any). Otherwise, the first available entry. The caller should check + * entry->state to check whether a match was found or not. + **/ +static cairo_hash_entry_t ** +_cairo_hash_table_lookup_internal (cairo_hash_table_t *hash_table, + cairo_hash_entry_t *key, + cairo_bool_t key_is_unique) { - - cairo_cache_entry_base_t **probe; - unsigned long hash; + cairo_hash_entry_t **entry, **first_available = NULL; unsigned long table_size, i, idx, step; - _cache_sane_state (cache); - assert (key != NULL); + table_size = hash_table->arrangement->size; - table_size = cache->arrangement->size; - hash = cache->backend->hash (cache, key); - idx = hash % table_size; + idx = key->hash % table_size; step = 0; for (i = 0; i < table_size; ++i) { -#ifdef CAIRO_MEASURE_CACHE_PERFORMANCE - cache->probes++; -#endif - assert(idx < table_size); - probe = cache->entries + idx; - - /* - * There are two lookup modes: searching for a free slot and searching - * for an exact entry. - */ - - if (predicate != NULL) + entry = &hash_table->entries[idx]; + + if (ENTRY_IS_FREE(*entry)) { - /* We are looking up an exact entry. */ - if (*probe == NULL) - { - /* Found an empty spot, there can't be a match */ - break; - } - else if (*probe != DEAD_ENTRY - && (*probe)->hashcode == hash - && predicate (cache, key, *probe)) - { - return probe; - } + return entry; } - else + else if (ENTRY_IS_DEAD(*entry)) { - /* We are just looking for a free slot. */ - if (*probe == NULL - || *probe == DEAD_ENTRY) - { - return probe; + if (key_is_unique) { + return entry; + } else { + if (! first_available) + first_available = entry; } } + else /* ENTRY_IS_LIVE(*entry) */ + { + if (! key_is_unique) + if (hash_table->keys_equal (key, *entry)) + return entry; + } if (step == 0) { - step = hash % cache->arrangement->rehash; + step = key->hash % hash_table->arrangement->rehash; if (step == 0) step = 1; } @@ -218,110 +271,153 @@ _cache_lookup (cairo_cache_t *cache, * The table should not have permitted you to get here if you were just * looking for a free slot: there should have been room. */ - assert(predicate != NULL); - return NULL; -} - -static cairo_cache_entry_base_t ** -_find_available_entry_for (cairo_cache_t *cache, - void *key) -{ - return _cache_lookup (cache, key, NULL); -} + assert (key_is_unique == 0); -static cairo_cache_entry_base_t ** -_find_exact_live_entry_for (cairo_cache_t *cache, - void *key) -{ - return _cache_lookup (cache, key, cache->backend->keys_equal); -} - -static const cairo_cache_arrangement_t * -_find_cache_arrangement (unsigned long proposed_size) -{ - unsigned long idx; - - for (idx = 0; idx < N_CACHE_SIZES; ++idx) - if (cache_arrangements[idx].high_water_mark >= proposed_size) - return &cache_arrangements[idx]; - return NULL; + return first_available; } +/** + * _cairo_hash_table_resize: + * @hash_table: a hash table + * + * Resize the hash table if the number of entries has gotten much + * bigger or smaller than the ideal number of entries for the current + * size. + * + * Return value: CAIRO_STATUS_SUCCESS if successful or + * CAIRO_STATUS_NO_MEMORY if out of memory. + **/ static cairo_status_t -_resize_cache (cairo_cache_t *cache, unsigned long proposed_size) +_cairo_hash_table_resize (cairo_hash_table_t *hash_table) { - cairo_cache_t tmp; - cairo_cache_entry_base_t **e; + cairo_hash_table_t tmp; + cairo_hash_entry_t **entry; unsigned long new_size, i; - tmp = *cache; - tmp.arrangement = _find_cache_arrangement (proposed_size); - assert(tmp.arrangement != NULL); - if (tmp.arrangement == cache->arrangement) + /* This keeps the hash table between 25% and 50% full. */ + unsigned long high = hash_table->arrangement->high_water_mark; + unsigned long low = high >> 2; + + if (hash_table->live_entries >= low && hash_table->live_entries <= high) return CAIRO_STATUS_SUCCESS; + tmp = *hash_table; + + if (hash_table->live_entries > high) + { + tmp.arrangement = hash_table->arrangement + 1; + /* This code is being abused if we can't make a table big enough. */ + assert (tmp.arrangement - hash_table_arrangements < + NUM_HASH_TABLE_ARRANGEMENTS); + } + else /* hash_table->live_entries < low */ + { + /* Can't shrink if we're at the smallest size */ + if (hash_table->arrangement == &hash_table_arrangements[0]) + return CAIRO_STATUS_SUCCESS; + tmp.arrangement = hash_table->arrangement - 1; + } + new_size = tmp.arrangement->size; - tmp.entries = calloc (new_size, sizeof (cairo_cache_entry_base_t *)); + tmp.entries = calloc (new_size, sizeof (cairo_hash_entry_t*)); if (tmp.entries == NULL) return CAIRO_STATUS_NO_MEMORY; - for (i = 0; i < cache->arrangement->size; ++i) { - if (LIVE_ENTRY_P(cache, i)) { - e = _find_available_entry_for (&tmp, cache->entries[i]); - assert (e != NULL); - *e = cache->entries[i]; + for (i = 0; i < hash_table->arrangement->size; ++i) { + if (ENTRY_IS_LIVE (hash_table->entries[i])) { + entry = _cairo_hash_table_lookup_internal (&tmp, + hash_table->entries[i], + TRUE); + assert (ENTRY_IS_FREE(*entry)); + *entry = hash_table->entries[i]; } } - free (cache->entries); - cache->entries = tmp.entries; - cache->arrangement = tmp.arrangement; + + free (hash_table->entries); + hash_table->entries = tmp.entries; + hash_table->arrangement = tmp.arrangement; + return CAIRO_STATUS_SUCCESS; } - -#ifdef CAIRO_MEASURE_CACHE_PERFORMANCE -static double -_load_factor (cairo_cache_t *cache) +/** + * _cairo_hash_table_lookup: + * @hash_table: a hash table + * @key: the key of interest + * @entry_return: pointer for return value. + * + * Performs a lookup in @hash_table looking for an entry which has a + * key that matches @key, (as determined by the keys_equal() function + * passed to _cairo_hash_table_create). + * + * Return value: TRUE if there is an entry in the hash table that + * matches the given key, (which will now be in *entry_return). FALSE + * otherwise, (in which case *entry_return will be NULL). + **/ +cairo_bool_t +_cairo_hash_table_lookup (cairo_hash_table_t *hash_table, + cairo_hash_entry_t *key, + cairo_hash_entry_t **entry_return) { - return ((double) cache->live_entries) - / ((double) cache->arrangement->size); + cairo_hash_entry_t **entry; + + /* See if we have an entry in the table already. */ + entry = _cairo_hash_table_lookup_internal (hash_table, key, FALSE); + if (ENTRY_IS_LIVE(*entry)) { + *entry_return = *entry; + return TRUE; + } + + *entry_return = NULL; + return FALSE; } -#endif - -/* Find a random in the cache matching the given predicate. We use the - * same algorithm as the probing algorithm to walk over the entries in - * the hash table in a pseudo-random order. Walking linearly would - * favor entries following gaps in the hash table. We could also - * call rand() repeatedly, which works well for almost-full tables, - * but degrades when the table is almost empty, or predicate - * returns false for most entries. - */ -static cairo_cache_entry_base_t ** -_random_entry (cairo_cache_t *cache, - int (*predicate)(void*)) -{ - cairo_cache_entry_base_t **probe; + +/** + * _cairo_hash_table_random_entry: + * @hash_table: a hash table + * @predicate: a predicate function, or NULL for any entry. + * + * Find a random entry in the hash table satisfying the given + * @predicate. A NULL @predicate is taken as equivalent to a function + * which always returns TRUE, (eg. any entry in the table will do). + * + * We use the same algorithm as the lookup algorithm to walk over the + * entries in the hash table in a pseudo-random order. Walking + * linearly would favor entries following gaps in the hash table. We + * could also call rand() repeatedly, which works well for almost-full + * tables, but degrades when the table is almost empty, or predicate + * returns TRUE for most entries. + * + * Return value: a random live entry or NULL if there are no entries + * that match the given predicate. In particular, if predicate is + * NULL, a NULL return value indicates that the table is empty. + **/ +void * +_cairo_hash_table_random_entry (cairo_hash_table_t *hash_table, + cairo_hash_predicate_func_t predicate) +{ + cairo_hash_entry_t **entry; unsigned long hash; unsigned long table_size, i, idx, step; - - _cache_sane_state (cache); - table_size = cache->arrangement->size; + table_size = hash_table->arrangement->size; + hash = rand (); idx = hash % table_size; step = 0; for (i = 0; i < table_size; ++i) { - assert(idx < table_size); - probe = cache->entries + idx; + entry = &hash_table->entries[idx]; - if (LIVE_ENTRY_P(cache, idx) - && (!predicate || predicate (*probe))) - return probe; + if (ENTRY_IS_LIVE (*entry) && + (predicate == NULL || predicate (*entry))) + { + return *entry; + } if (step == 0) { - step = hash % cache->arrangement->rehash; + step = hash % hash_table->arrangement->rehash; if (step == 0) step = 1; } @@ -334,180 +430,104 @@ _random_entry (cairo_cache_t *cache, return NULL; } -/* public API follows */ - -cairo_status_t -_cairo_cache_init (cairo_cache_t *cache, - const cairo_cache_backend_t *backend, - unsigned long max_memory) -{ - assert (backend != NULL); - - if (cache != NULL){ - cache->arrangement = &cache_arrangements[0]; - cache->max_memory = max_memory; - cache->used_memory = 0; - cache->live_entries = 0; - -#ifdef CAIRO_MEASURE_CACHE_PERFORMANCE - cache->hits = 0; - cache->misses = 0; - cache->probes = 0; -#endif - - cache->backend = backend; - cache->entries = calloc (cache->arrangement->size, - sizeof(cairo_cache_entry_base_t *)); - - if (cache->entries == NULL) - return CAIRO_STATUS_NO_MEMORY; - } - _cache_sane_state (cache); - return CAIRO_STATUS_SUCCESS; -} - -void -_cairo_cache_destroy (cairo_cache_t *cache) -{ - unsigned long i; - if (cache == NULL) - return; - - _cache_sane_state (cache); - - for (i = 0; i < cache->arrangement->size; ++i) - _entry_destroy (cache, i); - - free (cache->entries); - cache->entries = NULL; - cache->backend->destroy_cache (cache); -} - +/** + * _cairo_hash_table_insert: + * @hash_table: a hash table + * @key_and_value: an entry to be inserted + * + * Insert the entry #key_and_value into the hash table. + * + * WARNING: It is a fatal error if an entry exists in the hash table + * with a matching key, (this function will halt). + * + * Instead of using insert to replace an entry, consider just editing + * the entry obtained with _cairo_hash_table_lookup. Or if absolutely + * necessary, use _cairo_hash_table_remove first. + * + * Return value: CAIRO_STATUS_SUCCESS if successful or + * CAIRO_STATUS_NO_MEMORY if insufficient memory is available. + **/ cairo_status_t -_cairo_cache_lookup (cairo_cache_t *cache, - void *key, - void **entry_return, - int *created_entry) +_cairo_hash_table_insert (cairo_hash_table_t *hash_table, + cairo_hash_entry_t *key_and_value) { - - unsigned long idx; - cairo_status_t status = CAIRO_STATUS_SUCCESS; - cairo_cache_entry_base_t **slot = NULL, *new_entry; - - _cache_sane_state (cache); - -#ifdef CAIRO_MEASURE_CACHE_PERFORMANCE - if ((cache->hits + cache->misses) % 0xffff == 0) - printf("cache %p stats: size %ld, live %ld, load %.2f\n" - " mem %ld/%ld, hit %ld, miss %ld\n" - " probe %ld, %.2f probe/access\n", - cache, - cache->arrangement->size, - cache->live_entries, - _load_factor (cache), - cache->used_memory, - cache->max_memory, - cache->hits, - cache->misses, - cache->probes, - ((double) cache->probes) - / ((double) (cache->hits + - cache->misses + 1))); -#endif + cairo_status_t status; + cairo_hash_entry_t **entry; - /* See if we have an entry in the table already. */ - slot = _find_exact_live_entry_for (cache, key); - if (slot != NULL) { -#ifdef CAIRO_MEASURE_CACHE_PERFORMANCE - cache->hits++; -#endif - *entry_return = *slot; - if (created_entry) - *created_entry = 0; - return status; - } - -#ifdef CAIRO_MEASURE_CACHE_PERFORMANCE - cache->misses++; -#endif - - /* Build the new entry. */ - status = cache->backend->create_entry (cache, key, - (void **)&new_entry); - if (status != CAIRO_STATUS_SUCCESS) - return status; - - /* Store the hash value in case the backend forgot. */ - new_entry->hashcode = cache->backend->hash (cache, key); - - /* Make some entries die if we're under memory pressure. */ - while (cache->live_entries > 0 && - cache->max_memory > 0 && - ((cache->max_memory - cache->used_memory) < new_entry->memory)) { - idx = _random_entry (cache, NULL) - cache->entries; - assert (idx < cache->arrangement->size); - _entry_destroy (cache, idx); - } + entry = _cairo_hash_table_lookup_internal (hash_table, + key_and_value, FALSE); - /* Can't assert this; new_entry->memory may be larger than max_memory */ - /* assert(cache->max_memory >= (cache->used_memory + new_entry->memory)); */ - - /* Make room in the table for a new slot. */ - status = _resize_cache (cache, cache->live_entries + 1); - if (status != CAIRO_STATUS_SUCCESS) { - cache->backend->destroy_entry (cache, new_entry); - return status; + if (ENTRY_IS_LIVE(*entry)) + { + /* User is being bad, let's crash. */ + ASSERT_NOT_REACHED; } - slot = _find_available_entry_for (cache, key); - assert(slot != NULL); - - /* Store entry in slot and increment statistics. */ - *slot = new_entry; - cache->live_entries++; - cache->used_memory += new_entry->memory; + *entry = key_and_value; + hash_table->live_entries++; - _cache_sane_state (cache); + status = _cairo_hash_table_resize (hash_table); + if (status) + return status; - *entry_return = new_entry; - if (created_entry) - *created_entry = 1; - - return status; + return CAIRO_STATUS_SUCCESS; } -cairo_status_t -_cairo_cache_remove (cairo_cache_t *cache, - void *key) +/** + * _cairo_hash_table_remove: + * @hash_table: a hash table + * @key: key of entry to be removed + * + * Remove an entry from the hash table which has a key that matches + * @key, if any (as determined by the keys_equal() function passed to + * _cairo_hash_table_create). + * + * Return value: CAIRO_STATUS_SUCCESS if successful or + * CAIRO_STATUS_NO_MEMORY if out of memory. + **/ +void +_cairo_hash_table_remove (cairo_hash_table_t *hash_table, + cairo_hash_entry_t *key) { - cairo_cache_entry_base_t **slot; + cairo_hash_entry_t **entry; - _cache_sane_state (cache); + entry = _cairo_hash_table_lookup_internal (hash_table, key, FALSE); + if (! ENTRY_IS_LIVE(*entry)) + return; - /* See if we have an entry in the table already. */ - slot = _find_exact_live_entry_for (cache, key); - if (slot != NULL) - _entry_destroy (cache, slot - cache->entries); + *entry = DEAD_ENTRY; + hash_table->live_entries--; - return CAIRO_STATUS_SUCCESS; + /* This call _can_ fail, but only in failing to allocate new + * memory to shrink the hash table. It does leave the table in a + * consistent state, and we've already succeeded in removing the + * entry, so we don't examine the failure status of this call. */ + _cairo_hash_table_resize (hash_table); } -void * -_cairo_cache_random_entry (cairo_cache_t *cache, - int (*predicate)(void*)) +/** + * _cairo_hash_table_foreach: + * @hash_table: a hash table + * @hash_callback: function to be called for each live entry + * @closure: additional argument to be passed to @hash_callback + * + * Call @hash_callback for each live entry in the hash table, in a + * non-specified order. + **/ +void +_cairo_hash_table_foreach (cairo_hash_table_t *hash_table, + cairo_hash_callback_func_t hash_callback, + void *closure) { - cairo_cache_entry_base_t **slot = _random_entry (cache, predicate); - - return slot ? *slot : NULL; -} + unsigned long i; + cairo_hash_entry_t *entry; -unsigned long -_cairo_hash_string (const char *c) -{ - /* This is the djb2 hash. */ - unsigned long hash = 5381; - while (*c) - hash = ((hash << 5) + hash) + *c++; - return hash; + if (hash_table == NULL) + return; + + for (i = 0; i < hash_table->arrangement->size; i++) { + entry = hash_table->entries[i]; + if (ENTRY_IS_LIVE(entry)) + hash_callback (entry, closure); + } } - |