Back to index

lightning-sunbird  0.9+nobinonly
cairo-cache.c
Go to the documentation of this file.
00001 /* cairo - a vector graphics library with display and print output
00002  *
00003  * This file is Copyright © 2004 Red Hat, Inc.
00004  *
00005  * This library is free software; you can redistribute it and/or
00006  * modify it either under the terms of the GNU Lesser General Public
00007  * License version 2.1 as published by the Free Software Foundation
00008  * (the "LGPL") or, at your option, under the terms of the Mozilla
00009  * Public License Version 1.1 (the "MPL"). If you do not alter this
00010  * notice, a recipient may use your version of this file under either
00011  * the MPL or the LGPL.
00012  *
00013  * You should have received a copy of the LGPL along with this library
00014  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
00015  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
00016  * You should have received a copy of the MPL along with this library
00017  * in the file COPYING-MPL-1.1
00018  *
00019  * The contents of this file are subject to the Mozilla Public License
00020  * Version 1.1 (the "License"); you may not use this file except in
00021  * compliance with the License. You may obtain a copy of the License at
00022  * http://www.mozilla.org/MPL/
00023  *
00024  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
00025  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
00026  * the specific language governing rights and limitations.
00027  *
00028  * The Original Code is the cairo graphics library.
00029  *
00030  * The Initial Developer of the Original Code is Red Hat, Inc.
00031  *
00032  * Contributor(s):
00033  *      Keith Packard
00034  *     Graydon Hoare <graydon@redhat.com>
00035  */
00036 
00037 #include "cairoint.h"
00038 
00039 /* 
00040  * This structure, and accompanying table, is borrowed/modified from the
00041  * file xserver/render/glyph.c in the freedesktop.org x server, with
00042  * permission (and suggested modification of doubling sizes) by Keith
00043  * Packard.
00044  */
00045 
00046 static const cairo_cache_arrangement_t cache_arrangements [] = {
00047     { 16,            43,           41        },
00048     { 32,            73,           71        },
00049     { 64,            151,          149       },
00050     { 128,           283,          281       },
00051     { 256,           571,          569       },
00052     { 512,           1153,         1151      },
00053     { 1024,          2269,         2267      },
00054     { 2048,          4519,         4517      },
00055     { 4096,          9013,         9011      },
00056     { 8192,          18043,        18041     },
00057     { 16384,         36109,        36107     },
00058     { 32768,         72091,        72089     },
00059     { 65536,         144409,              144407    },
00060     { 131072,        288361,              288359    },
00061     { 262144,        576883,              576881    },
00062     { 524288,        1153459,      1153457   },
00063     { 1048576,              2307163,      2307161   },
00064     { 2097152,              4613893,      4613891   },
00065     { 4194304,              9227641,      9227639   },
00066     { 8388608,              18455029,     18455027  },
00067     { 16777216,             36911011,     36911009  },
00068     { 33554432,             73819861,     73819859  },
00069     { 67108864,             147639589,    147639587 },
00070     { 134217728,     295279081,    295279079 },
00071     { 268435456,     590559793,    590559791 }
00072 };
00073 
00074 #define N_CACHE_SIZES (sizeof(cache_arrangements)/sizeof(cache_arrangements[0]))
00075 
00076 /*
00077  * Entries 'e' are poiners, in one of 3 states:
00078  *
00079  * e == NULL: The entry has never had anything put in it
00080  * e != DEAD_ENTRY: The entry has an active value in it currently
00081  * e == DEAD_ENTRY: The entry *had* a value in it at some point, but the 
00082  *                  entry has been killed. Lookups requesting free space can
00083  *                  reuse these entries; lookups requesting a precise match
00084  *                  should neither return these entries nor stop searching when
00085  *                  seeing these entries. 
00086  *
00087  * We expect keys will not be destroyed frequently, so our table does not
00088  * contain any explicit shrinking code nor any chain-coalescing code for
00089  * entries randomly deleted by memory pressure (except during rehashing, of
00090  * course). These assumptions are potentially bad, but they make the
00091  * implementation straightforward.
00092  *
00093  * Revisit later if evidence appears that we're using excessive memory from
00094  * a mostly-dead table.
00095  *
00096  * Generally you do not need to worry about freeing cache entries; the
00097  * cache will expire entries randomly as it experiences memory pressure.
00098  * If max_memory is set, entries are not expired, and must be explicitely
00099  * removed.
00100  *
00101  * This table is open-addressed with double hashing. Each table size is a
00102  * prime chosen to be a little more than double the high water mark for a
00103  * given arrangement, so the tables should remain < 50% full. The table
00104  * size makes for the "first" hash modulus; a second prime (2 less than the
00105  * first prime) serves as the "second" hash modulus, which is co-prime and
00106  * thus guarantees a complete permutation of table indices.
00107  * 
00108  */
00109 
00110 #define DEAD_ENTRY ((cairo_cache_entry_base_t *) 1)
00111 #define NULL_ENTRY_P(cache, i) ((cache)->entries[i] == NULL)
00112 #define DEAD_ENTRY_P(cache, i) ((cache)->entries[i] == DEAD_ENTRY)
00113 #define LIVE_ENTRY_P(cache, i) \
00114  (!((NULL_ENTRY_P((cache),(i))) || (DEAD_ENTRY_P((cache),(i)))))
00115 
00116 #ifdef NDEBUG
00117 #define _cache_sane_state(c) 
00118 #else
00119 static void 
00120 _cache_sane_state (cairo_cache_t *cache)
00121 {
00122     assert (cache != NULL);
00123     assert (cache->entries != NULL);
00124     assert (cache->backend != NULL);
00125     assert (cache->arrangement != NULL);
00126     /* Cannot check this, a single object may larger */
00127     /* assert (cache->used_memory <= cache->max_memory); */
00128     assert (cache->live_entries <= cache->arrangement->size);   
00129 }
00130 #endif
00131 
00132 static void
00133 _entry_destroy (cairo_cache_t *cache, unsigned long i)
00134 {
00135     _cache_sane_state (cache);
00136 
00137     if (LIVE_ENTRY_P(cache, i))
00138     {
00139        cairo_cache_entry_base_t *entry = cache->entries[i];
00140        assert(cache->live_entries > 0);
00141        assert(cache->used_memory >= entry->memory);
00142 
00143        cache->live_entries--;
00144        cache->used_memory -= entry->memory;
00145        cache->backend->destroy_entry (cache, entry);
00146        cache->entries[i] = DEAD_ENTRY;
00147     }
00148 }
00149 
00150 static cairo_cache_entry_base_t **
00151 _cache_lookup (cairo_cache_t *cache,
00152               void *key,
00153               int (*predicate)(void*,void*,void*))
00154 {    
00155 
00156     cairo_cache_entry_base_t **probe;
00157     unsigned long hash;
00158     unsigned long table_size, i, idx, step;
00159     
00160     _cache_sane_state (cache);
00161     assert (key != NULL);
00162 
00163     table_size = cache->arrangement->size;
00164     hash = cache->backend->hash (cache, key);
00165     idx = hash % table_size;
00166     step = 0;
00167 
00168     for (i = 0; i < table_size; ++i)
00169     {
00170 #ifdef CAIRO_MEASURE_CACHE_PERFORMANCE
00171        cache->probes++;
00172 #endif 
00173        assert(idx < table_size);
00174        probe = cache->entries + idx;
00175 
00176        /* 
00177         * There are two lookup modes: searching for a free slot and searching
00178         * for an exact entry. 
00179         */ 
00180 
00181        if (predicate != NULL)
00182        {
00183            /* We are looking up an exact entry. */
00184            if (*probe == NULL)
00185            {
00186               /* Found an empty spot, there can't be a match */
00187               break;
00188            }
00189            else if (*probe != DEAD_ENTRY 
00190                    && (*probe)->hashcode == hash
00191                    && predicate (cache, key, *probe))
00192            {
00193               return probe;
00194            }
00195        }
00196        else
00197        {
00198            /* We are just looking for a free slot. */
00199            if (*probe == NULL 
00200               || *probe == DEAD_ENTRY)
00201            {
00202               return probe;
00203            }
00204        }
00205 
00206        if (step == 0) {         
00207            step = hash % cache->arrangement->rehash;
00208            if (step == 0)
00209               step = 1;
00210        }
00211 
00212        idx += step;
00213        if (idx >= table_size)
00214            idx -= table_size;
00215     }
00216 
00217     /* 
00218      * The table should not have permitted you to get here if you were just
00219      * looking for a free slot: there should have been room.
00220      */
00221     assert(predicate != NULL);
00222     return NULL;
00223 }
00224 
00225 static cairo_cache_entry_base_t **
00226 _find_available_entry_for (cairo_cache_t *cache,
00227                         void *key)
00228 {
00229     return _cache_lookup (cache, key, NULL);
00230 }
00231 
00232 static cairo_cache_entry_base_t **
00233 _find_exact_live_entry_for (cairo_cache_t *cache,
00234                          void *key)
00235 {    
00236     return _cache_lookup (cache, key, cache->backend->keys_equal);
00237 }
00238 
00239 static const cairo_cache_arrangement_t *
00240 _find_cache_arrangement (unsigned long proposed_size)
00241 {
00242     unsigned long idx;
00243 
00244     for (idx = 0; idx < N_CACHE_SIZES; ++idx)
00245        if (cache_arrangements[idx].high_water_mark >= proposed_size)
00246            return &cache_arrangements[idx];
00247     return NULL;
00248 }
00249 
00250 static cairo_status_t
00251 _resize_cache (cairo_cache_t *cache, unsigned long proposed_size)
00252 {
00253     cairo_cache_t tmp;
00254     cairo_cache_entry_base_t **e;
00255     unsigned long new_size, i;
00256 
00257     tmp = *cache;
00258     tmp.arrangement = _find_cache_arrangement (proposed_size);
00259     assert(tmp.arrangement != NULL);
00260     if (tmp.arrangement == cache->arrangement)
00261        return CAIRO_STATUS_SUCCESS;
00262 
00263     new_size = tmp.arrangement->size;
00264     tmp.entries = calloc (new_size, sizeof (cairo_cache_entry_base_t *));
00265     if (tmp.entries == NULL) 
00266        return CAIRO_STATUS_NO_MEMORY;
00267         
00268     for (i = 0; i < cache->arrangement->size; ++i) {
00269        if (LIVE_ENTRY_P(cache, i)) {
00270            e = _find_available_entry_for (&tmp, cache->entries[i]);
00271            assert (e != NULL);
00272            *e = cache->entries[i];
00273        }
00274     }
00275     free (cache->entries);
00276     cache->entries = tmp.entries;
00277     cache->arrangement = tmp.arrangement;
00278     return CAIRO_STATUS_SUCCESS;
00279 }
00280 
00281 
00282 #ifdef CAIRO_MEASURE_CACHE_PERFORMANCE
00283 static double
00284 _load_factor (cairo_cache_t *cache)
00285 {
00286     return ((double) cache->live_entries) 
00287        / ((double) cache->arrangement->size);
00288 }
00289 #endif
00290 
00291 /* Find a random in the cache matching the given predicate. We use the
00292  * same algorithm as the probing algorithm to walk over the entries in
00293  * the hash table in a pseudo-random order. Walking linearly would
00294  * favor entries following gaps in the hash table. We could also
00295  * call rand() repeatedly, which works well for almost-full tables,
00296  * but degrades when the table is almost empty, or predicate
00297  * returns false for most entries.
00298  */
00299 static cairo_cache_entry_base_t **
00300 _random_entry (cairo_cache_t *cache,
00301               int (*predicate)(void*))
00302 {    
00303     cairo_cache_entry_base_t **probe;
00304     unsigned long hash;
00305     unsigned long table_size, i, idx, step;
00306     
00307     _cache_sane_state (cache);
00308 
00309     table_size = cache->arrangement->size;
00310     hash = rand ();
00311     idx = hash % table_size;
00312     step = 0;
00313 
00314     for (i = 0; i < table_size; ++i)
00315     {
00316        assert(idx < table_size);
00317        probe = cache->entries + idx;
00318 
00319        if (LIVE_ENTRY_P(cache, idx)
00320            && (!predicate || predicate (*probe)))
00321            return probe;
00322 
00323        if (step == 0) {         
00324            step = hash % cache->arrangement->rehash;
00325            if (step == 0)
00326               step = 1;
00327        }
00328 
00329        idx += step;
00330        if (idx >= table_size)
00331            idx -= table_size;
00332     }
00333 
00334     return NULL;
00335 }
00336 
00337 /* public API follows */
00338 
00339 cairo_status_t
00340 _cairo_cache_init (cairo_cache_t *cache,
00341                  const cairo_cache_backend_t *backend,
00342                  unsigned long max_memory)
00343 {    
00344     assert (backend != NULL);
00345 
00346     if (cache != NULL){
00347        cache->arrangement = &cache_arrangements[0];
00348        cache->max_memory = max_memory;
00349        cache->used_memory = 0;
00350        cache->live_entries = 0;
00351 
00352 #ifdef CAIRO_MEASURE_CACHE_PERFORMANCE
00353        cache->hits = 0;
00354        cache->misses = 0;
00355        cache->probes = 0;
00356 #endif
00357 
00358        cache->backend = backend;   
00359        cache->entries = calloc (cache->arrangement->size,
00360                              sizeof(cairo_cache_entry_base_t *));
00361                              
00362        if (cache->entries == NULL)
00363            return CAIRO_STATUS_NO_MEMORY;
00364     }    
00365     _cache_sane_state (cache);
00366     return CAIRO_STATUS_SUCCESS;
00367 }
00368 
00369 void
00370 _cairo_cache_destroy (cairo_cache_t *cache)
00371 {
00372     unsigned long i;
00373     if (cache == NULL)
00374        return;
00375        
00376     _cache_sane_state (cache);
00377 
00378     for (i = 0; i < cache->arrangement->size; ++i)
00379        _entry_destroy (cache, i);
00380        
00381     free (cache->entries);
00382     cache->entries = NULL;
00383     cache->backend->destroy_cache (cache);
00384 }
00385 
00386 void
00387 _cairo_cache_shrink_to (cairo_cache_t *cache,
00388                      unsigned long max_memory)
00389 {
00390     unsigned long idx;
00391     /* Make some entries die if we're under memory pressure. */
00392     while (cache->live_entries > 0 && cache->used_memory > max_memory) {
00393        idx =  _random_entry (cache, NULL) - cache->entries;
00394        assert (idx < cache->arrangement->size);
00395        _entry_destroy (cache, idx);
00396     }
00397 }
00398 
00399 cairo_status_t
00400 _cairo_cache_lookup (cairo_cache_t *cache,
00401                    void          *key,
00402                    void         **entry_return,
00403                    int           *created_entry)
00404 {
00405 
00406     cairo_status_t status = CAIRO_STATUS_SUCCESS;
00407     cairo_cache_entry_base_t **slot = NULL, *new_entry;
00408 
00409     _cache_sane_state (cache);
00410 
00411 #ifdef CAIRO_MEASURE_CACHE_PERFORMANCE
00412     if ((cache->hits + cache->misses) % 0xffff == 0)
00413        printf("cache %p stats: size %ld, live %ld, load %.2f\n"
00414               "                      mem %ld/%ld, hit %ld, miss %ld\n"
00415               "                      probe %ld, %.2f probe/access\n", 
00416               cache,
00417               cache->arrangement->size, 
00418               cache->live_entries, 
00419               _load_factor (cache),
00420               cache->used_memory, 
00421               cache->max_memory,
00422               cache->hits, 
00423               cache->misses, 
00424               cache->probes,
00425               ((double) cache->probes) 
00426               / ((double) (cache->hits + 
00427                          cache->misses + 1)));
00428 #endif
00429     
00430     /* See if we have an entry in the table already. */
00431     slot = _find_exact_live_entry_for (cache, key);
00432     if (slot != NULL) {
00433 #ifdef CAIRO_MEASURE_CACHE_PERFORMANCE
00434        cache->hits++;
00435 #endif
00436        *entry_return = *slot;
00437        if (created_entry)
00438            *created_entry = 0;
00439        return status;
00440     }
00441 
00442 #ifdef CAIRO_MEASURE_CACHE_PERFORMANCE
00443     cache->misses++;
00444 #endif
00445 
00446     /* Build the new entry. */
00447     status = cache->backend->create_entry (cache, key, 
00448                                       (void **)&new_entry);
00449     if (status != CAIRO_STATUS_SUCCESS)
00450        return status;
00451 
00452     /* Store the hash value in case the backend forgot. */
00453     new_entry->hashcode = cache->backend->hash (cache, key);
00454 
00455     if (cache->live_entries && cache->max_memory)
00456         _cairo_cache_shrink_to (cache, cache->max_memory);
00457     
00458     /* Can't assert this; new_entry->memory may be larger than max_memory */
00459     /* assert(cache->max_memory >= (cache->used_memory + new_entry->memory)); */
00460     
00461     /* Make room in the table for a new slot. */
00462     status = _resize_cache (cache, cache->live_entries + 1);
00463     if (status != CAIRO_STATUS_SUCCESS) {
00464        cache->backend->destroy_entry (cache, new_entry);
00465        return status;
00466     }
00467 
00468     slot = _find_available_entry_for (cache, key);
00469     assert(slot != NULL);
00470     
00471     /* Store entry in slot and increment statistics. */
00472     *slot = new_entry;
00473     cache->live_entries++;
00474     cache->used_memory += new_entry->memory;
00475 
00476     _cache_sane_state (cache);
00477 
00478     *entry_return = new_entry;
00479     if (created_entry)
00480       *created_entry = 1;
00481     
00482     return status;
00483 }
00484 
00485 cairo_status_t
00486 _cairo_cache_remove (cairo_cache_t *cache,
00487                    void          *key)
00488 {
00489     cairo_cache_entry_base_t **slot;
00490 
00491     _cache_sane_state (cache);
00492 
00493     /* See if we have an entry in the table already. */
00494     slot = _find_exact_live_entry_for (cache, key);
00495     if (slot != NULL)
00496        _entry_destroy (cache, slot - cache->entries);
00497 
00498     return CAIRO_STATUS_SUCCESS;
00499 }
00500 
00501 void *
00502 _cairo_cache_random_entry (cairo_cache_t *cache,
00503                         int (*predicate)(void*))
00504 {
00505     cairo_cache_entry_base_t **slot = _random_entry (cache, predicate);
00506 
00507     return slot ? *slot : NULL;
00508 }
00509 
00510 unsigned long
00511 _cairo_hash_string (const char *c)
00512 {
00513     /* This is the djb2 hash. */
00514     unsigned long hash = 5381;
00515     while (c && *c)
00516        hash = ((hash << 5) + hash) + *c++;
00517     return hash;
00518 }
00519