WebSVN – Kolibri OS – Diff – /programs/develop/libraries/cairo/src/cairo-hash.c

 #define ENTRY_IS_FREE(entry) ((entry) == NULL)
 #define ENTRY_IS_DEAD(entry) ((entry) == DEAD_ENTRY)
+#define ENTRY_IS_LIVE(entry) ((entry) >  DEAD_ENTRY)
-#define ENTRY_IS_LIVE(entry) ((entry) >  DEAD_ENTRY)
+/*
-/* We expect keys will not be destroyed frequently, so our table does not
+ * This table is open-addressed with double hashing. Each table size
- * contain any explicit shrinking code nor any chain-coalescing code for
+ * is a prime and it makes for the "first" hash modulus; a second
- * entries randomly deleted by memory pressure (except during rehashing, of
+ * prime (2 less than the first prime) serves as the "second" hash
- * course). These assumptions are potentially bad, but they make the
+ * modulus, which is smaller and thus guarantees a complete
+ * permutation of table indices.
- * implementation straightforward.
+ *
- *
+ * Hash tables are rehashed in order to keep between 12.5% and 50%
- * Revisit later if evidence appears that we're using excessive memory from
+ * entries in the hash table alive and at least 25% free. When table
- * a mostly-dead table.
- *
+ * size is changed, the new table has about 25% live elements.
- * 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
+ * The free entries guarantee an expected constant-time lookup.
- * first prime) serves as the "second" hash modulus, which is co-prime and
+ * Doubling/halving the table in the described fashion guarantees
- * thus guarantees a complete permutation of table indices.
+ * amortized O(1) insertion/removal.
+ *
  * 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.
- */
-typedef struct _cairo_hash_table_arrangement {
-    unsigned long high_water_mark;
-    unsigned long size;
-    unsigned long rehash;
+ * Packard.
-} cairo_hash_table_arrangement_t;
+ */
-static const cairo_hash_table_arrangement_t hash_table_arrangements [] = {
+static const unsigned long hash_table_sizes[] = {
-    { 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		},
+    1153459,
-    { 1048576,		2307163,	2307161		},
+    2307163,
-    { 2097152,		4613893,	4613891		},
+    4613893,
-    { 4194304,		9227641,	9227639		},
+    9227641,
-    { 8388608,		18455029,	18455027	},
+    18455029,
-    { 16777216,		36911011,	36911009	},
+    36911011,
-    { 33554432,		73819861,	73819859	},
+    73819861,
-    { 67108864,		147639589,	147639587	},
+    147639589,
-    { 134217728,	295279081,	295279079	},
-    { 268435456,	590559793,	590559791	}
-};
+    295279081,
     590559793
-#define NUM_HASH_TABLE_ARRANGEMENTS ARRAY_LENGTH (hash_table_arrangements)
+};
+struct _cairo_hash_table {
     cairo_hash_keys_equal_func_t keys_equal;
 struct _cairo_hash_table {
+    cairo_hash_entry_t *cache[32];
     cairo_hash_keys_equal_func_t keys_equal;
     const unsigned long *table_size;
-    const cairo_hash_table_arrangement_t *arrangement;
+    cairo_hash_entry_t **entries;
+    unsigned long live_entries;
+    unsigned long free_entries;
+    unsigned long iterating;   /* Iterating, no insert, no resize */
+};
+/**
+ * _cairo_hash_table_uid_keys_equal:
+ * @key_a: the first key to be compared
+ * @key_b: the second key to be compared
+ *
+ * Provides a #cairo_hash_keys_equal_func_t which always returns
+ * %TRUE. This is useful to create hash tables using keys whose hash
+ * completely describes the key, because in this special case
+ * comparing the hashes is sufficient to guarantee that the keys are
+ * equal.
+ *
+ * Return value: %TRUE.
+ **/
-    cairo_hash_entry_t **entries;
+static cairo_bool_t
 _cairo_hash_table_uid_keys_equal (const void *key_a, const void *key_b)
     unsigned long live_entries;
-    unsigned long iterating;   /* Iterating, no insert, no resize */
+    return TRUE;
 };
  * 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).
+ *
+ * If @keys_equal is %NULL, two keys will be considered equal if and
+ * only if their hashes are equal.
+ *
  * See #cairo_hash_entry_t for more details.
+ *
  * Return value: the new hash table or %NULL if out of memory.
  **/
 cairo_hash_table_t *
     if (unlikely (hash_table == NULL)) {
 	_cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
 	return NULL;
+    }
+    if (keys_equal == NULL)
+	hash_table->keys_equal = _cairo_hash_table_uid_keys_equal;
     else
+	hash_table->keys_equal = keys_equal;
-    hash_table->keys_equal = keys_equal;
+    memset (&hash_table->cache, 0, sizeof (hash_table->cache));
-    hash_table->arrangement = &hash_table_arrangements[0];
+    hash_table->table_size = &hash_table_sizes[0];
-    hash_table->entries = calloc (hash_table->arrangement->size,
+    hash_table->entries = calloc (*hash_table->table_size,
-				  sizeof(cairo_hash_entry_t *));
+				  sizeof (cairo_hash_entry_t *));
     if (unlikely (hash_table->entries == NULL)) {
 	_cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
 	free (hash_table);
+	return NULL;
 	return NULL;
     hash_table->live_entries = 0;
     assert (hash_table->live_entries == 0);
     /* No iterators can be running. Otherwise, halt. */
     assert (hash_table->iterating == 0);
-    free (hash_table->entries);
-    hash_table->entries = NULL;
     free (hash_table->entries);
     free (hash_table);
+}
 static cairo_hash_entry_t **
 _cairo_hash_table_lookup_unique_key (cairo_hash_table_t *hash_table,
 				     cairo_hash_entry_t *key)
+{
     unsigned long table_size, i, idx, step;
     cairo_hash_entry_t **entry;
-    table_size = hash_table->arrangement->size;
+    table_size = *hash_table->table_size;
     idx = key->hash % table_size;
     entry = &hash_table->entries[idx];
-    if (! ENTRY_IS_LIVE (*entry))
-	return entry;
     if (! ENTRY_IS_LIVE (*entry))
-    i = 1;
+	return entry;
     step = key->hash % hash_table->arrangement->rehash;
-    if (step == 0)
+    i = 1;
     ASSERT_NOT_REACHED;
     return NULL;
+}
 /**
- * _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
- * bigger or smaller than the ideal number of entries for the current
+ * size and guarantee some free entries to be used as lookup
- * size.
+ * termination points.
+ *
  * 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;
     unsigned long new_size, i;
+    /* Keep between 12.5% and 50% entries in the hash table alive and
-    /* This keeps the hash table between 25% and 50% full. */
+     * at least 25% free. */
-    unsigned long high = hash_table->arrangement->high_water_mark;
-    unsigned long low = high >> 2;
+    unsigned long live_high = *hash_table->table_size >> 1;
-    if (hash_table->live_entries >= low && hash_table->live_entries <= high)
+    unsigned long live_low = live_high >> 2;
-	return CAIRO_STATUS_SUCCESS;
+    unsigned long free_low = live_high >> 1;
     tmp = *hash_table;
-    if (hash_table->live_entries > high)
+    if (hash_table->live_entries > live_high)
     {
-	tmp.arrangement = hash_table->arrangement + 1;
+	tmp.table_size = hash_table->table_size + 1;
 	/* This code is being abused if we can't make a table big enough. */
-	assert (tmp.arrangement - hash_table_arrangements <
+	assert (tmp.table_size - hash_table_sizes <
-		NUM_HASH_TABLE_ARRANGEMENTS);
+		ARRAY_LENGTH (hash_table_sizes));
     }
+    else if (hash_table->live_entries < live_low)
+    {
+	/* Can't shrink if we're at the smallest size */
+	if (hash_table->table_size == &hash_table_sizes[0])
+	    tmp.table_size = hash_table->table_size;
+	else
+	    tmp.table_size = hash_table->table_size - 1;
+    }
+    if (tmp.table_size == hash_table->table_size &&
+	hash_table->free_entries > free_low)
     else /* hash_table->live_entries < low */
-    {
-	/* Can't shrink if we're at the smallest size */
+	/* The number of live entries is within the desired bounds
-	if (hash_table->arrangement == &hash_table_arrangements[0])
+	 * (we're not going to resize the table) and we have enough
-	    return CAIRO_STATUS_SUCCESS;
+	 * free entries. Do nothing. */
-	tmp.arrangement = hash_table->arrangement - 1;
+	return CAIRO_STATUS_SUCCESS;
+    }
-    new_size = tmp.arrangement->size;
+    new_size = *tmp.table_size;
     tmp.entries = calloc (new_size, sizeof (cairo_hash_entry_t*));
     if (unlikely (tmp.entries == NULL))
 	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
-    for (i = 0; i < hash_table->arrangement->size; ++i) {
+    for (i = 0; i < *hash_table->table_size; ++i) {
 	if (ENTRY_IS_LIVE (hash_table->entries[i])) {
 	    *_cairo_hash_table_lookup_unique_key (&tmp, hash_table->entries[i])
+		= hash_table->entries[i];
 		= hash_table->entries[i];
+    }
 _cairo_hash_table_lookup (cairo_hash_table_t *hash_table,
 			  cairo_hash_entry_t *key)
+{
     cairo_hash_entry_t *entry;
     unsigned long table_size, i, idx, step;
+    unsigned long hash = key->hash;
+    entry = hash_table->cache[hash & 31];
+    if (entry && entry->hash == hash && hash_table->keys_equal (key, entry))
+	return entry;
-    table_size = hash_table->arrangement->size;
+    table_size = *hash_table->table_size;
-    idx = key->hash % table_size;
+    idx = hash % table_size;
     entry = hash_table->entries[idx];
     if (ENTRY_IS_LIVE (entry)) {
-	if (hash_table->keys_equal (key, entry))
+	if (entry->hash == hash && hash_table->keys_equal (key, entry))
-	    return entry;
+		goto insert_cache;
     } else if (ENTRY_IS_FREE (entry))
 	return NULL;
-    i = 1;
     step = key->hash % hash_table->arrangement->rehash;
-    if (step == 0)
+    i = 1;
-	step = 1;
+    step = 1 + hash % (table_size - 2);
     do {
 	idx += step;
 	if (idx >= table_size)
 	    idx -= table_size;
 	entry = hash_table->entries[idx];
 	if (ENTRY_IS_LIVE (entry)) {
-	    if (hash_table->keys_equal (key, entry))
+	    if (entry->hash == hash && hash_table->keys_equal (key, entry))
+		    goto insert_cache;
-		return entry;
+	} else if (ENTRY_IS_FREE (entry))
+	    return NULL;
+    } while (++i < table_size);
+    ASSERT_NOT_REACHED;
-	} else if (ENTRY_IS_FREE (entry))
+    return NULL;
 	    return NULL;
-    } while (++i < table_size);
+insert_cache:
     hash_table->cache[hash & 31] = entry;
     unsigned long hash;
     unsigned long table_size, i, idx, step;
     assert (predicate != NULL);
-    table_size = hash_table->arrangement->size;
+    table_size = *hash_table->table_size;
     hash = rand ();
     idx = hash % table_size;
     entry = hash_table->entries[idx];
     if (ENTRY_IS_LIVE (entry) && predicate (entry))
-	return entry;
-    i = 1;
+	return entry;
     step = hash % hash_table->arrangement->rehash;
-    if (step == 0)
+    i = 1;
-	step = 1;
+    step = 1 + hash % (table_size - 2);
  **/
 cairo_status_t
 _cairo_hash_table_insert (cairo_hash_table_t *hash_table,
 			  cairo_hash_entry_t *key_and_value)
+{
+    cairo_hash_entry_t **entry;
     cairo_status_t status;
     /* Insert is illegal while an iterator is running. */
-    assert (hash_table->iterating == 0);
+    assert (hash_table->iterating == 0);
-    hash_table->live_entries++;
-    status = _cairo_hash_table_resize (hash_table);
-    if (unlikely (status)) {
-	/* abort the insert... */
+    status = _cairo_hash_table_manage (hash_table);
-	hash_table->live_entries--;
-	return status;
+    if (unlikely (status))
+	return status;
+    entry = _cairo_hash_table_lookup_unique_key (hash_table, key_and_value);
-    }
+    if (ENTRY_IS_FREE (*entry))
+	hash_table->free_entries--;
     *entry = key_and_value;
-    *_cairo_hash_table_lookup_unique_key (hash_table,
+    hash_table->cache[key_and_value->hash & 31] = key_and_value;
-					  key_and_value) = key_and_value;
+    hash_table->live_entries++;
 				    cairo_hash_entry_t *key)
+{
     unsigned long table_size, i, idx, step;
     cairo_hash_entry_t **entry;
-    table_size = hash_table->arrangement->size;
+    table_size = *hash_table->table_size;
     idx = key->hash % table_size;
     entry = &hash_table->entries[idx];
     if (*entry == key)
 	return entry;
-    i = 1;
     step = key->hash % hash_table->arrangement->rehash;
-    if (step == 0)
+    i = 1;
-	step = 1;
+    step = 1 + key->hash % (table_size - 2);
     do {
 _cairo_hash_table_remove (cairo_hash_table_t *hash_table,
 			  cairo_hash_entry_t *key)
+{
     *_cairo_hash_table_lookup_exact_key (hash_table, key) = DEAD_ENTRY;
     hash_table->live_entries--;
+    hash_table->cache[key->hash & 31] = NULL;
     /* 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);
+    }
+}
     unsigned long i;
     cairo_hash_entry_t *entry;
     /* Mark the table for iteration */
     ++hash_table->iterating;
-    for (i = 0; i < hash_table->arrangement->size; i++) {
+    for (i = 0; i < *hash_table->table_size; i++) {
 	entry = hash_table->entries[i];
 	if (ENTRY_IS_LIVE(entry))
 	    hash_callback (entry, closure);
+    }
      * 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);
+    }
+}

Subversion Repositories Kolibri OS

(root)/programs/develop/libraries/cairo/src/cairo-hash.c – Rev 1892 → 3959