/* 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
= 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);
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
); }
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;
table_size = *hash_table->table_size;
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);
}
}