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 */ |
356 | |