Attachment 19802 Details for Bug 17399 – reshuffle to remove dead entries

[patch] reshuffle to remove dead entries

cairo-hash-reshuffle-1.diff (text/plain), 9.12 KB, created by Karl Tomlinson on 2008-10-21 23:05:17 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Karl Tomlinson

Created: 2008-10-21 23:05:17 UTC

Size: 9.12 KB

patch

obsolete

>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 <keithp@keithp.com>
>  *	Graydon Hoare <graydon@redhat.com>
>  *	Carl Worth <cworth@cworth.org>
>+ *	Karl Tomlinson <karlt+@karlt.net>, 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);
>     }
> }

Actions: View | Splinter Review

Attachments on bug 17399: 19802

Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.