summaryrefslogtreecommitdiff
path: root/libs/cairo-1.16.0/src/cairo-hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'libs/cairo-1.16.0/src/cairo-hash.c')
-rw-r--r--libs/cairo-1.16.0/src/cairo-hash.c578
1 files changed, 578 insertions, 0 deletions
diff --git a/libs/cairo-1.16.0/src/cairo-hash.c b/libs/cairo-1.16.0/src/cairo-hash.c
new file mode 100644
index 0000000..5a78990
--- /dev/null
+++ b/libs/cairo-1.16.0/src/cairo-hash.c
@@ -0,0 +1,578 @@
+/* cairo - a vector graphics library with display and print output
+ *
+ * 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
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * 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>
+ */
+
+#include "cairoint.h"
+#include "cairo-error-private.h"
+
+/*
+ * 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.
+ */
+
+#define DEAD_ENTRY ((cairo_hash_entry_t *) 0x1)
+
+#define ENTRY_IS_FREE(entry) ((entry) == NULL)
+#define ENTRY_IS_DEAD(entry) ((entry) == DEAD_ENTRY)
+#define ENTRY_IS_LIVE(entry) ((entry) > DEAD_ENTRY)
+
+/*
+ * This table is open-addressed with double hashing. Each table size
+ * is a prime and it makes for the "first" hash modulus; a second
+ * prime (2 less than the first prime) serves as the "second" hash
+ * modulus, which is smaller and thus guarantees a complete
+ * permutation of table indices.
+ *
+ * Hash tables are rehashed in order to keep between 12.5% and 50%
+ * entries in the hash table alive and at least 25% free. When table
+ * size is changed, the new table has about 25% live elements.
+ *
+ * The free entries guarantee an expected constant-time lookup.
+ * Doubling/halving the table in the described fashion guarantees
+ * 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.
+ */
+
+static const unsigned long hash_table_sizes[] = {
+ 43,
+ 73,
+ 151,
+ 283,
+ 571,
+ 1153,
+ 2269,
+ 4519,
+ 9013,
+ 18043,
+ 36109,
+ 72091,
+ 144409,
+ 288361,
+ 576883,
+ 1153459,
+ 2307163,
+ 4613893,
+ 9227641,
+ 18455029,
+ 36911011,
+ 73819861,
+ 147639589,
+ 295279081,
+ 590559793
+};
+
+struct _cairo_hash_table {
+ cairo_hash_keys_equal_func_t keys_equal;
+
+ cairo_hash_entry_t *cache[32];
+
+ const unsigned long *table_size;
+ 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.
+ **/
+static cairo_bool_t
+_cairo_hash_table_uid_keys_equal (const void *key_a, const void *key_b)
+{
+ return TRUE;
+}
+
+/**
+ * _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).
+ *
+ * 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 *
+_cairo_hash_table_create (cairo_hash_keys_equal_func_t keys_equal)
+{
+ cairo_hash_table_t *hash_table;
+
+ hash_table = _cairo_malloc (sizeof (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;
+
+ memset (&hash_table->cache, 0, sizeof (hash_table->cache));
+ hash_table->table_size = &hash_table_sizes[0];
+
+ hash_table->entries = calloc (*hash_table->table_size,
+ sizeof (cairo_hash_entry_t *));
+ if (unlikely (hash_table->entries == NULL)) {
+ _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
+ free (hash_table);
+ return NULL;
+ }
+
+ hash_table->live_entries = 0;
+ hash_table->free_entries = *hash_table->table_size;
+ hash_table->iterating = 0;
+
+ return hash_table;
+}
+
+/**
+ * _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.
+ *
+ * WARNING: The hash_table must have no running iterators in it when
+ * _cairo_hash_table_destroy is called. It is a fatal error otherwise,
+ * and this function will halt.
+ **/
+void
+_cairo_hash_table_destroy (cairo_hash_table_t *hash_table)
+{
+ /* The hash table must be empty. Otherwise, halt. */
+ assert (hash_table->live_entries == 0);
+ /* No iterators can be running. Otherwise, halt. */
+ assert (hash_table->iterating == 0);
+
+ 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->table_size;
+ idx = key->hash % table_size;
+
+ entry = &hash_table->entries[idx];
+ if (! ENTRY_IS_LIVE (*entry))
+ return entry;
+
+ i = 1;
+ step = 1 + key->hash % (table_size - 2);
+ do {
+ idx += step;
+ if (idx >= table_size)
+ idx -= table_size;
+
+ entry = &hash_table->entries[idx];
+ if (! ENTRY_IS_LIVE (*entry))
+ return entry;
+ } while (++i < table_size);
+
+ ASSERT_NOT_REACHED;
+ return NULL;
+}
+
+/**
+ * _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 and guarantee some free entries to be used as lookup
+ * 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_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
+ * at least 25% free. */
+ unsigned long live_high = *hash_table->table_size >> 1;
+ unsigned long live_low = live_high >> 2;
+ unsigned long free_low = live_high >> 1;
+
+ tmp = *hash_table;
+
+ if (hash_table->live_entries > live_high)
+ {
+ tmp.table_size = hash_table->table_size + 1;
+ /* This code is being abused if we can't make a table big enough. */
+ assert (tmp.table_size - hash_table_sizes <
+ 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)
+ {
+ /* The number of live entries is within the desired bounds
+ * (we're not going to resize the table) and we have enough
+ * free entries. Do nothing. */
+ return CAIRO_STATUS_SUCCESS;
+ }
+
+ 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->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];
+ }
+ }
+
+ free (hash_table->entries);
+ hash_table->entries = tmp.entries;
+ hash_table->table_size = tmp.table_size;
+ hash_table->free_entries = new_size - hash_table->live_entries;
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+/**
+ * _cairo_hash_table_lookup:
+ * @hash_table: a hash table
+ * @key: the key of interest
+ *
+ * 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: the matching entry, of %NULL if no match was found.
+ **/
+void *
+_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->table_size;
+ idx = hash % table_size;
+
+ entry = hash_table->entries[idx];
+ if (ENTRY_IS_LIVE (entry)) {
+ if (entry->hash == hash && hash_table->keys_equal (key, entry))
+ goto insert_cache;
+ } else if (ENTRY_IS_FREE (entry))
+ return NULL;
+
+ i = 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 (entry->hash == hash && hash_table->keys_equal (key, entry))
+ goto insert_cache;
+ } else if (ENTRY_IS_FREE (entry))
+ return NULL;
+ } while (++i < table_size);
+
+ ASSERT_NOT_REACHED;
+ return NULL;
+
+insert_cache:
+ hash_table->cache[hash & 31] = entry;
+ return entry;
+}
+
+/**
+ * _cairo_hash_table_random_entry:
+ * @hash_table: a hash table
+ * @predicate: a predicate function.
+ *
+ * Find a random entry in the hash table satisfying the given
+ * @predicate.
+ *
+ * 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;
+
+ assert (predicate != NULL);
+
+ 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;
+ 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) && predicate (entry))
+ return entry;
+ } while (++i < table_size);
+
+ return NULL;
+}
+
+/**
+ * _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: There must not be an existing entry in the hash table
+ * with a matching key.
+ *
+ * WARNING: It is a fatal error to insert an element while
+ * an iterator is running
+ *
+ * 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_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);
+
+ status = _cairo_hash_table_manage (hash_table);
+ 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;
+ hash_table->cache[key_and_value->hash & 31] = key_and_value;
+ hash_table->live_entries++;
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_hash_entry_t **
+_cairo_hash_table_lookup_exact_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->table_size;
+ idx = key->hash % table_size;
+
+ entry = &hash_table->entries[idx];
+ if (*entry == key)
+ return entry;
+
+ i = 1;
+ step = 1 + key->hash % (table_size - 2);
+ do {
+ idx += step;
+ if (idx >= table_size)
+ idx -= table_size;
+
+ entry = &hash_table->entries[idx];
+ if (*entry == key)
+ return entry;
+ } while (++i < table_size);
+
+ ASSERT_NOT_REACHED;
+ return NULL;
+}
+/**
+ * _cairo_hash_table_remove:
+ * @hash_table: a hash table
+ * @key: key of entry to be removed
+ *
+ * Remove an entry from the hash table which points to @key.
+ *
+ * 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_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_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
+ *
+ * Call @hash_callback for each live entry in the hash table, in a
+ * non-specified order.
+ *
+ * Entries in @hash_table may be removed by code executed from @hash_callback.
+ *
+ * Entries may not be inserted to @hash_table, nor may @hash_table
+ * be destroyed by code executed from @hash_callback. The relevant
+ * functions will halt in these cases.
+ **/
+void
+_cairo_hash_table_foreach (cairo_hash_table_t *hash_table,
+ cairo_hash_callback_func_t hash_callback,
+ void *closure)
+{
+ unsigned long i;
+ cairo_hash_entry_t *entry;
+
+ /* Mark the table for iteration */
+ ++hash_table->iterating;
+ for (i = 0; i < *hash_table->table_size; i++) {
+ entry = hash_table->entries[i];
+ if (ENTRY_IS_LIVE(entry))
+ hash_callback (entry, closure);
+ }
+ /* 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_manage (hash_table);
+ }
+}
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-01 07:21:27 +0000