Go to most recent revision | Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 3918 | Serge | 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 */ |