/* * gcache.c -- Provide the cache mechanicsm for outlines * Copyright (C) 1996 Li-Da Lho, All right reserved * * This file is a little bit more complicated, the structure of the cache is  * described as fellow: * Basically the cache can be divided onto two parts, the first one is a  * linear part which is a least recently utilitied list (LRU),  * the second part is the nonlinear one which is a binary serach tree.  * Normally each cache element is one the LRU as well as on the BST. * Those glyph elements are allocated at once as an array of glyph cache  * elements at the init phase of glyph cache. * * font->gcache-- *              | *      ________| *     | *     v  * ------------------------------------------------------------------ * |element 0|   1   |   2   |  3   |   4   |   5   |   6   |   7   | ... * ------------------------------------------------------------------  * The first element of the glyph cache array serves as a dummy header * for two purposes, one is for the head and tail of the LRU, the other is * to point to the root of the BST. As a pointer to the root of the * BST, the right subtree points to the root of the BST while the left one is  * not used and arbitrarly points to itself. * * After initialization, all the glyph cache element are on the LRU but * none of them is on the BST. *                                      *  |-----------------------------------------------------------| *  |   -------------         ------                  ------    | *  |-> |head & tail| <-----> |    |<-----> ...<----->|    | <--| *      -------------         ------                  ------  *         /  \                /  \                    /  \ *        /    \              /    \                  /    \ * left=self right=root    left  right             left  right * * The cached data are pointed by the entries of the glyph cache element * in a strait forward fashion. * *  |-----------------------------------------------------------| *  |   -------------         ------                  ------    | *  |-> |head & tail| <-----> |    |<-----> ...<----->|    | <--| *      -------------         ------                  ------  *       |  |     -------------|--|--------------------------------  *       |  |---->|            |  |->  array for flag, instruction| *       |        -------------|-----------------------------------  *       |        -------------|----------------------------------- *       |------->|            |---->  xcoordinates,  ycoordinates| *                ------------------------------------------------- * Implementation in this way is effecient for the reason that when we * need to free the cache, we only need to do the two things * 1. free the data pointed by the entries in the dummy header * 2. free the dummy header * * Every time a glyph outline is required and ttfLoadGlyphCached is called,  * the glyph is searched on the BST with its offset as a key. * If the glyph is on the BST then the address of the glyph cache is returned * and the glyph cache is moved to the tail of the LRU such that the order of  * LRU is mantained. * When the glyph required is not on the BST, something more complicated should * be done. *  1. Remove the first element on the LRU from the BST. *  2. Load the glyph data to the cache element. *  3. Insert the element back to the BST. *  4. Move the element to the tail of the LRU. * * The only problem remain is how to deal with composite components.  * The asnwer simply is not to support cache for composite components at the  * current stage for the two reasons: *  1. It will makes the code an order of magnitude more complicate to support *     composite glyf cache. *  2. The space occupied by composite glyf is not very much * * It is not clear right now if it is wise to add tree balancing code.  * The overhaed introduced by BST seems minimal for 256 elements cache. */#include <stdio.h>#include <stdlib.h>#include <string.h>#include "config.h"#include "ttf.h"#include "ttfutil.h"#ifdef MEMCHECK#include <dmalloc.h>#endif/* 	$Id: gcache.c,v 1.1.1.1 1998/06/05 07:47:52 robert Exp $	 */#ifndef lintstatic char vcid[] = "$Id: gcache.c,v 1.1.1.1 1998/06/05 07:47:52 robert Exp $";#endif /* lint */static GlyphCachePtr ttfAllocCache(TTFontPtr font);static void ttfInitCache(TTFontPtr font);static void ttfFreeCache(TTFontPtr font);static void ttfRotateCache(TTFontPtr font);static void ttfAllocCacheData(TTFontPtr font);static void ttfInitCacheData(TTFontPtr font);static void ttfFreeCacheData(TTFontPtr font);static void ttfInsertBST(TTFontPtr font,GlyphCachePtr gcache);static GlyphCachePtr ttfSearchBST(TTFontPtr font,ULONG offset);static void ttfDeleteBST(TTFontPtr font,ULONG offset);static void merge(GlyphCachePtr *root);static void copy(GlyphCachePtr *root);void ttfInitGlyphCache(TTFontPtr font){    /* this should be made configurable */    if (font->maxp->numGlyphs > 256)	font->numCacheElements = 128;    else	font->numCacheElements = 64;    font->gcache = ttfAllocCache(font);    ttfInitCache(font);    ttfAllocCacheData(font);    ttfInitCacheData(font);}void ttfCleanUpGlyphCache(TTFontPtr font){    ttfFreeCacheData(font);    ttfFreeCache(font);    }/* provide cache mechanism for glyph */GLYFPtr ttfLoadGlyphCached(TTFontPtr font,ULONG offset){#ifdef OLDCODE    GLYFPtr glyf;        glyf = &(font->gcache->next->glyf);    font->gcache->next->offset = offset;    ttfRotateCache(font);    ttfLoadGLYF(font->fp,glyf,offset);       return glyf;#else    GlyphCachePtr gcache;    if ((gcache = ttfSearchBST(font,offset)) == NULL)	{	    /* if the glyph is not in the cache */	    ttfDeleteBST(font,font->gcache->next->offset);	    gcache = font->gcache->next;	    font->gcache->next->offset = offset;	    ttfRotateCache(font);	    ttfLoadGLYF(font->fp,&gcache->glyf,offset);	    ttfInsertBST(font,gcache);	}    return &gcache->glyf;#endif}/* alloc GlyphCache headers */static GlyphCachePtr ttfAllocCache(TTFontPtr font){    USHORT numCache = font->numCacheElements+1;    GlyphCachePtr gcache;    if ((gcache = (GlyphCachePtr) calloc(numCache,sizeof(GlyphCache))) == NULL)	{	    ttfError("Out of Memory");	    return NULL;	}    return gcache;}/* threading glyph cache headers */static void ttfInitCache(TTFontPtr font){    USHORT i,numCache = font->numCacheElements;    GlyphCachePtr cur,tmp;    cur = tmp = font->gcache;        tmp++;    /* there are numGlyph+1 of cache header, the first one is for     * mark as the head and tail of the queue */    for (i=0;i<numCache;i++)	{	    cur->right = cur->left = NULL;	    cur->next = tmp;	    tmp->prev = cur;	    cur = tmp;	    tmp++;	}    /* make the LRU circular */    cur->next = font->gcache;    font->gcache->prev = cur;    /* make the dummy header point to it self on the BST */    font->gcache->left = font->gcache;    font->gcache->offset = 0;}static void ttfFreeCache(TTFontPtr font){    free(font->gcache);}/* move the first element on the LRU the the tail */static void ttfRotateCache(TTFontPtr font){    GlyphCachePtr gcache = font->gcache, tmp = font->gcache->next;    /* remove the first element */    gcache->next = tmp->next;    tmp->next->prev = gcache;    /* add the element to the tail */    tmp->next = gcache;    tmp->prev = gcache->prev;    gcache->prev->next = tmp;    gcache->prev = tmp;}static void ttfAllocCacheData(TTFontPtr font){    USHORT numCache = font->numCacheElements+1;    USHORT maxPoints = font->maxp->maxPoints;    USHORT maxContours = font->maxp->maxContours;    USHORT insLength = font->maxp->maxSizeOfInstructions;          font->gcache->glyf.endPtsOfContours = (USHORT *) calloc(numCache*maxContours,							    sizeof(USHORT));    font->gcache->glyf.instructions = (BYTE *) calloc(numCache*insLength,						      sizeof(BYTE));    font->gcache->glyf.flags = (BYTE *) calloc(numCache*maxPoints,					       sizeof(BYTE));    font->gcache->glyf.xCoordinates = (SHORT *) calloc(numCache*maxPoints,						       sizeof(SHORT));    font->gcache->glyf.yCoordinates = (SHORT *) calloc(numCache*maxPoints,						       sizeof(SHORT));    font->gcache->glyf.comp = NULL;}static void ttfInitCacheData(TTFontPtr font){    USHORT i;    USHORT numCache = font->numCacheElements;    USHORT maxPoints = font->maxp->maxPoints;    USHORT maxContours = font->maxp->maxContours;    USHORT insLength = font->maxp->maxSizeOfInstructions;    GlyphCachePtr cur,tmp;       tmp = font->gcache;    cur = font->gcache->next;    for (i=0;i<numCache;i++)	{	    /* makes the pointer in the cache element point to correct	     * addresses in the data area */	    cur->glyf.endPtsOfContours = tmp->glyf.endPtsOfContours + maxContours;	    cur->glyf.instructions = tmp->glyf.instructions + insLength;	    cur->glyf.flags = tmp->glyf.flags + maxPoints;	    cur->glyf.xCoordinates = tmp->glyf.xCoordinates + maxPoints;	    cur->glyf.yCoordinates = tmp->glyf.yCoordinates + maxPoints;	    tmp = cur;	    cur = cur++;	}}static void ttfFreeCacheData(TTFontPtr font){    USHORT i,numCache = font->numCacheElements;    GlyphCachePtr cur = font->gcache+1;    /* free components of composite glyfs */    for (i=0;i<numCache;i++)	{	    ttfFreeGLYF(&cur->glyf);	    cur++;	}    free(font->gcache->glyf.endPtsOfContours);    free(font->gcache->glyf.instructions);    free(font->gcache->glyf.flags);    free(font->gcache->glyf.xCoordinates);    free(font->gcache->glyf.yCoordinates);}/* code to deal with nonlinear part of glyph cache */static void ttfInsertBST(TTFontPtr font,GlyphCachePtr gcache){    GlyphCachePtr root,parent;        parent = font->gcache;    root = parent->right;    while (root) 	{	    parent = root;	    if (root->offset > gcache->offset)		root = root->left;	    else		root = root->right;	}    if (parent->offset > gcache->offset)	parent->left = gcache;    else	parent->right = gcache;}static GlyphCachePtr ttfSearchBST(TTFontPtr font,ULONG offset){    GlyphCachePtr root = font->gcache->right;    while (root)	{	    if (root->offset == offset)		return root;	    if (root->offset > offset)		root = root->left;	    else		root = root->right;	}    return NULL;    }/* Deleting a node form a BST is a little bit tricky. * Basically, there are three different situations for deleteing a node *   1. The node to delete is a leaf, then just delete the node and make the *      node's parent point to null. *   2. The node has one subtree, the let the node's parent adopt it. *   3. The node has both subtrees, in this situation, there are two  *      alternatives *     a. let the parent adopt one of the subtree and the subtree adopt the  *        other. (delete by merge) *     b. replace the node with its precedeer, and leave the topology almost *        unchanged. */static void ttfDeleteBST(TTFontPtr font,ULONG offset){    GlyphCachePtr root,parent;    parent = font->gcache;    root = parent->right;    /* find the node to delete */    while (root) 	{	    if (root->offset == offset)		break;	    parent = root;	    if (root->offset > offset)		root = root->left;	    else		root = root->right;	}    if (root != NULL)	{	    /* the node to be deleted is on the tree */	    if (root->glyf.numberOfContours < 0)		/* a composite glyf with components */		ttfFreeGLYF(&root->glyf);#ifdef MERGEDELETE	    if (parent == font->gcache)		/* delete root */		merge(&parent->right);	    else if (parent->left == root)		merge(&parent->left);	    else 		merge(&parent->right);#else	    if (parent == font->gcache)		/* delete root */		copy(&parent->right);	    else if (parent->left == root)		copy(&parent->left);	    else 		copy(&parent->right);#endif	    root->left = root->right = NULL;	}    else	; /* the tree is empty or the node is not on the tree */    }static void merge(GlyphCachePtr *root){    GlyphCachePtr tmp;        if ((*root)->right == NULL)	*root = (*root)->left;    else if ((*root)->left == NULL)	*root = (*root)->right;    else	{	    /* the node to be attached has both left and right	     * subtrees */	    tmp = (*root)->left;	    while (tmp->right)		{		    tmp = tmp->right;		}	    tmp->right = (*root)->right;	    *root = (*root)->left;	}}static void copy(GlyphCachePtr *root){    GlyphCachePtr tmp, parent;        if ((*root)->right == NULL)	*root = (*root)->left;    else if ((*root)->left == NULL)	*root = (*root)->right;    else	{	    tmp = (*root)->left;	    parent = *root;	    while (tmp->right)		{		    parent = tmp;		    tmp = tmp->right;		}	    tmp->right = (*root)->right;	    if (parent != *root)		{		    parent->right = tmp->left;		    tmp->left = parent;		}	    *root = tmp;	}}