OLD | NEW |
(Empty) | |
| 1 /***************************************************************************/ |
| 2 /* */ |
| 3 /* ftccache.h */ |
| 4 /* */ |
| 5 /* FreeType internal cache interface (specification). */ |
| 6 /* */ |
| 7 /* Copyright 2000-2007, 2009-2011, 2013 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 |
| 25 FT_BEGIN_HEADER |
| 26 |
| 27 #define _FTC_FACE_ID_HASH( i ) \ |
| 28 ((FT_PtrDist)(( (FT_PtrDist)(i) >> 3 ) ^ ( (FT_PtrDist)(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_PtrDist 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 #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 |
| 82 FT_LOCAL( FTC_Node* ) |
| 83 ftc_get_top_node_for_hash( FTC_Cache cache, |
| 84 FT_PtrDist hash ); |
| 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, |
| 101 FT_Pointer query, |
| 102 FTC_Cache cache ); |
| 103 |
| 104 typedef FT_Offset |
| 105 (*FTC_Node_WeightFunc)( FTC_Node node, |
| 106 FTC_Cache cache ); |
| 107 |
| 108 /* compare a node to a given key pair */ |
| 109 typedef FT_Bool |
| 110 (*FTC_Node_CompareFunc)( FTC_Node node, |
| 111 FT_Pointer key, |
| 112 FTC_Cache cache, |
| 113 FT_Bool* list_changed ); |
| 114 |
| 115 |
| 116 typedef void |
| 117 (*FTC_Node_FreeFunc)( FTC_Node node, |
| 118 FTC_Cache cache ); |
| 119 |
| 120 typedef FT_Error |
| 121 (*FTC_Cache_InitFunc)( FTC_Cache cache ); |
| 122 |
| 123 typedef void |
| 124 (*FTC_Cache_DoneFunc)( FTC_Cache cache ); |
| 125 |
| 126 |
| 127 typedef struct FTC_CacheClassRec_ |
| 128 { |
| 129 FTC_Node_NewFunc node_new; |
| 130 FTC_Node_WeightFunc node_weight; |
| 131 FTC_Node_CompareFunc node_compare; |
| 132 FTC_Node_CompareFunc node_remove_faceid; |
| 133 FTC_Node_FreeFunc node_free; |
| 134 |
| 135 FT_Offset cache_size; |
| 136 FTC_Cache_InitFunc cache_init; |
| 137 FTC_Cache_DoneFunc cache_done; |
| 138 |
| 139 } FTC_CacheClassRec; |
| 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; |
| 147 FT_Long slack; |
| 148 FTC_Node* buckets; |
| 149 |
| 150 FTC_CacheClassRec clazz; /* local copy, for speed */ |
| 151 |
| 152 FTC_Manager manager; |
| 153 FT_Memory memory; |
| 154 FT_UInt index; /* in manager's table */ |
| 155 |
| 156 FTC_CacheClass org_class; /* original class pointer */ |
| 157 |
| 158 } FTC_CacheRec; |
| 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 */ |
| 166 FT_LOCAL( FT_Error ) |
| 167 FTC_Cache_Init( FTC_Cache cache ); |
| 168 |
| 169 /* default cache finalizer */ |
| 170 FT_LOCAL( void ) |
| 171 FTC_Cache_Done( FTC_Cache cache ); |
| 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 |
| 180 FT_LOCAL( FT_Error ) |
| 181 FTC_Cache_Lookup( FTC_Cache cache, |
| 182 FT_PtrDist hash, |
| 183 FT_Pointer query, |
| 184 FTC_Node *anode ); |
| 185 #endif |
| 186 |
| 187 FT_LOCAL( FT_Error ) |
| 188 FTC_Cache_NewNode( FTC_Cache cache, |
| 189 FT_PtrDist hash, |
| 190 FT_Pointer query, |
| 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 ) |
| 204 FTC_Cache_RemoveFaceID( FTC_Cache cache, |
| 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_PtrDist _hash = (FT_PtrDist)(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 == NULL ) \ |
| 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 == NULL ) \ |
| 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 ) ) \ |
| 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 |
| 346 FT_END_HEADER |
| 347 |
| 348 |
| 349 #endif /* __FTCCACHE_H__ */ |
| 350 |
| 351 |
| 352 /* END */ |
OLD | NEW |