godot/thirdparty/freetype/src/cache/ftccache.c

/****************************************************************************
 *
 * ftccache.c
 *
 *   The FreeType internal cache interface (body).
 *
 * Copyright (C) 2000-2023 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 "ftcmanag.h"
#include <freetype/internal/ftobjs.h>
#include <freetype/internal/ftdebug.h>

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

#undef  FT_COMPONENT
#define FT_COMPONENT …


#define FTC_HASH_MAX_LOAD …
#define FTC_HASH_MIN_LOAD …
#define FTC_HASH_SUB_LOAD …

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


  /*************************************************************************/
  /*************************************************************************/
  /*****                                                               *****/
  /*****                   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 )
  { … }


  /* remove a node from the manager's MRU list */
  static void
  ftc_node_mru_unlink( FTC_Node     node,
                       FTC_Manager  manager )
  { … }


#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 )
  {
    FT_Offset  idx;


    idx = hash & cache->mask;
    if ( idx >= cache->p )
      idx = hash & ( cache->mask >> 1 );

    return cache->buckets + idx;
  }

#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 )
  { … }


  /* remove a node from its cache's hash table */
  static void
  ftc_node_hash_unlink( FTC_Node   node0,
                        FTC_Cache  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 )
  { … }


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


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


  FT_LOCAL_DEF( FT_Error )
  ftc_cache_init( FTC_Cache  cache )
  { … }


  FT_LOCAL_DEF( FT_Error )
  FTC_Cache_Init( FTC_Cache  cache )
  { … }


  FT_LOCAL_DEF( void )
  ftc_cache_done( FTC_Cache  cache )
  { … }


  FT_LOCAL_DEF( void )
  FTC_Cache_Done( FTC_Cache  cache )
  { … }


  static void
  ftc_cache_add( FTC_Cache  cache,
                 FT_Offset  hash,
                 FTC_Node   node )
  { … }


  FT_LOCAL_DEF( FT_Error )
  FTC_Cache_NewNode( FTC_Cache   cache,
                     FT_Offset   hash,
                     FT_Pointer  query,
                     FTC_Node   *anode )
  { … }


#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 )
  { … }


/* END */