Back to index

lightning-sunbird  0.9+nobinonly
Defines | Functions | Variables
cairo-cache.c File Reference
#include "cairoint.h"

Go to the source code of this file.

Defines

#define N_CACHE_SIZES   (sizeof(cache_arrangements)/sizeof(cache_arrangements[0]))
#define DEAD_ENTRY   ((cairo_cache_entry_base_t *) 1)
#define NULL_ENTRY_P(cache, i)   ((cache)->entries[i] == NULL)
#define DEAD_ENTRY_P(cache, i)   ((cache)->entries[i] == DEAD_ENTRY)
#define LIVE_ENTRY_P(cache, i)   (!((NULL_ENTRY_P((cache),(i))) || (DEAD_ENTRY_P((cache),(i)))))

Functions

static void _cache_sane_state (cairo_cache_t *cache)
static void _entry_destroy (cairo_cache_t *cache, unsigned long i)
static cairo_cache_entry_base_t ** _cache_lookup (cairo_cache_t *cache, void *key, int(*predicate)(void *, void *, void *))
static cairo_cache_entry_base_t ** _find_available_entry_for (cairo_cache_t *cache, void *key)
static cairo_cache_entry_base_t ** _find_exact_live_entry_for (cairo_cache_t *cache, void *key)
static const
cairo_cache_arrangement_t
_find_cache_arrangement (unsigned long proposed_size)
static cairo_status_t _resize_cache (cairo_cache_t *cache, unsigned long proposed_size)
static cairo_cache_entry_base_t ** _random_entry (cairo_cache_t *cache, int(*predicate)(void *))
cairo_status_t _cairo_cache_init (cairo_cache_t *cache, const cairo_cache_backend_t *backend, unsigned long max_memory)
void _cairo_cache_destroy (cairo_cache_t *cache)
void _cairo_cache_shrink_to (cairo_cache_t *cache, unsigned long max_memory)
cairo_status_t _cairo_cache_lookup (cairo_cache_t *cache, void *key, void **entry_return, int *created_entry)
cairo_status_t _cairo_cache_remove (cairo_cache_t *cache, void *key)
void_cairo_cache_random_entry (cairo_cache_t *cache, int(*predicate)(void *))
unsigned long _cairo_hash_string (const char *c)

Variables

static const
cairo_cache_arrangement_t 
cache_arrangements []

Define Documentation

Definition at line 110 of file cairo-cache.c.

#define DEAD_ENTRY_P (   cache,
  i 
)    ((cache)->entries[i] == DEAD_ENTRY)

Definition at line 112 of file cairo-cache.c.

#define LIVE_ENTRY_P (   cache,
  i 
)    (!((NULL_ENTRY_P((cache),(i))) || (DEAD_ENTRY_P((cache),(i)))))

Definition at line 113 of file cairo-cache.c.

Definition at line 74 of file cairo-cache.c.

#define NULL_ENTRY_P (   cache,
  i 
)    ((cache)->entries[i] == NULL)

Definition at line 111 of file cairo-cache.c.


Function Documentation

static cairo_cache_entry_base_t** _cache_lookup ( cairo_cache_t cache,
void key,
int(*)(void *, void *, void *)  predicate 
) [static]

Definition at line 151 of file cairo-cache.c.

{    

    cairo_cache_entry_base_t **probe;
    unsigned long hash;
    unsigned long table_size, i, idx, step;
    
    _cache_sane_state (cache);
    assert (key != NULL);

    table_size = cache->arrangement->size;
    hash = cache->backend->hash (cache, key);
    idx = hash % table_size;
    step = 0;

    for (i = 0; i < table_size; ++i)
    {
#ifdef CAIRO_MEASURE_CACHE_PERFORMANCE
       cache->probes++;
#endif 
       assert(idx < table_size);
       probe = cache->entries + idx;

       /* 
        * There are two lookup modes: searching for a free slot and searching
        * for an exact entry. 
        */ 

       if (predicate != NULL)
       {
           /* We are looking up an exact entry. */
           if (*probe == NULL)
           {
              /* Found an empty spot, there can't be a match */
              break;
           }
           else if (*probe != DEAD_ENTRY 
                   && (*probe)->hashcode == hash
                   && predicate (cache, key, *probe))
           {
              return probe;
           }
       }
       else
       {
           /* We are just looking for a free slot. */
           if (*probe == NULL 
              || *probe == DEAD_ENTRY)
           {
              return probe;
           }
       }

       if (step == 0) {         
           step = hash % cache->arrangement->rehash;
           if (step == 0)
              step = 1;
       }

       idx += step;
       if (idx >= table_size)
           idx -= table_size;
    }

    /* 
     * The table should not have permitted you to get here if you were just
     * looking for a free slot: there should have been room.
     */
    assert(predicate != NULL);
    return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void _cache_sane_state ( cairo_cache_t cache) [static]

Definition at line 120 of file cairo-cache.c.

{
    assert (cache != NULL);
    assert (cache->entries != NULL);
    assert (cache->backend != NULL);
    assert (cache->arrangement != NULL);
    /* Cannot check this, a single object may larger */
    /* assert (cache->used_memory <= cache->max_memory); */
    assert (cache->live_entries <= cache->arrangement->size);   
}

Here is the caller graph for this function:

Definition at line 370 of file cairo-cache.c.

{
    unsigned long i;
    if (cache == NULL)
       return;
       
    _cache_sane_state (cache);

    for (i = 0; i < cache->arrangement->size; ++i)
       _entry_destroy (cache, i);
       
    free (cache->entries);
    cache->entries = NULL;
    cache->backend->destroy_cache (cache);
}

Here is the call graph for this function:

Here is the caller graph for this function:

cairo_status_t _cairo_cache_init ( cairo_cache_t cache,
const cairo_cache_backend_t backend,
unsigned long  max_memory 
)

Definition at line 340 of file cairo-cache.c.

{    
    assert (backend != NULL);

    if (cache != NULL){
       cache->arrangement = &cache_arrangements[0];
       cache->max_memory = max_memory;
       cache->used_memory = 0;
       cache->live_entries = 0;

#ifdef CAIRO_MEASURE_CACHE_PERFORMANCE
       cache->hits = 0;
       cache->misses = 0;
       cache->probes = 0;
#endif

       cache->backend = backend;   
       cache->entries = calloc (cache->arrangement->size,
                             sizeof(cairo_cache_entry_base_t *));
                             
       if (cache->entries == NULL)
           return CAIRO_STATUS_NO_MEMORY;
    }    
    _cache_sane_state (cache);
    return CAIRO_STATUS_SUCCESS;
}

Here is the call graph for this function:

Here is the caller graph for this function:

cairo_status_t _cairo_cache_lookup ( cairo_cache_t cache,
void key,
void **  entry_return,
int created_entry 
)

Definition at line 400 of file cairo-cache.c.

{

    cairo_status_t status = CAIRO_STATUS_SUCCESS;
    cairo_cache_entry_base_t **slot = NULL, *new_entry;

    _cache_sane_state (cache);

#ifdef CAIRO_MEASURE_CACHE_PERFORMANCE
    if ((cache->hits + cache->misses) % 0xffff == 0)
       printf("cache %p stats: size %ld, live %ld, load %.2f\n"
              "                      mem %ld/%ld, hit %ld, miss %ld\n"
              "                      probe %ld, %.2f probe/access\n", 
              cache,
              cache->arrangement->size, 
              cache->live_entries, 
              _load_factor (cache),
              cache->used_memory, 
              cache->max_memory,
              cache->hits, 
              cache->misses, 
              cache->probes,
              ((double) cache->probes) 
              / ((double) (cache->hits + 
                         cache->misses + 1)));
#endif
    
    /* See if we have an entry in the table already. */
    slot = _find_exact_live_entry_for (cache, key);
    if (slot != NULL) {
#ifdef CAIRO_MEASURE_CACHE_PERFORMANCE
       cache->hits++;
#endif
       *entry_return = *slot;
       if (created_entry)
           *created_entry = 0;
       return status;
    }

#ifdef CAIRO_MEASURE_CACHE_PERFORMANCE
    cache->misses++;
#endif

    /* Build the new entry. */
    status = cache->backend->create_entry (cache, key, 
                                      (void **)&new_entry);
    if (status != CAIRO_STATUS_SUCCESS)
       return status;

    /* Store the hash value in case the backend forgot. */
    new_entry->hashcode = cache->backend->hash (cache, key);

    if (cache->live_entries && cache->max_memory)
        _cairo_cache_shrink_to (cache, cache->max_memory);
    
    /* Can't assert this; new_entry->memory may be larger than max_memory */
    /* assert(cache->max_memory >= (cache->used_memory + new_entry->memory)); */
    
    /* Make room in the table for a new slot. */
    status = _resize_cache (cache, cache->live_entries + 1);
    if (status != CAIRO_STATUS_SUCCESS) {
       cache->backend->destroy_entry (cache, new_entry);
       return status;
    }

    slot = _find_available_entry_for (cache, key);
    assert(slot != NULL);
    
    /* Store entry in slot and increment statistics. */
    *slot = new_entry;
    cache->live_entries++;
    cache->used_memory += new_entry->memory;

    _cache_sane_state (cache);

    *entry_return = new_entry;
    if (created_entry)
      *created_entry = 1;
    
    return status;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* _cairo_cache_random_entry ( cairo_cache_t cache,
int(*)(void *)  predicate 
)

Definition at line 502 of file cairo-cache.c.

{
    cairo_cache_entry_base_t **slot = _random_entry (cache, predicate);

    return slot ? *slot : NULL;
}

Here is the call graph for this function:

Definition at line 486 of file cairo-cache.c.

{
    cairo_cache_entry_base_t **slot;

    _cache_sane_state (cache);

    /* See if we have an entry in the table already. */
    slot = _find_exact_live_entry_for (cache, key);
    if (slot != NULL)
       _entry_destroy (cache, slot - cache->entries);

    return CAIRO_STATUS_SUCCESS;
}

Here is the call graph for this function:

void _cairo_cache_shrink_to ( cairo_cache_t cache,
unsigned long  max_memory 
)

Definition at line 387 of file cairo-cache.c.

{
    unsigned long idx;
    /* Make some entries die if we're under memory pressure. */
    while (cache->live_entries > 0 && cache->used_memory > max_memory) {
       idx =  _random_entry (cache, NULL) - cache->entries;
       assert (idx < cache->arrangement->size);
       _entry_destroy (cache, idx);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned long _cairo_hash_string ( const char *  c)

Definition at line 511 of file cairo-cache.c.

{
    /* This is the djb2 hash. */
    unsigned long hash = 5381;
    while (c && *c)
       hash = ((hash << 5) + hash) + *c++;
    return hash;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void _entry_destroy ( cairo_cache_t cache,
unsigned long  i 
) [static]

Definition at line 133 of file cairo-cache.c.

{
    _cache_sane_state (cache);

    if (LIVE_ENTRY_P(cache, i))
    {
       cairo_cache_entry_base_t *entry = cache->entries[i];
       assert(cache->live_entries > 0);
       assert(cache->used_memory >= entry->memory);

       cache->live_entries--;
       cache->used_memory -= entry->memory;
       cache->backend->destroy_entry (cache, entry);
       cache->entries[i] = DEAD_ENTRY;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static cairo_cache_entry_base_t** _find_available_entry_for ( cairo_cache_t cache,
void key 
) [static]

Definition at line 226 of file cairo-cache.c.

{
    return _cache_lookup (cache, key, NULL);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static const cairo_cache_arrangement_t* _find_cache_arrangement ( unsigned long  proposed_size) [static]

Definition at line 240 of file cairo-cache.c.

{
    unsigned long idx;

    for (idx = 0; idx < N_CACHE_SIZES; ++idx)
       if (cache_arrangements[idx].high_water_mark >= proposed_size)
           return &cache_arrangements[idx];
    return NULL;
}

Here is the caller graph for this function:

static cairo_cache_entry_base_t** _find_exact_live_entry_for ( cairo_cache_t cache,
void key 
) [static]

Definition at line 233 of file cairo-cache.c.

{    
    return _cache_lookup (cache, key, cache->backend->keys_equal);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static cairo_cache_entry_base_t** _random_entry ( cairo_cache_t cache,
int(*)(void *)  predicate 
) [static]

Definition at line 300 of file cairo-cache.c.

{    
    cairo_cache_entry_base_t **probe;
    unsigned long hash;
    unsigned long table_size, i, idx, step;
    
    _cache_sane_state (cache);

    table_size = cache->arrangement->size;
    hash = rand ();
    idx = hash % table_size;
    step = 0;

    for (i = 0; i < table_size; ++i)
    {
       assert(idx < table_size);
       probe = cache->entries + idx;

       if (LIVE_ENTRY_P(cache, idx)
           && (!predicate || predicate (*probe)))
           return probe;

       if (step == 0) {         
           step = hash % cache->arrangement->rehash;
           if (step == 0)
              step = 1;
       }

       idx += step;
       if (idx >= table_size)
           idx -= table_size;
    }

    return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static cairo_status_t _resize_cache ( cairo_cache_t cache,
unsigned long  proposed_size 
) [static]

Definition at line 251 of file cairo-cache.c.

{
    cairo_cache_t tmp;
    cairo_cache_entry_base_t **e;
    unsigned long new_size, i;

    tmp = *cache;
    tmp.arrangement = _find_cache_arrangement (proposed_size);
    assert(tmp.arrangement != NULL);
    if (tmp.arrangement == cache->arrangement)
       return CAIRO_STATUS_SUCCESS;

    new_size = tmp.arrangement->size;
    tmp.entries = calloc (new_size, sizeof (cairo_cache_entry_base_t *));
    if (tmp.entries == NULL) 
       return CAIRO_STATUS_NO_MEMORY;
        
    for (i = 0; i < cache->arrangement->size; ++i) {
       if (LIVE_ENTRY_P(cache, i)) {
           e = _find_available_entry_for (&tmp, cache->entries[i]);
           assert (e != NULL);
           *e = cache->entries[i];
       }
    }
    free (cache->entries);
    cache->entries = tmp.entries;
    cache->arrangement = tmp.arrangement;
    return CAIRO_STATUS_SUCCESS;
}

Here is the call graph for this function:

Here is the caller graph for this function:


Variable Documentation

Initial value:
 {
    { 16,            43,           41        },
    { 32,            73,           71        },
    { 64,            151,          149       },
    { 128,           283,          281       },
    { 256,           571,          569       },
    { 512,           1153,         1151      },
    { 1024,          2269,         2267      },
    { 2048,          4519,         4517      },
    { 4096,          9013,         9011      },
    { 8192,          18043,        18041     },
    { 16384,         36109,        36107     },
    { 32768,         72091,        72089     },
    { 65536,         144409,              144407    },
    { 131072,        288361,              288359    },
    { 262144,        576883,              576881    },
    { 524288,        1153459,      1153457   },
    { 1048576,              2307163,      2307161   },
    { 2097152,              4613893,      4613891   },
    { 4194304,              9227641,      9227639   },
    { 8388608,              18455029,     18455027  },
    { 16777216,             36911011,     36911009  },
    { 33554432,             73819861,     73819859  },
    { 67108864,             147639589,    147639587 },
    { 134217728,     295279081,    295279079 },
    { 268435456,     590559793,    590559791 }
}

Definition at line 46 of file cairo-cache.c.