src/cache/ftccache.h

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  ftccache.h                                                             */
   4 /*                                                                         */
   5 /*    FreeType internal cache interface (specification).                   */
   6 /*                                                                         */
   7 /*  Copyright 2000-2001, 2002, 2003, 2004, 2005, 2006, 2007, 2009, 2010,   */
   8 /*            2011 by                                                      */
   9 /*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
  10 /*                                                                         */
  11 /*  This file is part of the FreeType project, and may only be used,       */
  12 /*  modified, and distributed under the terms of the FreeType project      */
  13 /*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */
  14 /*  this file you indicate that you have read the license and              */
  15 /*  understand and accept it fully.                                        */
  16 /*                                                                         */
  17 /***************************************************************************/
  18
  19
  20 #ifndef __FTCCACHE_H__
  21 #define __FTCCACHE_H__
  22
  23
  24 #include "ftcmru.h"
  25
  26 FT_BEGIN_HEADER
  27
  28 #define _FTC_FACE_ID_HASH( i )                                                \
  29           ((FT_PtrDist)(( (FT_PtrDist)(i) >> 3 ) ^ ( (FT_PtrDist)(i) << 7 )))
  30
  31   /* handle to cache object */
  32   typedef struct FTC_CacheRec_*  FTC_Cache;
  33
  34   /* handle to cache class */
  35   typedef const struct FTC_CacheClassRec_*  FTC_CacheClass;
  36
  37
  38   /*************************************************************************/
  39   /*************************************************************************/
  40   /*****                                                               *****/
  41   /*****                   CACHE NODE DEFINITIONS                      *****/
  42   /*****                                                               *****/
  43   /*************************************************************************/
  44   /*************************************************************************/
  45
  46   /*************************************************************************/
  47   /*                                                                       */
  48   /* Each cache controls one or more cache nodes.  Each node is part of    */
  49   /* the global_lru list of the manager.  Its `data' field however is used */
  50   /* as a reference count for now.                                         */
  51   /*                                                                       */
  52   /* A node can be anything, depending on the type of information held by  */
  53   /* the cache.  It can be an individual glyph image, a set of bitmaps     */
  54   /* glyphs for a given size, some metrics, etc.                           */
  55   /*                                                                       */
  56   /*************************************************************************/
  57
  58   /* structure size should be 20 bytes on 32-bits machines */
  59   typedef struct  FTC_NodeRec_
  60   {
  61     FTC_MruNodeRec  mru;          /* circular mru list pointer           */
  62     FTC_Node        link;         /* used for hashing                    */
  63     FT_PtrDist      hash;         /* used for hashing too                */
  64     FT_UShort       cache_index;  /* index of cache the node belongs to  */
  65     FT_Short        ref_count;    /* reference count for this node       */
  66
  67   } FTC_NodeRec;
  68
  69
  70 #define FTC_NODE( x )    ( (FTC_Node)(x) )
  71 #define FTC_NODE_P( x )  ( (FTC_Node*)(x) )
  72
  73 #define FTC_NODE__NEXT( x )  FTC_NODE( (x)->mru.next )
  74 #define FTC_NODE__PREV( x )  FTC_NODE( (x)->mru.prev )
  75
  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 * 2 + 1 ) )        \
  81               : ( ( hash ) &   ( cache )->mask ) ) )
  82 #else
  83   FT_LOCAL( FTC_Node* )
  84   ftc_get_top_node_for_hash( FTC_Cache   cache,
  85                              FT_PtrDist  hash );
  86 #define FTC_NODE__TOP_FOR_HASH( cache, hash )            \
  87         ftc_get_top_node_for_hash( ( cache ), ( hash ) )
  88 #endif
  89
  90 #ifdef FT_CONFIG_OPTION_OLD_INTERNALS
  91   FT_BASE( void )
  92   ftc_node_destroy( FTC_Node     node,
  93                     FTC_Manager  manager );
  94 #endif
  95
  96
  97   /*************************************************************************/
  98   /*************************************************************************/
  99   /*****                                                               *****/
 100   /*****                       CACHE DEFINITIONS                       *****/
 101   /*****                                                               *****/
 102   /*************************************************************************/
 103   /*************************************************************************/
 104
 105   /* initialize a new cache node */
 106   typedef FT_Error
 107   (*FTC_Node_NewFunc)( FTC_Node    *pnode,
 108                        FT_Pointer   query,
 109                        FTC_Cache    cache );
 110
 111   typedef FT_Offset
 112   (*FTC_Node_WeightFunc)( FTC_Node   node,
 113                           FTC_Cache  cache );
 114
 115   /* compare a node to a given key pair */
 116   typedef FT_Bool
 117   (*FTC_Node_CompareFunc)( FTC_Node    node,
 118                            FT_Pointer  key,
 119                            FTC_Cache   cache,
 120                            FT_Bool*    list_changed );
 121
 122
 123   typedef void
 124   (*FTC_Node_FreeFunc)( FTC_Node   node,
 125                         FTC_Cache  cache );
 126
 127   typedef FT_Error
 128   (*FTC_Cache_InitFunc)( FTC_Cache  cache );
 129
 130   typedef void
 131   (*FTC_Cache_DoneFunc)( FTC_Cache  cache );
 132
 133
 134   typedef struct  FTC_CacheClassRec_
 135   {
 136     FTC_Node_NewFunc      node_new;
 137     FTC_Node_WeightFunc   node_weight;
 138     FTC_Node_CompareFunc  node_compare;
 139     FTC_Node_CompareFunc  node_remove_faceid;
 140     FTC_Node_FreeFunc     node_free;
 141
 142     FT_Offset             cache_size;
 143     FTC_Cache_InitFunc    cache_init;
 144     FTC_Cache_DoneFunc    cache_done;
 145
 146   } FTC_CacheClassRec;
 147
 148
 149   /* each cache really implements a dynamic hash table to manage its nodes */
 150   typedef struct  FTC_CacheRec_
 151   {
 152     FT_UFast           p;
 153     FT_UFast           mask;
 154     FT_Long            slack;
 155     FTC_Node*          buckets;
 156
 157     FTC_CacheClassRec  clazz;       /* local copy, for speed  */
 158
 159     FTC_Manager        manager;
 160     FT_Memory          memory;
 161     FT_UInt            index;       /* in manager's table     */
 162
 163     FTC_CacheClass     org_class;   /* original class pointer */
 164
 165   } FTC_CacheRec;
 166
 167
 168 #define FTC_CACHE( x )    ( (FTC_Cache)(x) )
 169 #define FTC_CACHE_P( x )  ( (FTC_Cache*)(x) )
 170
 171
 172   /* default cache initialize */
 173   FT_LOCAL( FT_Error )
 174   FTC_Cache_Init( FTC_Cache  cache );
 175
 176   /* default cache finalizer */
 177   FT_LOCAL( void )
 178   FTC_Cache_Done( FTC_Cache  cache );
 179
 180   /* Call this function to look up the cache.  If no corresponding
 181    * node is found, a new one is automatically created.  This function
 182    * is capable of flushing the cache adequately to make room for the
 183    * new cache object.
 184    */
 185
 186 #ifndef FTC_INLINE
 187   FT_LOCAL( FT_Error )
 188   FTC_Cache_Lookup( FTC_Cache   cache,
 189                     FT_PtrDist  hash,
 190                     FT_Pointer  query,
 191                     FTC_Node   *anode );
 192 #endif
 193
 194   FT_LOCAL( FT_Error )
 195   FTC_Cache_NewNode( FTC_Cache   cache,
 196                      FT_PtrDist  hash,
 197                      FT_Pointer  query,
 198                      FTC_Node   *anode );
 199
 200   /* Remove all nodes that relate to a given face_id.  This is useful
 201    * when un-installing fonts.  Note that if a cache node relates to
 202    * the face_id but is locked (i.e., has `ref_count > 0'), the node
 203    * will _not_ be destroyed, but its internal face_id reference will
 204    * be modified.
 205    *
 206    * The final result will be that the node will never come back
 207    * in further lookup requests, and will be flushed on demand from
 208    * the cache normally when its reference count reaches 0.
 209    */
 210   FT_LOCAL( void )
 211   FTC_Cache_RemoveFaceID( FTC_Cache   cache,
 212                           FTC_FaceID  face_id );
 213
 214
 215 #ifdef FTC_INLINE
 216
 217 #define FTC_CACHE_LOOKUP_CMP( cache, nodecmp, hash, query, node, error ) \
 218   FT_BEGIN_STMNT                                                         \
 219     FTC_Node             *_bucket, *_pnode, _node;                       \
 220     FTC_Cache             _cache   = FTC_CACHE(cache);                   \
 221     FT_PtrDist            _hash    = (FT_PtrDist)(hash);                 \
 222     FTC_Node_CompareFunc  _nodcomp = (FTC_Node_CompareFunc)(nodecmp);    \
 223     FT_Bool               _list_changed = FALSE;                         \
 224                                                                          \
 225                                                                          \
 226     error = FTC_Err_Ok;                                                  \
 227     node  = NULL;                                                        \
 228                                                                          \
 229     /* Go to the `top' node of the list sharing same masked hash */      \
 230     _bucket = _pnode = FTC_NODE__TOP_FOR_HASH( _cache, _hash );          \
 231                                                                          \
 232     /* Look up a node with identical hash and queried properties.    */  \
 233     /* NOTE: _nodcomp() may change the linked list to reduce memory. */  \
 234     for (;;)                                                             \
 235     {                                                                    \
 236       _node = *_pnode;                                                   \
 237       if ( _node == NULL )                                               \
 238         goto _NewNode;                                                   \
 239                                                                          \
 240       if ( _node->hash == _hash                             &&           \
 241            _nodcomp( _node, query, _cache, &_list_changed ) )            \
 242         break;                                                           \
 243                                                                          \
 244       _pnode = &_node->link;                                             \
 245     }                                                                    \
 246                                                                          \
 247     if ( _list_changed )                                                 \
 248     {                                                                    \
 249       /* Update _bucket by possibly modified linked list */              \
 250       _bucket = _pnode = FTC_NODE__TOP_FOR_HASH( _cache, _hash );        \
 251                                                                          \
 252       /* Update _pnode by possibly modified linked list */               \
 253       while ( *_pnode != _node )                                         \
 254       {                                                                  \
 255         if ( *_pnode == NULL )                                           \
 256         {                                                                \
 257           FT_ERROR(( "FTC_CACHE_LOOKUP_CMP: oops!!! node missing\n" ));  \
 258           goto _NewNode;                                                 \
 259         }                                                                \
 260         else                                                             \
 261           _pnode = &((*_pnode)->link);                                   \
 262       }                                                                  \
 263     }                                                                    \
 264                                                                          \
 265     /* Reorder the list to move the found node to the `top' */           \
 266     if ( _node != *_bucket )                                             \
 267     {                                                                    \
 268       *_pnode     = _node->link;                                         \
 269       _node->link = *_bucket;                                            \
 270       *_bucket    = _node;                                               \
 271     }                                                                    \
 272                                                                          \
 273     /* Update MRU list */                                                \
 274     {                                                                    \
 275       FTC_Manager  _manager = _cache->manager;                           \
 276       void*        _nl      = &_manager->nodes_list;                     \
 277                                                                          \
 278                                                                          \
 279       if ( _node != _manager->nodes_list )                               \
 280         FTC_MruNode_Up( (FTC_MruNode*)_nl,                               \
 281                         (FTC_MruNode)_node );                            \
 282     }                                                                    \
 283     goto _Ok;                                                            \
 284                                                                          \
 285   _NewNode:                                                              \
 286     error = FTC_Cache_NewNode( _cache, _hash, query, &_node );           \
 287                                                                          \
 288   _Ok:                                                                   \
 289     node = _node;                                                        \
 290   FT_END_STMNT
 291
 292 #else /* !FTC_INLINE */
 293
 294 #define FTC_CACHE_LOOKUP_CMP( cache, nodecmp, hash, query, node, error ) \
 295   FT_BEGIN_STMNT                                                         \
 296     error = FTC_Cache_Lookup( FTC_CACHE( cache ), hash, query,           \
 297                               (FTC_Node*)&(node) );                      \
 298   FT_END_STMNT
 299
 300 #endif /* !FTC_INLINE */
 301
 302
 303   /*
 304    * This macro, together with FTC_CACHE_TRYLOOP_END, defines a retry
 305    * loop to flush the cache repeatedly in case of memory overflows.
 306    *
 307    * It is used when creating a new cache node, or within a lookup
 308    * that needs to allocate data (e.g. the sbit cache lookup).
 309    *
 310    * Example:
 311    *
 312    *   {
 313    *     FTC_CACHE_TRYLOOP( cache )
 314    *       error = load_data( ... );
 315    *     FTC_CACHE_TRYLOOP_END()
 316    *   }
 317    *
 318    */
 319 #define FTC_CACHE_TRYLOOP( cache )                           \
 320   {                                                          \
 321     FTC_Manager  _try_manager = FTC_CACHE( cache )->manager; \
 322     FT_UInt      _try_count   = 4;                           \
 323                                                              \
 324                                                              \
 325     for (;;)                                                 \
 326     {                                                        \
 327       FT_UInt  _try_done;
 328
 329
 330 #define FTC_CACHE_TRYLOOP_END( list_changed )                     \
 331       if ( !error || error != FTC_Err_Out_Of_Memory )             \
 332         break;                                                    \
 333                                                                   \
 334       _try_done = FTC_Manager_FlushN( _try_manager, _try_count ); \
 335       if ( _try_done > 0 && ( list_changed ) )                    \
 336         *(FT_Bool*)( list_changed ) = TRUE;                       \
 337                                                                   \
 338       if ( _try_done == 0 )                                       \
 339         break;                                                    \
 340                                                                   \
 341       if ( _try_done == _try_count )                              \
 342       {                                                           \
 343         _try_count *= 2;                                          \
 344         if ( _try_count < _try_done              ||               \
 345             _try_count > _try_manager->num_nodes )                \
 346           _try_count = _try_manager->num_nodes;                   \
 347       }                                                           \
 348     }                                                             \
 349   }
 350
 351  /* */
 352
 353 FT_END_HEADER
 354
 355
 356 #endif /* __FTCCACHE_H__ */
 357
 358
 359 /* END */