SSL cairo-scaled-font.c   Sprache: unbekannt

/* -*- 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 <keithp@keithp.com>
 * Carl D. Worth <cworth@cworth.org>
 *      Graydon Hoare <graydon@redhat.com>
 *      Owen Taylor <otaylor@redhat.com>
 *      Behdad Esfahbod <behdad@behdad.org>
 *      Chris Wilson <chris@chris-wilson.co.uk>
 */

#include "cairoint.h"
#include "cairo-array-private.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"

/**
 * 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 uintptr_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_scaled_font_t *scaled_font;
    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_status_t status;

 /* If the recording surface contains other fonts, destroying
 * it while holding _cairo_scaled_glyph_page_cache_mutex will
 * result in deadlock when the recording surface font is
 * destroyed. Instead, move the recording surface to a list of
 * surfaces to free and free it in
 * _cairo_scaled_font_thaw_cache() after
 * _cairo_scaled_glyph_page_cache_mutex is unlocked. */
 status = _cairo_array_append (&scaled_font->recording_surfaces_to_free, &scaled_glyph->recording_surface);
 assert (status == CAIRO_STATUS_SUCCESS);
    }

    if (scaled_glyph->color_surface != NULL)
 cairo_surface_destroy (&scaled_glyph->color_surface->base);
}

#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 */
    { 0, 0, sizeof(cairo_surface_t*), NULL }, /* recording_surfaces_to_free */
    { 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;
}

/* 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 = _cairo_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 = page->scaled_font;

    /* The font is locked in _cairo_scaled_glyph_page_can_remove () */
    _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 = _cairo_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_64_PRIME ((uint64_t)0x00000100000001B3)
#define FNV1_64_INIT ((uint64_t)0xcbf29ce484222325)

static uint64_t
_hash_matrix_fnv (const cairo_matrix_t *matrix,
    uint64_t   hval)
{
    const uint8_t *buffer = (const uint8_t *) matrix;
    int len = sizeof (cairo_matrix_t);
    do {
 hval *= FNV_64_PRIME;
 hval ^= *buffer++;
    } while (--len);

    return hval;
}

static uint64_t
_hash_mix_bits (uint64_t hash)
{
    hash += hash << 12;
    hash ^= hash >> 7;
    hash += hash << 3;
    hash ^= hash >> 17;
    hash += hash << 5;
    return hash;
}

static uintptr_t
_cairo_scaled_font_compute_hash (cairo_scaled_font_t *scaled_font)
{
    uint64_t hash = FNV1_64_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 ^= (uintptr_t) 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 void
_cairo_scaled_font_fini_key (cairo_scaled_font_t *scaled_font)
{
    _cairo_font_options_fini (&scaled_font->options);
}

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;
    _cairo_array_init (&scaled_font->recording_surfaces_to_free, sizeof (cairo_surface_t *));

    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_RECURSIVE_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;
}

static void _cairo_scaled_font_free_recording_surfaces (cairo_scaled_font_t *scaled_font)
{
    int num_recording_surfaces;
    cairo_surface_t *surface;

    num_recording_surfaces = _cairo_array_num_elements (&scaled_font->recording_surfaces_to_free);
    if (num_recording_surfaces > 0) {
 for (int i = 0; i < num_recording_surfaces; i++) {
     _cairo_array_copy_element (&scaled_font->recording_surfaces_to_free, i, &surface);
     cairo_surface_finish (surface);
     cairo_surface_destroy (surface);
 }
 _cairo_array_truncate (&scaled_font->recording_surfaces_to_free, 0);
    }
}

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;
    }

    _cairo_scaled_font_free_recording_surfaces (scaled_font);

    scaled_font->cache_frozen = FALSE;
    CAIRO_MUTEX_UNLOCK (scaled_font->mutex);
}

void
_cairo_scaled_font_reset_cache (cairo_scaled_font_t *scaled_font)
{
    cairo_scaled_glyph_page_t *page;

    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);

    cairo_list_foreach_entry (page,
         cairo_scaled_glyph_page_t,
         &scaled_font->glyph_pages,
         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_MUTEX_UNLOCK (_cairo_scaled_glyph_page_cache_mutex);

    /* Destroy scaled_font's pages while holding its lock only, and not the
     * global page cache lock. The destructor can cause us to recurse and
     * end up back here for a different scaled_font. */

    while (! cairo_list_is_empty (&scaled_font->glyph_pages)) {
 page = cairo_list_first_entry (&scaled_font->glyph_pages,
           cairo_scaled_glyph_page_t,
           link);
 _cairo_scaled_glyph_page_destroy (scaled_font, page);
    }

    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_options_fini (&scaled_font->options);

    cairo_font_face_destroy (scaled_font->font_face);
    cairo_font_face_destroy (scaled_font->original_font_face);

    _cairo_scaled_font_free_recording_surfaces (scaled_font);
    _cairo_array_fini (&scaled_font->recording_surfaces_to_free);

    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);
    }
    _cairo_scaled_font_fini_key (&key);

    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;
 }

 /* 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;
    }


    /* Otherwise create it and insert it into the hash table. */
    if (font_face->backend->get_implementation != NULL) {
 font_face = font_face->backend->get_implementation (font_face,
           font_matrix,
           ctm,
           options);
 if (unlikely (font_face->status)) {
     _cairo_scaled_font_map_unlock ();
     return _cairo_scaled_font_create_in_error (font_face->status);
 }
    }

    status = font_face->backend->scaled_font_create (font_face, font_matrix,
           ctm, options, &scaled_font);
    if (unlikely (status)) {
 _cairo_scaled_font_map_unlock ();
 if (font_face != original_font_face)
     cairo_font_face_destroy (font_face);

 if (dead != NULL)
     cairo_scaled_font_destroy (dead);

 return _cairo_scaled_font_create_in_error (status);
    }
    /* Or did we encounter an error whilst constructing the scaled font? */
    if (unlikely (scaled_font->status)) {
 _cairo_scaled_font_map_unlock ();
 if (font_face != original_font_face)
     cairo_font_face_destroy (font_face);

 if (dead != NULL)
     cairo_scaled_font_destroy (dead);

 return scaled_font;
    }

    /* Our caching above is defeated if the backend switches fonts on us -
     * e.g. old incarnations of toy-font-face and lazily resolved
     * ft-font-faces
     */
    assert (scaled_font->font_face == font_face);
    assert (! scaled_font->cache_frozen);
    assert (! scaled_font->global_cache_frozen);

    scaled_font->original_font_face =
 cairo_font_face_reference (original_font_face);

    scaled_font->hash_entry.hash = _cairo_scaled_font_compute_hash(scaled_font);

    status = _cairo_hash_table_insert (font_map->hash_table,
           &scaled_font->hash_entry);
    if (likely (status == CAIRO_STATUS_SUCCESS)) {
 old = font_map->mru_scaled_font;
 font_map->mru_scaled_font = scaled_font;
 _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);

    if (dead != NULL)
 cairo_scaled_font_destroy (dead);

    if (unlikely (status)) {
 /* We can't call _cairo_scaled_font_destroy here since it expects
 * that the font has already been successfully inserted into the
 * hash table. */
 _cairo_scaled_font_fini_internal (scaled_font);
 free (scaled_font);
 return _cairo_scaled_font_create_in_error (status);
    }

    return scaled_font;
}

static cairo_scaled_font_t *_cairo_scaled_font_nil_objects[CAIRO_STATUS_LAST_STATUS + 1];

/* XXX This should disappear in favour of a common pool of error objects. */
cairo_scaled_font_t *
_cairo_scaled_font_create_in_error (cairo_status_t status)
{
    cairo_scaled_font_t *scaled_font;

    assert (status != CAIRO_STATUS_SUCCESS);

    if (status == CAIRO_STATUS_NO_MEMORY)
 return (cairo_scaled_font_t *) &_cairo_scaled_font_nil;

    CAIRO_MUTEX_LOCK (_cairo_scaled_font_error_mutex);
    scaled_font = _cairo_scaled_font_nil_objects[status];
    if (unlikely (scaled_font == NULL)) {
 scaled_font = _cairo_malloc (sizeof (cairo_scaled_font_t));
 if (unlikely (scaled_font == NULL)) {
     CAIRO_MUTEX_UNLOCK (_cairo_scaled_font_error_mutex);
     _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
     return (cairo_scaled_font_t *) &_cairo_scaled_font_nil;
 }

 *scaled_font = _cairo_scaled_font_nil;
 scaled_font->status = status;
 _cairo_scaled_font_nil_objects[status] = scaled_font;
    }
    CAIRO_MUTEX_UNLOCK (_cairo_scaled_font_error_mutex);

    return scaled_font;
}

void
_cairo_scaled_font_reset_static_data (void)
{
    int status;

    CAIRO_MUTEX_LOCK (_cairo_scaled_font_error_mutex);
    for (status = CAIRO_STATUS_SUCCESS;
  status <= CAIRO_STATUS_LAST_STATUS;
  status++)
    {
 free (_cairo_scaled_font_nil_objects[status]);
 _cairo_scaled_font_nil_objects[status] = NULL;
    }
    CAIRO_MUTEX_UNLOCK (_cairo_scaled_font_error_mutex);

    CAIRO_MUTEX_LOCK (_cairo_scaled_glyph_page_cache_mutex);
    if (cairo_scaled_glyph_page_cache.hash_table != NULL) {
 _cairo_cache_fini (&cairo_scaled_glyph_page_cache);
 cairo_scaled_glyph_page_cache.hash_table = NULL;
    }
    CAIRO_MUTEX_UNLOCK (_cairo_scaled_glyph_page_cache_mutex);
}

/**
 * cairo_scaled_font_reference:
 * @scaled_font: a #cairo_scaled_font_t, (may be %NULL in which case
 * this function does nothing)
 *
 * Increases the reference count on @scaled_font by one. This prevents
 * @scaled_font from being destroyed until a matching call to
 * cairo_scaled_font_destroy() is made.
 *
 * Use cairo_scaled_font_get_reference_count() to get the number of
 * references to a #cairo_scaled_font_t.
 *
 * Returns: the referenced #cairo_scaled_font_t
 *
 * Since: 1.0
 **/
cairo_scaled_font_t *
cairo_scaled_font_reference (cairo_scaled_font_t *scaled_font)
{
    if (scaled_font == NULL ||
     CAIRO_REFERENCE_COUNT_IS_INVALID (&scaled_font->ref_count))
 return scaled_font;

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

    _cairo_reference_count_inc (&scaled_font->ref_count);

    return scaled_font;
}

/**
 * cairo_scaled_font_destroy:
 * @scaled_font: a #cairo_scaled_font_t
 *
 * Decreases the reference count on @font by one. If the result
 * is zero, then @font and all associated resources are freed.
 * See cairo_scaled_font_reference().
 *
 * Since: 1.0
 **/
void
cairo_scaled_font_destroy (cairo_scaled_font_t *scaled_font)
{
    cairo_scaled_font_t *lru = NULL;
    cairo_scaled_font_map_t *font_map;

    assert (CAIRO_MUTEX_IS_UNLOCKED (_cairo_scaled_font_map_mutex));

    if (scaled_font == NULL ||
     CAIRO_REFERENCE_COUNT_IS_INVALID (&scaled_font->ref_count))
 return;

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

    font_map = _cairo_scaled_font_map_lock ();
    assert (font_map != NULL);

    if (! _cairo_reference_count_dec_and_test (&scaled_font->ref_count))
 goto unlock;

    assert (! scaled_font->cache_frozen);
    assert (! scaled_font->global_cache_frozen);

    /* Another thread may have resurrected the font whilst we waited */
    if (! CAIRO_REFERENCE_COUNT_HAS_REFERENCE (&scaled_font->ref_count)) {
 if (! scaled_font->placeholder &&
     scaled_font->hash_entry.hash != ZOMBIE)
 {
     /* Another thread may have already inserted us into the holdovers */
     if (scaled_font->holdover)
  goto unlock;

     /* Rather than immediately destroying this object, we put it into
     * the font_map->holdovers array in case it will get used again
     * soon (and is why we must hold the lock over the atomic op on
     * the reference count). To make room for it, we do actually
     * destroy the least-recently-used holdover.
     */

     if (font_map->num_holdovers == CAIRO_SCALED_FONT_MAX_HOLDOVERS) {
  lru = font_map->holdovers[0];
  assert (! CAIRO_REFERENCE_COUNT_HAS_REFERENCE (&lru->ref_count));

  _cairo_hash_table_remove (font_map->hash_table,
       &lru->hash_entry);

  font_map->num_holdovers--;
  memmove (&font_map->holdovers[0],
    &font_map->holdovers[1],
    font_map->num_holdovers * sizeof (cairo_scaled_font_t*));
     }

     font_map->holdovers[font_map->num_holdovers++] = scaled_font;
     scaled_font->holdover = TRUE;
 } else
     lru = scaled_font;
    }

  unlock:
    _cairo_scaled_font_map_unlock ();

    /* If we pulled an item from the holdovers array, (while the font
     * map lock was held, of course), then there is no way that anyone
     * else could have acquired a reference to it. So we can now
     * safely call fini on it without any lock held. This is desirable
     * as we never want to call into any backend function with a lock
     * held. */
    if (lru != NULL) {
 _cairo_scaled_font_fini_internal (lru);
 free (lru);
    }
}

/**
 * cairo_scaled_font_get_reference_count:
 * @scaled_font: a #cairo_scaled_font_t
 *
 * Returns the current reference count of @scaled_font.
 *
 * Return value: the current reference count of @scaled_font.  If the
 * object is a nil object, 0 will be returned.
 *
 * Since: 1.4
 **/
unsigned int
cairo_scaled_font_get_reference_count (cairo_scaled_font_t *scaled_font)
{
    if (scaled_font == NULL ||
     CAIRO_REFERENCE_COUNT_IS_INVALID (&scaled_font->ref_count))
 return 0;

    return CAIRO_REFERENCE_COUNT_GET_VALUE (&scaled_font->ref_count);
}

/**
 * cairo_scaled_font_get_user_data:
 * @scaled_font: a #cairo_scaled_font_t
 * @key: the address of the #cairo_user_data_key_t the user data was
 * attached to
 *
 * Return user data previously attached to @scaled_font using the
 * specified key.  If no user data has been attached with the given
 * key this function returns %NULL.
 *
 * Return value: the user data previously attached or %NULL.
 *
 * Since: 1.4
 **/
void *
cairo_scaled_font_get_user_data (cairo_scaled_font_t      *scaled_font,
     const cairo_user_data_key_t *key)
{
    return _cairo_user_data_array_get_data (&scaled_font->user_data,
         key);
}

/**
 * cairo_scaled_font_set_user_data:
 * @scaled_font: a #cairo_scaled_font_t
 * @key: the address of a #cairo_user_data_key_t to attach the user data to
 * @user_data: the user data to attach to the #cairo_scaled_font_t
 * @destroy: a #cairo_destroy_func_t which will be called when the
 * #cairo_t is destroyed or when new user data is attached using the
 * same key.
 *
 * Attach user data to @scaled_font.  To remove user data from a surface,
 * call this function with the key that was used to set it and %NULL
 * for @data.
 *
 * Return value: %CAIRO_STATUS_SUCCESS or %CAIRO_STATUS_NO_MEMORY if a
 * slot could not be allocated for the user data.
 *
 * Since: 1.4
 **/
cairo_status_t
cairo_scaled_font_set_user_data (cairo_scaled_font_t      *scaled_font,
     const cairo_user_data_key_t *key,
     void        *user_data,
     cairo_destroy_func_t       destroy)
{
    if (CAIRO_REFERENCE_COUNT_IS_INVALID (&scaled_font->ref_count))
 return scaled_font->status;

    return _cairo_user_data_array_set_data (&scaled_font->user_data,
         key, user_data, destroy);
}

/* Public font API follows. */

/**
 * cairo_scaled_font_extents:
 * @scaled_font: a #cairo_scaled_font_t
 * @extents: a #cairo_font_extents_t which to store the retrieved extents.
 *
 * Gets the metrics for a #cairo_scaled_font_t.
 *
 * Since: 1.0
 **/
void
cairo_scaled_font_extents (cairo_scaled_font_t  *scaled_font,
      cairo_font_extents_t *extents)
{
    if (scaled_font->status) {
 extents->ascent  = 0.0;
 extents->descent = 0.0;
 extents->height  = 0.0;
 extents->max_x_advance = 0.0;
 extents->max_y_advance = 0.0;
 return;
    }

    *extents = scaled_font->extents;
}

/**
 * cairo_scaled_font_text_extents:
 * @scaled_font: a #cairo_scaled_font_t
 * @utf8: a NUL-terminated string of text, encoded in UTF-8
 * @extents: a #cairo_text_extents_t which to store the retrieved extents.
 *
 * Gets the extents for a string of text. The extents describe a
 * user-space rectangle that encloses the "inked" portion of the text
 * drawn at the origin (0,0) (as it would be drawn by cairo_show_text()
 * if the cairo graphics state were set to the same font_face,
 * font_matrix, ctm, and font_options as @scaled_font).  Additionally,
 * the x_advance and y_advance values indicate the amount by which the
 * current point would be advanced by cairo_show_text().
 *
 * Note that whitespace characters do not directly contribute to the
 * size of the rectangle (extents.width and extents.height). They do
 * contribute indirectly by changing the position of non-whitespace
 * characters. In particular, trailing whitespace characters are
 * likely to not affect the size of the rectangle, though they will
 * affect the x_advance and y_advance values.
 *
 * Since: 1.2
 **/
void
cairo_scaled_font_text_extents (cairo_scaled_font_t   *scaled_font,
    const char            *utf8,
    cairo_text_extents_t  *extents)
{
    cairo_status_t status;
    cairo_glyph_t *glyphs = NULL;
    int num_glyphs;

    if (scaled_font->status)
 goto ZERO_EXTENTS;

    if (utf8 == NULL)
 goto ZERO_EXTENTS;

    status = cairo_scaled_font_text_to_glyphs (scaled_font, 0., 0.,
            utf8, -1,
            &glyphs, &num_glyphs,
            NULL, NULL,
            NULL);
    if (unlikely (status)) {
 status = _cairo_scaled_font_set_error (scaled_font, status);
 goto ZERO_EXTENTS;
    }

    cairo_scaled_font_glyph_extents (scaled_font, glyphs, num_glyphs, extents);
    free (glyphs);

    return;

ZERO_EXTENTS:
    extents->x_bearing = 0.0;
    extents->y_bearing = 0.0;
    extents->width  = 0.0;
    extents->height = 0.0;
    extents->x_advance = 0.0;
    extents->y_advance = 0.0;
}

/**
 * cairo_scaled_font_glyph_extents:
 * @scaled_font: a #cairo_scaled_font_t
 * @glyphs: an array of glyph IDs with X and Y offsets.
 * @num_glyphs: the number of glyphs in the @glyphs array
 * @extents: a #cairo_text_extents_t which to store the retrieved extents.
 *
 * Gets the extents for an array of glyphs. The extents describe a
 * user-space rectangle that encloses the "inked" portion of the
 * glyphs, (as they would be drawn by cairo_show_glyphs() if the cairo
 * graphics state were set to the same font_face, font_matrix, ctm,
 * and font_options as @scaled_font).  Additionally, the x_advance and
 * y_advance values indicate the amount by which the current point
 * would be advanced by cairo_show_glyphs().
 *
 * Note that whitespace glyphs do not contribute to the size of the
 * rectangle (extents.width and extents.height).
 *
 * Since: 1.0
 **/
void
cairo_scaled_font_glyph_extents (cairo_scaled_font_t   *scaled_font,
     const cairo_glyph_t   *glyphs,
     int                    num_glyphs,
     cairo_text_extents_t  *extents)
{
    cairo_status_t status;
    int i;
    double min_x = 0.0, min_y = 0.0, max_x = 0.0, max_y = 0.0;
    cairo_bool_t visible = FALSE;
    cairo_scaled_glyph_t *scaled_glyph = NULL;

    extents->x_bearing = 0.0;
    extents->y_bearing = 0.0;
    extents->width  = 0.0;
    extents->height = 0.0;
    extents->x_advance = 0.0;
    extents->y_advance = 0.0;

    if (unlikely (scaled_font->status))
 goto ZERO_EXTENTS;

    if (num_glyphs == 0)
 goto ZERO_EXTENTS;

    if (unlikely (num_glyphs < 0)) {
 _cairo_error_throw (CAIRO_STATUS_NEGATIVE_COUNT);
 /* XXX Can't propagate error */
 goto ZERO_EXTENTS;
    }

    if (unlikely (glyphs == NULL)) {
 _cairo_error_throw (CAIRO_STATUS_NULL_POINTER);
 /* XXX Can't propagate error */
 goto ZERO_EXTENTS;
    }

    _cairo_scaled_font_freeze_cache (scaled_font);

    for (i = 0; i < num_glyphs; i++) {
 double   left, top, right, bottom;

 status = _cairo_scaled_glyph_lookup (scaled_font,
          glyphs[i].index,
          CAIRO_SCALED_GLYPH_INFO_METRICS,
          NULL, /* foreground color */
          &scaled_glyph);
 if (unlikely (status)) {
     status = _cairo_scaled_font_set_error (scaled_font, status);
     goto UNLOCK;
 }

 /* "Ink" extents should skip "invisible" glyphs */
 if (scaled_glyph->metrics.width == 0 || scaled_glyph->metrics.height == 0)
     continue;

 left = scaled_glyph->metrics.x_bearing + glyphs[i].x;
 right = left + scaled_glyph->metrics.width;
 top = scaled_glyph->metrics.y_bearing + glyphs[i].y;
 bottom = top + scaled_glyph->metrics.height;

 if (!visible) {
     visible = TRUE;
     min_x = left;
     max_x = right;
     min_y = top;
     max_y = bottom;
 } else {
     if (left < min_x) min_x = left;
     if (right > max_x) max_x = right;
     if (top < min_y) min_y = top;
     if (bottom > max_y) max_y = bottom;
 }
    }

    if (visible) {
 extents->x_bearing = min_x - glyphs[0].x;
 extents->y_bearing = min_y - glyphs[0].y;
 extents->width = max_x - min_x;
 extents->height = max_y - min_y;
    } else {
 extents->x_bearing = 0.0;
 extents->y_bearing = 0.0;
 extents->width = 0.0;
 extents->height = 0.0;
    }

    if (num_glyphs) {
        double x0, y0, x1, y1;

 x0 = glyphs[0].x;
 y0 = glyphs[0].y;

 /* scaled_glyph contains the glyph for num_glyphs - 1 already. */
 x1 = glyphs[num_glyphs - 1].x + scaled_glyph->metrics.x_advance;
 y1 = glyphs[num_glyphs - 1].y + scaled_glyph->metrics.y_advance;

 extents->x_advance = x1 - x0;
 extents->y_advance = y1 - y0;
    } else {
 extents->x_advance = 0.0;
 extents->y_advance = 0.0;
    }

 UNLOCK:
    _cairo_scaled_font_thaw_cache (scaled_font);
    return;

ZERO_EXTENTS:
    extents->x_bearing = 0.0;
    extents->y_bearing = 0.0;
    extents->width  = 0.0;
    extents->height = 0.0;
    extents->x_advance = 0.0;
    extents->y_advance = 0.0;
}

#define GLYPH_LUT_SIZE 64
static cairo_status_t
cairo_scaled_font_text_to_glyphs_internal_cached (cairo_scaled_font_t   *scaled_font,
          double     x,
          double     y,
          const char    *utf8,
          cairo_glyph_t   *glyphs,
          cairo_text_cluster_t **clusters,
          int      num_chars)
{
    struct glyph_lut_elt {
 unsigned long index;
 double x_advance;
 double y_advance;
    } glyph_lut[GLYPH_LUT_SIZE];
    uint32_t glyph_lut_unicode[GLYPH_LUT_SIZE];
    cairo_status_t status;
    const char *p;
    int i;

    for (i = 0; i < GLYPH_LUT_SIZE; i++)
 glyph_lut_unicode[i] = ~0U;

    p = utf8;
    for (i = 0; i < num_chars; i++) {
 int idx, num_bytes;
 uint32_t unicode;
 cairo_scaled_glyph_t *scaled_glyph;
 struct glyph_lut_elt *glyph_slot;

 num_bytes = _cairo_utf8_get_char_validated (p, &unicode);
 p += num_bytes;

 glyphs[i].x = x;
 glyphs[i].y = y;

 idx = unicode % ARRAY_LENGTH (glyph_lut);
 glyph_slot = &glyph_lut[idx];
 if (glyph_lut_unicode[idx] == unicode) {
     glyphs[i].index = glyph_slot->index;
     x += glyph_slot->x_advance;
     y += glyph_slot->y_advance;
 } else {
     unsigned long g;

     g = scaled_font->backend->ucs4_to_index (scaled_font, unicode);
     status = _cairo_scaled_glyph_lookup (scaled_font,
       g,
       CAIRO_SCALED_GLYPH_INFO_METRICS,
       NULL, /* foreground color */
       &scaled_glyph);
     if (unlikely (status))
  return status;

     x += scaled_glyph->metrics.x_advance;
     y += scaled_glyph->metrics.y_advance;

     glyph_lut_unicode[idx] = unicode;
     glyph_slot->index = g;
     glyph_slot->x_advance = scaled_glyph->metrics.x_advance;
     glyph_slot->y_advance = scaled_glyph->metrics.y_advance;

     glyphs[i].index = g;
 }

 if (clusters) {
     (*clusters)[i].num_bytes  = num_bytes;
     (*clusters)[i].num_glyphs = 1;
 }
    }

    return CAIRO_STATUS_SUCCESS;
}

static cairo_status_t
cairo_scaled_font_text_to_glyphs_internal_uncached (cairo_scaled_font_t  *scaled_font,
        double    x,
        double    y,
        const char   *utf8,
        cairo_glyph_t   *glyphs,
        cairo_text_cluster_t **clusters,
        int     num_chars)
{
    const char *p;
    int i;

    p = utf8;
    for (i = 0; i < num_chars; i++) {
 unsigned long g;
 int num_bytes;
 uint32_t unicode;
 cairo_scaled_glyph_t *scaled_glyph;
 cairo_status_t status;

 num_bytes = _cairo_utf8_get_char_validated (p, &unicode);
 p += num_bytes;

 glyphs[i].x = x;
 glyphs[i].y = y;

 g = scaled_font->backend->ucs4_to_index (scaled_font, unicode);

 /*
 * No advance needed for a single character string. So, let's speed up
 * one-character strings by skipping glyph lookup.
 */
 if (num_chars > 1) {
     status = _cairo_scaled_glyph_lookup (scaled_font,
          g,
          CAIRO_SCALED_GLYPH_INFO_METRICS,
          NULL, /* foreground color */
          &scaled_glyph);
     if (unlikely (status))
  return status;

     x += scaled_glyph->metrics.x_advance;
     y += scaled_glyph->metrics.y_advance;
 }

 glyphs[i].index = g;

 if (clusters) {
     (*clusters)[i].num_bytes  = num_bytes;
     (*clusters)[i].num_glyphs = 1;
 }
    }

    return CAIRO_STATUS_SUCCESS;
}

/**
 * cairo_scaled_font_text_to_glyphs:
 * @scaled_font: a #cairo_scaled_font_t
 * @x: X position to place first glyph
 * @y: Y position to place first glyph
 * @utf8: a string of text encoded in UTF-8
 * @utf8_len: length of @utf8 in bytes, or -1 if it is NUL-terminated
 * @glyphs: pointer to array of glyphs to fill
 * @num_glyphs: pointer to number of glyphs
 * @clusters: pointer to array of cluster mapping information to fill, or %NULL
 * @num_clusters: pointer to number of clusters, or %NULL
 * @cluster_flags: pointer to location to store cluster flags corresponding to the
 *                 output @clusters, or %NULL
 *
 * Converts UTF-8 text to an array of glyphs, optionally with cluster
 * mapping, that can be used to render later using @scaled_font.
 *
 * If @glyphs initially points to a non-%NULL value, that array is used
 * as a glyph buffer, and @num_glyphs should point to the number of glyph
 * entries available there.  If the provided glyph array is too short for
 * the conversion, a new glyph array is allocated using cairo_glyph_allocate()
 * and placed in @glyphs.  Upon return, @num_glyphs always contains the
 * number of generated glyphs.  If the value @glyphs points to has changed
 * after the call, the user is responsible for freeing the allocated glyph
 * array using cairo_glyph_free().  This may happen even if the provided
 * array was large enough.
 *
 * If @clusters is not %NULL, @num_clusters and @cluster_flags should not be %NULL,
 * and cluster mapping will be computed.
 * The semantics of how cluster array allocation works is similar to the glyph
 * array.  That is,
 * if @clusters initially points to a non-%NULL value, that array is used
 * as a cluster buffer, and @num_clusters should point to the number of cluster
 * entries available there.  If the provided cluster array is too short for
 * the conversion, a new cluster array is allocated using cairo_text_cluster_allocate()
 * and placed in @clusters.  Upon return, @num_clusters always contains the
 * number of generated clusters.  If the value @clusters points at has changed
 * after the call, the user is responsible for freeing the allocated cluster
 * array using cairo_text_cluster_free().  This may happen even if the provided
 * array was large enough.
 *
 * In the simplest case, @glyphs and @clusters can point to %NULL initially
 * and a suitable array will be allocated.  In code:
 * <informalexample><programlisting>
 * cairo_status_t status;
 *
 * cairo_glyph_t *glyphs = NULL;
 * int num_glyphs;
 * cairo_text_cluster_t *clusters = NULL;
 * int num_clusters;
 * cairo_text_cluster_flags_t cluster_flags;
 *
 * status = cairo_scaled_font_text_to_glyphs (scaled_font,
 *                                            x, y,
 *                                            utf8, utf8_len,
 *                                            &glyphs, &num_glyphs,
 *                                            &clusters, &num_clusters, &cluster_flags);
 *
 * if (status == CAIRO_STATUS_SUCCESS) {
 *     cairo_show_text_glyphs (cr,
 *                             utf8, utf8_len,
 *                             glyphs, num_glyphs,
 *                             clusters, num_clusters, cluster_flags);
 *
 *     cairo_glyph_free (glyphs);
 *     cairo_text_cluster_free (clusters);
 * }
 * </programlisting></informalexample>
 *
 * If no cluster mapping is needed:
 * <informalexample><programlisting>
 * cairo_status_t status;
 *
 * cairo_glyph_t *glyphs = NULL;
 * int num_glyphs;
 *
 * status = cairo_scaled_font_text_to_glyphs (scaled_font,
 *                                            x, y,
 *                                            utf8, utf8_len,
 *                                            &glyphs, &num_glyphs,
 *                                            NULL, NULL,
 *                                            NULL);
 *
 * if (status == CAIRO_STATUS_SUCCESS) {
 *     cairo_show_glyphs (cr, glyphs, num_glyphs);
 *     cairo_glyph_free (glyphs);
 * }
 * </programlisting></informalexample>
 *
 * If stack-based glyph and cluster arrays are to be used for small
 * arrays:
 * <informalexample><programlisting>
 * cairo_status_t status;
 *
 * cairo_glyph_t stack_glyphs[40];
 * cairo_glyph_t *glyphs = stack_glyphs;
 * int num_glyphs = sizeof (stack_glyphs) / sizeof (stack_glyphs[0]);
 * cairo_text_cluster_t stack_clusters[40];
 * cairo_text_cluster_t *clusters = stack_clusters;
 * int num_clusters = sizeof (stack_clusters) / sizeof (stack_clusters[0]);
 * cairo_text_cluster_flags_t cluster_flags;
 *
 * status = cairo_scaled_font_text_to_glyphs (scaled_font,
 *                                            x, y,
 *                                            utf8, utf8_len,
 *                                            &glyphs, &num_glyphs,
 *                                            &clusters, &num_clusters, &cluster_flags);
 *
 * if (status == CAIRO_STATUS_SUCCESS) {
 *     cairo_show_text_glyphs (cr,
 *                             utf8, utf8_len,
 *                             glyphs, num_glyphs,
 *                             clusters, num_clusters, cluster_flags);
 *
 *     if (glyphs != stack_glyphs)
 *         cairo_glyph_free (glyphs);
 *     if (clusters != stack_clusters)
 *         cairo_text_cluster_free (clusters);
 * }
 * </programlisting></informalexample>
 *
 * For details of how @clusters, @num_clusters, and @cluster_flags map input
 * UTF-8 text to the output glyphs see cairo_show_text_glyphs().
 *
 * The output values can be readily passed to cairo_show_text_glyphs()
 * cairo_show_glyphs(), or related functions, assuming that the exact
 * same @scaled_font is used for the operation.
 *
 * Return value: %CAIRO_STATUS_SUCCESS upon success, or an error status
 * if the input values are wrong or if conversion failed.  If the input
 * values are correct but the conversion failed, the error status is also
 * set on @scaled_font.
 *
 * Since: 1.8
 **/
#define CACHING_THRESHOLD 16
cairo_status_t
cairo_scaled_font_text_to_glyphs (cairo_scaled_font_t   *scaled_font,
      double   x,
      double   y,
      const char         *utf8,
      int           utf8_len,
      cairo_glyph_t        **glyphs,
      int          *num_glyphs,
      cairo_text_cluster_t **clusters,
      int          *num_clusters,
      cairo_text_cluster_flags_t *cluster_flags)
{
    int num_chars = 0;
    cairo_int_status_t status;
    cairo_glyph_t *orig_glyphs;
    cairo_text_cluster_t *orig_clusters;

    status = scaled_font->status;
    if (unlikely (status))
 return status;

    /* A slew of sanity checks */

    /* glyphs and num_glyphs can't be NULL */
--> --------------------

--> maximum size reached

--> --------------------