diff options
Diffstat (limited to 'libs/cairo-1.16.0/src/cairo-cache.c')
| -rw-r--r-- | libs/cairo-1.16.0/src/cairo-cache.c | 338 |
1 files changed, 338 insertions, 0 deletions
diff --git a/libs/cairo-1.16.0/src/cairo-cache.c b/libs/cairo-1.16.0/src/cairo-cache.c new file mode 100644 index 0000000..5c4e4ca --- /dev/null +++ b/libs/cairo-1.16.0/src/cairo-cache.c @@ -0,0 +1,338 @@ +/* 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" + +static void +_cairo_cache_shrink_to_accommodate (cairo_cache_t *cache, + unsigned long additional); + +static cairo_bool_t +_cairo_cache_entry_is_non_zero (const void *entry) +{ + return ((const cairo_cache_entry_t *) entry)->size; +} + + +/** + * _cairo_cache_init: + * @cache: the #cairo_cache_t to initialise + * @keys_equal: a function to return %TRUE if two keys are equal + * @entry_destroy: destroy notifier for cache entries + * @max_size: the maximum size for this cache + * Returns: the newly created #cairo_cache_t + * + * Creates a new cache using the keys_equal() function to determine + * the equality of entries. + * + * Data is provided to the cache in the form of user-derived version + * of #cairo_cache_entry_t. A cache entry must be able to hold hash + * code, a size, and the key/value pair being stored in the + * cache. Sometimes only the key will be necessary, (as in + * _cairo_cache_lookup()), and in these cases the value portion of the + * entry need not be initialized. + * + * The units for max_size can be chosen by the caller, but should be + * consistent with the units of the size field of cache entries. When + * adding an entry with _cairo_cache_insert() if the total size of + * entries in the cache would exceed max_size then entries will be + * removed at random until the new entry would fit or the cache is + * empty. Then the new entry is inserted. + * + * There are cases in which the automatic removal of entries is + * undesired. If the cache entries have reference counts, then it is a + * simple matter to use the reference counts to ensure that entries + * continue to live even after being ejected from the cache. However, + * in some cases the memory overhead of adding a reference count to + * the entry would be objectionable. In such cases, the + * _cairo_cache_freeze() and _cairo_cache_thaw() calls can be + * used to establish a window during which no automatic removal of + * entries will occur. + **/ +cairo_status_t +_cairo_cache_init (cairo_cache_t *cache, + cairo_cache_keys_equal_func_t keys_equal, + cairo_cache_predicate_func_t predicate, + cairo_destroy_func_t entry_destroy, + unsigned long max_size) +{ + cache->hash_table = _cairo_hash_table_create (keys_equal); + if (unlikely (cache->hash_table == NULL)) + return _cairo_error (CAIRO_STATUS_NO_MEMORY); + + if (predicate == NULL) + predicate = _cairo_cache_entry_is_non_zero; + cache->predicate = predicate; + cache->entry_destroy = entry_destroy; + + cache->max_size = max_size; + cache->size = 0; + + cache->freeze_count = 0; + + return CAIRO_STATUS_SUCCESS; +} + +static void +_cairo_cache_pluck (void *entry, void *closure) +{ + _cairo_cache_remove (closure, entry); +} + +/** + * _cairo_cache_fini: + * @cache: a cache to destroy + * + * Immediately destroys the given cache, freeing all resources + * associated with it. As part of this process, the entry_destroy() + * function, (as passed to _cairo_cache_init()), will be called for + * each entry in the cache. + **/ +void +_cairo_cache_fini (cairo_cache_t *cache) +{ + _cairo_hash_table_foreach (cache->hash_table, + _cairo_cache_pluck, + cache); + assert (cache->size == 0); + _cairo_hash_table_destroy (cache->hash_table); +} + +/** + * _cairo_cache_freeze: + * @cache: a cache with some precious entries in it (or about to be + * added) + * + * Disable the automatic ejection of entries from the cache. For as + * long as the cache is "frozen", calls to _cairo_cache_insert() will + * add new entries to the cache regardless of how large the cache + * grows. See _cairo_cache_thaw(). + * + * Note: Multiple calls to _cairo_cache_freeze() will stack, in that + * the cache will remain "frozen" until a corresponding number of + * calls are made to _cairo_cache_thaw(). + **/ +void +_cairo_cache_freeze (cairo_cache_t *cache) +{ + assert (cache->freeze_count >= 0); + + cache->freeze_count++; +} + +/** + * _cairo_cache_thaw: + * @cache: a cache, just after the entries in it have become less + * precious + * + * Cancels the effects of _cairo_cache_freeze(). + * + * When a number of calls to _cairo_cache_thaw() is made corresponding + * to the number of calls to _cairo_cache_freeze() the cache will no + * longer be "frozen". If the cache had grown larger than max_size + * while frozen, entries will immediately be ejected (by random) from + * the cache until the cache is smaller than max_size. Also, the + * automatic ejection of entries on _cairo_cache_insert() will resume. + **/ +void +_cairo_cache_thaw (cairo_cache_t *cache) +{ + assert (cache->freeze_count > 0); + + if (--cache->freeze_count == 0) + _cairo_cache_shrink_to_accommodate (cache, 0); +} + +/** + * _cairo_cache_lookup: + * @cache: a cache + * @key: the key of interest + * @entry_return: pointer for return value + * + * Performs a lookup in @cache looking for an entry which has a key + * that matches @key, (as determined by the keys_equal() function + * passed to _cairo_cache_init()). + * + * Return value: %TRUE if there is an entry in the cache that matches + * @key, (which will now be in *entry_return). %FALSE otherwise, (in + * which case *entry_return will be %NULL). + **/ +void * +_cairo_cache_lookup (cairo_cache_t *cache, + cairo_cache_entry_t *key) +{ + return _cairo_hash_table_lookup (cache->hash_table, + (cairo_hash_entry_t *) key); +} + +/** + * _cairo_cache_remove_random: + * @cache: a cache + * + * Remove a random entry from the cache. + * + * Return value: %TRUE if an entry was successfully removed. + * %FALSE if there are no entries that can be removed. + **/ +static cairo_bool_t +_cairo_cache_remove_random (cairo_cache_t *cache) +{ + cairo_cache_entry_t *entry; + + entry = _cairo_hash_table_random_entry (cache->hash_table, + cache->predicate); + if (unlikely (entry == NULL)) + return FALSE; + + _cairo_cache_remove (cache, entry); + + return TRUE; +} + +/** + * _cairo_cache_shrink_to_accommodate: + * @cache: a cache + * @additional: additional size requested in bytes + * + * If cache is not frozen, eject entries randomly until the size of + * the cache is at least @additional bytes less than + * cache->max_size. That is, make enough room to accommodate a new + * entry of size @additional. + **/ +static void +_cairo_cache_shrink_to_accommodate (cairo_cache_t *cache, + unsigned long additional) +{ + while (cache->size + additional > cache->max_size) { + if (! _cairo_cache_remove_random (cache)) + return; + } +} + +/** + * _cairo_cache_insert: + * @cache: a cache + * @entry: an entry to be inserted + * + * Insert @entry into the cache. If an entry exists in the cache with + * a matching key, then the old entry will be removed first, (and the + * entry_destroy() callback will be called on it). + * + * Return value: %CAIRO_STATUS_SUCCESS if successful or + * %CAIRO_STATUS_NO_MEMORY if insufficient memory is available. + **/ +cairo_status_t +_cairo_cache_insert (cairo_cache_t *cache, + cairo_cache_entry_t *entry) +{ + cairo_status_t status; + + if (entry->size && ! cache->freeze_count) + _cairo_cache_shrink_to_accommodate (cache, entry->size); + + status = _cairo_hash_table_insert (cache->hash_table, + (cairo_hash_entry_t *) entry); + if (unlikely (status)) + return status; + + cache->size += entry->size; + + return CAIRO_STATUS_SUCCESS; +} + +/** + * _cairo_cache_remove: + * @cache: a cache + * @entry: an entry that exists in the cache + * + * Remove an existing entry from the cache. + **/ +void +_cairo_cache_remove (cairo_cache_t *cache, + cairo_cache_entry_t *entry) +{ + cache->size -= entry->size; + + _cairo_hash_table_remove (cache->hash_table, + (cairo_hash_entry_t *) entry); + + if (cache->entry_destroy) + cache->entry_destroy (entry); +} + +/** + * _cairo_cache_foreach: + * @cache: a cache + * @cache_callback: function to be called for each entry + * @closure: additional argument to be passed to @cache_callback + * + * Call @cache_callback for each entry in the cache, in a + * non-specified order. + **/ +void +_cairo_cache_foreach (cairo_cache_t *cache, + cairo_cache_callback_func_t cache_callback, + void *closure) +{ + _cairo_hash_table_foreach (cache->hash_table, + cache_callback, + closure); +} + +unsigned long +_cairo_hash_string (const char *c) +{ + /* This is the djb2 hash. */ + unsigned long hash = _CAIRO_HASH_INIT_VALUE; + while (c && *c) + hash = ((hash << 5) + hash) + *c++; + return hash; +} + +unsigned long +_cairo_hash_bytes (unsigned long hash, + const void *ptr, + unsigned int length) +{ + const uint8_t *bytes = ptr; + /* This is the djb2 hash. */ + while (length--) + hash = ((hash << 5) + hash) + *bytes++; + return hash; +} |