lib/3rdparty/freetype/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 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
  76 #ifdef FT_CONFIG_OPTION_OLD_INTERNALS
  77   FT_BASE( void )
  78   ftc_node_destroy( FTC_Node     node,
  79                     FTC_Manager  manager );
  80 #endif
  81
  82
  83   /*************************************************************************/
  84   /*************************************************************************/
  85   /*****                                                               *****/
  86   /*****                       CACHE DEFINITIONS                       *****/
  87   /*****                                                               *****/
  88   /*************************************************************************/
  89   /*************************************************************************/
  90
  91   /* initialize a new cache node */
  92   typedef FT_Error
  93   (*FTC_Node_NewFunc)( FTC_Node    *pnode,
  94                        FT_Pointer   query,
  95                        FTC_Cache    cache );
  96
  97   typedef FT_Offset
  98   (*FTC_Node_WeightFunc)( FTC_Node   node,
  99                           FTC_Cache  cache );
 100
 101   /* compare a node to a given key pair */
 102   typedef FT_Bool
 103   (*FTC_Node_CompareFunc)( FTC_Node    node,
 104                            FT_Pointer  key,
 105                            FTC_Cache   cache );
 106
 107
 108   typedef void
 109   (*FTC_Node_FreeFunc)( FTC_Node   node,
 110                         FTC_Cache  cache );
 111
 112   typedef FT_Error
 113   (*FTC_Cache_InitFunc)( FTC_Cache  cache );
 114
 115   typedef void
 116   (*FTC_Cache_DoneFunc)( FTC_Cache  cache );
 117
 118
 119   typedef struct  FTC_CacheClassRec_
 120   {
 121     FTC_Node_NewFunc      node_new;
 122     FTC_Node_WeightFunc   node_weight;
 123     FTC_Node_CompareFunc  node_compare;
 124     FTC_Node_CompareFunc  node_remove_faceid;
 125     FTC_Node_FreeFunc     node_free;
 126
 127     FT_Offset             cache_size;
 128     FTC_Cache_InitFunc    cache_init;
 129     FTC_Cache_DoneFunc    cache_done;
 130
 131   } FTC_CacheClassRec;
 132
 133
 134   /* each cache really implements a dynamic hash table to manage its nodes */
 135   typedef struct  FTC_CacheRec_
 136   {
 137     FT_UFast           p;
 138     FT_UFast           mask;
 139     FT_Long            slack;
 140     FTC_Node*          buckets;
 141
 142     FTC_CacheClassRec  clazz;       /* local copy, for speed  */
 143
 144     FTC_Manager        manager;
 145     FT_Memory          memory;
 146     FT_UInt            index;       /* in manager's table     */
 147
 148     FTC_CacheClass     org_class;   /* original class pointer */
 149
 150   } FTC_CacheRec;
 151
 152
 153 #define FTC_CACHE( x )    ( (FTC_Cache)(x) )
 154 #define FTC_CACHE_P( x )  ( (FTC_Cache*)(x) )
 155
 156
 157   /* default cache initialize */
 158   FT_LOCAL( FT_Error )
 159   FTC_Cache_Init( FTC_Cache  cache );
 160
 161   /* default cache finalizer */
 162   FT_LOCAL( void )
 163   FTC_Cache_Done( FTC_Cache  cache );
 164
 165   /* Call this function to lookup the cache.  If no corresponding
 166    * node is found, a new one is automatically created.  This function
 167    * is capable of flushing the cache adequately to make room for the
 168    * new cache object.
 169    */
 170
 171 #ifndef FTC_INLINE
 172   FT_LOCAL( FT_Error )
 173   FTC_Cache_Lookup( FTC_Cache   cache,
 174                     FT_PtrDist  hash,
 175                     FT_Pointer  query,
 176                     FTC_Node   *anode );
 177 #endif
 178
 179   FT_LOCAL( FT_Error )
 180   FTC_Cache_NewNode( FTC_Cache   cache,
 181                      FT_PtrDist  hash,
 182                      FT_Pointer  query,
 183                      FTC_Node   *anode );
 184
 185   /* Remove all nodes that relate to a given face_id.  This is useful
 186    * when un-installing fonts.  Note that if a cache node relates to
 187    * the face_id, but is locked (i.e., has `ref_count > 0'), the node
 188    * will _not_ be destroyed, but its internal face_id reference will
 189    * be modified.
 190    *
 191    * The final result will be that the node will never come back
 192    * in further lookup requests, and will be flushed on demand from
 193    * the cache normally when its reference count reaches 0.
 194    */
 195   FT_LOCAL( void )
 196   FTC_Cache_RemoveFaceID( FTC_Cache   cache,
 197                           FTC_FaceID  face_id );
 198
 199
 200 #ifdef FTC_INLINE
 201
 202 #define FTC_CACHE_LOOKUP_CMP( cache, nodecmp, hash, query, node, error ) \
 203   FT_BEGIN_STMNT                                                         \
 204     FTC_Node             *_bucket, *_pnode, _node;                       \
 205     FTC_Cache             _cache   = FTC_CACHE(cache);                   \
 206     FT_PtrDist            _hash    = (FT_PtrDist)(hash);                 \
 207     FTC_Node_CompareFunc  _nodcomp = (FTC_Node_CompareFunc)(nodecmp);    \
 208     FT_UFast              _idx;                                          \
 209                                                                          \
 210                                                                          \
 211     error = FTC_Err_Ok;                                                  \
 212     node  = NULL;                                                        \
 213     _idx  = _hash & _cache->mask;                                        \
 214     if ( _idx < _cache->p )                                              \
 215       _idx = _hash & ( _cache->mask*2 + 1 );                             \
 216                                                                          \
 217     _bucket = _pnode = _cache->buckets + _idx;                           \
 218     for (;;)                                                             \
 219     {                                                                    \
 220       _node = *_pnode;                                                   \
 221       if ( _node == NULL )                                               \
 222         goto _NewNode;                                                   \
 223                                                                          \
 224       if ( _node->hash == _hash && _nodcomp( _node, query, _cache ) )    \
 225         break;                                                           \
 226                                                                          \
 227       _pnode = &_node->link;                                             \
 228     }                                                                    \
 229                                                                          \
 230     if ( _node != *_bucket )                                             \
 231     {                                                                    \
 232       *_pnode     = _node->link;                                         \
 233       _node->link = *_bucket;                                            \
 234       *_bucket    = _node;                                               \
 235     }                                                                    \
 236                                                                          \
 237     {                                                                    \
 238       FTC_Manager  _manager = _cache->manager;                           \
 239       void*        _nl      = &_manager->nodes_list;                     \
 240                                                                          \
 241                                                                          \
 242       if ( _node != _manager->nodes_list )                               \
 243         FTC_MruNode_Up( (FTC_MruNode*)_nl,                               \
 244                         (FTC_MruNode)_node );                            \
 245     }                                                                    \
 246     goto _Ok;                                                            \
 247                                                                          \
 248   _NewNode:                                                              \
 249     error = FTC_Cache_NewNode( _cache, _hash, query, &_node );           \
 250                                                                          \
 251   _Ok:                                                                   \
 252     node = _node;                                                        \
 253   FT_END_STMNT
 254
 255 #else /* !FTC_INLINE */
 256
 257 #define FTC_CACHE_LOOKUP_CMP( cache, nodecmp, hash, query, node, error ) \
 258   FT_BEGIN_STMNT                                                         \
 259     error = FTC_Cache_Lookup( FTC_CACHE( cache ), hash, query,           \
 260                               (FTC_Node*)&(node) );                      \
 261   FT_END_STMNT
 262
 263 #endif /* !FTC_INLINE */
 264
 265
 266   /*
 267    * This macro, together with FTC_CACHE_TRYLOOP_END, defines a retry
 268    * loop to flush the cache repeatedly in case of memory overflows.
 269    *
 270    * It is used when creating a new cache node, or within a lookup
 271    * that needs to allocate data (e.g., the sbit cache lookup).
 272    *
 273    * Example:
 274    *
 275    *   {
 276    *     FTC_CACHE_TRYLOOP( cache )
 277    *       error = load_data( ... );
 278    *     FTC_CACHE_TRYLOOP_END()
 279    *   }
 280    *
 281    */
 282 #define FTC_CACHE_TRYLOOP( cache )                           \
 283   {                                                          \
 284     FTC_Manager  _try_manager = FTC_CACHE( cache )->manager; \
 285     FT_UInt      _try_count   = 4;                           \
 286                                                              \
 287                                                              \
 288     for (;;)                                                 \
 289     {                                                        \
 290       FT_UInt  _try_done;
 291
 292
 293 #define FTC_CACHE_TRYLOOP_END()                                   \
 294       if ( !error || error != FTC_Err_Out_Of_Memory )             \
 295         break;                                                    \
 296                                                                   \
 297       _try_done = FTC_Manager_FlushN( _try_manager, _try_count ); \
 298       if ( _try_done == 0 )                                       \
 299         break;                                                    \
 300                                                                   \
 301       if ( _try_done == _try_count )                              \
 302       {                                                           \
 303         _try_count *= 2;                                          \
 304         if ( _try_count < _try_done              ||               \
 305             _try_count > _try_manager->num_nodes )                \
 306           _try_count = _try_manager->num_nodes;                   \
 307       }                                                           \
 308     }                                                             \
 309   }
 310
 311  /* */
 312
 313 FT_END_HEADER
 314
 315
 316 #endif /* __FTCCACHE_H__ */
 317
 318
 319 /* END */