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