source/libs/cairo/cairo-src/src/cairo-cache.c

   1 /* cairo - a vector graphics library with display and print output
   2  *
   3  * Copyright © 2004 Red Hat, Inc.
   4  * Copyright © 2005 Red Hat, Inc.
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it either under the terms of the GNU Lesser General Public
   8  * License version 2.1 as published by the Free Software Foundation
   9  * (the "LGPL") or, at your option, under the terms of the Mozilla
  10  * Public License Version 1.1 (the "MPL"). If you do not alter this
  11  * notice, a recipient may use your version of this file under either
  12  * the MPL or the LGPL.
  13  *
  14  * You should have received a copy of the LGPL along with this library
  15  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
  17  * You should have received a copy of the MPL along with this library
  18  * in the file COPYING-MPL-1.1
  19  *
  20  * The contents of this file are subject to the Mozilla Public License
  21  * Version 1.1 (the "License"); you may not use this file except in
  22  * compliance with the License. You may obtain a copy of the License at
  23  * http://www.mozilla.org/MPL/
  24  *
  25  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  26  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  27  * the specific language governing rights and limitations.
  28  *
  29  * The Original Code is the cairo graphics library.
  30  *
  31  * The Initial Developer of the Original Code is Red Hat, Inc.
  32  *
  33  * Contributor(s):
  34  *      Keith Packard <keithp@keithp.com>
  35  *      Graydon Hoare <graydon@redhat.com>
  36  *      Carl Worth <cworth@cworth.org>
  37  */
  38
  39 #include "cairoint.h"
  40 #include "cairo-error-private.h"
  41
  42 static void
  43 _cairo_cache_shrink_to_accommodate (cairo_cache_t *cache,
  44                                     unsigned long  additional);
  45
  46 static cairo_bool_t
  47 _cairo_cache_entry_is_non_zero (const void *entry)
  48 {
  49     return ((const cairo_cache_entry_t *) entry)->size;
  50 }
  51
  52
  53 /**
  54  * _cairo_cache_init:
  55  * @cache: the #cairo_cache_t to initialise
  56  * @keys_equal: a function to return %TRUE if two keys are equal
  57  * @entry_destroy: destroy notifier for cache entries
  58  * @max_size: the maximum size for this cache
  59  * Returns: the newly created #cairo_cache_t
  60  *
  61  * Creates a new cache using the keys_equal() function to determine
  62  * the equality of entries.
  63  *
  64  * Data is provided to the cache in the form of user-derived version
  65  * of #cairo_cache_entry_t. A cache entry must be able to hold hash
  66  * code, a size, and the key/value pair being stored in the
  67  * cache. Sometimes only the key will be necessary, (as in
  68  * _cairo_cache_lookup()), and in these cases the value portion of the
  69  * entry need not be initialized.
  70  *
  71  * The units for max_size can be chosen by the caller, but should be
  72  * consistent with the units of the size field of cache entries. When
  73  * adding an entry with _cairo_cache_insert() if the total size of
  74  * entries in the cache would exceed max_size then entries will be
  75  * removed at random until the new entry would fit or the cache is
  76  * empty. Then the new entry is inserted.
  77  *
  78  * There are cases in which the automatic removal of entries is
  79  * undesired. If the cache entries have reference counts, then it is a
  80  * simple matter to use the reference counts to ensure that entries
  81  * continue to live even after being ejected from the cache. However,
  82  * in some cases the memory overhead of adding a reference count to
  83  * the entry would be objectionable. In such cases, the
  84  * _cairo_cache_freeze() and _cairo_cache_thaw() calls can be
  85  * used to establish a window during which no automatic removal of
  86  * entries will occur.
  87  **/
  88 cairo_status_t
  89 _cairo_cache_init (cairo_cache_t                *cache,
  90                    cairo_cache_keys_equal_func_t keys_equal,
  91                    cairo_cache_predicate_func_t  predicate,
  92                    cairo_destroy_func_t          entry_destroy,
  93                    unsigned long                 max_size)
  94 {
  95     cache->hash_table = _cairo_hash_table_create (keys_equal);
  96     if (unlikely (cache->hash_table == NULL))
  97         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  98
  99     if (predicate == NULL)
 100         predicate = _cairo_cache_entry_is_non_zero;
 101     cache->predicate = predicate;
 102     cache->entry_destroy = entry_destroy;
 103
 104     cache->max_size = max_size;
 105     cache->size = 0;
 106
 107     cache->freeze_count = 0;
 108
 109     return CAIRO_STATUS_SUCCESS;
 110 }
 111
 112 static void
 113 _cairo_cache_pluck (void *entry, void *closure)
 114 {
 115     _cairo_cache_remove (closure, entry);
 116 }
 117
 118 /**
 119  * _cairo_cache_fini:
 120  * @cache: a cache to destroy
 121  *
 122  * Immediately destroys the given cache, freeing all resources
 123  * associated with it. As part of this process, the entry_destroy()
 124  * function, (as passed to _cairo_cache_init()), will be called for
 125  * each entry in the cache.
 126  **/
 127 void
 128 _cairo_cache_fini (cairo_cache_t *cache)
 129 {
 130     _cairo_hash_table_foreach (cache->hash_table,
 131                                _cairo_cache_pluck,
 132                                cache);
 133     assert (cache->size == 0);
 134     _cairo_hash_table_destroy (cache->hash_table);
 135 }
 136
 137 /**
 138  * _cairo_cache_freeze:
 139  * @cache: a cache with some precious entries in it (or about to be
 140  * added)
 141  *
 142  * Disable the automatic ejection of entries from the cache. For as
 143  * long as the cache is "frozen", calls to _cairo_cache_insert() will
 144  * add new entries to the cache regardless of how large the cache
 145  * grows. See _cairo_cache_thaw().
 146  *
 147  * Note: Multiple calls to _cairo_cache_freeze() will stack, in that
 148  * the cache will remain "frozen" until a corresponding number of
 149  * calls are made to _cairo_cache_thaw().
 150  **/
 151 void
 152 _cairo_cache_freeze (cairo_cache_t *cache)
 153 {
 154     assert (cache->freeze_count >= 0);
 155
 156     cache->freeze_count++;
 157 }
 158
 159 /**
 160  * _cairo_cache_thaw:
 161  * @cache: a cache, just after the entries in it have become less
 162  * precious
 163  *
 164  * Cancels the effects of _cairo_cache_freeze().
 165  *
 166  * When a number of calls to _cairo_cache_thaw() is made corresponding
 167  * to the number of calls to _cairo_cache_freeze() the cache will no
 168  * longer be "frozen". If the cache had grown larger than max_size
 169  * while frozen, entries will immediately be ejected (by random) from
 170  * the cache until the cache is smaller than max_size. Also, the
 171  * automatic ejection of entries on _cairo_cache_insert() will resume.
 172  **/
 173 void
 174 _cairo_cache_thaw (cairo_cache_t *cache)
 175 {
 176     assert (cache->freeze_count > 0);
 177
 178     if (--cache->freeze_count == 0)
 179         _cairo_cache_shrink_to_accommodate (cache, 0);
 180 }
 181
 182 /**
 183  * _cairo_cache_lookup:
 184  * @cache: a cache
 185  * @key: the key of interest
 186  * @entry_return: pointer for return value
 187  *
 188  * Performs a lookup in @cache looking for an entry which has a key
 189  * that matches @key, (as determined by the keys_equal() function
 190  * passed to _cairo_cache_init()).
 191  *
 192  * Return value: %TRUE if there is an entry in the cache that matches
 193  * @key, (which will now be in *entry_return). %FALSE otherwise, (in
 194  * which case *entry_return will be %NULL).
 195  **/
 196 void *
 197 _cairo_cache_lookup (cairo_cache_t        *cache,
 198                      cairo_cache_entry_t  *key)
 199 {
 200     return _cairo_hash_table_lookup (cache->hash_table,
 201                                      (cairo_hash_entry_t *) key);
 202 }
 203
 204 /**
 205  * _cairo_cache_remove_random:
 206  * @cache: a cache
 207  *
 208  * Remove a random entry from the cache.
 209  *
 210  * Return value: %TRUE if an entry was successfully removed.
 211  * %FALSE if there are no entries that can be removed.
 212  **/
 213 static cairo_bool_t
 214 _cairo_cache_remove_random (cairo_cache_t *cache)
 215 {
 216     cairo_cache_entry_t *entry;
 217
 218     entry = _cairo_hash_table_random_entry (cache->hash_table,
 219                                             cache->predicate);
 220     if (unlikely (entry == NULL))
 221         return FALSE;
 222
 223     _cairo_cache_remove (cache, entry);
 224
 225     return TRUE;
 226 }
 227
 228 /**
 229  * _cairo_cache_shrink_to_accommodate:
 230  * @cache: a cache
 231  * @additional: additional size requested in bytes
 232  *
 233  * If cache is not frozen, eject entries randomly until the size of
 234  * the cache is at least @additional bytes less than
 235  * cache->max_size. That is, make enough room to accommodate a new
 236  * entry of size @additional.
 237  **/
 238 static void
 239 _cairo_cache_shrink_to_accommodate (cairo_cache_t *cache,
 240                                     unsigned long  additional)
 241 {
 242     while (cache->size + additional > cache->max_size) {
 243         if (! _cairo_cache_remove_random (cache))
 244             return;
 245     }
 246 }
 247
 248 /**
 249  * _cairo_cache_insert:
 250  * @cache: a cache
 251  * @entry: an entry to be inserted
 252  *
 253  * Insert @entry into the cache. If an entry exists in the cache with
 254  * a matching key, then the old entry will be removed first, (and the
 255  * entry_destroy() callback will be called on it).
 256  *
 257  * Return value: %CAIRO_STATUS_SUCCESS if successful or
 258  * %CAIRO_STATUS_NO_MEMORY if insufficient memory is available.
 259  **/
 260 cairo_status_t
 261 _cairo_cache_insert (cairo_cache_t       *cache,
 262                      cairo_cache_entry_t *entry)
 263 {
 264     cairo_status_t status;
 265
 266     if (entry->size && ! cache->freeze_count)
 267         _cairo_cache_shrink_to_accommodate (cache, entry->size);
 268
 269     status = _cairo_hash_table_insert (cache->hash_table,
 270                                        (cairo_hash_entry_t *) entry);
 271     if (unlikely (status))
 272         return status;
 273
 274     cache->size += entry->size;
 275
 276     return CAIRO_STATUS_SUCCESS;
 277 }
 278
 279 /**
 280  * _cairo_cache_remove:
 281  * @cache: a cache
 282  * @entry: an entry that exists in the cache
 283  *
 284  * Remove an existing entry from the cache.
 285  **/
 286 void
 287 _cairo_cache_remove (cairo_cache_t       *cache,
 288                      cairo_cache_entry_t *entry)
 289 {
 290     cache->size -= entry->size;
 291
 292     _cairo_hash_table_remove (cache->hash_table,
 293                               (cairo_hash_entry_t *) entry);
 294
 295     if (cache->entry_destroy)
 296         cache->entry_destroy (entry);
 297 }
 298
 299 /**
 300  * _cairo_cache_foreach:
 301  * @cache: a cache
 302  * @cache_callback: function to be called for each entry
 303  * @closure: additional argument to be passed to @cache_callback
 304  *
 305  * Call @cache_callback for each entry in the cache, in a
 306  * non-specified order.
 307  **/
 308 void
 309 _cairo_cache_foreach (cairo_cache_t                   *cache,
 310                       cairo_cache_callback_func_t      cache_callback,
 311                       void                            *closure)
 312 {
 313     _cairo_hash_table_foreach (cache->hash_table,
 314                                cache_callback,
 315                                closure);
 316 }
 317
 318 unsigned long
 319 _cairo_hash_string (const char *c)
 320 {
 321     /* This is the djb2 hash. */
 322     unsigned long hash = _CAIRO_HASH_INIT_VALUE;
 323     while (c && *c)
 324         hash = ((hash << 5) + hash) + *c++;
 325     return hash;
 326 }
 327
 328 unsigned long
 329 _cairo_hash_bytes (unsigned long hash,
 330                    const void *ptr,
 331                    unsigned int length)
 332 {
 333     const uint8_t *bytes = ptr;
 334     /* This is the djb2 hash. */
 335     while (length--)
 336         hash = ((hash << 5) + hash) + *bytes++;
 337     return hash;
 338 }