ReactOS  0.4.15-dev-1384-g878186b
ftccache.c
Go to the documentation of this file.
1 /***************************************************************************/
2 /* */
3 /* ftccache.c */
4 /* */
5 /* The FreeType internal cache interface (body). */
6 /* */
7 /* Copyright 2000-2018 by */
8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */
9 /* */
10 /* This file is part of the FreeType project, and may only be used, */
11 /* modified, and distributed under the terms of the FreeType project */
12 /* license, LICENSE.TXT. By continuing to use, modify, or distribute */
13 /* this file you indicate that you have read the license and */
14 /* understand and accept it fully. */
15 /* */
16 /***************************************************************************/
17 
18 
19 #include <ft2build.h>
20 #include "ftcmanag.h"
21 #include FT_INTERNAL_OBJECTS_H
22 #include FT_INTERNAL_DEBUG_H
23 
24 #include "ftccback.h"
25 #include "ftcerror.h"
26 
27 #undef FT_COMPONENT
28 #define FT_COMPONENT trace_cache
29 
30 
31 #define FTC_HASH_MAX_LOAD 2
32 #define FTC_HASH_MIN_LOAD 1
33 #define FTC_HASH_SUB_LOAD ( FTC_HASH_MAX_LOAD - FTC_HASH_MIN_LOAD )
34 
35  /* this one _must_ be a power of 2! */
36 #define FTC_HASH_INITIAL_SIZE 8
37 
38 
39  /*************************************************************************/
40  /*************************************************************************/
41  /***** *****/
42  /***** CACHE NODE DEFINITIONS *****/
43  /***** *****/
44  /*************************************************************************/
45  /*************************************************************************/
46 
47  /* add a new node to the head of the manager's circular MRU list */
48  static void
50  FTC_Manager manager )
51  {
52  void *nl = &manager->nodes_list;
53 
54 
56  (FTC_MruNode)node );
57  manager->num_nodes++;
58  }
59 
60 
61  /* remove a node from the manager's MRU list */
62  static void
64  FTC_Manager manager )
65  {
66  void *nl = &manager->nodes_list;
67 
68 
70  (FTC_MruNode)node );
71  manager->num_nodes--;
72  }
73 
74 
75 #ifndef FTC_INLINE
76 
77  /* move a node to the head of the manager's MRU list */
78  static void
79  ftc_node_mru_up( FTC_Node node,
80  FTC_Manager manager )
81  {
83  (FTC_MruNode)node );
84  }
85 
86 
87  /* get a top bucket for specified hash from cache,
88  * body for FTC_NODE_TOP_FOR_HASH( cache, hash )
89  */
91  ftc_get_top_node_for_hash( FTC_Cache cache,
92  FT_Offset hash )
93  {
94  FTC_Node* pnode;
95  FT_Offset idx;
96 
97 
98  idx = hash & cache->mask;
99  if ( idx < cache->p )
100  idx = hash & ( 2 * cache->mask + 1 );
101  pnode = cache->buckets + idx;
102  return pnode;
103  }
104 
105 #endif /* !FTC_INLINE */
106 
107 
108  /* Note that this function cannot fail. If we cannot re-size the
109  * buckets array appropriately, we simply degrade the hash table's
110  * performance!
111  */
112  static void
114  {
115  for (;;)
116  {
117  FTC_Node node, *pnode;
118  FT_UFast p = cache->p;
119  FT_UFast mask = cache->mask;
120  FT_UFast count = mask + p + 1; /* number of buckets */
121 
122 
123  /* do we need to shrink the buckets array? */
124  if ( cache->slack < 0 )
125  {
126  FTC_Node new_list = NULL;
127 
128 
129  /* try to expand the buckets array _before_ splitting
130  * the bucket lists
131  */
132  if ( p >= mask )
133  {
134  FT_Memory memory = cache->memory;
135  FT_Error error;
136 
137 
138  /* if we can't expand the array, leave immediately */
139  if ( FT_RENEW_ARRAY( cache->buckets,
140  ( mask + 1 ) * 2, ( mask + 1 ) * 4 ) )
141  break;
142  }
143 
144  /* split a single bucket */
145  pnode = cache->buckets + p;
146 
147  for (;;)
148  {
149  node = *pnode;
150  if ( !node )
151  break;
152 
153  if ( node->hash & ( mask + 1 ) )
154  {
155  *pnode = node->link;
156  node->link = new_list;
157  new_list = node;
158  }
159  else
160  pnode = &node->link;
161  }
162 
163  cache->buckets[p + mask + 1] = new_list;
164 
165  cache->slack += FTC_HASH_MAX_LOAD;
166 
167  if ( p >= mask )
168  {
169  cache->mask = 2 * mask + 1;
170  cache->p = 0;
171  }
172  else
173  cache->p = p + 1;
174  }
175 
176  /* do we need to expand the buckets array? */
177  else if ( cache->slack > (FT_Long)count * FTC_HASH_SUB_LOAD )
178  {
179  FT_UFast old_index = p + mask;
180  FTC_Node* pold;
181 
182 
183  if ( old_index + 1 <= FTC_HASH_INITIAL_SIZE )
184  break;
185 
186  if ( p == 0 )
187  {
188  FT_Memory memory = cache->memory;
189  FT_Error error;
190 
191 
192  /* if we can't shrink the array, leave immediately */
193  if ( FT_RENEW_ARRAY( cache->buckets,
194  ( mask + 1 ) * 2, mask + 1 ) )
195  break;
196 
197  cache->mask >>= 1;
198  p = cache->mask;
199  }
200  else
201  p--;
202 
203  pnode = cache->buckets + p;
204  while ( *pnode )
205  pnode = &(*pnode)->link;
206 
207  pold = cache->buckets + old_index;
208  *pnode = *pold;
209  *pold = NULL;
210 
211  cache->slack -= FTC_HASH_MAX_LOAD;
212  cache->p = p;
213  }
214 
215  /* otherwise, the hash table is balanced */
216  else
217  break;
218  }
219  }
220 
221 
222  /* remove a node from its cache's hash table */
223  static void
225  FTC_Cache cache )
226  {
227  FTC_Node *pnode = FTC_NODE_TOP_FOR_HASH( cache, node0->hash );
228 
229 
230  for (;;)
231  {
232  FTC_Node node = *pnode;
233 
234 
235  if ( !node )
236  {
237  FT_TRACE0(( "ftc_node_hash_unlink: unknown node\n" ));
238  return;
239  }
240 
241  if ( node == node0 )
242  break;
243 
244  pnode = &(*pnode)->link;
245  }
246 
247  *pnode = node0->link;
248  node0->link = NULL;
249 
250  cache->slack++;
252  }
253 
254 
255  /* add a node to the `top' of its cache's hash table */
256  static void
258  FTC_Cache cache )
259  {
260  FTC_Node *pnode = FTC_NODE_TOP_FOR_HASH( cache, node->hash );
261 
262 
263  node->link = *pnode;
264  *pnode = node;
265 
266  cache->slack--;
268  }
269 
270 
271  /* remove a node from the cache manager */
272  FT_LOCAL_DEF( void )
274  FTC_Manager manager )
275  {
277 
278 
279 #ifdef FT_DEBUG_ERROR
280  /* find node's cache */
281  if ( node->cache_index >= manager->num_caches )
282  {
283  FT_TRACE0(( "ftc_node_destroy: invalid node handle\n" ));
284  return;
285  }
286 #endif
287 
288  cache = manager->caches[node->cache_index];
289 
290 #ifdef FT_DEBUG_ERROR
291  if ( !cache )
292  {
293  FT_TRACE0(( "ftc_node_destroy: invalid node handle\n" ));
294  return;
295  }
296 #endif
297 
298  manager->cur_weight -= cache->clazz.node_weight( node, cache );
299 
300  /* remove node from mru list */
301  ftc_node_mru_unlink( node, manager );
302 
303  /* remove node from cache's hash table */
305 
306  /* now finalize it */
307  cache->clazz.node_free( node, cache );
308 
309 #if 0
310  /* check, just in case of general corruption :-) */
311  if ( manager->num_nodes == 0 )
312  FT_TRACE0(( "ftc_node_destroy: invalid cache node count (%d)\n",
313  manager->num_nodes ));
314 #endif
315  }
316 
317 
318  /*************************************************************************/
319  /*************************************************************************/
320  /***** *****/
321  /***** ABSTRACT CACHE CLASS *****/
322  /***** *****/
323  /*************************************************************************/
324  /*************************************************************************/
325 
326 
329  {
330  return ftc_cache_init( cache );
331  }
332 
333 
336  {
337  FT_Memory memory = cache->memory;
338  FT_Error error;
339 
340 
341  cache->p = 0;
342  cache->mask = FTC_HASH_INITIAL_SIZE - 1;
344 
345  (void)FT_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE * 2 );
346  return error;
347  }
348 
349 
350  static void
352  {
353  if ( cache && cache->buckets )
354  {
355  FTC_Manager manager = cache->manager;
356  FT_UFast i;
357  FT_UFast count;
358 
359 
360  count = cache->p + cache->mask + 1;
361 
362  for ( i = 0; i < count; i++ )
363  {
364  FTC_Node *pnode = cache->buckets + i, next, node = *pnode;
365 
366 
367  while ( node )
368  {
369  next = node->link;
370  node->link = NULL;
371 
372  /* remove node from mru list */
373  ftc_node_mru_unlink( node, manager );
374 
375  /* now finalize it */
376  manager->cur_weight -= cache->clazz.node_weight( node, cache );
377 
378  cache->clazz.node_free( node, cache );
379  node = next;
380  }
381  cache->buckets[i] = NULL;
382  }
384  }
385  }
386 
387 
388  FT_LOCAL_DEF( void )
390  {
391  if ( cache->memory )
392  {
393  FT_Memory memory = cache->memory;
394 
395 
397 
398  FT_FREE( cache->buckets );
399  cache->mask = 0;
400  cache->p = 0;
401  cache->slack = 0;
402 
403  cache->memory = NULL;
404  }
405  }
406 
407 
408  FT_LOCAL_DEF( void )
410  {
412  }
413 
414 
415  static void
417  FT_Offset hash,
418  FTC_Node node )
419  {
420  node->hash = hash;
421  node->cache_index = (FT_UInt16)cache->index;
422  node->ref_count = 0;
423 
425  ftc_node_mru_link( node, cache->manager );
426 
427  {
428  FTC_Manager manager = cache->manager;
429 
430 
431  manager->cur_weight += cache->clazz.node_weight( node, cache );
432 
433  if ( manager->cur_weight >= manager->max_weight )
434  {
435  node->ref_count++;
436  FTC_Manager_Compress( manager );
437  node->ref_count--;
438  }
439  }
440  }
441 
442 
445  FT_Offset hash,
447  FTC_Node *anode )
448  {
449  FT_Error error;
450  FTC_Node node;
451 
452 
453  /*
454  * We use the FTC_CACHE_TRYLOOP macros to support out-of-memory
455  * errors (OOM) correctly, i.e., by flushing the cache progressively
456  * in order to make more room.
457  */
458 
460  {
461  error = cache->clazz.node_new( &node, query, cache );
462  }
464 
465  if ( error )
466  node = NULL;
467  else
468  {
469  /* don't assume that the cache has the same number of buckets, since
470  * our allocation request might have triggered global cache flushing
471  */
473  }
474 
475  *anode = node;
476  return error;
477  }
478 
479 
480 #ifndef FTC_INLINE
481 
483  FTC_Cache_Lookup( FTC_Cache cache,
484  FT_Offset hash,
486  FTC_Node *anode )
487  {
488  FTC_Node* bucket;
489  FTC_Node* pnode;
490  FTC_Node node;
492  FT_Bool list_changed = FALSE;
493 
494  FTC_Node_CompareFunc compare = cache->clazz.node_compare;
495 
496 
497  if ( !cache || !anode )
498  return FT_THROW( Invalid_Argument );
499 
500  /* Go to the `top' node of the list sharing same masked hash */
501  bucket = pnode = FTC_NODE_TOP_FOR_HASH( cache, hash );
502 
503  /* Lookup a node with exactly same hash and queried properties. */
504  /* NOTE: _nodcomp() may change the linked list to reduce memory. */
505  for (;;)
506  {
507  node = *pnode;
508  if ( !node )
509  goto NewNode;
510 
511  if ( node->hash == hash &&
512  compare( node, query, cache, &list_changed ) )
513  break;
514 
515  pnode = &node->link;
516  }
517 
518  if ( list_changed )
519  {
520  /* Update bucket by modified linked list */
521  bucket = pnode = FTC_NODE_TOP_FOR_HASH( cache, hash );
522 
523  /* Update pnode by modified linked list */
524  while ( *pnode != node )
525  {
526  if ( !*pnode )
527  {
528  FT_ERROR(( "FTC_Cache_Lookup: oops!!! node missing\n" ));
529  goto NewNode;
530  }
531  else
532  pnode = &((*pnode)->link);
533  }
534  }
535 
536  /* Reorder the list to move the found node to the `top' */
537  if ( node != *bucket )
538  {
539  *pnode = node->link;
540  node->link = *bucket;
541  *bucket = node;
542  }
543 
544  /* move to head of MRU list */
545  {
546  FTC_Manager manager = cache->manager;
547 
548 
549  if ( node != manager->nodes_list )
550  ftc_node_mru_up( node, manager );
551  }
552  *anode = node;
553 
554  return error;
555 
556  NewNode:
557  return FTC_Cache_NewNode( cache, hash, query, anode );
558  }
559 
560 #endif /* !FTC_INLINE */
561 
562 
563  FT_LOCAL_DEF( void )
565  FTC_FaceID face_id )
566  {
567  FT_UFast i, count;
568  FTC_Manager manager = cache->manager;
569  FTC_Node frees = NULL;
570 
571 
572  count = cache->p + cache->mask + 1;
573  for ( i = 0; i < count; i++ )
574  {
575  FTC_Node* bucket = cache->buckets + i;
576  FTC_Node* pnode = bucket;
577 
578 
579  for (;;)
580  {
581  FTC_Node node = *pnode;
582  FT_Bool list_changed = FALSE;
583 
584 
585  if ( !node )
586  break;
587 
588  if ( cache->clazz.node_remove_faceid( node, face_id,
589  cache, &list_changed ) )
590  {
591  *pnode = node->link;
592  node->link = frees;
593  frees = node;
594  }
595  else
596  pnode = &node->link;
597  }
598  }
599 
600  /* remove all nodes in the free list */
601  while ( frees )
602  {
603  FTC_Node node;
604 
605 
606  node = frees;
607  frees = node->link;
608 
609  manager->cur_weight -= cache->clazz.node_weight( node, cache );
610  ftc_node_mru_unlink( node, manager );
611 
612  cache->clazz.node_free( node, cache );
613 
614  cache->slack++;
615  }
616 
618  }
619 
620 
621 /* END */
static void ftc_node_hash_link(FTC_Node node, FTC_Cache cache)
Definition: ftccache.c:257
Definition: cache.c:48
Definition: bug.cpp:7
int FT_Error
Definition: fttypes.h:300
FT_Bool(* FTC_Node_CompareFunc)(FTC_Node node, FT_Pointer key, FTC_Cache cache, FT_Bool *list_changed)
Definition: ftccache.h:110
static void ftc_cache_add(FTC_Cache cache, FT_Offset hash, FTC_Node node)
Definition: ftccache.c:416
#define FTC_CACHE_TRYLOOP_END(list_changed)
Definition: ftccache.h:323
signed long FT_Long
Definition: fttypes.h:242
FT_UInt num_nodes
Definition: ftcmanag.h:99
struct png_info_def **typedef void(__cdecl typeof(png_destroy_read_struct))(struct png_struct_def **
Definition: typeof.h:49
#define error(str)
Definition: mkdosfs.c:1605
unsigned short FT_UInt16
Definition: ftconfig.h:181
FTC_Manager_Compress(FTC_Manager manager)
Definition: ftcmanag.c:538
GLuint GLuint GLsizei count
Definition: gl.h:1545
FTC_Node link
Definition: ftccache.h:61
FT_Offset max_weight
Definition: ftcmanag.h:97
typedefFT_BEGIN_HEADER struct FTC_MruNodeRec_ * FTC_MruNode
Definition: ftcmru.h:61
return FT_Err_Ok
Definition: ftbbox.c:511
static char memory[1024 *256]
Definition: process.c:116
FT_Offset cur_weight
Definition: ftcmanag.h:98
FTC_MruNode_Remove(FTC_MruNode *plist, FTC_MruNode node)
Definition: ftcmru.c:122
#define FTC_CACHE_TRYLOOP(cache)
Definition: ftccache.h:312
FT_BEGIN_HEADER typedef FT_Pointer FTC_FaceID
Definition: ftcache.h:171
ftc_cache_init(FTC_Cache cache)
Definition: ftccache.c:335
FT_BEGIN_HEADER typedef unsigned char FT_Bool
Definition: fttypes.h:108
struct node node
GLenum GLint GLuint mask
Definition: glext.h:6028
#define FT_ERROR(varformat)
Definition: ftdebug.h:181
#define FALSE
Definition: types.h:117
int hash
Definition: main.c:58
#define FT_THROW(e)
Definition: ftdebug.h:213
unsigned int idx
Definition: utils.c:41
FTC_Cache_Done(FTC_Cache cache)
Definition: ftccache.c:409
#define FTC_HASH_MAX_LOAD
Definition: ftccache.c:31
#define FT_FREE(ptr)
Definition: ftmemory.h:329
#define FTC_HASH_SUB_LOAD
Definition: ftccache.c:33
#define FTC_HASH_INITIAL_SIZE
Definition: ftccache.c:36
#define FT_LOCAL_DEF(x)
Definition: ftconfig.h:388
static void ftc_cache_resize(FTC_Cache cache)
Definition: ftccache.c:113
#define FT_TRACE0(varformat)
Definition: ftdebug.h:157
FTC_MruNode_Up(FTC_MruNode *plist, FTC_MruNode node)
Definition: ftcmru.c:73
#define FTC_NODE_TOP_FOR_HASH(cache, hash)
Definition: ftccache.h:76
static void ftc_node_hash_unlink(FTC_Node node0, FTC_Cache cache)
Definition: ftccache.c:224
#define FT_RENEW_ARRAY(ptr, curcnt, newcnt)
Definition: ftmemory.h:336
ftc_node_destroy(FTC_Node node, FTC_Manager manager)
Definition: ftccache.c:273
static IOleCache * cache
Definition: ole2.c:75
static void ftc_node_mru_link(FTC_Node node, FTC_Manager manager)
Definition: ftccache.c:49
typedefFT_BEGIN_HEADER struct FT_MemoryRec_ * FT_Memory
Definition: ftsystem.h:66
#define FT_NEW_ARRAY(ptr, count)
Definition: ftmemory.h:333
FTC_Cache_NewNode(FTC_Cache cache, FT_Offset hash, FT_Pointer query, FTC_Node *anode)
Definition: ftccache.c:444
FTC_Cache_RemoveFaceID(FTC_Cache cache, FTC_FaceID face_id)
Definition: ftccache.c:564
static unsigned __int64 next
Definition: rand_nt.c:6
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
FTC_Node nodes_list
Definition: ftcmanag.h:96
#define NULL
Definition: types.h:112
FT_Offset hash
Definition: ftccache.h:62
static void FTC_Cache_Clear(FTC_Cache cache)
Definition: ftccache.c:351
FTC_Cache_Init(FTC_Cache cache)
Definition: ftccache.c:328
GLfloat GLfloat p
Definition: glext.h:8902
Definition: _hash_fun.h:40
ftc_cache_done(FTC_Cache cache)
Definition: ftccache.c:389
static void ftc_node_mru_unlink(FTC_Node node, FTC_Manager manager)
Definition: ftccache.c:63
size_t FT_Offset
Definition: fttypes.h:324
FTC_MruNode_Prepend(FTC_MruNode *plist, FTC_MruNode node)
Definition: ftcmru.c:29
Definition: dlist.c:348