[cairo] [patch] caching, glyph, font, and glyphset patch

[graydon hoare]

hi,

this is a big patch. it probably ought to be several smaller patches,
and if absolutely necessary I'll break it up, but I'd like to at least
get some high level commentary before proceeding. I'd really prefer
not to break it up because many of the changes involve "reorganization
in 4 files at once", and are related, and it'll take many days to
unwind the dependencies to make sure it can build after each partial
patch (plus none of the partial-patch states are at all interesting; it
really only works well in concert). the patch is 122k, so I'll just
put a link here:

   http://people.redhat.com/graydon/cairo-caches-sept-28-2004.patch

anyways, the patch does several things:

   - introduces a new generic cache type: a random replacement,
     open-addressed hashtable with a memory cap and a pluggable
     backend.

   - adds caching to the font construction system.

   - adds caching to the freetype loading system.

   - replaces the duplicate text and glyph APIs with a single
     glyph API and a font call to convert text to a glyph string.

   - moves the font matrix and DPI into a specific "font device size"
     type, calculated from the gstate, making fonts "sizeless" objects
     which can be referenced in a gstate push rather than duplicated.

   - removes the old per-font glyph caches.

   - adds a new global glyph cache which holds glyph images and
     metrics, keyed to font and device size.

   - adds a per-surface backend glyph rendering call, with a
     fallback to using images from the global image cache.

   - adds an implementation of this backend call to xlib, using
     X RENDER glyphsets.

   - re-enables rectangular clipping (this requires the change I
     posted for pixman first).

most of this work is internal plumbing; the only changes to the
user-visible API are that you can't scale or transform fonts directly
anymore, you have to "set" them into a cairo_t and then
scale/transform the "current font" (you're actually just adjusting the
gstate now, since fonts are sizeless).

the net results are quite positive:

   - glyph rendering speed on xlib improves by about 300x, and now
     appears to be ballpark-competitive with Xft.

   - font rendering is now DPI-sensitive (and thus some test output in
     snippets changes size, because freetype used to be running at
     default 72 DPI, and now it runs at cairo's default 96 DPI).

   - a lot of horribly incorrect metrics calculations are gone; the
     screen output of eg. java2d tests generally looks much better.

   - saving and restoring gstate, changing size of font without
     rendering, duplicate "select_font" calls, etc. are all essentially
     free in terms of font resources.

   - cache memory use is more easily controlled due to centralization
     of memory accounting (including X server-side glyphset accounting).

comments would be appreciated. this involved quite a lot of fidgeting
with the design to "get right" and there are probably still some ugly
artifacts of all the reorganization to clean up. changelog follows.

-graydon


2004-09-28  Graydon Hoare  <graydon at redhat.com>

	* src/Makefile.am (libcairo_la_SOURCES): Add cairo_cache.c

	* src/cairo.c (cairo_set_font_transform): New function.
	(cairo_current_font_transform): New function.
	(cairo_text_extents)
	(cairo_show_text)
	(cairo_text_path): Rewrite using temporary glyph arrays

	* src/cairo.h (cairo_set_font_transform): Declare.
	(cairo_current_font_transform): Likewise.
	(cairo_font_set_transform): Remove declaration.
	(cairo_font_current_transform): Likewise.

	* src/cairo_cache.c: New file.

	* src/cairo_font.c (_cairo_glyph_cache_create)
	(_cairo_glyph_cache_destroy)
	(_cairo_glyph_cache_reference)
	(_cairo_glyph_cache_pop_last)
	(_cairo_glyph_surface_init): Remove glyph cache code.
	(_cairo_font_lookup_glyph)
	(_cairo_font_scale)
	(_cairo_font_transform)
	(_cairo_font_set_transform)
	(_cairo_font_current_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_primary_hash)
	(_font_cache_secondary_hash)
	(_font_cache_copy_key)
	(_font_cache_keys_equal)
	(_font_cache_create_value)
	(_font_cache_destroy_key)
	(_font_cache_destroy_value)
	(_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_primary_hash)
	(_cairo_glyph_cache_secondary_hash)
	(_cairo_glyph_cache_copy_key)
	(_cairo_glyph_cache_keys_equal)
	(_cairo_glyph_cache_destroy_key)
	(_image_glyph_cache_create_value)
	(_image_glyph_cache_destroy_value)		
	(_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_glyph_extents)
	(_cairo_font_glyph_bbox)
	(_cairo_font_glyph_path)
	(_cairo_font_font_extents)
	(_cairo_font_show_glyphs): Add size parameter.
	(_cairo_font_show_glyphs): Delegate to surface when possible.

	* src/cairo_ft_font.c
	(ft_cache_t)
	(ft_font_val_t): New structure types.
	(_create_from_face)
	(_reference_font_val)
	(_destroy_font_val)
	(_create_from_library_and_pattern): New functions.
	(_ft_font_cache_primary_hash)
	(_ft_font_cache_secondary_hash)
	(_ft_font_cache_copy_key)
	(_ft_font_cache_keys_equal)
	(_ft_font_cache_create_value)
	(_ft_font_cache_destroy_key)
	(_ft_font_cache_destroy_value)	
	(_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_device_size.
	(_install_font_device_size): Install DPI as well.
	(_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.

	* src/cairo_gstate.c (cairo_gstate_init_copy): 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_device_size): 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.

	* src/cairo_xlib_surface.c
	(_cairo_xlib_surface_set_clip_region): Minor bug fix.
	(_cairo_xlib_surface_show_glyphs): New function.
	(_cairo_xlib_surface_backend): Add reference to new function.
	(glyphset_cache_t)
	(glyphset_cache_value_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.

	* src/cairo_glitz_surface.c (cairo_glitz_surface_backend):
	Add NULL entry for show_glyphs.

	* src/cairo_image_surface.c (cairo_image_surface_backend):
	Add NULL entry for show_glyphs.

	* src/cairo_ps_surface.c (cairo_ps_surface_backend):
	Add NULL entry for show_glyphs.

	* src/cairo_png_surface.c (cairo_png_surface_backend):
	Add NULL entry for show_glyphs.

	* src/cairo_xcb_surface.c (cairo_xcb_surface_backend):
	Add NULL entry for show_glyphs.

	* src/cairoint.h (cairo_cache_backend_t): New structure type.
	(struct cairo_cache_statistics)
	(struct cairo_cache_buckets): Declare but do not define.
	(cairo_cache_t): New structure type.
	(_cairo_cache_init)
	(_cairo_cache_reference)
	(_cairo_cache_destroy)
	(_cairo_cache_get_value)
	(_cairo_hash_string_primary)
	(_cairo_hash_string_secondary): New cache functions.
	(CAIRO_CACHE_BUCKET_EXPONENT_DEFAULT)
	(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_device_size_t)
	(cairo_glyph_cache_key_t)
	(cairo_image_glyph_cache_value_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_primary_hash)
	(_cairo_glyph_cache_secondary_hash)
	(_cairo_glyph_cache_copy_key)
	(_cairo_glyph_cache_keys_equal)
	(_cairo_glyph_cache_destroy_key): New functions for glyph caches.
	(cairo_font_backend_t): Remove text-API calls, add size 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_font): Remove matrix, glyph cache members.
	(cairo_gstate): Add font_matrix member.	
	(_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 size parameter.