Add cairo_cache.c

Rewrite using temporary glyph arrays
New file.
Remove old glyph cache code. (_cairo_font_scale) (_cairo_font_transform): Remove font-transforming code. (_cairo_font_text_extents) (_cairo_font_text_bbox) (_cairo_font_show_text) (_cairo_font_text_path): Remove text-API code. (_cairo_font_cache_key_t): New structure type. (_font_cache_hash) (_font_cache_keys_equal) (_font_cache_create_entry) (_font_cache_destroy_entry) (_font_cache_destroy_cache): New font cache code. (_global_font_cache) (_lock_global_font_cache) (_unlock_global_font_cache) (_get_global_font_cache): New global font cache. (_cairo_font_text_to_glyphs) (_cairo_glyph_cache_hash) (_cairo_glyph_cache_keys_equal) (_image_glyph_cache_create_entry) (_image_glyph_cache_destroy_entry) (_image_glyph_cache_destroy_cache): New glyph cache code. (_global_image_glyph_cache) (_cairo_lock_global_image_glyph_cache) (_cairo_unlock_global_image_glyph_cache) (_cairo_get_global_image_glyph_cache): New global glyph cache. (_cairo_font_cache_backend): New structure. (_cairo_image_cache_backend): Likewise. (_cairo_font_create): Reimplement in terms of font cache. (_cairo_font_init): Remove matrix and glyph cache related code. (_cairo_font_copy): Likewise. (_cairo_font_show_glyphs): Delegate to surface when possible. (_cairo_font_glyph_extents) (_cairo_font_glyph_bbox) (_cairo_font_glyph_path) (_cairo_font_font_extents) (_cairo_font_show_glyphs): Rename to as cairo_unscaled_font_XXX, and add scale parameter.
New structure types. (_create_from_face) (_reference_font_val) (_destroy_font_val) (_create_from_library_and_pattern): New functions. (_ft_font_cache_hash) (_ft_font_cache_keys_equal) (_ft_font_cache_create_entry) (_ft_font_cache_destroy_entry) (_ft_font_cache_destroy_cache): New ft font cache code. (_global_ft_cache) (_lock_global_ft_cache) (_unlock_global_ft_cache) (_get_global_ft_cache): New global ft font cache. (_ft_font_cache_backend): New structure. (_cairo_ft_font_create): Rewrite to use cache. (_cairo_ft_font_destroy): Likewise. (_cairo_ft_font_copy): Remove. (_install_font_matrix): Rename as _install_font_scale. (_utf8_to_glyphs): Rename as _cairo_ft_font_text_to_glyphs. (_cairo_ft_font_text_to_glyphs): Use cache for metrics. (_cairo_ft_font_extents): Accept size, use scaled metrics. (_cairo_ft_font_glyph_extents) (_cairo_ft_font_glyph_bbox) (_cairo_ft_font_show_glyphs) (_cairo_ft_font_glyph_path): Modify to use size, cache. (_cairo_ft_font_text_extents) (_cairo_ft_font_text_bbox) (_cairo_ft_font_show_text) (_cairo_ft_font_text_path): Remove text-API code. (cairo_ft_font_create) (cairo_ft_font_create_for_ft_face) (cairo_ft_font_face) (cairo_ft_font_pattern): Rewrite using ft_font_val_t.
Just reference font. (_cairo_gstate_fini): Finalize font matrix. (_cairo_gstate_default_matrix): Initialize font matrix. (_cairo_gstate_clip): Re-enable clipping rectangle. (_cairo_gstate_select_font) (_cairo_gstate_set_font): Set font matrix to identity. (_cairo_gstate_scale_font): Scale font matrix, not font. (_cairo_gstate_transform_font): Transform font matrix, not font. (_cairo_gstate_set_font_transform): Install as font matrix, not in font. (_build_font_scale): New helper function. (_cairo_gstate_text_to_glyphs): New function. (_cairo_gstate_current_font_extents) (_cairo_gstate_glyph_extents) (_cairo_gstate_show_glyphs) (_cairo_gstate_glyph_path): Rewrite using font matrix and size. (_cairo_gstate_text_path (_cairo_gstate_text_extents) (_cairo_gstate_show_text): Remove text-API code.
Minor bug fix. (_cairo_xlib_surface_show_glyphs): New function. (_cairo_xlib_surface_backend): Add reference to new function. (glyphset_cache_t) (glyphset_cache_entry_t): New structure types. (_next_xlib_glyph): New helper function. (_xlib_glyphset_cache_create_value) (_xlib_glyphset_cache_destroy_cache) (_xlib_glyphset_cache_destroy_value) (_xlib_glyphset_cache_backend): New glyphset cache code. (_xlib_glyphset_caches) (_lock_xlib_glyphset_caches) (_unlock_xlib_glyphset_caches) (_get_glyphset_cache): New global glyphset cache.
Add NULL entry for show_glyphs.
Add NULL entry for show_glyphs.
Add NULL entry for show_glyphs.
Add NULL entry for show_glyphs.
Add NULL entry for show_glyphs.
New structure type. (cairo_cache_entry_base_t) (cairo_cache_arrangement_t) (cairo_cache_t): New structure types. (_cairo_cache_init) (_cairo_cache_reference) (_cairo_cache_destroy) (_cairo_cache_lookup) (_cairo_hash_string): New cache functions. (CAIRO_IMAGE_GLYPH_CACHE_MEMORY_DEFAULT) (CAIRO_XLIB_GLYPH_CACHE_MEMORY_DEFAULT) (CAIRO_FONT_CACHE_NUM_FONTS_DEFAULT) (CAIRO_FT_CACHE_NUM_FONTS_DEFAULT): New constants. (cairo_font_scale_t) (cairo_glyph_cache_key_t) (cairo_image_glyph_cache_entry_t): New structure types. (_cairo_lock_global_image_glyph_cache) (_cairo_unlock_global_image_glyph_cache) (_cairo_get_global_image_glyph_cache) (_cairo_glyph_cache_hash) (_cairo_glyph_cache_keys_equal): New functions for glyph caches. (cairo_font_backend_t): Remove text-API calls, add scale params, remove copy call. (cairo_surface_backend_t): Add show_glyphs entry. (cairo_glyph_surface_t) (cairo_glyph_surface_node_t): Remove old glyph cache structures. (cairo_unscaled_font_t): New structure type. (cairo_font): Remove glyph cache member, add pointer to unscaled. (cairo_gstate): Add font_matrix member, change to hold unscaled. (_cairo_gstate_set_font_transform) (_cairo_gstate_current_font_transform) (_cairo_gstate_text_to_glyphs): New functions. (_cairo_gstate_text_path (_cairo_gstate_text_extents) (_cairo_gstate_show_text) (_cairo_font_text_extents) (_cairo_font_text_bbox) (_cairo_font_show_text) (_cairo_font_text_path): Remove text-API code. (_cairo_font_glyph_extents) (_cairo_font_glyph_bbox) (_cairo_font_glyph_path) (_cairo_font_font_extents) (_cairo_font_show_glyphs): Add scale parameter.

1 files changed, 454 insertions, 0 deletions

diff --git a/src/cairo-cache.c b/src/cairo-cache.c
new file mode 100644
index 000000000..c5ce39935
--- /dev/null
+++ b/src/cairo-cache.c
@@ -0,0 +1,454 @@
+/* cairo - a vector graphics library with display and print output
+ *
+ * This file is Copyright © 2004 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
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * The Original Code is the cairo graphics library.
+ *
+ * The Initial Developer of the Original Code is Red Hat, Inc.
+ *
+ * Contributor(s):
+ *      Keith Packard
+ *	Graydon Hoare <graydon@redhat.com>
+ */
+
+#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.
+ */
+
+static 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 }
+};
+
+#define N_CACHE_SIZES (sizeof(cache_arrangements)/sizeof(cache_arrangements[0]))
+
+/*
+ * 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. 
+ * There is currently no explicit entry-removing call, though one can be 
+ * added easily.
+ *
+ * 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.
+ * 
+ */
+
+#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 CAIRO_DO_SANITY_CHECKING
+#include <assert.h>
+static void 
+_cache_sane_state (cairo_cache_t *cache)
+{
+    assert (cache != NULL);
+    assert (cache->entries != NULL);
+    assert (cache->backend != NULL);
+    assert (cache->arrangement != NULL);
+    assert (cache->refcount > 0);
+    assert (cache->used_memory <= cache->max_memory);
+    assert (cache->live_entries <= cache->arrangement->size);   
+}
+#else
+#define _cache_sane_state(c) 
+#define assert(x) 
+#endif
+
+static void
+_entry_destroy (cairo_cache_t *cache, unsigned long i)
+{
+    _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;
+    }
+}
+
+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 
+		&& *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;
+}
+
+static cairo_cache_entry_base_t **
+_find_available_entry_for (cairo_cache_t *cache,
+			   void *key)
+{
+    return _cache_lookup (cache, key, NULL);
+}
+
+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);
+}
+
+
+static cairo_cache_arrangement_t *
+_find_cache_arrangement (unsigned long proposed_size)
+{
+    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;
+}
+
+static cairo_status_t
+_resize_cache (cairo_cache_t *cache, unsigned long proposed_size)
+{
+    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;
+}
+
+
+#ifdef CAIRO_MEASURE_CACHE_PERFORMANCE
+static double
+_load_factor (cairo_cache_t *cache)
+{
+    return ((double) cache->live_entries) 
+	/ ((double) cache->arrangement->size);
+}
+#endif
+
+static unsigned long
+_random_live_entry (cairo_cache_t *cache)
+{
+    unsigned long idx;
+    assert(cache != NULL);
+    do {
+	idx = rand () % cache->arrangement->size;
+    } while (! LIVE_ENTRY_P(cache, idx));
+    return idx;
+}
+
+
+/* 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->refcount = 1;
+	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 (sizeof(cairo_cache_entry_base_t *),
+				 cache->arrangement->size);
+	if (cache->entries == NULL)
+	    return CAIRO_STATUS_NO_MEMORY;
+    }    
+    _cache_sane_state (cache);
+    return CAIRO_STATUS_SUCCESS;
+}
+
+void
+_cairo_cache_reference (cairo_cache_t *cache)
+{
+    _cache_sane_state (cache);
+    cache->refcount++;
+}
+
+void
+_cairo_cache_destroy (cairo_cache_t *cache)
+{
+    unsigned long i;
+    if (cache != NULL) {
+	
+	_cache_sane_state (cache);
+
+	if (cache->refcount-- > 0)
+	    return;
+	
+	for (i = 0; i < cache->arrangement->size; ++i) {
+	    _entry_destroy (cache, i);
+	}
+	
+	free (cache->entries);
+	cache->entries = NULL;
+	cache->backend->destroy_cache (cache);
+    }
+}
+
+cairo_status_t
+_cairo_cache_lookup (cairo_cache_t *cache,
+		     void *key,
+		     void **entry_return)
+{
+
+    unsigned long idx;
+    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;
+	return status;
+    }
+
+#ifdef CAIRO_MEASURE_CACHE_PERFORMANCE
+    cache->misses++;
+#endif
+
+    /* Build the new entry. */
+    status = cache->backend->create_entry (cache, key, 
+					   entry_return);
+    if (status != CAIRO_STATUS_SUCCESS)
+	return status;
+
+    new_entry = (cairo_cache_entry_base_t *) (*entry_return);
+
+    /* Store the hash value in case the backend forgot. */
+    new_entry->hashcode = cache->backend->hash (cache, key);
+
+    /* Make some entries die if we're under memory pressure. */
+    while (cache->live_entries > 0 &&
+	   ((cache->max_memory - cache->used_memory) < new_entry->memory)) {
+	idx = _random_live_entry (cache);
+	assert (idx < cache->arrangement->size);
+	_entry_destroy (cache, idx);
+    }
+    
+    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);
+	*entry_return = NULL;
+	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);
+
+    return status;
+}
+
+unsigned long
+_cairo_hash_string (const char *c)
+{
+    /* This is the djb2 hash. */
+    unsigned long hash = 5381;
+    while (*c)
+	hash = ((hash << 5) + hash) + *c++;
+    return hash;
+}
+