diff --git a/gfx/cairo/cairo/src/cairo-hash.c b/gfx/cairo/cairo/src/cairo-hash.c --- a/gfx/cairo/cairo/src/cairo-hash.c +++ b/gfx/cairo/cairo/src/cairo-hash.c @@ -29,16 +29,17 @@ * The Original Code is the cairo graphics library. * * The Initial Developer of the Original Code is Red Hat, Inc. * * Contributor(s): * Keith Packard * Graydon Hoare * Carl Worth + * Karl Tomlinson , Mozilla Corporation */ #include "cairoint.h" /* * An entry can be in one of three states: * * FREE: Entry has never been used, terminates all searches. @@ -54,26 +55,17 @@ static cairo_hash_entry_t dead_entry = { 0 }; #define DEAD_ENTRY (&dead_entry) #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)) -/* 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 - * implementation straightforward. - * - * Revisit later if evidence appears that we're using excessive memory from - * a mostly-dead table. - * - * This table is open-addressed with double hashing. Each table size is a +/* 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 @@ -119,16 +111,17 @@ static const cairo_hash_table_arrangemen 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; + unsigned long used_entries; unsigned long iterating; /* Iterating, no insert, no resize */ }; /** * _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 @@ -162,16 +155,17 @@ _cairo_hash_table_create (cairo_hash_key sizeof(cairo_hash_entry_t *)); if (hash_table->entries == NULL) { _cairo_error_throw (CAIRO_STATUS_NO_MEMORY); free (hash_table); return NULL; } hash_table->live_entries = 0; + hash_table->used_entries = 0; hash_table->iterating = 0; return hash_table; } /** * _cairo_hash_table_destroy: * @hash_table: an empty hash table to destroy @@ -283,75 +277,104 @@ _cairo_hash_table_lookup_internal (cairo * looking for a free slot: there should have been room. */ assert (key_is_unique == 0); return first_available; } /** - * _cairo_hash_table_resize: + * _cairo_hash_table_manage: * @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. + * size, or control the number of dead entries by moving the entries + * within the table. * * Return value: %CAIRO_STATUS_SUCCESS if successful or * %CAIRO_STATUS_NO_MEMORY if out of memory. **/ static cairo_status_t -_cairo_hash_table_resize (cairo_hash_table_t *hash_table) +_cairo_hash_table_manage (cairo_hash_table_t *hash_table) { cairo_hash_table_t tmp; - cairo_hash_entry_t **entry; - unsigned long new_size, i; + cairo_hash_entry_t *entry, **pos; + cairo_bool_t realloc = TRUE; + unsigned long i; - /* This keeps the hash table between 25% and 50% full. */ + /* This keeps the size of the hash table between 2 and approximately 8 + * times the number of live entries and keeps the proportion of free + * entries (search-terminations) > 25%. */ 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; + unsigned long max_used = high + high / 2; 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 */ + else if (hash_table->live_entries < low && + /* Can't shrink if we're at the smallest size */ + hash_table->arrangement != &hash_table_arrangements[0]) { - /* 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; } + else if(hash_table->used_entries > max_used) + { + /* Clean out dead entries to prevent lookups from becoming too slow. */ + for (i = 0; i < hash_table->arrangement->size; ++i) { + if (ENTRY_IS_DEAD (hash_table->entries[i])) + hash_table->entries[i] = NULL; + } + hash_table->used_entries = hash_table->live_entries; - new_size = tmp.arrangement->size; - tmp.entries = calloc (new_size, sizeof (cairo_hash_entry_t*)); - if (tmp.entries == NULL) - return _cairo_error (CAIRO_STATUS_NO_MEMORY); + /* There is no need to reallocate but some entries may need to be + * moved. Typically the proportion of entries needing to be moved is + * small, but, if the moving should leave a large number of dead + * entries, they will be cleaned out next time this code is + * executed. */ + realloc = FALSE; + } + else + { + return CAIRO_STATUS_SUCCESS; + } + + if (realloc) { + unsigned long new_size = tmp.arrangement->size; + tmp.entries = calloc (new_size, sizeof (cairo_hash_entry_t*)); + if (tmp.entries == NULL) + return _cairo_error (CAIRO_STATUS_NO_MEMORY); + hash_table->used_entries = 0; + } 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]; + entry = hash_table->entries[i]; + hash_table->entries[i] = DEAD_ENTRY; + + pos = _cairo_hash_table_lookup_internal (&tmp, entry, TRUE); + assert (! ENTRY_IS_LIVE(*pos)); + if (ENTRY_IS_FREE(*pos)) + hash_table->used_entries++; + *pos = entry; } } - free (hash_table->entries); - hash_table->entries = tmp.entries; - hash_table->arrangement = tmp.arrangement; + if (realloc) { + free (hash_table->entries); + hash_table->entries = tmp.entries; + hash_table->arrangement = tmp.arrangement; + } return CAIRO_STATUS_SUCCESS; } /** * _cairo_hash_table_lookup: * @hash_table: a hash table * @key: the key of interest @@ -475,20 +498,22 @@ _cairo_hash_table_insert (cairo_hash_tab key_and_value, FALSE); if (ENTRY_IS_LIVE(*entry)) { /* User is being bad, let's crash. */ ASSERT_NOT_REACHED; } + hash_table->live_entries++; + if (ENTRY_IS_FREE(*entry)) + hash_table->used_entries++; *entry = key_and_value; - hash_table->live_entries++; - status = _cairo_hash_table_resize (hash_table); + status = _cairo_hash_table_manage (hash_table); if (status) { /* abort the insert... */ *entry = DEAD_ENTRY; hash_table->live_entries--; return status; } return CAIRO_STATUS_SUCCESS; @@ -522,17 +544,17 @@ _cairo_hash_table_remove (cairo_hash_tab /* Check for table resize. Don't do this when iterating as this will * reorder elements of the table and cause the iteration to potentially * skip some elements. */ if (hash_table->iterating == 0) { /* 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); + _cairo_hash_table_manage (hash_table); } } /** * _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 @@ -566,11 +588,11 @@ _cairo_hash_table_foreach (cairo_hash_ta } /* If some elements were deleted during the iteration, * the table may need resizing. Just do this every time * as the check is inexpensive. */ if (--hash_table->iterating == 0) { /* Should we fail to shrink the hash table, it is left unaltered, * and we don't need to propagate the error status. */ - _cairo_hash_table_resize (hash_table); + _cairo_hash_table_manage (hash_table); } }