• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /****************************************************************************
2  *
3  * ftccache.h
4  *
5  *   FreeType internal cache interface (specification).
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 #ifndef FTCCACHE_H_
20 #define FTCCACHE_H_
21 
22 
23 #include "ftcmru.h"
24 
25 FT_BEGIN_HEADER
26 
27 #define FTC_FACE_ID_HASH( i )                                  \
28          ( ( (FT_Offset)(i) >> 3 ) ^ ( (FT_Offset)(i) << 7 ) )
29 
30   /* handle to cache object */
31   typedef struct FTC_CacheRec_*  FTC_Cache;
32 
33   /* handle to cache class */
34   typedef const struct FTC_CacheClassRec_*  FTC_CacheClass;
35 
36 
37   /*************************************************************************/
38   /*************************************************************************/
39   /*****                                                               *****/
40   /*****                   CACHE NODE DEFINITIONS                      *****/
41   /*****                                                               *****/
42   /*************************************************************************/
43   /*************************************************************************/
44 
45   /**************************************************************************
46    *
47    * Each cache controls one or more cache nodes.  Each node is part of
48    * the global_lru list of the manager.  Its `data' field however is used
49    * as a reference count for now.
50    *
51    * A node can be anything, depending on the type of information held by
52    * the cache.  It can be an individual glyph image, a set of bitmaps
53    * glyphs for a given size, some metrics, etc.
54    *
55    */
56 
57   /* structure size should be 20 bytes on 32-bits machines */
58   typedef struct  FTC_NodeRec_
59   {
60     FTC_MruNodeRec  mru;          /* circular mru list pointer           */
61     FTC_Node        link;         /* used for hashing                    */
62     FT_Offset       hash;         /* used for hashing too                */
63     FT_UShort       cache_index;  /* index of cache the node belongs to  */
64     FT_Short        ref_count;    /* reference count for this node       */
65 
66   } FTC_NodeRec;
67 
68 
69 #define FTC_NODE( x )    ( (FTC_Node)(x) )
70 #define FTC_NODE_P( x )  ( (FTC_Node*)(x) )
71 
72 #define FTC_NODE_NEXT( x )  FTC_NODE( (x)->mru.next )
73 #define FTC_NODE_PREV( x )  FTC_NODE( (x)->mru.prev )
74 
75 #ifdef FTC_INLINE
76 #define FTC_NODE_TOP_FOR_HASH( cache, hash )                      \
77         ( ( cache )->buckets +                                    \
78             ( ( ( ( hash ) &   ( cache )->mask ) < ( cache )->p ) \
79               ? ( ( hash ) & ( ( cache )->mask * 2 + 1 ) )        \
80               : ( ( hash ) &   ( cache )->mask ) ) )
81 #else
82   FT_LOCAL( FTC_Node* )
83   ftc_get_top_node_for_hash( FTC_Cache  cache,
84                              FT_Offset  hash );
85 #define FTC_NODE_TOP_FOR_HASH( cache, hash )             \
86         ftc_get_top_node_for_hash( ( cache ), ( hash ) )
87 #endif
88 
89 
90   /*************************************************************************/
91   /*************************************************************************/
92   /*****                                                               *****/
93   /*****                       CACHE DEFINITIONS                       *****/
94   /*****                                                               *****/
95   /*************************************************************************/
96   /*************************************************************************/
97 
98   /* initialize a new cache node */
99   typedef FT_Error
100   (*FTC_Node_NewFunc)( FTC_Node    *pnode,
101                        FT_Pointer   query,
102                        FTC_Cache    cache );
103 
104   typedef FT_Offset
105   (*FTC_Node_WeightFunc)( FTC_Node   node,
106                           FTC_Cache  cache );
107 
108   /* compare a node to a given key pair */
109   typedef FT_Bool
110   (*FTC_Node_CompareFunc)( FTC_Node    node,
111                            FT_Pointer  key,
112                            FTC_Cache   cache,
113                            FT_Bool*    list_changed );
114 
115 
116   typedef void
117   (*FTC_Node_FreeFunc)( FTC_Node   node,
118                         FTC_Cache  cache );
119 
120   typedef FT_Error
121   (*FTC_Cache_InitFunc)( FTC_Cache  cache );
122 
123   typedef void
124   (*FTC_Cache_DoneFunc)( FTC_Cache  cache );
125 
126 
127   typedef struct  FTC_CacheClassRec_
128   {
129     FTC_Node_NewFunc      node_new;
130     FTC_Node_WeightFunc   node_weight;
131     FTC_Node_CompareFunc  node_compare;
132     FTC_Node_CompareFunc  node_remove_faceid;
133     FTC_Node_FreeFunc     node_free;
134 
135     FT_Offset             cache_size;
136     FTC_Cache_InitFunc    cache_init;
137     FTC_Cache_DoneFunc    cache_done;
138 
139   } FTC_CacheClassRec;
140 
141 
142   /* each cache really implements a dynamic hash table to manage its nodes */
143   typedef struct  FTC_CacheRec_
144   {
145     FT_UFast           p;
146     FT_UFast           mask;
147     FT_Long            slack;
148     FTC_Node*          buckets;
149 
150     FTC_CacheClassRec  clazz;       /* local copy, for speed  */
151 
152     FTC_Manager        manager;
153     FT_Memory          memory;
154     FT_UInt            index;       /* in manager's table     */
155 
156     FTC_CacheClass     org_class;   /* original class pointer */
157 
158   } FTC_CacheRec;
159 
160 
161 #define FTC_CACHE( x )    ( (FTC_Cache)(x) )
162 #define FTC_CACHE_P( x )  ( (FTC_Cache*)(x) )
163 
164 
165   /* default cache initialize */
166   FT_LOCAL( FT_Error )
167   FTC_Cache_Init( FTC_Cache  cache );
168 
169   /* default cache finalizer */
170   FT_LOCAL( void )
171   FTC_Cache_Done( FTC_Cache  cache );
172 
173   /* Call this function to look up the cache.  If no corresponding
174    * node is found, a new one is automatically created.  This function
175    * is capable of flushing the cache adequately to make room for the
176    * new cache object.
177    */
178 
179 #ifndef FTC_INLINE
180   FT_LOCAL( FT_Error )
181   FTC_Cache_Lookup( FTC_Cache   cache,
182                     FT_Offset   hash,
183                     FT_Pointer  query,
184                     FTC_Node   *anode );
185 #endif
186 
187   FT_LOCAL( FT_Error )
188   FTC_Cache_NewNode( FTC_Cache   cache,
189                      FT_Offset   hash,
190                      FT_Pointer  query,
191                      FTC_Node   *anode );
192 
193   /* Remove all nodes that relate to a given face_id.  This is useful
194    * when un-installing fonts.  Note that if a cache node relates to
195    * the face_id but is locked (i.e., has `ref_count > 0'), the node
196    * will _not_ be destroyed, but its internal face_id reference will
197    * be modified.
198    *
199    * The final result will be that the node will never come back
200    * in further lookup requests, and will be flushed on demand from
201    * the cache normally when its reference count reaches 0.
202    */
203   FT_LOCAL( void )
204   FTC_Cache_RemoveFaceID( FTC_Cache   cache,
205                           FTC_FaceID  face_id );
206 
207 
208 #ifdef FTC_INLINE
209 
210 #define FTC_CACHE_LOOKUP_CMP( cache, nodecmp, hash, query, node, error ) \
211   FT_BEGIN_STMNT                                                         \
212     FTC_Node             *_bucket, *_pnode, _node;                       \
213     FTC_Cache             _cache   = FTC_CACHE(cache);                   \
214     FT_Offset             _hash    = (FT_Offset)(hash);                  \
215     FTC_Node_CompareFunc  _nodcomp = (FTC_Node_CompareFunc)(nodecmp);    \
216     FT_Bool               _list_changed = FALSE;                         \
217                                                                          \
218                                                                          \
219     error = FT_Err_Ok;                                                   \
220     node  = NULL;                                                        \
221                                                                          \
222     /* Go to the `top' node of the list sharing same masked hash */      \
223     _bucket = _pnode = FTC_NODE_TOP_FOR_HASH( _cache, _hash );           \
224                                                                          \
225     /* Look up a node with identical hash and queried properties.    */  \
226     /* NOTE: _nodcomp() may change the linked list to reduce memory. */  \
227     for (;;)                                                             \
228     {                                                                    \
229       _node = *_pnode;                                                   \
230       if ( !_node )                                                      \
231         goto NewNode_;                                                   \
232                                                                          \
233       if ( _node->hash == _hash                             &&           \
234            _nodcomp( _node, query, _cache, &_list_changed ) )            \
235         break;                                                           \
236                                                                          \
237       _pnode = &_node->link;                                             \
238     }                                                                    \
239                                                                          \
240     if ( _list_changed )                                                 \
241     {                                                                    \
242       /* Update _bucket by possibly modified linked list */              \
243       _bucket = _pnode = FTC_NODE_TOP_FOR_HASH( _cache, _hash );         \
244                                                                          \
245       /* Update _pnode by possibly modified linked list */               \
246       while ( *_pnode != _node )                                         \
247       {                                                                  \
248         if ( !*_pnode )                                                  \
249         {                                                                \
250           FT_ERROR(( "FTC_CACHE_LOOKUP_CMP: oops!!! node missing\n" ));  \
251           goto NewNode_;                                                 \
252         }                                                                \
253         else                                                             \
254           _pnode = &((*_pnode)->link);                                   \
255       }                                                                  \
256     }                                                                    \
257                                                                          \
258     /* Reorder the list to move the found node to the `top' */           \
259     if ( _node != *_bucket )                                             \
260     {                                                                    \
261       *_pnode     = _node->link;                                         \
262       _node->link = *_bucket;                                            \
263       *_bucket    = _node;                                               \
264     }                                                                    \
265                                                                          \
266     /* Update MRU list */                                                \
267     {                                                                    \
268       FTC_Manager  _manager = _cache->manager;                           \
269       void*        _nl      = &_manager->nodes_list;                     \
270                                                                          \
271                                                                          \
272       if ( _node != _manager->nodes_list )                               \
273         FTC_MruNode_Up( (FTC_MruNode*)_nl,                               \
274                         (FTC_MruNode)_node );                            \
275     }                                                                    \
276     goto Ok_;                                                            \
277                                                                          \
278   NewNode_:                                                              \
279     error = FTC_Cache_NewNode( _cache, _hash, query, &_node );           \
280                                                                          \
281   Ok_:                                                                   \
282     node = _node;                                                        \
283   FT_END_STMNT
284 
285 #else /* !FTC_INLINE */
286 
287 #define FTC_CACHE_LOOKUP_CMP( cache, nodecmp, hash, query, node, error ) \
288   FT_BEGIN_STMNT                                                         \
289     error = FTC_Cache_Lookup( FTC_CACHE( cache ), hash, query,           \
290                               (FTC_Node*)&(node) );                      \
291   FT_END_STMNT
292 
293 #endif /* !FTC_INLINE */
294 
295 
296   /*
297    * This macro, together with FTC_CACHE_TRYLOOP_END, defines a retry
298    * loop to flush the cache repeatedly in case of memory overflows.
299    *
300    * It is used when creating a new cache node, or within a lookup
301    * that needs to allocate data (e.g. the sbit cache lookup).
302    *
303    * Example:
304    *
305    * {
306    *   FTC_CACHE_TRYLOOP( cache )
307    *     error = load_data( ... );
308    *   FTC_CACHE_TRYLOOP_END()
309    * }
310    *
311    */
312 #define FTC_CACHE_TRYLOOP( cache )                           \
313   {                                                          \
314     FTC_Manager  _try_manager = FTC_CACHE( cache )->manager; \
315     FT_UInt      _try_count   = 4;                           \
316                                                              \
317                                                              \
318     for (;;)                                                 \
319     {                                                        \
320       FT_UInt  _try_done;
321 
322 
323 #define FTC_CACHE_TRYLOOP_END( list_changed )                     \
324       if ( !error || FT_ERR_NEQ( error, Out_Of_Memory ) )         \
325         break;                                                    \
326                                                                   \
327       _try_done = FTC_Manager_FlushN( _try_manager, _try_count ); \
328       if ( _try_done > 0 && list_changed != NULL )                \
329         *(FT_Bool*)( list_changed ) = TRUE;                       \
330                                                                   \
331       if ( _try_done == 0 )                                       \
332         break;                                                    \
333                                                                   \
334       if ( _try_done == _try_count )                              \
335       {                                                           \
336         _try_count *= 2;                                          \
337         if ( _try_count < _try_done              ||               \
338             _try_count > _try_manager->num_nodes )                \
339           _try_count = _try_manager->num_nodes;                   \
340       }                                                           \
341     }                                                             \
342   }
343 
344  /* */
345 
346 FT_END_HEADER
347 
348 
349 #endif /* FTCCACHE_H_ */
350 
351 
352 /* END */
353