w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

gcache.c
Go to the documentation of this file.
1 /*
2  * gcache.c -- Provide the cache mechanicsm for outlines
3  * Copyright (C) 1996 Li-Da Lho, All right reserved
4  *
5  * This file is a little bit more complicated, the structure of the cache is
6  * described as fellow:
7  * Basically the cache can be divided onto two parts, the first one is a
8  * linear part which is a least recently utilitied list (LRU),
9  * the second part is the nonlinear one which is a binary serach tree.
10  * Normally each cache element is on the LRU as well as on the BST.
11  * Those glyph elements are allocated at once as an array of glyph cache
12  * elements at the init phase of glyph cache.
13  *
14  * font->gcache--
15  * |
16  * ________|
17  * |
18  * v
19  * ------------------------------------------------------------------
20  * |element 0| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ...
21  * ------------------------------------------------------------------
22  * The first element of the glyph cache array serves as a dummy header
23  * for two purposes, one is for the head and tail of the LRU, the other is
24  * to point to the root of the BST. As a pointer to the root of the
25  * BST, the right subtree points to the root of the BST while the left one is
26  * not used and arbitrarly points to itself.
27  *
28  * After initialization, all the glyph cache element are on the LRU but
29  * none of them is on the BST.
30  *
31  * |-----------------------------------------------------------|
32  * | ------------- ------ ------ |
33  * |-> |head & tail| <-----> | |<-----> ...<----->| | <--|
34  * ------------- ------ ------
35  * / \ / \ / \
36  * / \ / \ / \
37  * left=self right=root left right left right
38  *
39  * The cached data are pointed by the entries of the glyph cache element
40  * in a strait forward fashion.
41  *
42  * |-----------------------------------------------------------|
43  * | ------------- ------ ------ |
44  * |-> |head & tail| <-----> | |<-----> ...<----->| | <--|
45  * ------------- ------ ------
46  * | | -------------|--|--------------------------------
47  * | |---->| | |-> array for flag, instruction|
48  * | -------------|-----------------------------------
49  * | -------------|-----------------------------------
50  * |------->| |----> xcoordinates, ycoordinates|
51  * -------------------------------------------------
52  * Implementation in this way is effecient for the reason that when we
53  * need to free the cache, we only need to do the two things
54  * 1. free the data pointed by the entries in the dummy header
55  * 2. free the dummy header
56  *
57  * Every time a glyph outline is required and ttfLoadGlyphCached is called,
58  * the glyph is searched on the BST with its offset as a key.
59  * If the glyph is on the BST then the address of the glyph cache is returned
60  * and the glyph cache is moved to the tail of the LRU such that the order of
61  * LRU is mantained.
62  * When the glyph required is not on the BST, something more complicated should
63  * be done.
64  * 1. Remove the first element on the LRU from the BST.
65  * 2. Load the glyph data to the cache element.
66  * 3. Insert the element back to the BST.
67  * 4. Move the element to the tail of the LRU.
68  *
69  * The only problem remain is how to deal with composite components.
70  * The asnwer simply is not to support cache for composite components at the
71  * current stage for the two reasons:
72  * 1. It will makes the code an order of magnitude more complicate to support
73  * composite glyf cache.
74  * 2. The space occupied by composite glyf is not very much
75  *
76  * It is not clear right now if it is wise to add tree balancing code.
77  * The overhaed introduced by BST seems minimal for 256 elements cache.
78  */
79 #ifdef HAVE_CONFIG_H
80 #include <config.h>
81 #endif
82 
83 #include <stdio.h>
84 #include <stdlib.h>
85 #include <string.h>
86 #include "ttf.h"
87 #include "ttfutil.h"
88 
89 /* $Id: gcache.c,v 1.1.1.1 1998/06/05 07:47:52 robert Exp $ */
90 
91 static void ttfInitCache(TTFontPtr font);
92 static void ttfFreeCache(TTFontPtr font);
93 static void ttfRotateCache(TTFontPtr font);
94 static void ttfAllocCacheData(TTFontPtr font);
95 static void ttfInitCacheData(TTFontPtr font);
96 static void ttfFreeCacheData(TTFontPtr font);
97 static void ttfInsertBST(TTFontPtr font,GlyphCachePtr gcache);
100 #ifdef MERGEDELETE
101 static void merge(GlyphCachePtr *root);
102 #endif
103 static void copy(GlyphCachePtr *root);
104 
106 {
107  /* this should be made configurable */
108  if (font->maxp->numGlyphs > 256)
109  font->numCacheElements = 128;
110  else
111  font->numCacheElements = 64;
112 
113  font->gcache = XCALLOC (font->numCacheElements+1, GlyphCache);
115 
118 }
119 
121 {
123  ttfFreeCache(font);
124 }
125 
126 /* provide cache mechanism for glyph */
128 {
129 #ifdef OLDCODE
130  GLYFPtr glyf;
131 
132  glyf = &(font->gcache->next->glyf);
133  font->gcache->next->offset = offset;
135  ttfLoadGLYF(font->fp,glyf,offset);
136  return glyf;
137 
138 #else
139  GlyphCachePtr gcache;
140 
141  if ((gcache = ttfSearchBST(font,offset)) == NULL)
142  {
143  /* if the glyph is not in the cache */
144  ttfDeleteBST(font,font->gcache->next->offset);
145  gcache = font->gcache->next;
146  font->gcache->next->offset = offset;
148  ttfLoadGLYF(font->fp,&gcache->glyf,offset);
149  ttfInsertBST(font,gcache);
150  }
151  return &gcache->glyf;
152 #endif
153 }
154 
155 /* threading glyph cache headers */
157 {
158  USHORT i,numCache = font->numCacheElements;
159  GlyphCachePtr cur,tmp;
160 
161  cur = tmp = font->gcache;
162  tmp++;
163  /* there are numGlyph+1 of cache header, the first one is for
164  * mark as the head and tail of the queue */
165  for (i=0;i<numCache;i++)
166  {
167  cur->right = cur->left = NULL;
168  cur->next = tmp;
169  tmp->prev = cur;
170  cur = tmp;
171  tmp++;
172  }
173 
174  /* make the LRU circular */
175  cur->next = font->gcache;
176  font->gcache->prev = cur;
177 
178  /* make the dummy header point to it self on the BST */
179  font->gcache->left = font->gcache;
180  font->gcache->offset = 0;
181 }
183 {
184  free(font->gcache);
185 }
186 /* move the first element on the LRU the the tail */
188 {
189  GlyphCachePtr gcache = font->gcache, tmp = font->gcache->next;
190 
191  /* remove the first element */
192  gcache->next = tmp->next;
193  tmp->next->prev = gcache;
194  /* add the element to the tail */
195  tmp->next = gcache;
196  tmp->prev = gcache->prev;
197  gcache->prev->next = tmp;
198  gcache->prev = tmp;
199 }
201 {
202  USHORT numCache = font->numCacheElements+1;
203  USHORT maxPoints = font->maxp->maxPoints;
204  USHORT maxContours = font->maxp->maxContours;
205  USHORT insLength = font->maxp->maxSizeOfInstructions;
206 
207  font->gcache->glyf.endPtsOfContours = XCALLOC (numCache*maxContours, USHORT);
208  font->gcache->glyf.instructions = XCALLOC (numCache*insLength, BYTE);
209  font->gcache->glyf.flags = XCALLOC (numCache*maxPoints, BYTE);
210  font->gcache->glyf.xCoordinates = XCALLOC (numCache*maxPoints, SHORT);
211  font->gcache->glyf.yCoordinates = XCALLOC (numCache*maxPoints, SHORT);
212  font->gcache->glyf.comp = NULL;
213 }
215 {
216  USHORT i;
217  USHORT numCache = font->numCacheElements;
218  USHORT maxPoints = font->maxp->maxPoints;
219  USHORT maxContours = font->maxp->maxContours;
220  USHORT insLength = font->maxp->maxSizeOfInstructions;
221  GlyphCachePtr cur,tmp;
222 
223  tmp = font->gcache;
224  cur = font->gcache->next;
225 
226  for (i=0;i<numCache;i++)
227  {
228  /* makes the pointer in the cache element point to correct
229  * addresses in the data area */
230  cur->glyf.endPtsOfContours = tmp->glyf.endPtsOfContours + maxContours;
231  cur->glyf.instructions = tmp->glyf.instructions + insLength;
232  cur->glyf.flags = tmp->glyf.flags + maxPoints;
233  cur->glyf.xCoordinates = tmp->glyf.xCoordinates + maxPoints;
234  cur->glyf.yCoordinates = tmp->glyf.yCoordinates + maxPoints;
235  tmp = cur++;
236  }
237 }
239 {
240  USHORT i,numCache = font->numCacheElements;
241  GlyphCachePtr cur = font->gcache+1;
242 
243  /* free components of composite glyfs */
244  for (i=0;i<numCache;i++)
245  {
246  ttfFreeGLYF(&cur->glyf);
247  cur++;
248  }
249  free(font->gcache->glyf.endPtsOfContours);
250  free(font->gcache->glyf.instructions);
251  free(font->gcache->glyf.flags);
252  free(font->gcache->glyf.xCoordinates);
253  free(font->gcache->glyf.yCoordinates);
254 }
255 
256 /* code to deal with nonlinear part of glyph cache */
258 {
260 
261  parent = font->gcache;
262  root = parent->right;
263 
264  while (root)
265  {
266  parent = root;
267  if (root->offset > gcache->offset)
268  root = root->left;
269  else
270  root = root->right;
271  }
272 
273  if (parent->offset > gcache->offset)
274  parent->left = gcache;
275  else
276  parent->right = gcache;
277 }
279 {
280  GlyphCachePtr root = font->gcache->right;
281 
282  while (root)
283  {
284  if (root->offset == offset)
285  return root;
286  if (root->offset > offset)
287  root = root->left;
288  else
289  root = root->right;
290  }
291  return NULL;
292 }
293 /* Deleting a node form a BST is a little bit tricky.
294  * Basically, there are three different situations for deleteing a node
295  * 1. The node to delete is a leaf, then just delete the node and make the
296  * node's parent point to null.
297  * 2. The node has one subtree, the let the node's parent adopt it.
298  * 3. The node has both subtrees, in this situation, there are two
299  * alternatives
300  * a. let the parent adopt one of the subtree and the subtree adopt the
301  * other. (delete by merge)
302  * b. replace the node with its precedeer, and leave the topology almost
303  * unchanged.
304  */
306 {
308 
309  parent = font->gcache;
310  root = parent->right;
311 
312  /* find the node to delete */
313  while (root)
314  {
315  if (root->offset == offset)
316  break;
317  parent = root;
318  if (root->offset > offset)
319  root = root->left;
320  else
321  root = root->right;
322  }
323  if (root != NULL)
324  {
325  /* the node to be deleted is on the tree */
326  if (root->glyf.numberOfContours < 0)
327  /* a composite glyf with components */
328  ttfFreeGLYF(&root->glyf);
329 
330 #ifdef MERGEDELETE
331  if (parent == font->gcache)
332  /* delete root */
333  merge(&parent->right);
334  else if (parent->left == root)
335  merge(&parent->left);
336  else
337  merge(&parent->right);
338 #else
339  if (parent == font->gcache)
340  /* delete root */
341  copy(&parent->right);
342  else if (parent->left == root)
343  copy(&parent->left);
344  else
345  copy(&parent->right);
346 #endif
347 
348  root->left = root->right = NULL;
349  }
350  else
351  ; /* the tree is empty or the node is not on the tree */
352 
353 }
354 
355 #ifdef MERGEDELETE
356 static void merge(GlyphCachePtr *root)
357 {
358  GlyphCachePtr tmp;
359 
360  if ((*root)->right == NULL)
361  *root = (*root)->left;
362  else if ((*root)->left == NULL)
363  *root = (*root)->right;
364  else
365  {
366  /* the node to be attached has both left and right
367  * subtrees */
368  tmp = (*root)->left;
369  while (tmp->right)
370  {
371  tmp = tmp->right;
372  }
373  tmp->right = (*root)->right;
374  *root = (*root)->left;
375  }
376 }
377 #endif
378 static void copy(GlyphCachePtr *root)
379 {
380  GlyphCachePtr tmp, parent;
381 
382  if ((*root)->right == NULL)
383  *root = (*root)->left;
384  else if ((*root)->left == NULL)
385  *root = (*root)->right;
386  else
387  {
388  tmp = (*root)->left;
389  parent = *root;
390  while (tmp->right)
391  {
392  parent = tmp;
393  tmp = tmp->right;
394  }
395  tmp->right = (*root)->right;
396  if (parent != *root)
397  {
398  parent->right = tmp->left;
399  tmp->left = parent;
400  }
401  *root = tmp;
402  }
403 }
static point_t cur
Definition: backend_eps.c:108
#define free(a)
Definition: decNumber.cpp:310
const unsigned int maxPoints
Definition: drvbase.h:80
static void ttfAllocCacheData(TTFontPtr font)
Definition: gcache.c:200
static void ttfInitCacheData(TTFontPtr font)
Definition: gcache.c:214
static void ttfInitCache(TTFontPtr font)
Definition: gcache.c:156
static void ttfInsertBST(TTFontPtr font, GlyphCachePtr gcache)
Definition: gcache.c:257
static void ttfFreeCache(TTFontPtr font)
Definition: gcache.c:182
static void ttfFreeCacheData(TTFontPtr font)
Definition: gcache.c:238
static void copy(GlyphCachePtr *root)
Definition: gcache.c:378
static void ttfRotateCache(TTFontPtr font)
Definition: gcache.c:187
void ttfCleanUpGlyphCache(TTFontPtr font)
Definition: gcache.c:120
void ttfInitGlyphCache(TTFontPtr font)
Definition: gcache.c:105
static GlyphCachePtr ttfSearchBST(TTFontPtr font, ULONG offset)
Definition: gcache.c:278
GLYFPtr ttfLoadGlyphCached(TTFontPtr font, ULONG offset)
Definition: gcache.c:127
static void ttfDeleteBST(TTFontPtr font, ULONG offset)
Definition: gcache.c:305
#define NULL
Definition: ftobjs.h:61
small capitals from c petite p scientific i
Definition: afcover.h:80
else
Definition: ftgrays.c:1658
signed short SHORT
Definition: sfnt.h:37
unsigned char BYTE
Definition: sfnt.h:34
unsigned short USHORT
Definition: sfnt.h:36
#define root
Definition: ctangleboot.c:69
void ttfFreeGLYF(GLYFPtr glyf)
Definition: glyf.c:72
void ttfLoadGLYF(FILE *fp, GLYFPtr glyf, ULONG offset)
Definition: glyf.c:41
unsigned long ULONG
Definition: pdfgen.h:158
static int offset
Definition: ppmtogif.c:642
#define parent(a, t)
Definition: interp.c:105
Definition: tables.h:253
BYTE * flags
Definition: tables.h:263
SHORT * yCoordinates
Definition: tables.h:267
USHORT * endPtsOfContours
Definition: tables.h:260
SHORT * xCoordinates
Definition: tables.h:266
BYTE * instructions
Definition: tables.h:262
Definition: ttf.h:110
Definition: gcache.h:9
ULONG offset
Definition: gcache.h:10
struct _gcache * right
Definition: gcache.h:15
GLYF glyf
Definition: gcache.h:17
struct _gcache * prev
Definition: gcache.h:13
struct _gcache * next
Definition: gcache.h:13
struct _gcache * left
Definition: gcache.h:15
Definition: pbmfont.h:11
ubyte flags
Definition: gf2pbm.c:117
#define XCALLOC(n, t)
Definition: ttfutil.h:59