Split out scaled font code to cairo-scaled-font.c

Replace cairo cache implementation (this code from cworth)
No more global glyph cache to clean up
Store glyphs in new per-scaled font caches which hold user-space metrics and device space bounding boxes
Refactor glyph drawing APIs so that the surface API is invoked directly from the gstate code.
Add path creation/destruction routines (to hold glyph paths)
New implementation of scaled fonts which uses per-scaled_font caches for glyphs and keeps user-space metrics, device-space bboxes along with glyph images and/or glyph paths.
Adapt to new scaled font API changes.
New cache and scaled_font APIs
Repond to bug fix in metrics computation for glyphs where y values were rounded up instead of down because of a sign difference between cairo and FreeType.
Reviewed by: otaylor, cworth

1 files changed, 239 insertions, 421 deletions

diff --git a/src/cairo-cache.c b/src/cairo-cache.c
index b43bccab..25a35bf8 100644
--- a/src/cairo-cache.c
+++ b/src/cairo-cache.c
@@ -1,6 +1,7 @@
 /* cairo - a vector graphics library with display and print output
  *
- * This file is Copyright © 2004 Red Hat, Inc.
+ * 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
@@ -30,481 +31,298 @@
  * The Initial Developer of the Original Code is Red Hat, Inc.
  *
  * Contributor(s):
- *      Keith Packard
+ *      Keith Packard <keithp@keithp.com>
  *	Graydon Hoare <graydon@redhat.com>
+ *	Carl Worth <cworth@cworth.org>
  */
 
 #include "cairoint.h"
 
-/* 
- * This structure, and accompanying table, is borrowed/modified from the
- * file xserver/render/glyph.c in the freedesktop.org x server, with
- * permission (and suggested modification of doubling sizes) by Keith
- * Packard.
- */
+struct _cairo_cache {
+    cairo_hash_table_t *hash_table;
 
-static const cairo_cache_arrangement_t cache_arrangements [] = {
-    { 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 }
-};
+    cairo_destroy_func_t entry_destroy;
 
-#define N_CACHE_SIZES (sizeof(cache_arrangements)/sizeof(cache_arrangements[0]))
+    unsigned long max_size;
+    unsigned long size;
 
-/*
- * Entries 'e' are poiners, in one of 3 states:
- *
- * e == NULL: The entry has never had anything put in it
- * e != DEAD_ENTRY: The entry has an active value in it currently
- * e == DEAD_ENTRY: The entry *had* a value in it at some point, but the 
- *                  entry has been killed. Lookups requesting free space can
- *                  reuse these entries; lookups requesting a precise match
- *                  should neither return these entries nor stop searching when
- *                  seeing these entries. 
- *
- * We expect keys will not be destroyed frequently, so our table does not
- * contain any explicit shrinking code nor any chain-coalescing code for
- * entries randomly deleted by memory pressure (except during rehashing, of
- * course). These assumptions are potentially bad, but they make the
- * implementation straightforward.
- *
- * Revisit later if evidence appears that we're using excessive memory from
- * a mostly-dead table.
- *
- * Generally you do not need to worry about freeing cache entries; the
- * cache will expire entries randomly as it experiences memory pressure.
- * If max_memory is set, entries are not expired, and must be explicitely
- * removed.
- *
- * This table is open-addressed with double hashing. Each table size is a
- * prime chosen to be a little more than double the high water mark for a
- * given arrangement, so the tables should remain < 50% full. The table
- * size makes for the "first" hash modulus; a second prime (2 less than the
- * first prime) serves as the "second" hash modulus, which is co-prime and
- * thus guarantees a complete permutation of table indices.
- * 
- */
+    cairo_bool_t preserve_entries;
+};
 
-#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)))))
-
-#ifdef NDEBUG
-#define _cache_sane_state(c) 
-#else
-static void 
-_cache_sane_state (cairo_cache_t *cache)
+static cairo_status_t
+_cairo_cache_init (cairo_cache_t		*cache,
+		   cairo_cache_keys_equal_func_t keys_equal,
+		   cairo_destroy_func_t		 entry_destroy,
+		   unsigned long		 max_size)
 {
-    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);   
+    cache->hash_table = _cairo_hash_table_create (keys_equal);
+    if (cache->hash_table == NULL)
+	return CAIRO_STATUS_NO_MEMORY;
+
+    cache->entry_destroy = entry_destroy;
+
+    cache->max_size = max_size;
+    cache->size = 0;
+
+    cache->preserve_entries = FALSE;
+
+    return CAIRO_STATUS_SUCCESS;
 }
-#endif
 
 static void
-_entry_destroy (cairo_cache_t *cache, unsigned long i)
+_cairo_cache_fini (cairo_cache_t *cache)
 {
-    _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;
+    cairo_cache_entry_t *entry;
+
+    /* We have to manually remove all entries from the cache ourselves
+     * rather than relying on _cairo_hash_table_destroy to do that
+     * since otherwise the cache->entry_destroy callback would not get
+     * called on each entry. */
+
+    while (1) {
+	entry = _cairo_hash_table_random_entry (cache->hash_table, NULL);
+	if (entry == NULL)
+	    break;
+	_cairo_cache_remove (cache, entry);
     }
+
+    _cairo_hash_table_destroy (cache->hash_table);
+    cache->size = 0;
 }
 
-static cairo_cache_entry_base_t **
-_cache_lookup (cairo_cache_t *cache,
-	       void *key,
-	       int (*predicate)(void*,void*,void*))
-{    
-
-    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;
-	    }
-	}
+/**
+ * _cairo_cache_create:
+ * @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
+ * 
+ * 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_remove()), 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_preserve() and _cairo_cache_release() calls can be
+ * used to establish a window during which no automatic removal of
+ * entries will occur.
+ * 
+ * Return value: 
+ **/
+cairo_cache_t *
+_cairo_cache_create (cairo_cache_keys_equal_func_t keys_equal,
+		     cairo_destroy_func_t	   entry_destroy,
+		     unsigned long		   max_size)
+{
+    cairo_status_t status;
+    cairo_cache_t *cache;
 
-	if (step == 0) { 	    
-	    step = hash % cache->arrangement->rehash;
-	    if (step == 0)
-		step = 1;
-	}
+    cache = malloc (sizeof (cairo_cache_t));
+    if (cache == NULL)
+	return NULL;
 
-	idx += step;
-	if (idx >= table_size)
-	    idx -= table_size;
+    status = _cairo_cache_init (cache, keys_equal, entry_destroy, max_size);
+    if (status) {
+	free (cache);
+	return NULL;
     }
 
-    /* 
-     * 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;
+    return cache;
 }
 
-static cairo_cache_entry_base_t **
-_find_available_entry_for (cairo_cache_t *cache,
-			   void *key)
+/**
+ * _cairo_cache_destroy:
+ * @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_create), will be called for
+ * each entry in the cache.
+ **/
+void
+_cairo_cache_destroy (cairo_cache_t *cache)
 {
-    return _cache_lookup (cache, key, NULL);
-}
+    _cairo_cache_fini (cache);
 
-static cairo_cache_entry_base_t **
-_find_exact_live_entry_for (cairo_cache_t *cache,
-			    void *key)
-{    
-    return _cache_lookup (cache, key, cache->backend->keys_equal);
+    free (cache);
 }
 
-static const cairo_cache_arrangement_t *
-_find_cache_arrangement (unsigned long proposed_size)
+/**
+ * _cairo_cache_preserve:
+ * @cache: a cache with some precious entries in it (or about to be
+ * added)
+ * 
+ * Disable the automatic ejection of entries from the cache. Future
+ * calls to _cairo_cache_insert will add new entries to the cache
+ * regardless of how large the cache grows. See
+ * _cairo_cache_release().
+ **/
+void
+_cairo_cache_preserve (cairo_cache_t *cache)
 {
-    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;
+    cache->preserve_entries = TRUE;
 }
 
-static cairo_status_t
-_resize_cache (cairo_cache_t *cache, unsigned long proposed_size)
+/**
+ * _cairo_cache_release:
+ * @cache: a cache, just after the entries in it have become less
+ * previous
+ * 
+ * Cancel the effects of _cairo_cache_preserve(). That is, allow the
+ * cache to resume ejecting entries when it is larger than max_size as
+ * passed to cairo_cache_create. If the cache is already larger than
+ * max_size, no entries will be immediately removed, but the cache
+ * will be brought down to size at the time of the next call to
+ * _cairo_cache_insert.
+ **/
+void
+_cairo_cache_release (cairo_cache_t *cache)
 {
-    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;
+    cache->preserve_entries = FALSE;
 }
 
-
-#ifdef CAIRO_MEASURE_CACHE_PERFORMANCE
-static double
-_load_factor (cairo_cache_t *cache)
+/**
+ * _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_create).
+ * 
+ * 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).
+ **/
+cairo_private cairo_bool_t
+_cairo_cache_lookup (cairo_cache_t	  *cache,
+		     cairo_cache_entry_t  *key,
+		     cairo_cache_entry_t **entry_return)
 {
-    return ((double) cache->live_entries) 
-	/ ((double) cache->arrangement->size);
+    return _cairo_hash_table_lookup (cache->hash_table,
+				     (cairo_hash_entry_t *) key,
+				     (cairo_hash_entry_t **) entry_return);
 }
-#endif
-
-/* Find a random in the cache matching the given predicate. We use the
- * same algorithm as the probing algorithm to walk over the entries in
- * the hash table in a pseudo-random order. Walking linearly would
- * favor entries following gaps in the hash table. We could also
- * call rand() repeatedly, which works well for almost-full tables,
- * but degrades when the table is almost empty, or predicate
- * returns false for most entries.
- */
-static cairo_cache_entry_base_t **
-_random_entry (cairo_cache_t *cache,
-	       int (*predicate)(void*))
-{    
-    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;
-}
+/**
+ * _cairo_cache_remove_random:
+ * @cache: a cache
+ * 
+ * Remove a random entry from the cache.
+ * 
+ * Return value: CAIRO_STATUS_SUCCESS if an entry was successfully
+ * removed. CAIRO_INT_STATUS_CACHE_EMPTY if there are no entries that
+ * can be removed.
+ **/
+static cairo_int_status_t
+_cairo_cache_remove_random (cairo_cache_t *cache)
+{
+    cairo_cache_entry_t *entry;
 
-/* public API follows */
-
-cairo_status_t
-_cairo_cache_init (cairo_cache_t *cache,
-		   const cairo_cache_backend_t *backend,
-		   unsigned long max_memory)
-{    
-    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;
-}
+    entry = _cairo_hash_table_random_entry (cache->hash_table, NULL);
+    if (entry == NULL)
+	return CAIRO_INT_STATUS_CACHE_EMPTY;
 
-void
-_cairo_cache_destroy (cairo_cache_t *cache)
-{
-    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);
-}
+    _cairo_cache_remove (cache, entry);
 
-void
-_cairo_cache_shrink_to (cairo_cache_t *cache,
-			unsigned long max_memory)
-{
-    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);
-    }
+    return CAIRO_STATUS_SUCCESS;
 }
 
-cairo_status_t
-_cairo_cache_lookup (cairo_cache_t *cache,
-		     void          *key,
-		     void         **entry_return,
-		     int           *created_entry)
+/**
+ * _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_private cairo_status_t
+_cairo_cache_insert (cairo_cache_t	 *cache,
+		     cairo_cache_entry_t *entry)
 {
-
-    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;
+    cairo_status_t status;
+
+    if (! cache->preserve_entries) {
+	while (cache->size + entry->size > cache->max_size) {
+	    status = _cairo_cache_remove_random (cache);
+	    if (status) {
+		if (status == CAIRO_INT_STATUS_CACHE_EMPTY)
+		    break;
+		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)
+    status = _cairo_hash_table_insert (cache->hash_table,
+				       (cairo_hash_entry_t *) entry);
+    if (status)
 	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;
-    }
+    cache->size += entry->size;
 
-    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;
+    return CAIRO_STATUS_SUCCESS;
 }
 
-cairo_status_t
-_cairo_cache_remove (cairo_cache_t *cache,
-		     void          *key)
+/**
+ * _cairo_cache_remove:
+ * @cache: a cache
+ * @entry: key of entry to be removed
+ * 
+ * Remove an entry from the cache which has a key that matches @key,
+ * if any (as determined by the keys_equal() function passed to
+ * _cairo_cache_create).
+ **/
+cairo_private void
+_cairo_cache_remove (cairo_cache_t	 *cache,
+		     cairo_cache_entry_t *entry)
 {
-    cairo_cache_entry_base_t **slot;
+    cache->size -= entry->size;
 
-    _cache_sane_state (cache);
+    _cairo_hash_table_remove (cache->hash_table,
+			      (cairo_hash_entry_t *) entry);
 
-    /* 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;
+    if (cache->entry_destroy)
+	cache->entry_destroy (entry);
 }
 
-void *
-_cairo_cache_random_entry (cairo_cache_t *cache,
-			   int (*predicate)(void*))
+/**
+ * _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_cache_entry_base_t **slot = _random_entry (cache, predicate);
-
-    return slot ? *slot : NULL;
+    _cairo_hash_table_foreach (cache->hash_table,
+			       cache_callback,
+			       closure);
 }
 
 unsigned long