ReactOS 0.4.15-dev-8102-g108db8f
ftccache.h
Go to the documentation of this file.
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
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
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
83 ftc_get_top_node_for_hash( FTC_Cache cache,
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,
103
104 typedef FT_Offset
107
108 /* compare a node to a given key pair */
109 typedef FT_Bool
113 FT_Bool* list_changed );
114
115
116 typedef void
119
120 typedef FT_Error
122
123 typedef void
125
126
127 typedef struct FTC_CacheClassRec_
128 {
134
138
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;
149
150 FTC_CacheClassRec clazz; /* local copy, for speed */
151
154 FT_UInt index; /* in manager's table */
155
156 FTC_CacheClass org_class; /* original class pointer */
157
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 */
168
169 /* default cache finalizer */
170 FT_LOCAL( void )
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
181 FTC_Cache_Lookup( FTC_Cache cache,
184 FTC_Node *anode );
185#endif
186
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 )
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
347
348
349#endif /* FTCCACHE_H_ */
350
351
352/* END */
FT_BEGIN_HEADER typedef FT_Pointer FTC_FaceID
Definition: ftcache.h:171
struct FTC_CacheRec_ FTC_CacheRec
FTC_Cache_NewNode(FTC_Cache cache, FT_Offset hash, FT_Pointer query, FTC_Node *anode)
Definition: ftccache.c:444
struct FTC_CacheRec_ * FTC_Cache
Definition: ftccache.h:31
FT_Error(* FTC_Node_NewFunc)(FTC_Node *pnode, FT_Pointer query, FTC_Cache cache)
Definition: ftccache.h:100
FTC_Cache_Done(FTC_Cache cache)
Definition: ftccache.c:409
void(* FTC_Node_FreeFunc)(FTC_Node node, FTC_Cache cache)
Definition: ftccache.h:117
FT_Error(* FTC_Cache_InitFunc)(FTC_Cache cache)
Definition: ftccache.h:121
const struct FTC_CacheClassRec_ * FTC_CacheClass
Definition: ftccache.h:34
struct FTC_CacheClassRec_ FTC_CacheClassRec
FT_Offset(* FTC_Node_WeightFunc)(FTC_Node node, FTC_Cache cache)
Definition: ftccache.h:105
struct FTC_NodeRec_ FTC_NodeRec
FT_Bool(* FTC_Node_CompareFunc)(FTC_Node node, FT_Pointer key, FTC_Cache cache, FT_Bool *list_changed)
Definition: ftccache.h:110
FTC_Cache_Init(FTC_Cache cache)
Definition: ftccache.c:328
void(* FTC_Cache_DoneFunc)(FTC_Cache cache)
Definition: ftccache.h:124
FTC_Cache_RemoveFaceID(FTC_Cache cache, FTC_FaceID face_id)
Definition: ftccache.c:564
#define FT_LOCAL(x)
Definition: ftconfig.h:387
#define FT_END_HEADER
Definition: ftheader.h:54
#define FT_BEGIN_HEADER
Definition: ftheader.h:36
typedefFT_BEGIN_HEADER struct FT_MemoryRec_ * FT_Memory
Definition: ftsystem.h:66
FT_BEGIN_HEADER typedef unsigned char FT_Bool
Definition: fttypes.h:108
int FT_Error
Definition: fttypes.h:300
signed long FT_Long
Definition: fttypes.h:242
unsigned short FT_UShort
Definition: fttypes.h:209
signed short FT_Short
Definition: fttypes.h:198
unsigned int FT_UInt
Definition: fttypes.h:231
size_t FT_Offset
Definition: fttypes.h:324
FTC_Cache_DoneFunc cache_done
Definition: ftccache.h:137
FTC_Node_CompareFunc node_remove_faceid
Definition: ftccache.h:132
FTC_Node_WeightFunc node_weight
Definition: ftccache.h:130
FTC_Node_FreeFunc node_free
Definition: ftccache.h:133
FT_Offset cache_size
Definition: ftccache.h:135
FTC_Cache_InitFunc cache_init
Definition: ftccache.h:136
FTC_Node_NewFunc node_new
Definition: ftccache.h:129
FTC_Node_CompareFunc node_compare
Definition: ftccache.h:131
FT_UInt index
Definition: ftccache.h:154
FT_UFast p
Definition: ftccache.h:145
FT_Memory memory
Definition: ftccache.h:153
FTC_CacheClassRec clazz
Definition: ftccache.h:150
FTC_CacheClass org_class
Definition: ftccache.h:156
FT_Long slack
Definition: ftccache.h:147
FT_UFast mask
Definition: ftccache.h:146
FTC_Node * buckets
Definition: ftccache.h:148
FTC_Manager manager
Definition: ftccache.h:152
FT_Short ref_count
Definition: ftccache.h:64
FT_Offset hash
Definition: ftccache.h:62
FTC_MruNodeRec mru
Definition: ftccache.h:60
FTC_Node link
Definition: ftccache.h:61
FT_UShort cache_index
Definition: ftccache.h:63
Definition: cache.c:49
Definition: _hash_fun.h:40
Definition: copy.c:22
Definition: dlist.c:348