/* -*- 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_t *scaled_glyph)

{

				    cairo_scaled_glyph_private_t,

				    link);

    }

	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. */

    }

#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_status_t status)

{

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

     * error, which is the most significant. */

}

/**

 * 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_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

{

}

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

{

    }

}

static void

{

void

{

    cairo_scaled_font_map_t *font_map;

    cairo_scaled_font_t *scaled_font;

    }

    }

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

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

				  &scaled_font->hash_entry);

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

	 * recursive deadlock when the scaled font destroy closure gets

	 * called

	 */

    }

static void

				  cairo_scaled_glyph_page_t *page)

{

    unsigned int n;

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

    }

static void

{

    cairo_scaled_font_t *scaled_font;

    /* The font is locked in _cairo_scaled_glyph_page_can_remove () */

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

    cairo_scaled_font_t *placeholder_scaled_font;

    assert (CAIRO_MUTEX_IS_LOCKED (_cairo_scaled_font_map_mutex));

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

				      scaled_font->font_face,

				      NULL);

    placeholder_scaled_font->hash_entry.hash

				       &placeholder_scaled_font->hash_entry);

}

void

{

    cairo_scaled_font_t *placeholder_scaled_font;

    /* temporary hash value to match the placeholder */

    scaled_font->hash_entry.hash

    placeholder_scaled_font =

				  &scaled_font->hash_entry);

    assert (CAIRO_MUTEX_IS_LOCKED (placeholder_scaled_font->mutex));

			      &placeholder_scaled_font->hash_entry);

static void

{

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

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

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

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

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

		  uint64_t		 hval)

{

    do {

}

static uint64_t

{

}

static uintptr_t

{

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

    /* final mixing of bits */

}

static void

			     cairo_font_face_t	        *font_face,

			     const cairo_matrix_t       *font_matrix,

			     const cairo_matrix_t       *ctm,

			     const cairo_font_options_t *options)

{

    /* ignore translation values in the ctm */

static void

{

static cairo_bool_t

			       const void *abstract_key_b)

{

}

static cairo_bool_t

	                    const cairo_font_face_t *font_face,

			    const cairo_matrix_t *font_matrix,

			    const cairo_matrix_t *ctm,

			    const cairo_font_options_t *options)

{

}

/*

 * Basic #cairo_scaled_font_t object management

 */

cairo_status_t

			 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;

    /* ignore translation values in the ctm */

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

	/* 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...

	 */

			       0, 0, 0, 0,

	} else

    }

}

{

    int num_recording_surfaces;

    cairo_surface_t *surface;

	}

    }

void

{

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

void

{

    }

void

{

    cairo_scaled_glyph_page_t *page;

			      cairo_scaled_glyph_page_t,

			      &scaled_font->glyph_pages,

			      link) {

    }

    /* 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. */

				       cairo_scaled_glyph_page_t,

				       link);

    }

cairo_status_t

				cairo_font_extents_t	    *fs_metrics)

{

    cairo_status_t status;

    double  font_scale_x, font_scale_y;

						  &font_scale_x, &font_scale_y,

						  1);

    /*

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

     * matrix scale factors to get to user space

     */

}

static void

{

				    cairo_scaled_font_private_t,

				    link);

    }

void

{

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

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

void

				   cairo_scaled_font_private_t *private,

				   const void *key,

				   void (*destroy) (cairo_scaled_font_private_t *,

						    cairo_scaled_font_t *))

{

cairo_scaled_font_private_t *

				 const void *key)

{

    cairo_scaled_font_private_t *priv;

			      &scaled_font->dev_privates, link)

    {

	}

    }

}

void

				   cairo_scaled_glyph_private_t *private,

				   const void *key,

				   void (*destroy) (cairo_scaled_glyph_private_t *,

						    cairo_scaled_glyph_t *,

						    cairo_scaled_font_t *))

{

cairo_scaled_glyph_private_t *

				 const void *key)

{

    cairo_scaled_glyph_private_t *priv;

			      &scaled_glyph->dev_privates, link)

    {

	}

    }

}

/**

 * 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 *

			  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;

    double det;

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

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

	                            font_face, font_matrix, ctm, options))

    {

	    /* 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. */

	}

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

    }

						    &key.hash_entry)))

    {

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

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

    }

	/* 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.

	 */

		int i;

		    }

		}

	    }

	    /* reset any error status */

	}

	    /* 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. */

	    /* increment reference count for the mru cache */

	    /* and increment for the returned reference */

	}

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

    }

    /* Otherwise create it and insert it into the hash table. */

							    font_matrix,

							    ctm,

							    options);

	}

    }

						     ctm, options, &scaled_font);

    }

    /* Or did we encounter an error whilst constructing the 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

     */

    }

	/* We can't call _cairo_scaled_font_destroy here since it expects

	 * that the font has already been successfully inserted into the

	 * hash table. */

    }

}

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_t *scaled_font;

	}

    }

}

void

{

    int status;

    {

    }

    }

/**

 * 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 *

{