0,0 → 1,542 |
/* 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) |
|
/* 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 |
* 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 |
* 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; |
} cairo_hash_table_arrangement_t; |
|
static const cairo_hash_table_arrangement_t hash_table_arrangements [] = { |
{ 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 }, |
{ 1048576, 2307163, 2307161 }, |
{ 2097152, 4613893, 4613891 }, |
{ 4194304, 9227641, 9227639 }, |
{ 8388608, 18455029, 18455027 }, |
{ 16777216, 36911011, 36911009 }, |
{ 33554432, 73819861, 73819859 }, |
{ 67108864, 147639589, 147639587 }, |
{ 134217728, 295279081, 295279079 }, |
{ 268435456, 590559793, 590559791 } |
}; |
|
#define NUM_HASH_TABLE_ARRANGEMENTS ARRAY_LENGTH (hash_table_arrangements) |
|
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 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 |
* 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). |
* |
* 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; |
} |
|
hash_table->keys_equal = keys_equal; |
|
hash_table->arrangement = &hash_table_arrangements[0]; |
|
hash_table->entries = calloc (hash_table->arrangement->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->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); |
hash_table->entries = NULL; |
|
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; |
idx = key->hash % table_size; |
|
entry = &hash_table->entries[idx]; |
if (! ENTRY_IS_LIVE (*entry)) |
return entry; |
|
i = 1; |
step = key->hash % hash_table->arrangement->rehash; |
if (step == 0) |
step = 1; |
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_resize: |
* @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. |
* |
* 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_t tmp; |
unsigned long new_size, i; |
|
/* This keeps the hash table between 25% and 50% full. */ |
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; |
|
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 */ |
{ |
/* 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; |
} |
|
new_size = tmp.arrangement->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) { |
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->arrangement = tmp.arrangement; |
|
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; |
|
table_size = hash_table->arrangement->size; |
idx = key->hash % table_size; |
|
entry = hash_table->entries[idx]; |
if (ENTRY_IS_LIVE (entry)) { |
if (hash_table->keys_equal (key, entry)) |
return entry; |
} else if (ENTRY_IS_FREE (entry)) |
return NULL; |
|
i = 1; |
step = key->hash % hash_table->arrangement->rehash; |
if (step == 0) |
step = 1; |
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)) |
return entry; |
} else if (ENTRY_IS_FREE (entry)) |
return NULL; |
} while (++i < table_size); |
|
return NULL; |
} |
|
/** |
* _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->arrangement->size; |
hash = rand (); |
idx = hash % table_size; |
|
entry = hash_table->entries[idx]; |
if (ENTRY_IS_LIVE (entry) && predicate (entry)) |
return entry; |
|
i = 1; |
step = hash % hash_table->arrangement->rehash; |
if (step == 0) |
step = 1; |
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_status_t status; |
|
/* Insert is illegal while an iterator is running. */ |
assert (hash_table->iterating == 0); |
|
hash_table->live_entries++; |
status = _cairo_hash_table_resize (hash_table); |
if (unlikely (status)) { |
/* abort the insert... */ |
hash_table->live_entries--; |
return status; |
} |
|
*_cairo_hash_table_lookup_unique_key (hash_table, |
key_and_value) = key_and_value; |
|
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->arrangement->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) |
step = 1; |
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--; |
|
/* 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_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->arrangement->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_resize (hash_table); |
} |
} |