cairo/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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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
  41 static void
  42 _cairo_cache_remove (cairo_cache_t       *cache,
  43                      cairo_cache_entry_t *entry);
  44
  45 static void
  46 _cairo_cache_shrink_to_accommodate (cairo_cache_t *cache,
  47                                    unsigned long  additional);
  48
  49 static cairo_status_t
  50 _cairo_cache_init (cairo_cache_t                *cache,
  51                    cairo_cache_keys_equal_func_t keys_equal,
  52                    cairo_destroy_func_t          entry_destroy,
  53                    unsigned long                 max_size)
  54 {
  55     cache->hash_table = _cairo_hash_table_create (keys_equal);
  56     if (cache->hash_table == NULL)
  57         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  58
  59     cache->entry_destroy = entry_destroy;
  60
  61     cache->max_size = max_size;
  62     cache->size = 0;
  63
  64     cache->freeze_count = 0;
  65
  66     return CAIRO_STATUS_SUCCESS;
  67 }
  68
  69 static void
  70 _cairo_cache_fini (cairo_cache_t *cache)
  71 {
  72     cairo_cache_entry_t *entry;
  73
  74     /* We have to manually remove all entries from the cache ourselves
  75      * rather than relying on _cairo_hash_table_destroy() to do that
  76      * since otherwise the cache->entry_destroy callback would not get
  77      * called on each entry. */
  78
  79     while (1) {
  80         entry = _cairo_hash_table_random_entry (cache->hash_table, NULL);
  81         if (entry == NULL)
  82             break;
  83         _cairo_cache_remove (cache, entry);
  84     }
  85
  86     _cairo_hash_table_destroy (cache->hash_table);
  87     cache->size = 0;
  88 }
  89
  90 /**
  91  * _cairo_cache_create:
  92  * @keys_equal: a function to return %TRUE if two keys are equal
  93  * @entry_destroy: destroy notifier for cache entries
  94  * @max_size: the maximum size for this cache
  95  * Returns: the newly created #cairo_cache_t
  96  *
  97  * Creates a new cache using the keys_equal() function to determine
  98  * the equality of entries.
  99  *
 100  * Data is provided to the cache in the form of user-derived version
 101  * of #cairo_cache_entry_t. A cache entry must be able to hold hash
 102  * code, a size, and the key/value pair being stored in the
 103  * cache. Sometimes only the key will be necessary, (as in
 104  * _cairo_cache_lookup()), and in these cases the value portion of the
 105  * entry need not be initialized.
 106  *
 107  * The units for max_size can be chosen by the caller, but should be
 108  * consistent with the units of the size field of cache entries. When
 109  * adding an entry with _cairo_cache_insert() if the total size of
 110  * entries in the cache would exceed max_size then entries will be
 111  * removed at random until the new entry would fit or the cache is
 112  * empty. Then the new entry is inserted.
 113  *
 114  * There are cases in which the automatic removal of entries is
 115  * undesired. If the cache entries have reference counts, then it is a
 116  * simple matter to use the reference counts to ensure that entries
 117  * continue to live even after being ejected from the cache. However,
 118  * in some cases the memory overhead of adding a reference count to
 119  * the entry would be objectionable. In such cases, the
 120  * _cairo_cache_freeze() and _cairo_cache_thaw() calls can be
 121  * used to establish a window during which no automatic removal of
 122  * entries will occur.
 123  **/
 124 cairo_cache_t *
 125 _cairo_cache_create (cairo_cache_keys_equal_func_t keys_equal,
 126                      cairo_destroy_func_t          entry_destroy,
 127                      unsigned long                 max_size)
 128 {
 129     cairo_status_t status;
 130     cairo_cache_t *cache;
 131
 132     cache = malloc (sizeof (cairo_cache_t));
 133     if (cache == NULL) {
 134         status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
 135         return NULL;
 136     }
 137
 138     status = _cairo_cache_init (cache, keys_equal, entry_destroy, max_size);
 139     if (status) {
 140         free (cache);
 141         return NULL;
 142     }
 143
 144     return cache;
 145 }
 146
 147 /**
 148  * _cairo_cache_destroy:
 149  * @cache: a cache to destroy
 150  *
 151  * Immediately destroys the given cache, freeing all resources
 152  * associated with it. As part of this process, the entry_destroy()
 153  * function, (as passed to _cairo_cache_create()), will be called for
 154  * each entry in the cache.
 155  **/
 156 void
 157 _cairo_cache_destroy (cairo_cache_t *cache)
 158 {
 159     _cairo_cache_fini (cache);
 160
 161     free (cache);
 162 }
 163
 164 /**
 165  * _cairo_cache_freeze:
 166  * @cache: a cache with some precious entries in it (or about to be
 167  * added)
 168  *
 169  * Disable the automatic ejection of entries from the cache. For as
 170  * long as the cache is "frozen", calls to _cairo_cache_insert() will
 171  * add new entries to the cache regardless of how large the cache
 172  * grows. See _cairo_cache_thaw().
 173  *
 174  * Note: Multiple calls to _cairo_cache_freeze() will stack, in that
 175  * the cache will remain "frozen" until a corresponding number of
 176  * calls are made to _cairo_cache_thaw().
 177  **/
 178 void
 179 _cairo_cache_freeze (cairo_cache_t *cache)
 180 {
 181     assert (cache->freeze_count >= 0);
 182
 183     cache->freeze_count++;
 184 }
 185
 186 /**
 187  * _cairo_cache_thaw:
 188  * @cache: a cache, just after the entries in it have become less
 189  * precious
 190  *
 191  * Cancels the effects of _cairo_cache_freeze().
 192  *
 193  * When a number of calls to _cairo_cache_thaw() is made corresponding
 194  * to the number of calls to _cairo_cache_freeze() the cache will no
 195  * longer be "frozen". If the cache had grown larger than max_size
 196  * while frozen, entries will immediately be ejected (by random) from
 197  * the cache until the cache is smaller than max_size. Also, the
 198  * automatic ejection of entries on _cairo_cache_insert() will resume.
 199  **/
 200 void
 201 _cairo_cache_thaw (cairo_cache_t *cache)
 202 {
 203     assert (cache->freeze_count > 0);
 204
 205     cache->freeze_count--;
 206
 207     if (cache->freeze_count == 0)
 208         _cairo_cache_shrink_to_accommodate (cache, 0);
 209 }
 210
 211 /**
 212  * _cairo_cache_lookup:
 213  * @cache: a cache
 214  * @key: the key of interest
 215  * @entry_return: pointer for return value
 216  *
 217  * Performs a lookup in @cache looking for an entry which has a key
 218  * that matches @key, (as determined by the keys_equal() function
 219  * passed to _cairo_cache_create()).
 220  *
 221  * Return value: %TRUE if there is an entry in the cache that matches
 222  * @key, (which will now be in *entry_return). %FALSE otherwise, (in
 223  * which case *entry_return will be %NULL).
 224  **/
 225 cairo_bool_t
 226 _cairo_cache_lookup (cairo_cache_t        *cache,
 227                      cairo_cache_entry_t  *key,
 228                      cairo_cache_entry_t **entry_return)
 229 {
 230     return _cairo_hash_table_lookup (cache->hash_table,
 231                                      (cairo_hash_entry_t *) key,
 232                                      (cairo_hash_entry_t **) entry_return);
 233 }
 234
 235 /**
 236  * _cairo_cache_remove_random:
 237  * @cache: a cache
 238  *
 239  * Remove a random entry from the cache.
 240  *
 241  * Return value: %TRUE if an entry was successfully removed.
 242  * %FALSE if there are no entries that can be removed.
 243  **/
 244 static cairo_bool_t
 245 _cairo_cache_remove_random (cairo_cache_t *cache)
 246 {
 247     cairo_cache_entry_t *entry;
 248
 249     entry = _cairo_hash_table_random_entry (cache->hash_table, NULL);
 250     if (entry == NULL)
 251         return FALSE;
 252
 253     _cairo_cache_remove (cache, entry);
 254
 255     return TRUE;
 256 }
 257
 258 /**
 259  * _cairo_cache_shrink_to_accommodate:
 260  * @cache: a cache
 261  * @additional: additional size requested in bytes
 262  *
 263  * If cache is not frozen, eject entries randomly until the size of
 264  * the cache is at least @additional bytes less than
 265  * cache->max_size. That is, make enough room to accommodate a new
 266  * entry of size @additional.
 267  **/
 268 static void
 269 _cairo_cache_shrink_to_accommodate (cairo_cache_t *cache,
 270                                     unsigned long  additional)
 271 {
 272     if (cache->freeze_count)
 273         return;
 274
 275     while (cache->size + additional > cache->max_size) {
 276         if (! _cairo_cache_remove_random (cache))
 277             return;
 278     }
 279 }
 280
 281 /**
 282  * _cairo_cache_insert:
 283  * @cache: a cache
 284  * @entry: an entry to be inserted
 285  *
 286  * Insert @entry into the cache. If an entry exists in the cache with
 287  * a matching key, then the old entry will be removed first, (and the
 288  * entry_destroy() callback will be called on it).
 289  *
 290  * Return value: %CAIRO_STATUS_SUCCESS if successful or
 291  * %CAIRO_STATUS_NO_MEMORY if insufficient memory is available.
 292  **/
 293 cairo_status_t
 294 _cairo_cache_insert (cairo_cache_t       *cache,
 295                      cairo_cache_entry_t *entry)
 296 {
 297     cairo_status_t status;
 298
 299     _cairo_cache_shrink_to_accommodate (cache, entry->size);
 300
 301     status = _cairo_hash_table_insert (cache->hash_table,
 302                                        (cairo_hash_entry_t *) entry);
 303     if (status)
 304         return status;
 305
 306     cache->size += entry->size;
 307
 308     return CAIRO_STATUS_SUCCESS;
 309 }
 310
 311 /**
 312  * _cairo_cache_remove:
 313  * @cache: a cache
 314  * @entry: an entry that exists in the cache
 315  *
 316  * Remove an existing entry from the cache.
 317  *
 318  * (Note: If any caller wanted access to a non-static version of this
 319  * function, an improved version would require only a key rather than
 320  * an entry. Fixing that would require fixing _cairo_hash_table_remove
 321  * to return (a copy of?) the entry being removed.)
 322  **/
 323 static void
 324 _cairo_cache_remove (cairo_cache_t       *cache,
 325                      cairo_cache_entry_t *entry)
 326 {
 327     cache->size -= entry->size;
 328
 329     _cairo_hash_table_remove (cache->hash_table,
 330                               (cairo_hash_entry_t *) entry);
 331
 332     if (cache->entry_destroy)
 333         cache->entry_destroy (entry);
 334 }
 335
 336 /**
 337  * _cairo_cache_foreach:
 338  * @cache: a cache
 339  * @cache_callback: function to be called for each entry
 340  * @closure: additional argument to be passed to @cache_callback
 341  *
 342  * Call @cache_callback for each entry in the cache, in a
 343  * non-specified order.
 344  **/
 345 void
 346 _cairo_cache_foreach (cairo_cache_t                   *cache,
 347                       cairo_cache_callback_func_t      cache_callback,
 348                       void                            *closure)
 349 {
 350     _cairo_hash_table_foreach (cache->hash_table,
 351                                cache_callback,
 352                                closure);
 353 }
 354
 355 unsigned long
 356 _cairo_hash_string (const char *c)
 357 {
 358     /* This is the djb2 hash. */
 359     unsigned long hash = 5381;
 360     while (c && *c)
 361         hash = ((hash << 5) + hash) + *c++;
 362     return hash;
 363 }