/* 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; }