Home | History | Annotate | Download | only in cache
      1 /***************************************************************************/
      2 /*                                                                         */
      3 /*  ftccache.h                                                             */
      4 /*                                                                         */
      5 /*    FreeType internal cache interface (specification).                   */
      6 /*                                                                         */
      7 /*  Copyright 2000-2015 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_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 #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_Offset  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_Offset   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_Offset   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_Offset             _hash    = (FT_Offset)(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 */
    353