Subversion Repositories Kolibri OS

/* -*- Mode: c; c-basic-offset: 4; indent-tabs-mode: t; tab-width: 8; -*- */

/*

 * Copyright © 2005 Keith Packard

 *

 * 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., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, 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 Keith Packard

 *

 * Contributor(s):

 *      Keith Packard 

 *	Carl D. Worth 

 *      Graydon Hoare 

 *      Owen Taylor 

 *      Behdad Esfahbod 

 *      Chris Wilson 

 */

#include "cairoint.h"

#include "cairo-error-private.h"

#include "cairo-image-surface-private.h"

#include "cairo-list-inline.h"

#include "cairo-pattern-private.h"

#include "cairo-scaled-font-private.h"

#include "cairo-surface-backend-private.h"

#if _XOPEN_SOURCE >= 600 || defined (_ISOC99_SOURCE)

#define ISFINITE(x) isfinite (x)

#else

#define ISFINITE(x) ((x) * (x) >= 0.) /* check for NaNs */

#endif

/**

 * SECTION:cairo-scaled-font

 * @Title: cairo_scaled_font_t

 * @Short_Description: Font face at particular size and options

 * @See_Also: #cairo_font_face_t, #cairo_matrix_t, #cairo_font_options_t

 *

 * #cairo_scaled_font_t represents a realization of a font face at a particular

 * size and transformation and a certain set of font options.

 **/

static uint32_t

_cairo_scaled_font_compute_hash (cairo_scaled_font_t *scaled_font);

/* Global Glyph Cache

 *

 * We maintain a global pool of glyphs split between all active fonts. This

 * allows a heavily used individual font to cache more glyphs than we could

 * manage if we used per-font glyph caches, but at the same time maintains

 * fairness across all fonts and provides a cap on the maximum number of

 * global glyphs.

 *

 * The glyphs are allocated in pages, which are capped in the global pool.

 * Using pages means we can reduce the frequency at which we have to probe the

 * global pool and ameliorates the memory allocation pressure.

 */

/* XXX: This number is arbitrary---we've never done any measurement of this. */

#define MAX_GLYPH_PAGES_CACHED 512

static cairo_cache_t cairo_scaled_glyph_page_cache;

#define CAIRO_SCALED_GLYPH_PAGE_SIZE 32

struct _cairo_scaled_glyph_page {

    cairo_cache_entry_t cache_entry;

    cairo_list_t link;

    unsigned int num_glyphs;

    cairo_scaled_glyph_t glyphs[CAIRO_SCALED_GLYPH_PAGE_SIZE];

};

/*

 *  Notes:

 *

 *  To store rasterizations of glyphs, we use an image surface and the

 *  device offset to represent the glyph origin.

 *

 *  A device_transform converts from device space (a conceptual space) to

 *  surface space.  For simple cases of translation only, it's called a

 *  device_offset and is public API (cairo_surface_[gs]et_device_offset()).

 *  A possibly better name for those functions could have been

 *  cairo_surface_[gs]et_origin().  So, that's what they do: they set where

 *  the device-space origin (0,0) is in the surface.  If the origin is inside

 *  the surface, device_offset values are positive.  It may look like this:

 *

 *  Device space:

 *        (-x,-y) <-- negative numbers

 *           +----------------+

 *           |      .         |

 *           |      .         |

 *           |......(0,0) <---|-- device-space origin

 *           |                |

 *           |                |

 *           +----------------+

 *                    (width-x,height-y)

 *

 *  Surface space:

 *         (0,0) <-- surface-space origin

 *           +---------------+

 *           |      .        |

 *           |      .        |

 *           |......(x,y) <--|-- device_offset

 *           |               |

 *           |               |

 *           +---------------+

 *                     (width,height)

 *

 *  In other words: device_offset is the coordinates of the device-space

 *  origin relative to the top-left of the surface.

 *

 *  We use device offsets in a couple of places:

 *

 *    - Public API: To let toolkits like Gtk+ give user a surface that

 *      only represents part of the final destination (say, the expose

 *      area), but has the same device space as the destination.  In these

 *      cases device_offset is typically negative.  Example:

 *

 *           application window

 *           +---------------+

 *           |      .        |

 *           | (x,y).        |

 *           |......+---+    |

 *           |      |   | <--|-- expose area

 *           |      +---+    |

 *           +---------------+

 *

 *      In this case, the user of cairo API can set the device_space on

 *      the expose area to (-x,-y) to move the device space origin to that

 *      of the application window, such that drawing in the expose area

 *      surface and painting it in the application window has the same

 *      effect as drawing in the application window directly.  Gtk+ has

 *      been using this feature.

 *

 *    - Glyph surfaces: In most font rendering systems, glyph surfaces

 *      have an origin at (0,0) and a bounding box that is typically

 *      represented as (x_bearing,y_bearing,width,height).  Depending on

 *      which way y progresses in the system, y_bearing may typically be

 *      negative (for systems similar to cairo, with origin at top left),

 *      or be positive (in systems like PDF with origin at bottom left).

 *      No matter which is the case, it is important to note that

 *      (x_bearing,y_bearing) is the coordinates of top-left of the glyph

 *      relative to the glyph origin.  That is, for example:

 *

 *      Scaled-glyph space:

 *

 *        (x_bearing,y_bearing) <-- negative numbers

 *           +----------------+

 *           |      .         |

 *           |      .         |

 *           |......(0,0) <---|-- glyph origin

 *           |                |

 *           |                |

 *           +----------------+

 *                    (width+x_bearing,height+y_bearing)

 *

 *      Note the similarity of the origin to the device space.  That is

 *      exactly how we use the device_offset to represent scaled glyphs:

 *      to use the device-space origin as the glyph origin.

 *

 *  Now compare the scaled-glyph space to device-space and surface-space

 *  and convince yourself that:

 *

 *	(x_bearing,y_bearing) = (-x,-y) = - device_offset

 *

 *  That's right.  If you are not convinced yet, contrast the definition

 *  of the two:

 *

 *	"(x_bearing,y_bearing) is the coordinates of top-left of the

 *	 glyph relative to the glyph origin."

 *

 *	"In other words: device_offset is the coordinates of the

 *	 device-space origin relative to the top-left of the surface."

 *

 *  and note that glyph origin = device-space origin.

 */

static void

_cairo_scaled_font_fini_internal (cairo_scaled_font_t *scaled_font);

static void

_cairo_scaled_glyph_fini (cairo_scaled_font_t *scaled_font,

			  cairo_scaled_glyph_t *scaled_glyph)

{

    while (! cairo_list_is_empty (&scaled_glyph->dev_privates)) {

	cairo_scaled_glyph_private_t *private =

	    cairo_list_first_entry (&scaled_glyph->dev_privates,

				    cairo_scaled_glyph_private_t,

				    link);

	private->destroy (private, scaled_glyph, scaled_font);

    }

    _cairo_image_scaled_glyph_fini (scaled_font, scaled_glyph);

    if (scaled_glyph->surface != NULL)

	cairo_surface_destroy (&scaled_glyph->surface->base);

    if (scaled_glyph->path != NULL)

	_cairo_path_fixed_destroy (scaled_glyph->path);

    if (scaled_glyph->recording_surface != NULL) {

	cairo_surface_finish (scaled_glyph->recording_surface);

	cairo_surface_destroy (scaled_glyph->recording_surface);

    }

}

#define ZOMBIE 0

static const cairo_scaled_font_t _cairo_scaled_font_nil = {

    { ZOMBIE },			/* hash_entry */

    CAIRO_STATUS_NO_MEMORY,	/* status */

    CAIRO_REFERENCE_COUNT_INVALID,	/* ref_count */

    { 0, 0, 0, NULL },		/* user_data */

    NULL,			/* original_font_face */

    NULL,			/* font_face */

    { 1., 0., 0., 1., 0, 0},	/* font_matrix */

    { 1., 0., 0., 1., 0, 0},	/* ctm */

    { CAIRO_ANTIALIAS_DEFAULT,	/* options */

      CAIRO_SUBPIXEL_ORDER_DEFAULT,

      CAIRO_HINT_STYLE_DEFAULT,

      CAIRO_HINT_METRICS_DEFAULT} ,

    FALSE,			/* placeholder */

    FALSE,			/* holdover */

    TRUE,			/* finished */

    { 1., 0., 0., 1., 0, 0},	/* scale */

    { 1., 0., 0., 1., 0, 0},	/* scale_inverse */

    1.,				/* max_scale */

    { 0., 0., 0., 0., 0. },	/* extents */

    { 0., 0., 0., 0., 0. },	/* fs_extents */

    CAIRO_MUTEX_NIL_INITIALIZER,/* mutex */

    NULL,			/* glyphs */

    { NULL, NULL },		/* pages */

    FALSE,			/* cache_frozen */

    FALSE,			/* global_cache_frozen */

    { NULL, NULL },		/* privates */

    NULL			/* backend */

};

/**

 * _cairo_scaled_font_set_error:

 * @scaled_font: a scaled_font

 * @status: a status value indicating an error

 *

 * Atomically sets scaled_font->status to @status and calls _cairo_error;

 * Does nothing if status is %CAIRO_STATUS_SUCCESS.

 *

 * All assignments of an error status to scaled_font->status should happen

 * through _cairo_scaled_font_set_error(). Note that due to the nature of

 * the atomic operation, it is not safe to call this function on the nil

 * objects.

 *

 * The purpose of this function is to allow the user to set a

 * breakpoint in _cairo_error() to generate a stack trace for when the

 * user causes cairo to detect an error.

 *

 * Return value: the error status.

 **/

cairo_status_t

_cairo_scaled_font_set_error (cairo_scaled_font_t *scaled_font,

			      cairo_status_t status)

{

    if (status == CAIRO_STATUS_SUCCESS)

	return status;

    /* Don't overwrite an existing error. This preserves the first

     * error, which is the most significant. */

    _cairo_status_set_error (&scaled_font->status, status);

    return _cairo_error (status);

}

/**

 * cairo_scaled_font_get_type:

 * @scaled_font: a #cairo_scaled_font_t

 *

 * This function returns the type of the backend used to create

 * a scaled font. See #cairo_font_type_t for available types.

 * However, this function never returns %CAIRO_FONT_TYPE_TOY.

 *

 * Return value: The type of @scaled_font.

 *

 * Since: 1.2

 **/

cairo_font_type_t

cairo_scaled_font_get_type (cairo_scaled_font_t *scaled_font)

{

    if (CAIRO_REFERENCE_COUNT_IS_INVALID (&scaled_font->ref_count))

	return CAIRO_FONT_TYPE_TOY;

    return scaled_font->backend->type;

}

/**

 * cairo_scaled_font_status:

 * @scaled_font: a #cairo_scaled_font_t

 *

 * Checks whether an error has previously occurred for this

 * scaled_font.

 *

 * Return value: %CAIRO_STATUS_SUCCESS or another error such as

 *   %CAIRO_STATUS_NO_MEMORY.

 *

 * Since: 1.0

 **/

cairo_status_t

cairo_scaled_font_status (cairo_scaled_font_t *scaled_font)

{

    return scaled_font->status;

}

slim_hidden_def (cairo_scaled_font_status);

/* Here we keep a unique mapping from

 * font_face/matrix/ctm/font_options => #cairo_scaled_font_t.

 *

 * Here are the things that we want to map:

 *

 *  a) All otherwise referenced #cairo_scaled_font_t's

 *  b) Some number of not otherwise referenced #cairo_scaled_font_t's

 *

 * The implementation uses a hash table which covers (a)

 * completely. Then, for (b) we have an array of otherwise

 * unreferenced fonts (holdovers) which are expired in

 * least-recently-used order.

 *

 * The cairo_scaled_font_create() code gets to treat this like a regular

 * hash table. All of the magic for the little holdover cache is in

 * cairo_scaled_font_reference() and cairo_scaled_font_destroy().

 */

/* This defines the size of the holdover array ... that is, the number

 * of scaled fonts we keep around even when not otherwise referenced

 */

#define CAIRO_SCALED_FONT_MAX_HOLDOVERS 256

typedef struct _cairo_scaled_font_map {

    cairo_scaled_font_t *mru_scaled_font;

    cairo_hash_table_t *hash_table;

    cairo_scaled_font_t *holdovers[CAIRO_SCALED_FONT_MAX_HOLDOVERS];

    int num_holdovers;

} cairo_scaled_font_map_t;

static cairo_scaled_font_map_t *cairo_scaled_font_map;

static int

_cairo_scaled_font_keys_equal (const void *abstract_key_a, const void *abstract_key_b);

static cairo_scaled_font_map_t *

_cairo_scaled_font_map_lock (void)

{

    CAIRO_MUTEX_LOCK (_cairo_scaled_font_map_mutex);

    if (cairo_scaled_font_map == NULL) {

	cairo_scaled_font_map = malloc (sizeof (cairo_scaled_font_map_t));

	if (unlikely (cairo_scaled_font_map == NULL))

	    goto CLEANUP_MUTEX_LOCK;

	cairo_scaled_font_map->mru_scaled_font = NULL;

	cairo_scaled_font_map->hash_table =

	    _cairo_hash_table_create (_cairo_scaled_font_keys_equal);

	if (unlikely (cairo_scaled_font_map->hash_table == NULL))

	    goto CLEANUP_SCALED_FONT_MAP;

	cairo_scaled_font_map->num_holdovers = 0;

    }

    return cairo_scaled_font_map;

 CLEANUP_SCALED_FONT_MAP:

    free (cairo_scaled_font_map);

    cairo_scaled_font_map = NULL;

 CLEANUP_MUTEX_LOCK:

    CAIRO_MUTEX_UNLOCK (_cairo_scaled_font_map_mutex);

    _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);

    return NULL;

}

static void

_cairo_scaled_font_map_unlock (void)

{

   CAIRO_MUTEX_UNLOCK (_cairo_scaled_font_map_mutex);

}

void

_cairo_scaled_font_map_destroy (void)

{

    cairo_scaled_font_map_t *font_map;

    cairo_scaled_font_t *scaled_font;

    CAIRO_MUTEX_LOCK (_cairo_scaled_font_map_mutex);

    font_map = cairo_scaled_font_map;

    if (unlikely (font_map == NULL)) {

        goto CLEANUP_MUTEX_LOCK;

    }

    scaled_font = font_map->mru_scaled_font;

    if (scaled_font != NULL) {

	CAIRO_MUTEX_UNLOCK (_cairo_scaled_font_map_mutex);

	cairo_scaled_font_destroy (scaled_font);

	CAIRO_MUTEX_LOCK (_cairo_scaled_font_map_mutex);

    }

    /* remove scaled_fonts starting from the end so that font_map->holdovers

     * is always in a consistent state when we release the mutex. */

    while (font_map->num_holdovers) {

	scaled_font = font_map->holdovers[font_map->num_holdovers-1];

	assert (! CAIRO_REFERENCE_COUNT_HAS_REFERENCE (&scaled_font->ref_count));

	_cairo_hash_table_remove (font_map->hash_table,

				  &scaled_font->hash_entry);

	font_map->num_holdovers--;

	/* This releases the font_map lock to avoid the possibility of a

	 * recursive deadlock when the scaled font destroy closure gets

	 * called

	 */

	_cairo_scaled_font_fini (scaled_font);

	free (scaled_font);

    }

    _cairo_hash_table_destroy (font_map->hash_table);

    free (cairo_scaled_font_map);

    cairo_scaled_font_map = NULL;

 CLEANUP_MUTEX_LOCK:

    CAIRO_MUTEX_UNLOCK (_cairo_scaled_font_map_mutex);

}

static void

_cairo_scaled_glyph_page_destroy (cairo_scaled_font_t *scaled_font,

				  cairo_scaled_glyph_page_t *page)

{

    unsigned int n;

    assert (!scaled_font->cache_frozen);

    assert (!scaled_font->global_cache_frozen);

    for (n = 0; n < page->num_glyphs; n++) {

	_cairo_hash_table_remove (scaled_font->glyphs,

				  &page->glyphs[n].hash_entry);

	_cairo_scaled_glyph_fini (scaled_font, &page->glyphs[n]);

    }

    cairo_list_del (&page->link);

    free (page);

}

static void

_cairo_scaled_glyph_page_pluck (void *closure)

{

    cairo_scaled_glyph_page_t *page = closure;

    cairo_scaled_font_t *scaled_font;

    assert (! cairo_list_is_empty (&page->link));

    scaled_font = (cairo_scaled_font_t *) page->cache_entry.hash;

    CAIRO_MUTEX_LOCK (scaled_font->mutex);

    _cairo_scaled_glyph_page_destroy (scaled_font, page);

    CAIRO_MUTEX_UNLOCK (scaled_font->mutex);

}

/* If a scaled font wants to unlock the font map while still being

 * created (needed for user-fonts), we need to take extra care not

 * ending up with multiple identical scaled fonts being created.

 *

 * What we do is, we create a fake identical scaled font, and mark

 * it as placeholder, lock its mutex, and insert that in the fontmap

 * hash table.  This makes other code trying to create an identical

 * scaled font to just wait and retry.

 *

 * The reason we have to create a fake scaled font instead of just using

 * scaled_font is for lifecycle management: we need to (or rather,

 * other code needs to) reference the scaled_font in the hash table.

 * We can't do that on the input scaled_font as it may be freed by

 * font backend upon error.

 */

cairo_status_t

_cairo_scaled_font_register_placeholder_and_unlock_font_map (cairo_scaled_font_t *scaled_font)

{

    cairo_status_t status;

    cairo_scaled_font_t *placeholder_scaled_font;

    assert (CAIRO_MUTEX_IS_LOCKED (_cairo_scaled_font_map_mutex));

    status = scaled_font->status;

    if (unlikely (status))

	return status;

    placeholder_scaled_font = malloc (sizeof (cairo_scaled_font_t));

    if (unlikely (placeholder_scaled_font == NULL))

	return _cairo_error (CAIRO_STATUS_NO_MEMORY);

    /* full initialization is wasteful, but who cares... */

    status = _cairo_scaled_font_init (placeholder_scaled_font,

				      scaled_font->font_face,

				      &scaled_font->font_matrix,

				      &scaled_font->ctm,

				      &scaled_font->options,

				      NULL);

    if (unlikely (status))

	goto FREE_PLACEHOLDER;

    placeholder_scaled_font->placeholder = TRUE;

    placeholder_scaled_font->hash_entry.hash

	= _cairo_scaled_font_compute_hash (placeholder_scaled_font);

    status = _cairo_hash_table_insert (cairo_scaled_font_map->hash_table,

				       &placeholder_scaled_font->hash_entry);

    if (unlikely (status))

	goto FINI_PLACEHOLDER;

    CAIRO_MUTEX_UNLOCK (_cairo_scaled_font_map_mutex);

    CAIRO_MUTEX_LOCK (placeholder_scaled_font->mutex);

    return CAIRO_STATUS_SUCCESS;

  FINI_PLACEHOLDER:

    _cairo_scaled_font_fini_internal (placeholder_scaled_font);

  FREE_PLACEHOLDER:

    free (placeholder_scaled_font);

    return _cairo_scaled_font_set_error (scaled_font, status);

}

void

_cairo_scaled_font_unregister_placeholder_and_lock_font_map (cairo_scaled_font_t *scaled_font)

{

    cairo_scaled_font_t *placeholder_scaled_font;

    CAIRO_MUTEX_LOCK (_cairo_scaled_font_map_mutex);

    /* temporary hash value to match the placeholder */

    scaled_font->hash_entry.hash

	= _cairo_scaled_font_compute_hash (scaled_font);

    placeholder_scaled_font =

	_cairo_hash_table_lookup (cairo_scaled_font_map->hash_table,

				  &scaled_font->hash_entry);

    assert (placeholder_scaled_font != NULL);

    assert (placeholder_scaled_font->placeholder);

    assert (CAIRO_MUTEX_IS_LOCKED (placeholder_scaled_font->mutex));

    _cairo_hash_table_remove (cairo_scaled_font_map->hash_table,

			      &placeholder_scaled_font->hash_entry);

    CAIRO_MUTEX_UNLOCK (_cairo_scaled_font_map_mutex);

    CAIRO_MUTEX_UNLOCK (placeholder_scaled_font->mutex);

    cairo_scaled_font_destroy (placeholder_scaled_font);

    CAIRO_MUTEX_LOCK (_cairo_scaled_font_map_mutex);

}

static void

_cairo_scaled_font_placeholder_wait_for_creation_to_finish (cairo_scaled_font_t *placeholder_scaled_font)

{

    /* reference the place holder so it doesn't go away */

    cairo_scaled_font_reference (placeholder_scaled_font);

    /* now unlock the fontmap mutex so creation has a chance to finish */

    CAIRO_MUTEX_UNLOCK (_cairo_scaled_font_map_mutex);

    /* wait on placeholder mutex until we are awaken */

    CAIRO_MUTEX_LOCK (placeholder_scaled_font->mutex);

    /* ok, creation done.  just clean up and back out */

    CAIRO_MUTEX_UNLOCK (placeholder_scaled_font->mutex);

    cairo_scaled_font_destroy (placeholder_scaled_font);

    CAIRO_MUTEX_LOCK (_cairo_scaled_font_map_mutex);

}

/* Fowler / Noll / Vo (FNV) Hash (http://www.isthe.com/chongo/tech/comp/fnv/)

 *

 * Not necessarily better than a lot of other hashes, but should be OK, and

 * well tested with binary data.

 */

#define FNV_32_PRIME ((uint32_t)0x01000193)

#define FNV1_32_INIT ((uint32_t)0x811c9dc5)

static uint32_t

_hash_matrix_fnv (const cairo_matrix_t	*matrix,

		  uint32_t		 hval)

{

    const uint8_t *buffer = (const uint8_t *) matrix;

    int len = sizeof (cairo_matrix_t);

    do {

	hval *= FNV_32_PRIME;

	hval ^= *buffer++;

    } while (--len);

    return hval;

}

static uint32_t

_hash_mix_bits (uint32_t hash)

{

    hash += hash << 12;

    hash ^= hash >> 7;

    hash += hash << 3;

    hash ^= hash >> 17;

    hash += hash << 5;

    return hash;

}

static uint32_t

_cairo_scaled_font_compute_hash (cairo_scaled_font_t *scaled_font)

{

    uint32_t hash = FNV1_32_INIT;

    /* We do a bytewise hash on the font matrices */

    hash = _hash_matrix_fnv (&scaled_font->font_matrix, hash);

    hash = _hash_matrix_fnv (&scaled_font->ctm, hash);

    hash = _hash_mix_bits (hash);

    hash ^= (unsigned long) scaled_font->original_font_face;

    hash ^= cairo_font_options_hash (&scaled_font->options);

    /* final mixing of bits */

    hash = _hash_mix_bits (hash);

    assert (hash != ZOMBIE);

    return hash;

}

static void

_cairo_scaled_font_init_key (cairo_scaled_font_t        *scaled_font,

			     cairo_font_face_t	        *font_face,

			     const cairo_matrix_t       *font_matrix,

			     const cairo_matrix_t       *ctm,

			     const cairo_font_options_t *options)

{

    scaled_font->status = CAIRO_STATUS_SUCCESS;

    scaled_font->placeholder = FALSE;

    scaled_font->font_face = font_face;

    scaled_font->original_font_face = font_face;

    scaled_font->font_matrix = *font_matrix;

    scaled_font->ctm = *ctm;

    /* ignore translation values in the ctm */

    scaled_font->ctm.x0 = 0.;

    scaled_font->ctm.y0 = 0.;

    _cairo_font_options_init_copy (&scaled_font->options, options);

    scaled_font->hash_entry.hash =

	_cairo_scaled_font_compute_hash (scaled_font);

}

static cairo_bool_t

_cairo_scaled_font_keys_equal (const void *abstract_key_a,

			       const void *abstract_key_b)

{

    const cairo_scaled_font_t *key_a = abstract_key_a;

    const cairo_scaled_font_t *key_b = abstract_key_b;

    return key_a->original_font_face == key_b->original_font_face &&

	    memcmp ((unsigned char *)(&key_a->font_matrix.xx),

		    (unsigned char *)(&key_b->font_matrix.xx),

		    sizeof(cairo_matrix_t)) == 0 &&

	    memcmp ((unsigned char *)(&key_a->ctm.xx),

		    (unsigned char *)(&key_b->ctm.xx),

		    sizeof(cairo_matrix_t)) == 0 &&

	    cairo_font_options_equal (&key_a->options, &key_b->options);

}

static cairo_bool_t

_cairo_scaled_font_matches (const cairo_scaled_font_t *scaled_font,

	                    const cairo_font_face_t *font_face,

			    const cairo_matrix_t *font_matrix,

			    const cairo_matrix_t *ctm,

			    const cairo_font_options_t *options)

{

    return scaled_font->original_font_face == font_face &&

	    memcmp ((unsigned char *)(&scaled_font->font_matrix.xx),

		    (unsigned char *)(&font_matrix->xx),

		    sizeof(cairo_matrix_t)) == 0 &&

	    memcmp ((unsigned char *)(&scaled_font->ctm.xx),

		    (unsigned char *)(&ctm->xx),

		    sizeof(cairo_matrix_t)) == 0 &&

	    cairo_font_options_equal (&scaled_font->options, options);

}

/*

 * Basic #cairo_scaled_font_t object management

 */

cairo_status_t

_cairo_scaled_font_init (cairo_scaled_font_t               *scaled_font,

			 cairo_font_face_t		   *font_face,

			 const cairo_matrix_t              *font_matrix,

			 const cairo_matrix_t              *ctm,

			 const cairo_font_options_t	   *options,

			 const cairo_scaled_font_backend_t *backend)

{

    cairo_status_t status;

    status = cairo_font_options_status ((cairo_font_options_t *) options);

    if (unlikely (status))

	return status;

    scaled_font->status = CAIRO_STATUS_SUCCESS;

    scaled_font->placeholder = FALSE;

    scaled_font->font_face = font_face;

    scaled_font->original_font_face = font_face;

    scaled_font->font_matrix = *font_matrix;

    scaled_font->ctm = *ctm;

    /* ignore translation values in the ctm */

    scaled_font->ctm.x0 = 0.;

    scaled_font->ctm.y0 = 0.;

    _cairo_font_options_init_copy (&scaled_font->options, options);

    cairo_matrix_multiply (&scaled_font->scale,

			   &scaled_font->font_matrix,

			   &scaled_font->ctm);

    scaled_font->max_scale = MAX (fabs (scaled_font->scale.xx) + fabs (scaled_font->scale.xy),

				  fabs (scaled_font->scale.yx) + fabs (scaled_font->scale.yy));

    scaled_font->scale_inverse = scaled_font->scale;

    status = cairo_matrix_invert (&scaled_font->scale_inverse);

    if (unlikely (status)) {

	/* If the font scale matrix is rank 0, just using an all-zero inverse matrix

	 * makes everything work correctly.  This make font size 0 work without

	 * producing an error.

	 *

	 * FIXME:  If the scale is rank 1, we still go into error mode.  But then

	 * again, that's what we do everywhere in cairo.

	 *

	 * Also, the check for == 0. below may be too harsh...

	 */

        if (_cairo_matrix_is_scale_0 (&scaled_font->scale)) {

	    cairo_matrix_init (&scaled_font->scale_inverse,

			       0, 0, 0, 0,

			       -scaled_font->scale.x0,

			       -scaled_font->scale.y0);

	} else

	    return status;

    }

    scaled_font->glyphs = _cairo_hash_table_create (NULL);

    if (unlikely (scaled_font->glyphs == NULL))

	return _cairo_error (CAIRO_STATUS_NO_MEMORY);

    cairo_list_init (&scaled_font->glyph_pages);

    scaled_font->cache_frozen = FALSE;

    scaled_font->global_cache_frozen = FALSE;

    scaled_font->holdover = FALSE;

    scaled_font->finished = FALSE;

    CAIRO_REFERENCE_COUNT_INIT (&scaled_font->ref_count, 1);

    _cairo_user_data_array_init (&scaled_font->user_data);

    cairo_font_face_reference (font_face);

    scaled_font->original_font_face = NULL;

    CAIRO_MUTEX_INIT (scaled_font->mutex);

    cairo_list_init (&scaled_font->dev_privates);

    scaled_font->backend = backend;

    cairo_list_init (&scaled_font->link);

    return CAIRO_STATUS_SUCCESS;

}

void

_cairo_scaled_font_freeze_cache (cairo_scaled_font_t *scaled_font)

{

    /* ensure we do not modify an error object */

    assert (scaled_font->status == CAIRO_STATUS_SUCCESS);

    CAIRO_MUTEX_LOCK (scaled_font->mutex);

    scaled_font->cache_frozen = TRUE;

}

void

_cairo_scaled_font_thaw_cache (cairo_scaled_font_t *scaled_font)

{

    assert (scaled_font->cache_frozen);

    if (scaled_font->global_cache_frozen) {

	CAIRO_MUTEX_LOCK (_cairo_scaled_glyph_page_cache_mutex);

	_cairo_cache_thaw (&cairo_scaled_glyph_page_cache);

	CAIRO_MUTEX_UNLOCK (_cairo_scaled_glyph_page_cache_mutex);

	scaled_font->global_cache_frozen = FALSE;

    }

    scaled_font->cache_frozen = FALSE;

    CAIRO_MUTEX_UNLOCK (scaled_font->mutex);

}

void

_cairo_scaled_font_reset_cache (cairo_scaled_font_t *scaled_font)

{

    CAIRO_MUTEX_LOCK (scaled_font->mutex);

    assert (! scaled_font->cache_frozen);

    assert (! scaled_font->global_cache_frozen);

    CAIRO_MUTEX_LOCK (_cairo_scaled_glyph_page_cache_mutex);

    while (! cairo_list_is_empty (&scaled_font->glyph_pages)) {

	cairo_scaled_glyph_page_t *page =

	    cairo_list_first_entry (&scaled_font->glyph_pages,

				    cairo_scaled_glyph_page_t,

				    link);

	cairo_scaled_glyph_page_cache.size -= page->cache_entry.size;

	_cairo_hash_table_remove (cairo_scaled_glyph_page_cache.hash_table,

				  (cairo_hash_entry_t *) &page->cache_entry);

	_cairo_scaled_glyph_page_destroy (scaled_font, page);

    }

    CAIRO_MUTEX_UNLOCK (_cairo_scaled_glyph_page_cache_mutex);

    CAIRO_MUTEX_UNLOCK (scaled_font->mutex);

}

cairo_status_t

_cairo_scaled_font_set_metrics (cairo_scaled_font_t	    *scaled_font,

				cairo_font_extents_t	    *fs_metrics)

{

    cairo_status_t status;

    double  font_scale_x, font_scale_y;

    scaled_font->fs_extents = *fs_metrics;

    status = _cairo_matrix_compute_basis_scale_factors (&scaled_font->font_matrix,

						  &font_scale_x, &font_scale_y,

						  1);

    if (unlikely (status))

	return status;

    /*

     * The font responded in unscaled units, scale by the font

     * matrix scale factors to get to user space

     */

    scaled_font->extents.ascent = fs_metrics->ascent * font_scale_y;

    scaled_font->extents.descent = fs_metrics->descent * font_scale_y;

    scaled_font->extents.height = fs_metrics->height * font_scale_y;

    scaled_font->extents.max_x_advance = fs_metrics->max_x_advance * font_scale_x;

    scaled_font->extents.max_y_advance = fs_metrics->max_y_advance * font_scale_y;

    return CAIRO_STATUS_SUCCESS;

}

static void

_cairo_scaled_font_fini_internal (cairo_scaled_font_t *scaled_font)

{

    assert (! scaled_font->cache_frozen);

    assert (! scaled_font->global_cache_frozen);

    scaled_font->finished = TRUE;

    _cairo_scaled_font_reset_cache (scaled_font);

    _cairo_hash_table_destroy (scaled_font->glyphs);

    cairo_font_face_destroy (scaled_font->font_face);

    cairo_font_face_destroy (scaled_font->original_font_face);

    CAIRO_MUTEX_FINI (scaled_font->mutex);

    while (! cairo_list_is_empty (&scaled_font->dev_privates)) {

	cairo_scaled_font_private_t *private =

	    cairo_list_first_entry (&scaled_font->dev_privates,

				    cairo_scaled_font_private_t,

				    link);

	private->destroy (private, scaled_font);

    }

    if (scaled_font->backend != NULL && scaled_font->backend->fini != NULL)

	scaled_font->backend->fini (scaled_font);

    _cairo_user_data_array_fini (&scaled_font->user_data);

}

void

_cairo_scaled_font_fini (cairo_scaled_font_t *scaled_font)

{

    /* Release the lock to avoid the possibility of a recursive

     * deadlock when the scaled font destroy closure gets called. */

    CAIRO_MUTEX_UNLOCK (_cairo_scaled_font_map_mutex);

    _cairo_scaled_font_fini_internal (scaled_font);

    CAIRO_MUTEX_LOCK (_cairo_scaled_font_map_mutex);

}

void

_cairo_scaled_font_attach_private (cairo_scaled_font_t *scaled_font,

				   cairo_scaled_font_private_t *private,

				   const void *key,

				   void (*destroy) (cairo_scaled_font_private_t *,

						    cairo_scaled_font_t *))

{

    private->key = key;

    private->destroy = destroy;

    cairo_list_add (&private->link, &scaled_font->dev_privates);

}

cairo_scaled_font_private_t *

_cairo_scaled_font_find_private (cairo_scaled_font_t *scaled_font,

				 const void *key)

{

    cairo_scaled_font_private_t *priv;

    cairo_list_foreach_entry (priv, cairo_scaled_font_private_t,

			      &scaled_font->dev_privates, link)

    {

	if (priv->key == key) {

	    if (priv->link.prev != &scaled_font->dev_privates)

		cairo_list_move (&priv->link, &scaled_font->dev_privates);

	    return priv;

	}

    }

    return NULL;

}

void

_cairo_scaled_glyph_attach_private (cairo_scaled_glyph_t *scaled_glyph,

				   cairo_scaled_glyph_private_t *private,

				   const void *key,

				   void (*destroy) (cairo_scaled_glyph_private_t *,

						    cairo_scaled_glyph_t *,

						    cairo_scaled_font_t *))

{

    private->key = key;

    private->destroy = destroy;

    cairo_list_add (&private->link, &scaled_glyph->dev_privates);

}

cairo_scaled_glyph_private_t *

_cairo_scaled_glyph_find_private (cairo_scaled_glyph_t *scaled_glyph,

				 const void *key)

{

    cairo_scaled_glyph_private_t *priv;

    cairo_list_foreach_entry (priv, cairo_scaled_glyph_private_t,

			      &scaled_glyph->dev_privates, link)

    {

	if (priv->key == key) {

	    if (priv->link.prev != &scaled_glyph->dev_privates)

		cairo_list_move (&priv->link, &scaled_glyph->dev_privates);

	    return priv;

	}

    }

    return NULL;

}

/**

 * cairo_scaled_font_create:

 * @font_face: a #cairo_font_face_t

 * @font_matrix: font space to user space transformation matrix for the

 *       font. In the simplest case of a N point font, this matrix is

 *       just a scale by N, but it can also be used to shear the font

 *       or stretch it unequally along the two axes. See

 *       cairo_set_font_matrix().

 * @ctm: user to device transformation matrix with which the font will

 *       be used.

 * @options: options to use when getting metrics for the font and

 *           rendering with it.

 *

 * Creates a #cairo_scaled_font_t object from a font face and matrices that

 * describe the size of the font and the environment in which it will

 * be used.

 *

 * Return value: a newly created #cairo_scaled_font_t. Destroy with

 *  cairo_scaled_font_destroy()

 *

 * Since: 1.0

 **/

cairo_scaled_font_t *

cairo_scaled_font_create (cairo_font_face_t          *font_face,

			  const cairo_matrix_t       *font_matrix,

			  const cairo_matrix_t       *ctm,

			  const cairo_font_options_t *options)

{

    cairo_status_t status;

    cairo_scaled_font_map_t *font_map;

    cairo_font_face_t *original_font_face = font_face;

    cairo_scaled_font_t key, *old = NULL, *scaled_font = NULL, *dead = NULL;

    double det;

    status = font_face->status;

    if (unlikely (status))

	return _cairo_scaled_font_create_in_error (status);

    det = _cairo_matrix_compute_determinant (font_matrix);

    if (! ISFINITE (det))

	return _cairo_scaled_font_create_in_error (_cairo_error (CAIRO_STATUS_INVALID_MATRIX));

    det = _cairo_matrix_compute_determinant (ctm);

    if (! ISFINITE (det))

	return _cairo_scaled_font_create_in_error (_cairo_error (CAIRO_STATUS_INVALID_MATRIX));

    status = cairo_font_options_status ((cairo_font_options_t *) options);

    if (unlikely (status))

	return _cairo_scaled_font_create_in_error (status);

    /* Note that degenerate ctm or font_matrix *are* allowed.

     * We want to support a font size of 0. */

    font_map = _cairo_scaled_font_map_lock ();

    if (unlikely (font_map == NULL))

	return _cairo_scaled_font_create_in_error (_cairo_error (CAIRO_STATUS_NO_MEMORY));

    scaled_font = font_map->mru_scaled_font;

    if (scaled_font != NULL &&

	_cairo_scaled_font_matches (scaled_font,

	                            font_face, font_matrix, ctm, options))

    {

	assert (scaled_font->hash_entry.hash != ZOMBIE);

	assert (! scaled_font->placeholder);

	if (likely (scaled_font->status == CAIRO_STATUS_SUCCESS)) {

	    /* We increment the reference count manually here, (rather

	     * than calling into cairo_scaled_font_reference), since we

	     * must modify the reference count while our lock is still

	     * held. */

	    _cairo_reference_count_inc (&scaled_font->ref_count);

	    _cairo_scaled_font_map_unlock ();

	    return scaled_font;

	}

	/* the font has been put into an error status - abandon the cache */

	_cairo_hash_table_remove (font_map->hash_table,

				  &scaled_font->hash_entry);

	scaled_font->hash_entry.hash = ZOMBIE;

	dead = scaled_font;

	font_map->mru_scaled_font = NULL;

    }

    _cairo_scaled_font_init_key (&key, font_face, font_matrix, ctm, options);

    while ((scaled_font = _cairo_hash_table_lookup (font_map->hash_table,

						    &key.hash_entry)))

    {

	if (! scaled_font->placeholder)

	    break;

	/* If the scaled font is being created (happens for user-font),

	 * just wait until it's done, then retry */

	_cairo_scaled_font_placeholder_wait_for_creation_to_finish (scaled_font);

    }

    if (scaled_font != NULL) {

	/* If the original reference count is 0, then this font must have

	 * been found in font_map->holdovers, (which means this caching is

	 * actually working). So now we remove it from the holdovers

	 * array, unless we caught the font in the middle of destruction.

	 */

	if (! CAIRO_REFERENCE_COUNT_HAS_REFERENCE (&scaled_font->ref_count)) {

	    if (scaled_font->holdover) {

		int i;

		for (i = 0; i < font_map->num_holdovers; i++) {

		    if (font_map->holdovers[i] == scaled_font) {

			font_map->num_holdovers--;

			memmove (&font_map->holdovers[i],

				 &font_map->holdovers[i+1],

				 (font_map->num_holdovers - i) * sizeof (cairo_scaled_font_t*));

			break;

		    }

		}

		scaled_font->holdover = FALSE;

	    }

	    /* reset any error status */

	    scaled_font->status = CAIRO_STATUS_SUCCESS;

	}

	if (likely (scaled_font->status == CAIRO_STATUS_SUCCESS)) {

	    /* We increment the reference count manually here, (rather

	     * than calling into cairo_scaled_font_reference), since we

	     * must modify the reference count while our lock is still

	     * held. */

	    old = font_map->mru_scaled_font;

	    font_map->mru_scaled_font = scaled_font;

	    /* increment reference count for the mru cache */

	    _cairo_reference_count_inc (&scaled_font->ref_count);

	    /* and increment for the returned reference */

	    _cairo_reference_count_inc (&scaled_font->ref_count);

	    _cairo_scaled_font_map_unlock ();

	    cairo_scaled_font_destroy (old);

	    if (font_face != original_font_face)

		cairo_font_face_destroy (font_face);

	    return scaled_font;