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