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