text:
/****************************************************************************
 *
 * ftccache.h
 *
 *   FreeType internal cache interface (specification).
 *
 * Copyright (C) 2000-2020 by
 * David Turner, Robert Wilhelm, and Werner Lemberg.
 *
 * This file is part of the FreeType project, and may only be used,
 * modified, and distributed under the terms of the FreeType project
 * license, LICENSE.TXT.  By continuing to use, modify, or distribute
 * this file you indicate that you have read the license and
 * understand and accept it fully.
 *
 */

#ifndef FTCCACHE_H_
#define FTCCACHE_H_

#include "ftcmru.h"

FT_BEGIN_HEADER

#define FTC_FACE_ID_HASH( i )                                  \
         ( ( (FT_Offset)(i) >> 3 ) ^ ( (FT_Offset)(i) << 7 ) )

  /* handle to cache object */
  typedef struct FTC_CacheRec_*  FTC_Cache;

  /* handle to cache class */
  typedef const struct FTC_CacheClassRec_*  FTC_CacheClass;

  /*************************************************************************/
  /*************************************************************************/
  /*****                                                               *****/
  /*****                   CACHE NODE DEFINITIONS                      *****/
  /*****                                                               *****/
  /*************************************************************************/
  /*************************************************************************/

  /**************************************************************************
   *
   * Each cache controls one or more cache nodes.  Each node is part of
   * the global_lru list of the manager.  Its `data' field however is used
   * as a reference count for now.
   *
   * A node can be anything, depending on the type of information held by
   * the cache.  It can be an individual glyph image, a set of bitmaps
   * glyphs for a given size, some metrics, etc.
   *
   */

  /* structure size should be 20 bytes on 32-bits machines */
  typedef struct  FTC_NodeRec_
  {
    FTC_MruNodeRec  mru;          /* circular mru list pointer           */
    FTC_Node        link;         /* used for hashing                    */
    FT_Offset       hash;         /* used for hashing too                */
    FT_UShort       cache_index;  /* index of cache the node belongs to  */
    FT_Short        ref_count;    /* reference count for this node       */

  } FTC_NodeRec;

#define FTC_NODE( x )    ( (FTC_Node)(x) )
#define FTC_NODE_P( x )  ( (FTC_Node*)(x) )

#define FTC_NODE_NEXT( x )  FTC_NODE( (x)->mru.next )
#define FTC_NODE_PREV( x )  FTC_NODE( (x)->mru.prev )

#ifdef FTC_INLINE
#define FTC_NODE_TOP_FOR_HASH( cache, hash )                      \
        ( ( cache )->buckets +                                    \
            ( ( ( ( hash ) &   ( cache )->mask ) < ( cache )->p ) \
              ? ( ( hash ) & ( ( cache )->mask * 2 + 1 ) )        \
              : ( ( hash ) &   ( cache )->mask ) ) )
#else
  FT_LOCAL( FTC_Node* )
  ftc_get_top_node_for_hash( FTC_Cache  cache,
                             FT_Offset  hash );
#define FTC_NODE_TOP_FOR_HASH( cache, hash )             \
        ftc_get_top_node_for_hash( ( cache ), ( hash ) )
#endif

  /*************************************************************************/
  /*************************************************************************/
  /*****                                                               *****/
  /*****                       CACHE DEFINITIONS                       *****/
  /*****                                                               *****/
  /*************************************************************************/
  /*************************************************************************/

  /* initialize a new cache node */
  typedef FT_Error
  (*FTC_Node_NewFunc)( FTC_Node    *pnode,
                       FT_Pointer   query,
                       FTC_Cache    cache );

  typedef FT_Offset
  (*FTC_Node_WeightFunc)( FTC_Node   node,
                          FTC_Cache  cache );

  /* compare a node to a given key pair */
  typedef FT_Bool
  (*FTC_Node_CompareFunc)( FTC_Node    node,
                           FT_Pointer  key,
                           FTC_Cache   cache,
                           FT_Bool*    list_changed );

  typedef void
  (*FTC_Node_FreeFunc)( FTC_Node   node,
                        FTC_Cache  cache );

  typedef FT_Error
  (*FTC_Cache_InitFunc)( FTC_Cache  cache );

  typedef void
  (*FTC_Cache_DoneFunc)( FTC_Cache  cache );

  typedef struct  FTC_CacheClassRec_
  {
    FTC_Node_NewFunc      node_new;
    FTC_Node_WeightFunc   node_weight;
    FTC_Node_CompareFunc  node_compare;
    FTC_Node_CompareFunc  node_remove_faceid;
    FTC_Node_FreeFunc     node_free;

    FT_Offset             cache_size;
    FTC_Cache_InitFunc    cache_init;
    FTC_Cache_DoneFunc    cache_done;

  } FTC_CacheClassRec;

  /* each cache really implements a dynamic hash table to manage its nodes */
  typedef struct  FTC_CacheRec_
  {
    FT_UFast           p;
    FT_UFast           mask;
    FT_Long            slack;
    FTC_Node*          buckets;

    FTC_CacheClassRec  clazz;       /* local copy, for speed  */

    FTC_Manager        manager;
    FT_Memory          memory;
    FT_UInt            index;       /* in manager's table     */

    FTC_CacheClass     org_class;   /* original class pointer */

  } FTC_CacheRec;

#define FTC_CACHE( x )    ( (FTC_Cache)(x) )
#define FTC_CACHE_P( x )  ( (FTC_Cache*)(x) )

  /* default cache initialize */
  FT_LOCAL( FT_Error )
  FTC_Cache_Init( FTC_Cache  cache );

  /* default cache finalizer */
  FT_LOCAL( void )
  FTC_Cache_Done( FTC_Cache  cache );

  /* Call this function to look up the cache.  If no corresponding
   * node is found, a new one is automatically created.  This function
   * is capable of flushing the cache adequately to make room for the
   * new cache object.
   */

#ifndef FTC_INLINE
  FT_LOCAL( FT_Error )
  FTC_Cache_Lookup( FTC_Cache   cache,
                    FT_Offset   hash,
                    FT_Pointer  query,
                    FTC_Node   *anode );
#endif

  FT_LOCAL( FT_Error )
  FTC_Cache_NewNode( FTC_Cache   cache,
                     FT_Offset   hash,
                     FT_Pointer  query,
                     FTC_Node   *anode );

  /* Remove all nodes that relate to a given face_id.  This is useful
   * when un-installing fonts.  Note that if a cache node relates to
   * the face_id but is locked (i.e., has `ref_count > 0'), the node
   * will _not_ be destroyed, but its internal face_id reference will
   * be modified.
   *
   * The final result will be that the node will never come back
   * in further lookup requests, and will be flushed on demand from
   * the cache normally when its reference count reaches 0.
   */
  FT_LOCAL( void )
  FTC_Cache_RemoveFaceID( FTC_Cache   cache,
                          FTC_FaceID  face_id );

#ifdef FTC_INLINE

#define FTC_CACHE_LOOKUP_CMP( cache, nodecmp, hash, query, node, error ) \
  FT_BEGIN_STMNT                                                         \
    FTC_Node             *_bucket, *_pnode, _node;                       \
    FTC_Cache             _cache   = FTC_CACHE(cache);                   \
    FT_Offset             _hash    = (FT_Offset)(hash);                  \
    FTC_Node_CompareFunc  _nodcomp = (FTC_Node_CompareFunc)(nodecmp);    \
    FT_Bool               _list_changed = FALSE;                         \
                                                                         \
                                                                         \
    error = FT_Err_Ok;                                                   \
    node  = NULL;                                                        \
                                                                         \
    /* Go to the `top' node of the list sharing same masked hash */      \
    _bucket = _pnode = FTC_NODE_TOP_FOR_HASH( _cache, _hash );           \
                                                                         \
    /* Look up a node with identical hash and queried properties.    */  \
    /* NOTE: _nodcomp() may change the linked list to reduce memory. */  \
    for (;;)                                                             \
    {                                                                    \
      _node = *_pnode;                                                   \
      if ( !_node )                                                      \
        goto NewNode_;                                                   \
                                                                         \
      if ( _node->hash == _hash                             &&           \
           _nodcomp( _node, query, _cache, &_list_changed ) )            \
        break;                                                           \
                                                                         \
      _pnode = &_node->link;                                             \
    }                                                                    \
                                                                         \
    if ( _list_changed )                                                 \
    {                                                                    \
      /* Update _bucket by possibly modified linked list */              \
      _bucket = _pnode = FTC_NODE_TOP_FOR_HASH( _cache, _hash );         \
                                                                         \
      /* Update _pnode by possibly modified linked list */               \
      while ( *_pnode != _node )                                         \
      {                                                                  \
        if ( !*_pnode )                                                  \
        {                                                                \
          FT_ERROR(( "FTC_CACHE_LOOKUP_CMP: oops!!! node missing\n" ));  \
          goto NewNode_;                                                 \
        }                                                                \
        else                                                             \
          _pnode = &((*_pnode)->link);                                   \
      }                                                                  \
    }                                                                    \
                                                                         \
    /* Reorder the list to move the found node to the `top' */           \
    if ( _node != *_bucket )                                             \
    {                                                                    \
      *_pnode     = _node->link;                                         \
      _node->link = *_bucket;                                            \
      *_bucket    = _node;                                               \
    }                                                                    \
                                                                         \
    /* Update MRU list */                                                \
    {                                                                    \
      FTC_Manager  _manager = _cache->manager;                           \
      void*        _nl      = &_manager->nodes_list;                     \
                                                                         \
                                                                         \
      if ( _node != _manager->nodes_list )                               \
        FTC_MruNode_Up( (FTC_MruNode*)_nl,                               \
                        (FTC_MruNode)_node );                            \
    }                                                                    \
    goto Ok_;                                                            \
                                                                         \
  NewNode_:                                                              \
    error = FTC_Cache_NewNode( _cache, _hash, query, &_node );           \
                                                                         \
  Ok_:                                                                   \
    node = _node;                                                        \
  FT_END_STMNT

#else /* !FTC_INLINE */

#define FTC_CACHE_LOOKUP_CMP( cache, nodecmp, hash, query, node, error ) \
  FT_BEGIN_STMNT                                                         \
    error = FTC_Cache_Lookup( FTC_CACHE( cache ), hash, query,           \
                              (FTC_Node*)&(node) );                      \
  FT_END_STMNT

#endif /* !FTC_INLINE */

  /*
   * This macro, together with FTC_CACHE_TRYLOOP_END, defines a retry
   * loop to flush the cache repeatedly in case of memory overflows.
   *
   * It is used when creating a new cache node, or within a lookup
   * that needs to allocate data (e.g. the sbit cache lookup).
   *
   * Example:
   *
   * {
   *   FTC_CACHE_TRYLOOP( cache )
   *     error = load_data( ... );
   *   FTC_CACHE_TRYLOOP_END()
   * }
   *
   */
#define FTC_CACHE_TRYLOOP( cache )                           \
  {                                                          \
    FTC_Manager  _try_manager = FTC_CACHE( cache )->manager; \
    FT_UInt      _try_count   = 4;                           \
                                                             \
                                                             \
    for (;;)                                                 \
    {                                                        \
      FT_UInt  _try_done;

#define FTC_CACHE_TRYLOOP_END( list_changed )                     \
      if ( !error || FT_ERR_NEQ( error, Out_Of_Memory ) )         \
        break;                                                    \
                                                                  \
      _try_done = FTC_Manager_FlushN( _try_manager, _try_count ); \
      if ( _try_done > 0 && list_changed != NULL )                \
        *(FT_Bool*)( list_changed ) = TRUE;                       \
                                                                  \
      if ( _try_done == 0 )                                       \
        break;                                                    \
                                                                  \
      if ( _try_done == _try_count )                              \
      {                                                           \
        _try_count *= 2;                                          \
        if ( _try_count < _try_done              ||               \
            _try_count > _try_manager->num_nodes )                \
          _try_count = _try_manager->num_nodes;                   \
      }                                                           \
    }                                                             \
  }

 /* */

FT_END_HEADER

#endif /* FTCCACHE_H_ */

/* END */


text:
/****************************************************************************
 *
 * ftcmru.c
 *
 *   FreeType MRU support (body).
 *
 * Copyright (C) 2003-2020 by
 * David Turner, Robert Wilhelm, and Werner Lemberg.
 *
 * This file is part of the FreeType project, and may only be used,
 * modified, and distributed under the terms of the FreeType project
 * license, LICENSE.TXT.  By continuing to use, modify, or distribute
 * this file you indicate that you have read the license and
 * understand and accept it fully.
 *
 */

#include <ft2build.h>
#include FT_CACHE_H
#include "ftcmru.h"
#include FT_INTERNAL_OBJECTS_H
#include FT_INTERNAL_DEBUG_H

#include "ftcerror.h"

  FT_LOCAL_DEF( void )
  FTC_MruNode_Prepend( FTC_MruNode  *plist,
                       FTC_MruNode   node )
  {
    FTC_MruNode  first = *plist;

    if ( first )
    {
      FTC_MruNode  last = first->prev;

#ifdef FT_DEBUG_ERROR
      {
        FTC_MruNode  cnode = first;

        do
        {
          if ( cnode == node )
          {
            fprintf( stderr, "FTC_MruNode_Prepend: invalid action\n" );
            exit( 2 );
          }
          cnode = cnode->next;

        } while ( cnode != first );
      }
#endif

      first->prev = node;
      last->next  = node;
      node->next  = first;
      node->prev  = last;
    }
    else
    {
      node->next = node;
      node->prev = node;
    }
    *plist = node;
  }

  FT_LOCAL_DEF( void )
  FTC_MruNode_Up( FTC_MruNode  *plist,
                  FTC_MruNode   node )
  {
    FTC_MruNode  first = *plist;

    FT_ASSERT( first );

    if ( first != node )
    {
      FTC_MruNode  prev, next, last;

#ifdef FT_DEBUG_ERROR
      {
        FTC_MruNode  cnode = first;
        do
        {
          if ( cnode == node )
            goto Ok;
          cnode = cnode->next;

        } while ( cnode != first );

        fprintf( stderr, "FTC_MruNode_Up: invalid action\n" );
        exit( 2 );
      Ok:
      }
#endif
      prev = node->prev;
      next = node->next;

      prev->next = next;
      next->prev = prev;

      last = first->prev;

      last->next  = node;
      first->prev = node;

      node->next = first;
      node->prev = last;

      *plist = node;
    }
  }

  FT_LOCAL_DEF( void )
  FTC_MruNode_Remove( FTC_MruNode  *plist,
                      FTC_MruNode   node )
  {
    FTC_MruNode  first = *plist;
    FTC_MruNode  prev, next;

    FT_ASSERT( first );

#ifdef FT_DEBUG_ERROR
      {
        FTC_MruNode  cnode = first;

        do
        {
          if ( cnode == node )
            goto Ok;
          cnode = cnode->next;

        } while ( cnode != first );

        fprintf( stderr, "FTC_MruNode_Remove: invalid action\n" );
        exit( 2 );
      Ok:
      }
#endif

    prev = node->prev;
    next = node->next;

    prev->next = next;
    next->prev = prev;

    if ( node == next )
    {
      FT_ASSERT( first == node );
      FT_ASSERT( prev  == node );

      *plist = NULL;
    }
    else if ( node == first )
      *plist = next;
  }

  FT_LOCAL_DEF( void )
  FTC_MruList_Init( FTC_MruList       list,
                    FTC_MruListClass  clazz,
                    FT_UInt           max_nodes,
                    FT_Pointer        data,
                    FT_Memory         memory )
  {
    list->num_nodes = 0;
    list->max_nodes = max_nodes;
    list->nodes     = NULL;
    list->clazz     = *clazz;
    list->data      = data;
    list->memory    = memory;
  }

  FT_LOCAL_DEF( void )
  FTC_MruList_Reset( FTC_MruList  list )
  {
    while ( list->nodes )
      FTC_MruList_Remove( list, list->nodes );

    FT_ASSERT( list->num_nodes == 0 );
  }

  FT_LOCAL_DEF( void )
  FTC_MruList_Done( FTC_MruList  list )
  {
    FTC_MruList_Reset( list );
  }

#ifndef FTC_INLINE
  FT_LOCAL_DEF( FTC_MruNode )
  FTC_MruList_Find( FTC_MruList  list,
                    FT_Pointer   key )
  {
    FTC_MruNode_CompareFunc  compare = list->clazz.node_compare;
    FTC_MruNode              first, node;

    first = list->nodes;
    node  = NULL;

    if ( first )
    {
      node = first;
      do
      {
        if ( compare( node, key ) )
        {
          if ( node != first )
            FTC_MruNode_Up( &list->nodes, node );

          return node;
        }

        node = node->next;

      } while ( node != first);
    }

    return NULL;
  }
#endif

  FT_LOCAL_DEF( FT_Error )
  FTC_MruList_New( FTC_MruList   list,
                   FT_Pointer    key,
                   FTC_MruNode  *anode )
  {
    FT_Error     error;
    FTC_MruNode  node   = NULL;
    FT_Memory    memory = list->memory;

    if ( list->num_nodes >= list->max_nodes && list->max_nodes > 0 )
    {
      node = list->nodes->prev;

      FT_ASSERT( node );

      if ( list->clazz.node_reset )
      {
        FTC_MruNode_Up( &list->nodes, node );

        error = list->clazz.node_reset( node, key, list->data );
        if ( !error )
          goto Exit;
      }

      FTC_MruNode_Remove( &list->nodes, node );
      list->num_nodes--;

      if ( list->clazz.node_done )
        list->clazz.node_done( node, list->data );
    }
    else if ( FT_ALLOC( node, list->clazz.node_size ) )
      goto Exit;

    error = list->clazz.node_init( node, key, list->data );
    if ( error )
      goto Fail;

    FTC_MruNode_Prepend( &list->nodes, node );
    list->num_nodes++;

  Exit:
    *anode = node;
    return error;

  Fail:
    if ( list->clazz.node_done )
      list->clazz.node_done( node, list->data );

    FT_FREE( node );
    goto Exit;
  }

#ifndef FTC_INLINE
  FT_LOCAL_DEF( FT_Error )
  FTC_MruList_Lookup( FTC_MruList   list,
                      FT_Pointer    key,
                      FTC_MruNode  *anode )
  {
    FTC_MruNode  node;

    node = FTC_MruList_Find( list, key );
    if ( !node )
      return FTC_MruList_New( list, key, anode );

    *anode = node;
    return 0;
  }
#endif /* FTC_INLINE */

  FT_LOCAL_DEF( void )
  FTC_MruList_Remove( FTC_MruList  list,
                      FTC_MruNode  node )
  {
    FTC_MruNode_Remove( &list->nodes, node );
    list->num_nodes--;

    {
      FT_Memory  memory = list->memory;

      if ( list->clazz.node_done )
        list->clazz.node_done( node, list->data );

      FT_FREE( node );
    }
  }

  FT_LOCAL_DEF( void )
  FTC_MruList_RemoveSelection( FTC_MruList              list,
                               FTC_MruNode_CompareFunc  selection,
                               FT_Pointer               key )
  {
    FTC_MruNode  first, node, next;

    first = list->nodes;
    while ( first && ( !selection || selection( first, key ) ) )
    {
      FTC_MruList_Remove( list, first );
      first = list->nodes;
    }

    if ( first )
    {
      node = first->next;
      while ( node != first )
      {
        next = node->next;

        if ( selection( node, key ) )
          FTC_MruList_Remove( list, node );

        node = next;
      }
    }
  }

/* END */

repo_language: C

mime_type: text/x-c


text:
/****************************************************************************
 *
 * ftcbasic.c
 *
 *   The FreeType basic cache interface (body).
 *
 * Copyright (C) 2003-2020 by
 * David Turner, Robert Wilhelm, and Werner Lemberg.
 *
 * This file is part of the FreeType project, and may only be used,
 * modified, and distributed under the terms of the FreeType project
 * license, LICENSE.TXT.  By continuing to use, modify, or distribute
 * this file you indicate that you have read the license and
 * understand and accept it fully.
 *
 */

#include <ft2build.h>
#include FT_INTERNAL_OBJECTS_H
#include FT_INTERNAL_DEBUG_H
#include FT_CACHE_H
#include "ftcglyph.h"
#include "ftcimage.h"
#include "ftcsbits.h"

#include "ftccback.h"
#include "ftcerror.h"

#define FT_COMPONENT  cache

  /*
   * Basic Families
   *
   */
  typedef struct  FTC_BasicAttrRec_
  {
    FTC_ScalerRec  scaler;
    FT_UInt        load_flags;

  } FTC_BasicAttrRec, *FTC_BasicAttrs;

#define FTC_BASIC_ATTR_COMPARE( a, b )                                 \
          FT_BOOL( FTC_SCALER_COMPARE( &(a)->scaler, &(b)->scaler ) && \
                   (a)->load_flags == (b)->load_flags               )

#define FTC_BASIC_ATTR_HASH( a )                                     \
          ( FTC_SCALER_HASH( &(a)->scaler ) + 31 * (a)->load_flags )

  typedef struct  FTC_BasicQueryRec_
  {
    FTC_GQueryRec     gquery;
    FTC_BasicAttrRec  attrs;

  } FTC_BasicQueryRec, *FTC_BasicQuery;

  typedef struct  FTC_BasicFamilyRec_
  {
    FTC_FamilyRec     family;
    FTC_BasicAttrRec  attrs;

  } FTC_BasicFamilyRec, *FTC_BasicFamily;

  FT_CALLBACK_DEF( FT_Bool )
  ftc_basic_family_compare( FTC_MruNode  ftcfamily,
                            FT_Pointer   ftcquery )
  {
    FTC_BasicFamily  family = (FTC_BasicFamily)ftcfamily;
    FTC_BasicQuery   query  = (FTC_BasicQuery)ftcquery;

    return FTC_BASIC_ATTR_COMPARE( &family->attrs, &query->attrs );
  }

  FT_CALLBACK_DEF( FT_Error )
  ftc_basic_family_init( FTC_MruNode  ftcfamily,
                         FT_Pointer   ftcquery,
                         FT_Pointer   ftccache )
  {
    FTC_BasicFamily  family = (FTC_BasicFamily)ftcfamily;
    FTC_BasicQuery   query  = (FTC_BasicQuery)ftcquery;
    FTC_Cache        cache  = (FTC_Cache)ftccache;

    FTC_Family_Init( FTC_FAMILY( family ), cache );
    family->attrs = query->attrs;
    return 0;
  }

  FT_CALLBACK_DEF( FT_UInt )
  ftc_basic_family_get_count( FTC_Family   ftcfamily,
                              FTC_Manager  manager )
  {
    FTC_BasicFamily  family = (FTC_BasicFamily)ftcfamily;
    FT_Error         error;
    FT_Face          face;
    FT_UInt          result = 0;

    error = FTC_Manager_LookupFace( manager, family->attrs.scaler.face_id,
                                    &face );

    if ( error || !face )
      return result;

    if ( (FT_ULong)face->num_glyphs > FT_UINT_MAX || 0 > face->num_glyphs )
      FT_TRACE1(( "ftc_basic_family_get_count:"
                  " too large number of glyphs in this face, truncated\n",
                  face->num_glyphs ));

    if ( !error )
      result = (FT_UInt)face->num_glyphs;

    return result;
  }

  FT_CALLBACK_DEF( FT_Error )
  ftc_basic_family_load_bitmap( FTC_Family   ftcfamily,
                                FT_UInt      gindex,
                                FTC_Manager  manager,
                                FT_Face     *aface )
  {
    FTC_BasicFamily  family = (FTC_BasicFamily)ftcfamily;
    FT_Error         error;
    FT_Size          size;

    error = FTC_Manager_LookupSize( manager, &family->attrs.scaler, &size );
    if ( !error )
    {
      FT_Face  face = size->face;

      error = FT_Load_Glyph(
                face,
                gindex,
                (FT_Int)family->attrs.load_flags | FT_LOAD_RENDER );
      if ( !error )
        *aface = face;
    }

    return error;
  }

  FT_CALLBACK_DEF( FT_Error )
  ftc_basic_family_load_glyph( FTC_Family  ftcfamily,
                               FT_UInt     gindex,
                               FTC_Cache   cache,
                               FT_Glyph   *aglyph )
  {
    FTC_BasicFamily  family = (FTC_BasicFamily)ftcfamily;
    FT_Error         error;
    FTC_Scaler       scaler = &family->attrs.scaler;
    FT_Face          face;
    FT_Size          size;

    /* we will now load the glyph image */
    error = FTC_Manager_LookupSize( cache->manager,
                                    scaler,
                                    &size );
    if ( !error )
    {
      face = size->face;

      error = FT_Load_Glyph( face,
                             gindex,
                             (FT_Int)family->attrs.load_flags );
      if ( !error )
      {
        if ( face->glyph->format == FT_GLYPH_FORMAT_BITMAP  ||
             face->glyph->format == FT_GLYPH_FORMAT_OUTLINE )
        {
          /* ok, copy it */
          FT_Glyph  glyph;

          error = FT_Get_Glyph( face->glyph, &glyph );
          if ( !error )
          {
            *aglyph = glyph;
            goto Exit;
          }
        }
        else
          error = FT_THROW( Invalid_Argument );
      }
    }

  Exit:
    return error;
  }

  FT_CALLBACK_DEF( FT_Bool )
  ftc_basic_gnode_compare_faceid( FTC_Node    ftcgnode,
                                  FT_Pointer  ftcface_id,
                                  FTC_Cache   cache,
                                  FT_Bool*    list_changed )
  {
    FTC_GNode        gnode   = (FTC_GNode)ftcgnode;
    FTC_FaceID       face_id = (FTC_FaceID)ftcface_id;
    FTC_BasicFamily  family  = (FTC_BasicFamily)gnode->family;
    FT_Bool          result;

    if ( list_changed )
      *list_changed = FALSE;
    result = FT_BOOL( family->attrs.scaler.face_id == face_id );
    if ( result )
    {
      /* we must call this function to avoid this node from appearing
       * in later lookups with the same face_id!
       */
      FTC_GNode_UnselectFamily( gnode, cache );
    }
    return result;
  }

 /*
  *
  * basic image cache
  *
  */

  static
  const FTC_IFamilyClassRec  ftc_basic_image_family_class =
  {
    {
      sizeof ( FTC_BasicFamilyRec ),

      ftc_basic_family_compare, /* FTC_MruNode_CompareFunc  node_compare */
      ftc_basic_family_init,    /* FTC_MruNode_InitFunc     node_init    */
      NULL,                     /* FTC_MruNode_ResetFunc    node_reset   */
      NULL                      /* FTC_MruNode_DoneFunc     node_done    */
    },

    ftc_basic_family_load_glyph /* FTC_IFamily_LoadGlyphFunc  family_load_glyph */
  };

  static
  const FTC_GCacheClassRec  ftc_basic_image_cache_class =
  {
    {
      ftc_inode_new,                  /* FTC_Node_NewFunc      node_new           */
      ftc_inode_weight,               /* FTC_Node_WeightFunc   node_weight        */
      ftc_gnode_compare,              /* FTC_Node_CompareFunc  node_compare       */
      ftc_basic_gnode_compare_faceid, /* FTC_Node_CompareFunc  node_remove_faceid */
      ftc_inode_free,                 /* FTC_Node_FreeFunc     node_free          */

      sizeof ( FTC_GCacheRec ),
      ftc_gcache_init,                /* FTC_Cache_InitFunc    cache_init         */
      ftc_gcache_done                 /* FTC_Cache_DoneFunc    cache_done         */
    },

    (FTC_MruListClass)&ftc_basic_image_family_class
  };

  /* documentation is in ftcache.h */

  FT_EXPORT_DEF( FT_Error )
  FTC_ImageCache_New( FTC_Manager      manager,
                      FTC_ImageCache  *acache )
  {
    return FTC_GCache_New( manager, &ftc_basic_image_cache_class,
                           (FTC_GCache*)acache );
  }

  /* documentation is in ftcache.h */

  FT_EXPORT_DEF( FT_Error )
  FTC_ImageCache_Lookup( FTC_ImageCache  cache,
                         FTC_ImageType   type,
                         FT_UInt         gindex,
                         FT_Glyph       *aglyph,
                         FTC_Node       *anode )
  {
    FTC_BasicQueryRec  query;
    FTC_Node           node = 0; /* make compiler happy */
    FT_Error           error;
    FT_Offset          hash;

    /* some argument checks are delayed to `FTC_Cache_Lookup' */
    if ( !aglyph )
    {
      error = FT_THROW( Invalid_Argument );
      goto Exit;
    }

    *aglyph = NULL;
    if ( anode )
      *anode  = NULL;

    /*
     * Internal `FTC_BasicAttr->load_flags' is of type `FT_UInt',
     * but public `FT_ImageType->flags' is of type `FT_Int32'.
     *
     * On 16bit systems, higher bits of type->flags cannot be handled.
     */
#if 0xFFFFFFFFUL > FT_UINT_MAX
    if ( (type->flags & (FT_ULong)FT_UINT_MAX) )
      FT_TRACE1(( "FTC_ImageCache_Lookup:"
                  " higher bits in load_flags 0x%x are dropped\n",
                  (FT_ULong)type->flags & ~((FT_ULong)FT_UINT_MAX) ));
#endif

    query.attrs.scaler.face_id = type->face_id;
    query.attrs.scaler.width   = type->width;
    query.attrs.scaler.height  = type->height;
    query.attrs.load_flags     = (FT_UInt)type->flags;

    query.attrs.scaler.pixel = 1;
    query.attrs.scaler.x_res = 0;  /* make compilers happy */
    query.attrs.scaler.y_res = 0;

    hash = FTC_BASIC_ATTR_HASH( &query.attrs ) + gindex;

#if 1  /* inlining is about 50% faster! */
    FTC_GCACHE_LOOKUP_CMP( cache,
                           ftc_basic_family_compare,
                           FTC_GNode_Compare,
                           hash, gindex,
                           &query,
                           node,
                           error );
#else
    error = FTC_GCache_Lookup( FTC_GCACHE( cache ),
                               hash, gindex,
                               FTC_GQUERY( &query ),
                               &node );
#endif
    if ( !error )
    {
      *aglyph = FTC_INODE( node )->glyph;

      if ( anode )
      {
        *anode = node;
        node->ref_count++;
      }
    }

  Exit:
    return error;
  }

  /* documentation is in ftcache.h */

  FT_EXPORT_DEF( FT_Error )
  FTC_ImageCache_LookupScaler( FTC_ImageCache  cache,
                               FTC_Scaler      scaler,
                               FT_ULong        load_flags,
                               FT_UInt         gindex,
                               FT_Glyph       *aglyph,
                               FTC_Node       *anode )
  {
    FTC_BasicQueryRec  query;
    FTC_Node           node = 0; /* make compiler happy */
    FT_Error           error;
    FT_Offset          hash;

    /* some argument checks are delayed to `FTC_Cache_Lookup' */
    if ( !aglyph || !scaler )
    {
      error = FT_THROW( Invalid_Argument );
      goto Exit;
    }

    *aglyph = NULL;
    if ( anode )
      *anode  = NULL;

    /*
     * Internal `FTC_BasicAttr->load_flags' is of type `FT_UInt',
     * but public `FT_Face->face_flags' is of type `FT_Long'.
     *
     * On long > int systems, higher bits of load_flags cannot be handled.
     */
#if FT_ULONG_MAX > FT_UINT_MAX
    if ( load_flags > FT_UINT_MAX )
      FT_TRACE1(( "FTC_ImageCache_LookupScaler:"
                  " higher bits in load_flags 0x%x are dropped\n",
                  load_flags & ~((FT_ULong)FT_UINT_MAX) ));
#endif

    query.attrs.scaler     = scaler[0];
    query.attrs.load_flags = (FT_UInt)load_flags;

    hash = FTC_BASIC_ATTR_HASH( &query.attrs ) + gindex;

    FTC_GCACHE_LOOKUP_CMP( cache,
                           ftc_basic_family_compare,
                           FTC_GNode_Compare,
                           hash, gindex,
                           &query,
                           node,
                           error );
    if ( !error )
    {
      *aglyph = FTC_INODE( node )->glyph;

      if ( anode )
      {
        *anode = node;
        node->ref_count++;
      }
    }

  Exit:
    return error;
  }

  /*
   *
   * basic small bitmap cache
   *
   */

  static
  const FTC_SFamilyClassRec  ftc_basic_sbit_family_class =
  {
    {
      sizeof ( FTC_BasicFamilyRec ),
      ftc_basic_family_compare,     /* FTC_MruNode_CompareFunc  node_compare */
      ftc_basic_family_init,        /* FTC_MruNode_InitFunc     node_init    */
      NULL,                         /* FTC_MruNode_ResetFunc    node_reset   */
      NULL                          /* FTC_MruNode_DoneFunc     node_done    */
    },

    ftc_basic_family_get_count,
    ftc_basic_family_load_bitmap
  };

  static
  const FTC_GCacheClassRec  ftc_basic_sbit_cache_class =
  {
    {
      ftc_snode_new,                  /* FTC_Node_NewFunc      node_new           */
      ftc_snode_weight,               /* FTC_Node_WeightFunc   node_weight        */
      ftc_snode_compare,              /* FTC_Node_CompareFunc  node_compare       */
      ftc_basic_gnode_compare_faceid, /* FTC_Node_CompareFunc  node_remove_faceid */
      ftc_snode_free,                 /* FTC_Node_FreeFunc     node_free          */

      sizeof ( FTC_GCacheRec ),
      ftc_gcache_init,                /* FTC_Cache_InitFunc    cache_init         */
      ftc_gcache_done                 /* FTC_Cache_DoneFunc    cache_done         */
    },

    (FTC_MruListClass)&ftc_basic_sbit_family_class
  };

  /* documentation is in ftcache.h */

  FT_EXPORT_DEF( FT_Error )
  FTC_SBitCache_New( FTC_Manager     manager,
                     FTC_SBitCache  *acache )
  {
    return FTC_GCache_New( manager, &ftc_basic_sbit_cache_class,
                           (FTC_GCache*)acache );
  }

  /* documentation is in ftcache.h */

  FT_EXPORT_DEF( FT_Error )
  FTC_SBitCache_Lookup( FTC_SBitCache  cache,
                        FTC_ImageType  type,
                        FT_UInt        gindex,
                        FTC_SBit      *ansbit,
                        FTC_Node      *anode )
  {
    FT_Error           error;
    FTC_BasicQueryRec  query;
    FTC_Node           node = 0; /* make compiler happy */
    FT_Offset          hash;

    if ( anode )
      *anode = NULL;

    /* other argument checks delayed to `FTC_Cache_Lookup' */
    if ( !ansbit )
      return FT_THROW( Invalid_Argument );

    *ansbit = NULL;

    /*
     * Internal `FTC_BasicAttr->load_flags' is of type `FT_UInt',
     * but public `FT_ImageType->flags' is of type `FT_Int32'.
     *
     * On 16bit systems, higher bits of type->flags cannot be handled.
     */
#if 0xFFFFFFFFUL > FT_UINT_MAX
    if ( (type->flags & (FT_ULong)FT_UINT_MAX) )
      FT_TRACE1(( "FTC_ImageCache_Lookup:"
                  " higher bits in load_flags 0x%x are dropped\n",
                  (FT_ULong)type->flags & ~((FT_ULong)FT_UINT_MAX) ));
#endif

    query.attrs.scaler.face_id = type->face_id;
    query.attrs.scaler.width   = type->width;
    query.attrs.scaler.height  = type->height;
    query.attrs.load_flags     = (FT_UInt)type->flags;

    query.attrs.scaler.pixel = 1;
    query.attrs.scaler.x_res = 0;  /* make compilers happy */
    query.attrs.scaler.y_res = 0;

    /* beware, the hash must be the same for all glyph ranges! */
    hash = FTC_BASIC_ATTR_HASH( &query.attrs ) +
           gindex / FTC_SBIT_ITEMS_PER_NODE;

#if 1  /* inlining is about 50% faster! */
    FTC_GCACHE_LOOKUP_CMP( cache,
                           ftc_basic_family_compare,
                           FTC_SNode_Compare,
                           hash, gindex,
                           &query,
                           node,
                           error );
#else
    error = FTC_GCache_Lookup( FTC_GCACHE( cache ),
                               hash,
                               gindex,
                               FTC_GQUERY( &query ),
                               &node );
#endif
    if ( error )
      goto Exit;

    *ansbit = FTC_SNODE( node )->sbits +
              ( gindex - FTC_GNODE( node )->gindex );

    if ( anode )
    {
      *anode = node;
      node->ref_count++;
    }

  Exit:
    return error;
  }

  /* documentation is in ftcache.h */

  FT_EXPORT_DEF( FT_Error )
  FTC_SBitCache_LookupScaler( FTC_SBitCache  cache,
                              FTC_Scaler     scaler,
                              FT_ULong       load_flags,
                              FT_UInt        gindex,
                              FTC_SBit      *ansbit,
                              FTC_Node      *anode )
  {
    FT_Error           error;
    FTC_BasicQueryRec  query;
    FTC_Node           node = 0; /* make compiler happy */
    FT_Offset          hash;

    if ( anode )
        *anode = NULL;

    /* other argument checks delayed to `FTC_Cache_Lookup' */
    if ( !ansbit || !scaler )
        return FT_THROW( Invalid_Argument );

    *ansbit = NULL;

    /*
     * Internal `FTC_BasicAttr->load_flags' is of type `FT_UInt',
     * but public `FT_Face->face_flags' is of type `FT_Long'.
     *
     * On long > int systems, higher bits of load_flags cannot be handled.
     */
#if FT_ULONG_MAX > FT_UINT_MAX
    if ( load_flags > FT_UINT_MAX )
      FT_TRACE1(( "FTC_ImageCache_LookupScaler:"
                  " higher bits in load_flags 0x%x are dropped\n",
                  load_flags & ~((FT_ULong)FT_UINT_MAX) ));
#endif

    query.attrs.scaler     = scaler[0];
    query.attrs.load_flags = (FT_UInt)load_flags;

    /* beware, the hash must be the same for all glyph ranges! */
    hash = FTC_BASIC_ATTR_HASH( &query.attrs ) +
             gindex / FTC_SBIT_ITEMS_PER_NODE;

    FTC_GCACHE_LOOKUP_CMP( cache,
                           ftc_basic_family_compare,
                           FTC_SNode_Compare,
                           hash, gindex,
                           &query,
                           node,
                           error );
    if ( error )
      goto Exit;

    *ansbit = FTC_SNODE( node )->sbits +
              ( gindex - FTC_GNODE( node )->gindex );

    if ( anode )
    {
      *anode = node;
      node->ref_count++;
    }

  Exit:
    return error;
  }

/* END */


text:
/****************************************************************************
 *
 * ftcglyph.c
 *
 *   FreeType Glyph Image (FT_Glyph) cache (body).
 *
 * Copyright (C) 2000-2020 by
 * David Turner, Robert Wilhelm, and Werner Lemberg.
 *
 * This file is part of the FreeType project, and may only be used,
 * modified, and distributed under the terms of the FreeType project
 * license, LICENSE.TXT.  By continuing to use, modify, or distribute
 * this file you indicate that you have read the license and
 * understand and accept it fully.
 *
 */

#include <ft2build.h>
#include FT_INTERNAL_OBJECTS_H
#include FT_CACHE_H
#include "ftcglyph.h"
#include FT_ERRORS_H

#include "ftccback.h"
#include "ftcerror.h"

  /* create a new chunk node, setting its cache index and ref count */
  FT_LOCAL_DEF( void )
  FTC_GNode_Init( FTC_GNode   gnode,
                  FT_UInt     gindex,
                  FTC_Family  family )
  {
    gnode->family = family;
    gnode->gindex = gindex;
    family->num_nodes++;
  }

  FT_LOCAL_DEF( void )
  FTC_GNode_UnselectFamily( FTC_GNode  gnode,
                            FTC_Cache  cache )
  {
    FTC_Family  family = gnode->family;

    gnode->family = NULL;
    if ( family && --family->num_nodes == 0 )
      FTC_FAMILY_FREE( family, cache );
  }

  FT_LOCAL_DEF( void )
  FTC_GNode_Done( FTC_GNode  gnode,
                  FTC_Cache  cache )
  {
    /* finalize the node */
    gnode->gindex = 0;

    FTC_GNode_UnselectFamily( gnode, cache );
  }

  FT_LOCAL_DEF( FT_Bool )
  ftc_gnode_compare( FTC_Node    ftcgnode,
                     FT_Pointer  ftcgquery,
                     FTC_Cache   cache,
                     FT_Bool*    list_changed )
  {
    FTC_GNode   gnode  = (FTC_GNode)ftcgnode;
    FTC_GQuery  gquery = (FTC_GQuery)ftcgquery;
    FT_UNUSED( cache );

    if ( list_changed )
      *list_changed = FALSE;
    return FT_BOOL( gnode->family == gquery->family &&
                    gnode->gindex == gquery->gindex );
  }

#ifdef FTC_INLINE

  FT_LOCAL_DEF( FT_Bool )
  FTC_GNode_Compare( FTC_GNode   gnode,
                     FTC_GQuery  gquery,
                     FTC_Cache   cache,
                     FT_Bool*    list_changed )
  {
    return ftc_gnode_compare( FTC_NODE( gnode ), gquery,
                              cache, list_changed );
  }

#endif

  /*************************************************************************/
  /*************************************************************************/
  /*****                                                               *****/
  /*****                      CHUNK SETS                               *****/
  /*****                                                               *****/
  /*************************************************************************/
  /*************************************************************************/

  FT_LOCAL_DEF( void )
  FTC_Family_Init( FTC_Family  family,
                   FTC_Cache   cache )
  {
    FTC_GCacheClass  clazz = FTC_CACHE_GCACHE_CLASS( cache );

    family->clazz     = clazz->family_class;
    family->num_nodes = 0;
    family->cache     = cache;
  }

  FT_LOCAL_DEF( FT_Error )
  ftc_gcache_init( FTC_Cache  ftccache )
  {
    FTC_GCache  cache = (FTC_GCache)ftccache;
    FT_Error    error;

    error = FTC_Cache_Init( FTC_CACHE( cache ) );
    if ( !error )
    {
      FTC_GCacheClass   clazz = (FTC_GCacheClass)FTC_CACHE( cache )->org_class;

      FTC_MruList_Init( &cache->families,
                        clazz->family_class,
                        0,  /* no maximum here! */
                        cache,
                        FTC_CACHE( cache )->memory );
    }

    return error;
  }

#if 0

  FT_LOCAL_DEF( FT_Error )
  FTC_GCache_Init( FTC_GCache  cache )
  {
    return ftc_gcache_init( FTC_CACHE( cache ) );
  }

#endif /* 0 */

  FT_LOCAL_DEF( void )
  ftc_gcache_done( FTC_Cache  ftccache )
  {
    FTC_GCache  cache = (FTC_GCache)ftccache;

    FTC_Cache_Done( (FTC_Cache)cache );
    FTC_MruList_Done( &cache->families );
  }

#if 0

  FT_LOCAL_DEF( void )
  FTC_GCache_Done( FTC_GCache  cache )
  {
    ftc_gcache_done( FTC_CACHE( cache ) );
  }

#endif /* 0 */

  FT_LOCAL_DEF( FT_Error )
  FTC_GCache_New( FTC_Manager       manager,
                  FTC_GCacheClass   clazz,
                  FTC_GCache       *acache )
  {
    return FTC_Manager_RegisterCache( manager, (FTC_CacheClass)clazz,
                                      (FTC_Cache*)acache );
  }

#ifndef FTC_INLINE

  FT_LOCAL_DEF( FT_Error )
  FTC_GCache_Lookup( FTC_GCache   cache,
                     FT_Offset    hash,
                     FT_UInt      gindex,
                     FTC_GQuery   query,
                     FTC_Node    *anode )
  {
    FT_Error  error;

    query->gindex = gindex;

    FTC_MRULIST_LOOKUP( &cache->families, query, query->family, error );
    if ( !error )
    {
      FTC_Family  family = query->family;

      /* prevent the family from being destroyed too early when an        */
      /* out-of-memory condition occurs during glyph node initialization. */
      family->num_nodes++;

      error = FTC_Cache_Lookup( FTC_CACHE( cache ), hash, query, anode );

      if ( --family->num_nodes == 0 )
        FTC_FAMILY_FREE( family, cache );
    }
    return error;
  }

#endif /* !FTC_INLINE */

/* END */


text:
/****************************************************************************
 *
 * ftcsbits.h
 *
 *   A small-bitmap cache (specification).
 *
 * Copyright (C) 2000-2020 by
 * David Turner, Robert Wilhelm, and Werner Lemberg.
 *
 * This file is part of the FreeType project, and may only be used,
 * modified, and distributed under the terms of the FreeType project
 * license, LICENSE.TXT.  By continuing to use, modify, or distribute
 * this file you indicate that you have read the license and
 * understand and accept it fully.
 *
 */

#ifndef FTCSBITS_H_
#define FTCSBITS_H_

#include <ft2build.h>
#include FT_CACHE_H
#include "ftcglyph.h"

FT_BEGIN_HEADER

#define FTC_SBIT_ITEMS_PER_NODE  16

  typedef struct  FTC_SNodeRec_
  {
    FTC_GNodeRec  gnode;
    FT_UInt       count;
    FTC_SBitRec   sbits[FTC_SBIT_ITEMS_PER_NODE];

  } FTC_SNodeRec, *FTC_SNode;

#define FTC_SNODE( x )         ( (FTC_SNode)( x ) )
#define FTC_SNODE_GINDEX( x )  FTC_GNODE( x )->gindex
#define FTC_SNODE_FAMILY( x )  FTC_GNODE( x )->family

  typedef FT_UInt
  (*FTC_SFamily_GetCountFunc)( FTC_Family   family,
                               FTC_Manager  manager );

  typedef FT_Error
  (*FTC_SFamily_LoadGlyphFunc)( FTC_Family   family,
                                FT_UInt      gindex,
                                FTC_Manager  manager,
                                FT_Face     *aface );

  typedef struct  FTC_SFamilyClassRec_
  {
    FTC_MruListClassRec        clazz;
    FTC_SFamily_GetCountFunc   family_get_count;
    FTC_SFamily_LoadGlyphFunc  family_load_glyph;

  } FTC_SFamilyClassRec;

  typedef const FTC_SFamilyClassRec*  FTC_SFamilyClass;

#define FTC_SFAMILY_CLASS( x )  ((FTC_SFamilyClass)(x))

#define FTC_CACHE_SFAMILY_CLASS( x )  \
          FTC_SFAMILY_CLASS( FTC_CACHE_GCACHE_CLASS( x )->family_class )

  FT_LOCAL( void )
  FTC_SNode_Free( FTC_SNode  snode,
                  FTC_Cache  cache );

  FT_LOCAL( FT_Error )
  FTC_SNode_New( FTC_SNode   *psnode,
                 FTC_GQuery   gquery,
                 FTC_Cache    cache );

#if 0
  FT_LOCAL( FT_ULong )
  FTC_SNode_Weight( FTC_SNode  inode );
#endif

#ifdef FTC_INLINE

  FT_LOCAL( FT_Bool )
  FTC_SNode_Compare( FTC_SNode   snode,
                     FTC_GQuery  gquery,
                     FTC_Cache   cache,
                     FT_Bool*    list_changed);

#endif

  /* */

FT_END_HEADER

#endif /* FTCSBITS_H_ */

/* END */


text:
/****************************************************************************
 *
 * ftcimage.c
 *
 *   FreeType Image cache (body).
 *
 * Copyright (C) 2000-2020 by
 * David Turner, Robert Wilhelm, and Werner Lemberg.
 *
 * This file is part of the FreeType project, and may only be used,
 * modified, and distributed under the terms of the FreeType project
 * license, LICENSE.TXT.  By continuing to use, modify, or distribute
 * this file you indicate that you have read the license and
 * understand and accept it fully.
 *
 */

#include <ft2build.h>
#include FT_CACHE_H
#include "ftcimage.h"
#include FT_INTERNAL_MEMORY_H
#include FT_INTERNAL_OBJECTS_H

#include "ftccback.h"
#include "ftcerror.h"

  /* finalize a given glyph image node */
  FT_LOCAL_DEF( void )
  ftc_inode_free( FTC_Node   ftcinode,
                  FTC_Cache  cache )
  {
    FTC_INode  inode = (FTC_INode)ftcinode;
    FT_Memory  memory = cache->memory;

    if ( inode->glyph )
    {
      FT_Done_Glyph( inode->glyph );
      inode->glyph = NULL;
    }

    FTC_GNode_Done( FTC_GNODE( inode ), cache );
    FT_FREE( inode );
  }

  FT_LOCAL_DEF( void )
  FTC_INode_Free( FTC_INode  inode,
                  FTC_Cache  cache )
  {
    ftc_inode_free( FTC_NODE( inode ), cache );
  }

  /* initialize a new glyph image node */
  FT_LOCAL_DEF( FT_Error )
  FTC_INode_New( FTC_INode   *pinode,
                 FTC_GQuery   gquery,
                 FTC_Cache    cache )
  {
    FT_Memory  memory = cache->memory;
    FT_Error   error;
    FTC_INode  inode  = NULL;

    if ( !FT_NEW( inode ) )
    {
      FTC_GNode         gnode  = FTC_GNODE( inode );
      FTC_Family        family = gquery->family;
      FT_UInt           gindex = gquery->gindex;
      FTC_IFamilyClass  clazz  = FTC_CACHE_IFAMILY_CLASS( cache );

      /* initialize its inner fields */
      FTC_GNode_Init( gnode, gindex, family );

      /* we will now load the glyph image */
      error = clazz->family_load_glyph( family, gindex, cache,
                                        &inode->glyph );
      if ( error )
      {
        FTC_INode_Free( inode, cache );
        inode = NULL;
      }
    }

    *pinode = inode;
    return error;
  }

  FT_LOCAL_DEF( FT_Error )
  ftc_inode_new( FTC_Node   *ftcpinode,
                 FT_Pointer  ftcgquery,
                 FTC_Cache   cache )
  {
    FTC_INode  *pinode = (FTC_INode*)ftcpinode;
    FTC_GQuery  gquery = (FTC_GQuery)ftcgquery;

    return FTC_INode_New( pinode, gquery, cache );
  }

  FT_LOCAL_DEF( FT_Offset )
  ftc_inode_weight( FTC_Node   ftcinode,
                    FTC_Cache  ftccache )
  {
    FTC_INode  inode = (FTC_INode)ftcinode;
    FT_Offset  size  = 0;
    FT_Glyph   glyph = inode->glyph;

    FT_UNUSED( ftccache );

    switch ( glyph->format )
    {
    case FT_GLYPH_FORMAT_BITMAP:
      {
        FT_BitmapGlyph  bitg;

        bitg = (FT_BitmapGlyph)glyph;
        size = bitg->bitmap.rows * (FT_Offset)FT_ABS( bitg->bitmap.pitch ) +
               sizeof ( *bitg );
      }
      break;

    case FT_GLYPH_FORMAT_OUTLINE:
      {
        FT_OutlineGlyph  outg;

        outg = (FT_OutlineGlyph)glyph;
        size = (FT_Offset)outg->outline.n_points *
                 ( sizeof ( FT_Vector ) + sizeof ( FT_Byte ) ) +
               (FT_Offset)outg->outline.n_contours * sizeof ( FT_Short ) +
               sizeof ( *outg );
      }
      break;

    default:
      ;
    }

    size += sizeof ( *inode );
    return size;
  }

#if 0

  FT_LOCAL_DEF( FT_Offset )
  FTC_INode_Weight( FTC_INode  inode )
  {
    return ftc_inode_weight( FTC_NODE( inode ), NULL );
  }

#endif /* 0 */

/* END */


text:
/****************************************************************************
 *
 * ftcmru.h
 *
 *   Simple MRU list-cache (specification).
 *
 * Copyright (C) 2000-2020 by
 * David Turner, Robert Wilhelm, and Werner Lemberg.
 *
 * This file is part of the FreeType project, and may only be used,
 * modified, and distributed under the terms of the FreeType project
 * license, LICENSE.TXT.  By continuing to use, modify, or distribute
 * this file you indicate that you have read the license and
 * understand and accept it fully.
 *
 */

  /**************************************************************************
   *
   * An MRU is a list that cannot hold more than a certain number of
   * elements (`max_elements').  All elements in the list are sorted in
   * least-recently-used order, i.e., the `oldest' element is at the tail
   * of the list.
   *
   * When doing a lookup (either through `Lookup()' or `Lookup_Node()'),
   * the list is searched for an element with the corresponding key.  If
   * it is found, the element is moved to the head of the list and is
   * returned.
   *
   * If no corresponding element is found, the lookup routine will try to
   * obtain a new element with the relevant key.  If the list is already
   * full, the oldest element from the list is discarded and replaced by a
   * new one; a new element is added to the list otherwise.
   *
   * Note that it is possible to pre-allocate the element list nodes.
   * This is handy if `max_elements' is sufficiently small, as it saves
   * allocations/releases during the lookup process.
   *
   */

#ifndef FTCMRU_H_
#define FTCMRU_H_

#include <ft2build.h>
#include FT_FREETYPE_H

#ifdef FREETYPE_H
#error "freetype.h of FreeType 1 has been loaded!"
#error "Please fix the directory search order for header files"
#error "so that freetype.h of FreeType 2 is found first."
#endif

#define  xxFT_DEBUG_ERROR
#define  FTC_INLINE

FT_BEGIN_HEADER

  typedef struct FTC_MruNodeRec_*  FTC_MruNode;

  typedef struct  FTC_MruNodeRec_
  {
    FTC_MruNode  next;
    FTC_MruNode  prev;

  } FTC_MruNodeRec;

  FT_LOCAL( void )
  FTC_MruNode_Prepend( FTC_MruNode  *plist,
                       FTC_MruNode   node );

  FT_LOCAL( void )
  FTC_MruNode_Up( FTC_MruNode  *plist,
                  FTC_MruNode   node );

  FT_LOCAL( void )
  FTC_MruNode_Remove( FTC_MruNode  *plist,
                      FTC_MruNode   node );

  typedef struct FTC_MruListRec_*              FTC_MruList;

  typedef struct FTC_MruListClassRec_ const *  FTC_MruListClass;

  typedef FT_Bool
  (*FTC_MruNode_CompareFunc)( FTC_MruNode  node,
                              FT_Pointer   key );

  typedef FT_Error
  (*FTC_MruNode_InitFunc)( FTC_MruNode  node,
                           FT_Pointer   key,
                           FT_Pointer   data );

  typedef FT_Error
  (*FTC_MruNode_ResetFunc)( FTC_MruNode  node,
                            FT_Pointer   key,
                            FT_Pointer   data );

  typedef void
  (*FTC_MruNode_DoneFunc)( FTC_MruNode  node,
                           FT_Pointer   data );

  typedef struct  FTC_MruListClassRec_
  {
    FT_Offset                node_size;

    FTC_MruNode_CompareFunc  node_compare;
    FTC_MruNode_InitFunc     node_init;
    FTC_MruNode_ResetFunc    node_reset;
    FTC_MruNode_DoneFunc     node_done;

  } FTC_MruListClassRec;

  typedef struct  FTC_MruListRec_
  {
    FT_UInt              num_nodes;
    FT_UInt              max_nodes;
    FTC_MruNode          nodes;
    FT_Pointer           data;
    FTC_MruListClassRec  clazz;
    FT_Memory            memory;

  } FTC_MruListRec;

  FT_LOCAL( void )
  FTC_MruList_Init( FTC_MruList       list,
                    FTC_MruListClass  clazz,
                    FT_UInt           max_nodes,
                    FT_Pointer        data,
                    FT_Memory         memory );

  FT_LOCAL( void )
  FTC_MruList_Reset( FTC_MruList  list );

  FT_LOCAL( void )
  FTC_MruList_Done( FTC_MruList  list );

  FT_LOCAL( FT_Error )
  FTC_MruList_New( FTC_MruList   list,
                   FT_Pointer    key,
                   FTC_MruNode  *anode );

  FT_LOCAL( void )
  FTC_MruList_Remove( FTC_MruList  list,
                      FTC_MruNode  node );

  FT_LOCAL( void )
  FTC_MruList_RemoveSelection( FTC_MruList              list,
                               FTC_MruNode_CompareFunc  selection,
                               FT_Pointer               key );

#ifdef FTC_INLINE

#define FTC_MRULIST_LOOKUP_CMP( list, key, compare, node, error )           \
  FT_BEGIN_STMNT                                                            \
    FTC_MruNode*             _pfirst  = &(list)->nodes;                     \
    FTC_MruNode_CompareFunc  _compare = (FTC_MruNode_CompareFunc)(compare); \
    FTC_MruNode              _first, _node;                                 \
                                                                            \
                                                                            \
    error  = FT_Err_Ok;                                                     \
    _first = *(_pfirst);                                                    \
    _node  = NULL;                                                          \
                                                                            \
    if ( _first )                                                           \
    {                                                                       \
      _node = _first;                                                       \
      do                                                                    \
      {                                                                     \
        if ( _compare( _node, (key) ) )                                     \
        {                                                                   \
          if ( _node != _first )                                            \
            FTC_MruNode_Up( _pfirst, _node );                               \
                                                                            \
          node = _node;                                                     \
          goto MruOk_;                                                      \
        }                                                                   \
        _node = _node->next;                                                \
                                                                            \
      } while ( _node != _first);                                           \
    }                                                                       \
                                                                            \
    error = FTC_MruList_New( (list), (key), (FTC_MruNode*)(void*)&(node) ); \
  MruOk_:                                                                   \
    ;                                                                       \
  FT_END_STMNT

#define FTC_MRULIST_LOOKUP( list, key, node, error ) \
  FTC_MRULIST_LOOKUP_CMP( list, key, (list)->clazz.node_compare, node, error )

#else  /* !FTC_INLINE */

  FT_LOCAL( FTC_MruNode )
  FTC_MruList_Find( FTC_MruList  list,
                    FT_Pointer   key );

  FT_LOCAL( FT_Error )
  FTC_MruList_Lookup( FTC_MruList   list,
                      FT_Pointer    key,
                      FTC_MruNode  *pnode );

#define FTC_MRULIST_LOOKUP( list, key, node, error ) \
  error = FTC_MruList_Lookup( (list), (key), (FTC_MruNode*)&(node) )

#endif /* !FTC_INLINE */

#define FTC_MRULIST_LOOP( list, node )        \
  FT_BEGIN_STMNT                              \
    FTC_MruNode  _first = (list)->nodes;      \
                                              \
                                              \
    if ( _first )                             \
    {                                         \
      FTC_MruNode  _node = _first;            \
                                              \
                                              \
      do                                      \
      {                                       \
        *(FTC_MruNode*)&(node) = _node;

#define FTC_MRULIST_LOOP_END()               \
        _node = _node->next;                 \
                                             \
      } while ( _node != _first );           \
    }                                        \
  FT_END_STMNT

 /* */

FT_END_HEADER

#endif /* FTCMRU_H_ */

/* END */


text:
# FreeType 2 src/cache Jamfile
#
# Copyright (C) 2001-2020 by
# David Turner, Robert Wilhelm, and Werner Lemberg.
#
# This file is part of the FreeType project, and may only be used, modified,
# and distributed under the terms of the FreeType project license,
# LICENSE.TXT.  By continuing to use, modify, or distribute this file you
# indicate that you have read the license and understand and accept it
# fully.

SubDir  FT2_TOP $(FT2_SRC_DIR) cache ;

{
  local  _sources ;

  if $(FT2_MULTI)
  {
    _sources = ftcbasic
               ftccache
               ftcglyph
               ftcimage
               ftcmanag
               ftccmap
               ftcmru
               ftcsbits
               ;
  }
  else
  {
    _sources = ftcache ;
  }

  Library  $(FT2_LIB) : $(_sources).c ;
}

# end of src/cache Jamfile


text:
/****************************************************************************
 *
 * ftcimage.h
 *
 *   FreeType Generic Image cache (specification)
 *
 * Copyright (C) 2000-2020 by
 * David Turner, Robert Wilhelm, and Werner Lemberg.
 *
 * This file is part of the FreeType project, and may only be used,
 * modified, and distributed under the terms of the FreeType project
 * license, LICENSE.TXT.  By continuing to use, modify, or distribute
 * this file you indicate that you have read the license and
 * understand and accept it fully.
 *
 */

 /*
  * FTC_ICache is an _abstract_ cache used to store a single FT_Glyph
  * image per cache node.
  *
  * FTC_ICache extends FTC_GCache.  For an implementation example,
  * see FTC_ImageCache in `src/cache/ftbasic.c'.
  */

  /**************************************************************************
   *
   * Each image cache really manages FT_Glyph objects.
   *
   */

#ifndef FTCIMAGE_H_
#define FTCIMAGE_H_

#include <ft2build.h>
#include FT_CACHE_H
#include "ftcglyph.h"

FT_BEGIN_HEADER

  /* the FT_Glyph image node type - we store only 1 glyph per node */
  typedef struct  FTC_INodeRec_
  {
    FTC_GNodeRec  gnode;
    FT_Glyph      glyph;

  } FTC_INodeRec, *FTC_INode;

#define FTC_INODE( x )         ( (FTC_INode)( x ) )
#define FTC_INODE_GINDEX( x )  FTC_GNODE(x)->gindex
#define FTC_INODE_FAMILY( x )  FTC_GNODE(x)->family

  typedef FT_Error
  (*FTC_IFamily_LoadGlyphFunc)( FTC_Family  family,
                                FT_UInt     gindex,
                                FTC_Cache   cache,
                                FT_Glyph   *aglyph );

  typedef struct  FTC_IFamilyClassRec_
  {
    FTC_MruListClassRec        clazz;
    FTC_IFamily_LoadGlyphFunc  family_load_glyph;

  } FTC_IFamilyClassRec;

  typedef const FTC_IFamilyClassRec*  FTC_IFamilyClass;

#define FTC_IFAMILY_CLASS( x )  ((FTC_IFamilyClass)(x))

#define FTC_CACHE_IFAMILY_CLASS( x ) \
          FTC_IFAMILY_CLASS( FTC_CACHE_GCACHE_CLASS(x)->family_class )

  /* can be used as a @FTC_Node_FreeFunc */
  FT_LOCAL( void )
  FTC_INode_Free( FTC_INode  inode,
                  FTC_Cache  cache );

  /* Can be used as @FTC_Node_NewFunc.  `gquery.index' and `gquery.family'
   * must be set correctly.  This function will call the `family_load_glyph'
   * method to load the FT_Glyph into the cache node.
   */
  FT_LOCAL( FT_Error )
  FTC_INode_New( FTC_INode   *pinode,
                 FTC_GQuery   gquery,
                 FTC_Cache    cache );

#if 0
  /* can be used as @FTC_Node_WeightFunc */
  FT_LOCAL( FT_ULong )
  FTC_INode_Weight( FTC_INode  inode );
#endif

 /* */

FT_END_HEADER

#endif /* FTCIMAGE_H_ */

/* END */


text:
/****************************************************************************
 *
 * ftcerror.h
 *
 *   Caching sub-system error codes (specification only).
 *
 * Copyright (C) 2001-2020 by
 * David Turner, Robert Wilhelm, and Werner Lemberg.
 *
 * This file is part of the FreeType project, and may only be used,
 * modified, and distributed under the terms of the FreeType project
 * license, LICENSE.TXT.  By continuing to use, modify, or distribute
 * this file you indicate that you have read the license and
 * understand and accept it fully.
 *
 */

  /**************************************************************************
   *
   * This file is used to define the caching sub-system error enumeration
   * constants.
   *
   */

#ifndef FTCERROR_H_
#define FTCERROR_H_

#include FT_MODULE_ERRORS_H

#undef FTERRORS_H_

#undef  FT_ERR_PREFIX
#define FT_ERR_PREFIX  FTC_Err_
#define FT_ERR_BASE    FT_Mod_Err_Cache

#include FT_ERRORS_H

#endif /* FTCERROR_H_ */

/* END */


text:
/****************************************************************************
 *
 * ftccache.c
 *
 *   The FreeType internal cache interface (body).
 *
 * Copyright (C) 2000-2020 by
 * David Turner, Robert Wilhelm, and Werner Lemberg.
 *
 * This file is part of the FreeType project, and may only be used,
 * modified, and distributed under the terms of the FreeType project
 * license, LICENSE.TXT.  By continuing to use, modify, or distribute
 * this file you indicate that you have read the license and
 * understand and accept it fully.
 *
 */

#include <ft2build.h>
#include "ftcmanag.h"
#include FT_INTERNAL_OBJECTS_H
#include FT_INTERNAL_DEBUG_H

#include "ftccback.h"
#include "ftcerror.h"

#undef  FT_COMPONENT
#define FT_COMPONENT  cache

#define FTC_HASH_MAX_LOAD  2
#define FTC_HASH_MIN_LOAD  1
#define FTC_HASH_SUB_LOAD  ( FTC_HASH_MAX_LOAD - FTC_HASH_MIN_LOAD )

  /* this one _must_ be a power of 2! */
#define FTC_HASH_INITIAL_SIZE  8

  /*************************************************************************/
  /*************************************************************************/
  /*****                                                               *****/
  /*****                   CACHE NODE DEFINITIONS                      *****/
  /*****                                                               *****/
  /*************************************************************************/
  /*************************************************************************/

  /* add a new node to the head of the manager's circular MRU list */
  static void
  ftc_node_mru_link( FTC_Node     node,
                     FTC_Manager  manager )
  {
    void  *nl = &manager->nodes_list;

    FTC_MruNode_Prepend( (FTC_MruNode*)nl,
                         (FTC_MruNode)node );
    manager->num_nodes++;
  }

  /* remove a node from the manager's MRU list */
  static void
  ftc_node_mru_unlink( FTC_Node     node,
                       FTC_Manager  manager )
  {
    void  *nl = &manager->nodes_list;

    FTC_MruNode_Remove( (FTC_MruNode*)nl,
                        (FTC_MruNode)node );
    manager->num_nodes--;
  }

#ifndef FTC_INLINE

  /* move a node to the head of the manager's MRU list */
  static void
  ftc_node_mru_up( FTC_Node     node,
                   FTC_Manager  manager )
  {
    FTC_MruNode_Up( (FTC_MruNode*)&manager->nodes_list,
                    (FTC_MruNode)node );
  }

  /* get a top bucket for specified hash from cache,
   * body for FTC_NODE_TOP_FOR_HASH( cache, hash )
   */
  FT_LOCAL_DEF( FTC_Node* )
  ftc_get_top_node_for_hash( FTC_Cache  cache,
                             FT_Offset  hash )
  {
    FTC_Node*  pnode;
    FT_Offset  idx;

    idx = hash & cache->mask;
    if ( idx < cache->p )
      idx = hash & ( 2 * cache->mask + 1 );
    pnode = cache->buckets + idx;
    return pnode;
  }

#endif /* !FTC_INLINE */

  /* Note that this function cannot fail.  If we cannot re-size the
   * buckets array appropriately, we simply degrade the hash table's
   * performance!
   */
  static void
  ftc_cache_resize( FTC_Cache  cache )
  {
    for (;;)
    {
      FTC_Node  node, *pnode;
      FT_UFast  p     = cache->p;
      FT_UFast  mask  = cache->mask;
      FT_UFast  count = mask + p + 1;    /* number of buckets */

      /* do we need to shrink the buckets array? */
      if ( cache->slack < 0 )
      {
        FTC_Node  new_list = NULL;

        /* try to expand the buckets array _before_ splitting
         * the bucket lists
         */
        if ( p >= mask )
        {
          FT_Memory  memory = cache->memory;
          FT_Error   error;

          /* if we can't expand the array, leave immediately */
          if ( FT_RENEW_ARRAY( cache->buckets,
                               ( mask + 1 ) * 2, ( mask + 1 ) * 4 ) )
            break;
        }

        /* split a single bucket */
        pnode = cache->buckets + p;

        for (;;)
        {
          node = *pnode;
          if ( !node )
            break;

          if ( node->hash & ( mask + 1 ) )
          {
            *pnode     = node->link;
            node->link = new_list;
            new_list   = node;
          }
          else
            pnode = &node->link;
        }

        cache->buckets[p + mask + 1] = new_list;

        cache->slack += FTC_HASH_MAX_LOAD;

        if ( p >= mask )
        {
          cache->mask = 2 * mask + 1;
          cache->p    = 0;
        }
        else
          cache->p = p + 1;
      }

      /* do we need to expand the buckets array? */
      else if ( cache->slack > (FT_Long)count * FTC_HASH_SUB_LOAD )
      {
        FT_UFast   old_index = p + mask;
        FTC_Node*  pold;

        if ( old_index + 1 <= FTC_HASH_INITIAL_SIZE )
          break;

        if ( p == 0 )
        {
          FT_Memory  memory = cache->memory;
          FT_Error   error;

          /* if we can't shrink the array, leave immediately */
          if ( FT_RENEW_ARRAY( cache->buckets,
                               ( mask + 1 ) * 2, mask + 1 ) )
            break;

          cache->mask >>= 1;
          p             = cache->mask;
        }
        else
          p--;

        pnode = cache->buckets + p;
        while ( *pnode )
          pnode = &(*pnode)->link;

        pold   = cache->buckets + old_index;
        *pnode = *pold;
        *pold  = NULL;

        cache->slack -= FTC_HASH_MAX_LOAD;
        cache->p      = p;
      }

      /* otherwise, the hash table is balanced */
      else
        break;
    }
  }

  /* remove a node from its cache's hash table */
  static void
  ftc_node_hash_unlink( FTC_Node   node0,
                        FTC_Cache  cache )
  {
    FTC_Node  *pnode = FTC_NODE_TOP_FOR_HASH( cache, node0->hash );

    for (;;)
    {
      FTC_Node  node = *pnode;

      if ( !node )
      {
        FT_TRACE0(( "ftc_node_hash_unlink: unknown node\n" ));
        return;
      }

      if ( node == node0 )
        break;

      pnode = &(*pnode)->link;
    }

    *pnode      = node0->link;
    node0->link = NULL;

    cache->slack++;
    ftc_cache_resize( cache );
  }

  /* add a node to the `top' of its cache's hash table */
  static void
  ftc_node_hash_link( FTC_Node   node,
                      FTC_Cache  cache )
  {
    FTC_Node  *pnode = FTC_NODE_TOP_FOR_HASH( cache, node->hash );

    node->link = *pnode;
    *pnode     = node;

    cache->slack--;
    ftc_cache_resize( cache );
  }

  /* remove a node from the cache manager */
  FT_LOCAL_DEF( void )
  ftc_node_destroy( FTC_Node     node,
                    FTC_Manager  manager )
  {
    FTC_Cache  cache;

#ifdef FT_DEBUG_ERROR
    /* find node's cache */
    if ( node->cache_index >= manager->num_caches )
    {
      FT_TRACE0(( "ftc_node_destroy: invalid node handle\n" ));
      return;
    }
#endif

    cache = manager->caches[node->cache_index];

#ifdef FT_DEBUG_ERROR
    if ( !cache )
    {
      FT_TRACE0(( "ftc_node_destroy: invalid node handle\n" ));
      return;
    }
#endif

    manager->cur_weight -= cache->clazz.node_weight( node, cache );

    /* remove node from mru list */
    ftc_node_mru_unlink( node, manager );

    /* remove node from cache's hash table */
    ftc_node_hash_unlink( node, cache );

    /* now finalize it */
    cache->clazz.node_free( node, cache );

#if 0
    /* check, just in case of general corruption :-) */
    if ( manager->num_nodes == 0 )
      FT_TRACE0(( "ftc_node_destroy: invalid cache node count (%d)\n",
                  manager->num_nodes ));
#endif
  }

  /*************************************************************************/
  /*************************************************************************/
  /*****                                                               *****/
  /*****                    ABSTRACT CACHE CLASS                       *****/
  /*****                                                               *****/
  /*************************************************************************/
  /*************************************************************************/

  FT_LOCAL_DEF( FT_Error )
  FTC_Cache_Init( FTC_Cache  cache )
  {
    return ftc_cache_init( cache );
  }

  FT_LOCAL_DEF( FT_Error )
  ftc_cache_init( FTC_Cache  cache )
  {
    FT_Memory  memory = cache->memory;
    FT_Error   error;

    cache->p     = 0;
    cache->mask  = FTC_HASH_INITIAL_SIZE - 1;
    cache->slack = FTC_HASH_INITIAL_SIZE * FTC_HASH_MAX_LOAD;

    (void)FT_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE * 2 );
    return error;
  }

  static void
  FTC_Cache_Clear( FTC_Cache  cache )
  {
    if ( cache && cache->buckets )
    {
      FTC_Manager  manager = cache->manager;
      FT_UFast     i;
      FT_UFast     count;

      count = cache->p + cache->mask + 1;

      for ( i = 0; i < count; i++ )
      {
        FTC_Node  *pnode = cache->buckets + i, next, node = *pnode;

        while ( node )
        {
          next        = node->link;
          node->link  = NULL;

          /* remove node from mru list */
          ftc_node_mru_unlink( node, manager );

          /* now finalize it */
          manager->cur_weight -= cache->clazz.node_weight( node, cache );

          cache->clazz.node_free( node, cache );
          node = next;
        }
        cache->buckets[i] = NULL;
      }
      ftc_cache_resize( cache );
    }
  }

  FT_LOCAL_DEF( void )
  ftc_cache_done( FTC_Cache  cache )
  {
    if ( cache->memory )
    {
      FT_Memory  memory = cache->memory;

      FTC_Cache_Clear( cache );

      FT_FREE( cache->buckets );
      cache->mask  = 0;
      cache->p     = 0;
      cache->slack = 0;

      cache->memory = NULL;
    }
  }

  FT_LOCAL_DEF( void )
  FTC_Cache_Done( FTC_Cache  cache )
  {
    ftc_cache_done( cache );
  }

  static void
  ftc_cache_add( FTC_Cache  cache,
                 FT_Offset  hash,
                 FTC_Node   node )
  {
    node->hash        = hash;
    node->cache_index = (FT_UInt16)cache->index;
    node->ref_count   = 0;

    ftc_node_hash_link( node, cache );
    ftc_node_mru_link( node, cache->manager );

    {
      FTC_Manager  manager = cache->manager;

      manager->cur_weight += cache->clazz.node_weight( node, cache );

      if ( manager->cur_weight >= manager->max_weight )
      {
        node->ref_count++;
        FTC_Manager_Compress( manager );
        node->ref_count--;
      }
    }
  }

  FT_LOCAL_DEF( FT_Error )
  FTC_Cache_NewNode( FTC_Cache   cache,
                     FT_Offset   hash,
                     FT_Pointer  query,
                     FTC_Node   *anode )
  {
    FT_Error  error;
    FTC_Node  node;

    /*
     * We use the FTC_CACHE_TRYLOOP macros to support out-of-memory
     * errors (OOM) correctly, i.e., by flushing the cache progressively
     * in order to make more room.
     */

    FTC_CACHE_TRYLOOP( cache )
    {
      error = cache->clazz.node_new( &node, query, cache );
    }
    FTC_CACHE_TRYLOOP_END( NULL );

    if ( error )
      node = NULL;
    else
    {
     /* don't assume that the cache has the same number of buckets, since
      * our allocation request might have triggered global cache flushing
      */
      ftc_cache_add( cache, hash, node );
    }

    *anode = node;
    return error;
  }

#ifndef FTC_INLINE

  FT_LOCAL_DEF( FT_Error )
  FTC_Cache_Lookup( FTC_Cache   cache,
                    FT_Offset   hash,
                    FT_Pointer  query,
                    FTC_Node   *anode )
  {
    FTC_Node*  bucket;
    FTC_Node*  pnode;
    FTC_Node   node;
    FT_Error   error        = FT_Err_Ok;
    FT_Bool    list_changed = FALSE;

    FTC_Node_CompareFunc  compare = cache->clazz.node_compare;

    if ( !cache || !anode )
      return FT_THROW( Invalid_Argument );

    /* Go to the `top' node of the list sharing same masked hash */
    bucket = pnode = FTC_NODE_TOP_FOR_HASH( cache, hash );

    /* Lookup a node with exactly same hash and queried properties.  */
    /* NOTE: _nodcomp() may change the linked list to reduce memory. */
    for (;;)
    {
      node = *pnode;
      if ( !node )
        goto NewNode;

      if ( node->hash == hash                           &&
           compare( node, query, cache, &list_changed ) )
        break;

      pnode = &node->link;
    }

    if ( list_changed )
    {
      /* Update bucket by modified linked list */
      bucket = pnode = FTC_NODE_TOP_FOR_HASH( cache, hash );

      /* Update pnode by modified linked list */
      while ( *pnode != node )
      {
        if ( !*pnode )
        {
          FT_ERROR(( "FTC_Cache_Lookup: oops!!!  node missing\n" ));
          goto NewNode;
        }
        else
          pnode = &((*pnode)->link);
      }
    }

    /* Reorder the list to move the found node to the `top' */
    if ( node != *bucket )
    {
      *pnode     = node->link;
      node->link = *bucket;
      *bucket    = node;
    }

    /* move to head of MRU list */
    {
      FTC_Manager  manager = cache->manager;

      if ( node != manager->nodes_list )
        ftc_node_mru_up( node, manager );
    }
    *anode = node;

    return error;

  NewNode:
    return FTC_Cache_NewNode( cache, hash, query, anode );
  }

#endif /* !FTC_INLINE */

  FT_LOCAL_DEF( void )
  FTC_Cache_RemoveFaceID( FTC_Cache   cache,
                          FTC_FaceID  face_id )
  {
    FT_UFast     i, count;
    FTC_Manager  manager = cache->manager;
    FTC_Node     frees   = NULL;

    count = cache->p + cache->mask + 1;
    for ( i = 0; i < count; i++ )
    {
      FTC_Node*  bucket = cache->buckets + i;
      FTC_Node*  pnode  = bucket;

      for (;;)
      {
        FTC_Node  node = *pnode;
        FT_Bool   list_changed = FALSE;

        if ( !node )
          break;

        if ( cache->clazz.node_remove_faceid( node, face_id,
                                              cache, &list_changed ) )
        {
          *pnode     = node->link;
          node->link = frees;
          frees      = node;
        }
        else
          pnode = &node->link;
      }
    }

    /* remove all nodes in the free list */
    while ( frees )
    {
      FTC_Node  node;

      node  = frees;
      frees = node->link;

      manager->cur_weight -= cache->clazz.node_weight( node, cache );
      ftc_node_mru_unlink( node, manager );

      cache->clazz.node_free( node, cache );

      cache->slack++;
    }

    ftc_cache_resize( cache );
  }

/* END */


text:
/****************************************************************************
 *
 * ftcache.c
 *
 *   The FreeType Caching sub-system (body only).
 *
 * Copyright (C) 2000-2020 by
 * David Turner, Robert Wilhelm, and Werner Lemberg.
 *
 * This file is part of the FreeType project, and may only be used,
 * modified, and distributed under the terms of the FreeType project
 * license, LICENSE.TXT.  By continuing to use, modify, or distribute
 * this file you indicate that you have read the license and
 * understand and accept it fully.
 *
 */

#define FT_MAKE_OPTION_SINGLE_OBJECT
#include <ft2build.h>

#include "ftcbasic.c"
#include "ftccache.c"
#include "ftccmap.c"
#include "ftcglyph.c"
#include "ftcimage.c"
#include "ftcmanag.c"
#include "ftcmru.c"
#include "ftcsbits.c"

/* END */


text:
/****************************************************************************
 *
 * ftcsbits.c
 *
 *   FreeType sbits manager (body).
 *
 * Copyright (C) 2000-2020 by
 * David Turner, Robert Wilhelm, and Werner Lemberg.
 *
 * This file is part of the FreeType project, and may only be used,
 * modified, and distributed under the terms of the FreeType project
 * license, LICENSE.TXT.  By continuing to use, modify, or distribute
 * this file you indicate that you have read the license and
 * understand and accept it fully.
 *
 */

#include <ft2build.h>
#include FT_CACHE_H
#include "ftcsbits.h"
#include FT_INTERNAL_OBJECTS_H
#include FT_INTERNAL_DEBUG_H
#include FT_ERRORS_H

#include "ftccback.h"
#include "ftcerror.h"

#undef  FT_COMPONENT
#define FT_COMPONENT  cache

  /*************************************************************************/
  /*************************************************************************/
  /*****                                                               *****/
  /*****                     SBIT CACHE NODES                          *****/
  /*****                                                               *****/
  /*************************************************************************/
  /*************************************************************************/

  static FT_Error
  ftc_sbit_copy_bitmap( FTC_SBit    sbit,
                        FT_Bitmap*  bitmap,
                        FT_Memory   memory )
  {
    FT_Error  error;
    FT_Int    pitch = bitmap->pitch;
    FT_ULong  size;

    if ( pitch < 0 )
      pitch = -pitch;

    size = (FT_ULong)pitch * bitmap->rows;
    if ( !size )
      return FT_Err_Ok;

    if ( !FT_ALLOC( sbit->buffer, size ) )
      FT_MEM_COPY( sbit->buffer, bitmap->buffer, size );

    return error;
  }

  FT_LOCAL_DEF( void )
  ftc_snode_free( FTC_Node   ftcsnode,
                  FTC_Cache  cache )
  {
    FTC_SNode  snode  = (FTC_SNode)ftcsnode;
    FTC_SBit   sbit   = snode->sbits;
    FT_UInt    count  = snode->count;
    FT_Memory  memory = cache->memory;

    for ( ; count > 0; sbit++, count-- )
      FT_FREE( sbit->buffer );

    FTC_GNode_Done( FTC_GNODE( snode ), cache );

    FT_FREE( snode );
  }

  FT_LOCAL_DEF( void )
  FTC_SNode_Free( FTC_SNode  snode,
                  FTC_Cache  cache )
  {
    ftc_snode_free( FTC_NODE( snode ), cache );
  }

  /*
   * This function tries to load a small bitmap within a given FTC_SNode.
   * Note that it returns a non-zero error code _only_ in the case of
   * out-of-memory condition.  For all other errors (e.g., corresponding
   * to a bad font file), this function will mark the sbit as `unavailable'
   * and return a value of 0.
   *
   * You should also read the comment within the @ftc_snode_compare
   * function below to see how out-of-memory is handled during a lookup.
   */
  static FT_Error
  ftc_snode_load( FTC_SNode    snode,
                  FTC_Manager  manager,
                  FT_UInt      gindex,
                  FT_ULong    *asize )
  {
    FT_Error          error;
    FTC_GNode         gnode  = FTC_GNODE( snode );
    FTC_Family        family = gnode->family;
    FT_Memory         memory = manager->memory;
    FT_Face           face;
    FTC_SBit          sbit;
    FTC_SFamilyClass  clazz;

    if ( (FT_UInt)(gindex - gnode->gindex) >= snode->count )
    {
      FT_ERROR(( "ftc_snode_load: invalid glyph index" ));
      return FT_THROW( Invalid_Argument );
    }

    sbit  = snode->sbits + ( gindex - gnode->gindex );
    clazz = (FTC_SFamilyClass)family->clazz;

    sbit->buffer = 0;

    error = clazz->family_load_glyph( family, gindex, manager, &face );
    if ( error )
      goto BadGlyph;

    {
      FT_Int        temp;
      FT_GlyphSlot  slot   = face->glyph;
      FT_Bitmap*    bitmap = &slot->bitmap;
      FT_Pos        xadvance, yadvance; /* FT_GlyphSlot->advance.{x|y} */

      if ( slot->format != FT_GLYPH_FORMAT_BITMAP )
      {
        FT_TRACE0(( "ftc_snode_load:"
                    " glyph loaded didn't return a bitmap\n" ));
        goto BadGlyph;
      }

      /* Check whether our values fit into 8-bit containers!    */
      /* If this is not the case, our bitmap is too large       */
      /* and we will leave it as `missing' with sbit.buffer = 0 */

#define CHECK_CHAR( d )  ( temp = (FT_Char)d, (FT_Int) temp == (FT_Int) d )
#define CHECK_BYTE( d )  ( temp = (FT_Byte)d, (FT_UInt)temp == (FT_UInt)d )

      /* horizontal advance in pixels */
      xadvance = ( slot->advance.x + 32 ) >> 6;
      yadvance = ( slot->advance.y + 32 ) >> 6;

      if ( !CHECK_BYTE( bitmap->rows  )     ||
           !CHECK_BYTE( bitmap->width )     ||
           !CHECK_CHAR( bitmap->pitch )     ||
           !CHECK_CHAR( slot->bitmap_left ) ||
           !CHECK_CHAR( slot->bitmap_top  ) ||
           !CHECK_CHAR( xadvance )          ||
           !CHECK_CHAR( yadvance )          )
      {
        FT_TRACE2(( "ftc_snode_load:"
                    " glyph too large for small bitmap cache\n"));
        goto BadGlyph;
      }

      sbit->width     = (FT_Byte)bitmap->width;
      sbit->height    = (FT_Byte)bitmap->rows;
      sbit->pitch     = (FT_Char)bitmap->pitch;
      sbit->left      = (FT_Char)slot->bitmap_left;
      sbit->top       = (FT_Char)slot->bitmap_top;
      sbit->xadvance  = (FT_Char)xadvance;
      sbit->yadvance  = (FT_Char)yadvance;
      sbit->format    = (FT_Byte)bitmap->pixel_mode;
      sbit->max_grays = (FT_Byte)(bitmap->num_grays - 1);

      /* copy the bitmap into a new buffer -- ignore error */
      error = ftc_sbit_copy_bitmap( sbit, bitmap, memory );

      /* now, compute size */
      if ( asize )
        *asize = (FT_ULong)FT_ABS( sbit->pitch ) * sbit->height;

    } /* glyph loading successful */

    /* ignore the errors that might have occurred --   */
    /* we mark unloaded glyphs with `sbit.buffer == 0' */
    /* and `width == 255', `height == 0'               */
    /*                                                 */
    if ( error && FT_ERR_NEQ( error, Out_Of_Memory ) )
    {
    BadGlyph:
      sbit->width  = 255;
      sbit->height = 0;
      sbit->buffer = NULL;
      error        = FT_Err_Ok;
      if ( asize )
        *asize = 0;
    }

    return error;
  }

  FT_LOCAL_DEF( FT_Error )
  FTC_SNode_New( FTC_SNode  *psnode,
                 FTC_GQuery  gquery,
                 FTC_Cache   cache )
  {
    FT_Memory   memory = cache->memory;
    FT_Error    error;
    FTC_SNode   snode  = NULL;
    FT_UInt     gindex = gquery->gindex;
    FTC_Family  family = gquery->family;

    FTC_SFamilyClass  clazz = FTC_CACHE_SFAMILY_CLASS( cache );
    FT_UInt           total;
    FT_UInt           node_count;

    total = clazz->family_get_count( family, cache->manager );
    if ( total == 0 || gindex >= total )
    {
      error = FT_THROW( Invalid_Argument );
      goto Exit;
    }

    if ( !FT_NEW( snode ) )
    {
      FT_UInt  count, start;

      start = gindex - ( gindex % FTC_SBIT_ITEMS_PER_NODE );
      count = total - start;
      if ( count > FTC_SBIT_ITEMS_PER_NODE )
        count = FTC_SBIT_ITEMS_PER_NODE;

      FTC_GNode_Init( FTC_GNODE( snode ), start, family );

      snode->count = count;
      for ( node_count = 0; node_count < count; node_count++ )
      {
        snode->sbits[node_count].width = 255;
      }

      error = ftc_snode_load( snode,
                              cache->manager,
                              gindex,
                              NULL );
      if ( error )
      {
        FTC_SNode_Free( snode, cache );
        snode = NULL;
      }
    }

  Exit:
    *psnode = snode;
    return error;
  }

  FT_LOCAL_DEF( FT_Error )
  ftc_snode_new( FTC_Node   *ftcpsnode,
                 FT_Pointer  ftcgquery,
                 FTC_Cache   cache )
  {
    FTC_SNode  *psnode = (FTC_SNode*)ftcpsnode;
    FTC_GQuery  gquery = (FTC_GQuery)ftcgquery;

    return FTC_SNode_New( psnode, gquery, cache );
  }

  FT_LOCAL_DEF( FT_Offset )
  ftc_snode_weight( FTC_Node   ftcsnode,
                    FTC_Cache  cache )
  {
    FTC_SNode  snode = (FTC_SNode)ftcsnode;
    FT_UInt    count = snode->count;
    FTC_SBit   sbit  = snode->sbits;
    FT_Int     pitch;
    FT_Offset  size;

    FT_UNUSED( cache );

    FT_ASSERT( snode->count <= FTC_SBIT_ITEMS_PER_NODE );

    /* the node itself */
    size = sizeof ( *snode );

    for ( ; count > 0; count--, sbit++ )
    {
      if ( sbit->buffer )
      {
        pitch = sbit->pitch;
        if ( pitch < 0 )
          pitch = -pitch;

        /* add the size of a given glyph image */
        size += (FT_Offset)pitch * sbit->height;
      }
    }

    return size;
  }

#if 0

  FT_LOCAL_DEF( FT_Offset )
  FTC_SNode_Weight( FTC_SNode  snode )
  {
    return ftc_snode_weight( FTC_NODE( snode ), NULL );
  }

#endif /* 0 */

  FT_LOCAL_DEF( FT_Bool )
  ftc_snode_compare( FTC_Node    ftcsnode,
                     FT_Pointer  ftcgquery,
                     FTC_Cache   cache,
                     FT_Bool*    list_changed )
  {
    FTC_SNode   snode  = (FTC_SNode)ftcsnode;
    FTC_GQuery  gquery = (FTC_GQuery)ftcgquery;
    FTC_GNode   gnode  = FTC_GNODE( snode );
    FT_UInt     gindex = gquery->gindex;
    FT_Bool     result;

    if (list_changed)
      *list_changed = FALSE;
    result = FT_BOOL( gnode->family == gquery->family                    &&
                      (FT_UInt)( gindex - gnode->gindex ) < snode->count );
    if ( result )
    {
      /* check if we need to load the glyph bitmap now */
      FTC_SBit  sbit = snode->sbits + ( gindex - gnode->gindex );

      /*
       * The following code illustrates what to do when you want to
       * perform operations that may fail within a lookup function.
       *
       * Here, we want to load a small bitmap on-demand; we thus
       * need to call the `ftc_snode_load' function which may return
       * a non-zero error code only when we are out of memory (OOM).
       *
       * The correct thing to do is to use @FTC_CACHE_TRYLOOP and
       * @FTC_CACHE_TRYLOOP_END in order to implement a retry loop
       * that is capable of flushing the cache incrementally when
       * an OOM errors occur.
       *
       * However, we need to `lock' the node before this operation to
       * prevent it from being flushed within the loop.
       *
       * When we exit the loop, we unlock the node, then check the `error'
       * variable.  If it is non-zero, this means that the cache was
       * completely flushed and that no usable memory was found to load
       * the bitmap.
       *
       * We then prefer to return a value of 0 (i.e., NO MATCH).  This
       * ensures that the caller will try to allocate a new node.
       * This operation consequently _fail_ and the lookup function
       * returns the appropriate OOM error code.
       *
       * Note that `buffer == NULL && width == 255' is a hack used to
       * tag `unavailable' bitmaps in the array.  We should never try
       * to load these.
       *
       */

      if ( !sbit->buffer && sbit->width == 255 )
      {
        FT_ULong  size;
        FT_Error  error;

        ftcsnode->ref_count++;  /* lock node to prevent flushing */
                                /* in retry loop                 */

        FTC_CACHE_TRYLOOP( cache )
        {
          error = ftc_snode_load( snode, cache->manager, gindex, &size );
        }
        FTC_CACHE_TRYLOOP_END( list_changed );

        ftcsnode->ref_count--;  /* unlock the node */

        if ( error )
          result = 0;
        else
          cache->manager->cur_weight += size;
      }
    }

    return result;
  }

#ifdef FTC_INLINE

  FT_LOCAL_DEF( FT_Bool )
  FTC_SNode_Compare( FTC_SNode   snode,
                     FTC_GQuery  gquery,
                     FTC_Cache   cache,
                     FT_Bool*    list_changed )
  {
    return ftc_snode_compare( FTC_NODE( snode ), gquery,
                              cache, list_changed );
  }

#endif

/* END */


text:
#
# FreeType 2 Cache configuration rules
#

# Copyright (C) 2000-2020 by
# David Turner, Robert Wilhelm, and Werner Lemberg.
#
# This file is part of the FreeType project, and may only be used, modified,
# and distributed under the terms of the FreeType project license,
# LICENSE.TXT.  By continuing to use, modify, or distribute this file you
# indicate that you have read the license and understand and accept it
# fully.

# Cache driver directory
#
CACHE_DIR := $(SRC_DIR)/cache

# compilation flags for the driver
#
CACHE_COMPILE := $(CC) $(ANSIFLAGS)                              \
                       $I$(subst /,$(COMPILER_SEP),$(CACHE_DIR)) \
                       $(INCLUDE_FLAGS)                          \
                       $(FT_CFLAGS)

# Cache driver sources (i.e., C files)
#
CACHE_DRV_SRC := $(CACHE_DIR)/ftcbasic.c \
                 $(CACHE_DIR)/ftccache.c \
                 $(CACHE_DIR)/ftccmap.c  \
                 $(CACHE_DIR)/ftcglyph.c \
                 $(CACHE_DIR)/ftcimage.c \
                 $(CACHE_DIR)/ftcmanag.c \
                 $(CACHE_DIR)/ftcmru.c   \
                 $(CACHE_DIR)/ftcsbits.c

# Cache driver headers
#
CACHE_DRV_H := $(CACHE_DIR)/ftccache.h \
               $(CACHE_DIR)/ftccback.h \
               $(CACHE_DIR)/ftcerror.h \
               $(CACHE_DIR)/ftcglyph.h \
               $(CACHE_DIR)/ftcimage.h \
               $(CACHE_DIR)/ftcmanag.h \
               $(CACHE_DIR)/ftcmru.h   \
               $(CACHE_DIR)/ftcsbits.h

# Cache driver object(s)
#
#   CACHE_DRV_OBJ_M is used during `multi' builds.
#   CACHE_DRV_OBJ_S is used during `single' builds.
#
CACHE_DRV_OBJ_M := $(CACHE_DRV_SRC:$(CACHE_DIR)/%.c=$(OBJ_DIR)/%.$O)
CACHE_DRV_OBJ_S := $(OBJ_DIR)/ftcache.$O

# Cache driver source file for single build
#
CACHE_DRV_SRC_S := $(CACHE_DIR)/ftcache.c

# Cache driver - single object
#
$(CACHE_DRV_OBJ_S): $(CACHE_DRV_SRC_S) $(CACHE_DRV_SRC) \
                   $(FREETYPE_H) $(CACHE_DRV_H)
	$(CACHE_COMPILE) $T$(subst /,$(COMPILER_SEP),$@ $(CACHE_DRV_SRC_S))

# Cache driver - multiple objects
#
$(OBJ_DIR)/%.$O: $(CACHE_DIR)/%.c $(FREETYPE_H) $(CACHE_DRV_H)
	$(CACHE_COMPILE) $T$(subst /,$(COMPILER_SEP),$@ $<)

# update main driver object lists
#
DRV_OBJS_S += $(CACHE_DRV_OBJ_S)
DRV_OBJS_M += $(CACHE_DRV_OBJ_M)

# EOF


text:
/****************************************************************************
 *
 * ftccback.h
 *
 *   Callback functions of the caching sub-system (specification only).
 *
 * Copyright (C) 2004-2020 by
 * David Turner, Robert Wilhelm, and Werner Lemberg.
 *
 * This file is part of the FreeType project, and may only be used,
 * modified, and distributed under the terms of the FreeType project
 * license, LICENSE.TXT.  By continuing to use, modify, or distribute
 * this file you indicate that you have read the license and
 * understand and accept it fully.
 *
 */

#ifndef FTCCBACK_H_
#define FTCCBACK_H_

#include <ft2build.h>
#include FT_CACHE_H
#include "ftcmru.h"
#include "ftcimage.h"
#include "ftcmanag.h"
#include "ftcglyph.h"
#include "ftcsbits.h"

  FT_LOCAL( void )
  ftc_inode_free( FTC_Node   inode,
                  FTC_Cache  cache );

  FT_LOCAL( FT_Error )
  ftc_inode_new( FTC_Node   *pinode,
                 FT_Pointer  gquery,
                 FTC_Cache   cache );

  FT_LOCAL( FT_Offset )
  ftc_inode_weight( FTC_Node   inode,
                    FTC_Cache  cache );

  FT_LOCAL( void )
  ftc_snode_free( FTC_Node   snode,
                  FTC_Cache  cache );

  FT_LOCAL( FT_Error )
  ftc_snode_new( FTC_Node   *psnode,
                 FT_Pointer  gquery,
                 FTC_Cache   cache );

  FT_LOCAL( FT_Offset )
  ftc_snode_weight( FTC_Node   snode,
                    FTC_Cache  cache );

  FT_LOCAL( FT_Bool )
  ftc_snode_compare( FTC_Node    snode,
                     FT_Pointer  gquery,
                     FTC_Cache   cache,
                     FT_Bool*    list_changed );

  FT_LOCAL( FT_Bool )
  ftc_gnode_compare( FTC_Node    gnode,
                     FT_Pointer  gquery,
                     FTC_Cache   cache,
                     FT_Bool*    list_changed );

  FT_LOCAL( FT_Error )
  ftc_gcache_init( FTC_Cache  cache );

  FT_LOCAL( void )
  ftc_gcache_done( FTC_Cache  cache );

  FT_LOCAL( FT_Error )
  ftc_cache_init( FTC_Cache  cache );

  FT_LOCAL( void )
  ftc_cache_done( FTC_Cache  cache );

  FT_LOCAL( void )
  ftc_node_destroy( FTC_Node     node,
                    FTC_Manager  manager );

#endif /* FTCCBACK_H_ */

/* END */