src/cache/ftccache.h

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