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