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