xref: /inferno-os/include/freetype/cache/ftlru.h (revision 37da2899f40661e3e9631e497da8dc59b971cbd0)

/***************************************************************************/
/*                                                                         */
/*  ftlru.h                                                                */
/*                                                                         */
/*    Simple LRU list-cache (specification).                               */
/*                                                                         */
/*  Copyright 2000-2001 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 LRU 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.                       */
  /*                                                                       */
  /*************************************************************************/


  /*************************************************************************/
  /*************************************************************************/
  /*************************************************************************/
  /*************************************************************************/
  /*************************************************************************/
  /*********                                                       *********/
  /*********             WARNING, THIS IS BETA CODE.               *********/
  /*********                                                       *********/
  /*************************************************************************/
  /*************************************************************************/
  /*************************************************************************/
  /*************************************************************************/
  /*************************************************************************/


#ifndef __FTLRU_H__
#define __FTLRU_H__


#include <ft2build.h>
#include FT_FREETYPE_H


FT_BEGIN_HEADER


  /* generic list key type */
  typedef FT_Pointer  FT_LruKey;

  /* a list list handle */
  typedef struct FT_LruListRec_*  FT_LruList;

  /* a list class handle */
  typedef const struct FT_LruList_ClassRec_*  FT_LruList_Class;

  /* a list node handle */
  typedef struct FT_LruNodeRec_*  FT_LruNode;

  /* the list node structure */
  typedef struct  FT_LruNodeRec_
  {
    FT_LruNode  next;
    FT_LruKey   key;

  } FT_LruNodeRec;


  /* the list structure */
  typedef struct  FT_LruListRec_
  {
    FT_Memory         memory;
    FT_LruList_Class  clazz;
    FT_LruNode        nodes;
    FT_UInt           max_nodes;
    FT_UInt           num_nodes;
    FT_Pointer        data;

  } FT_LruListRec;


  /* initialize a list list */
  typedef FT_Error
  (*FT_LruList_InitFunc)( FT_LruList  list );

  /* finalize a list list */
  typedef void
  (*FT_LruList_DoneFunc)( FT_LruList  list );

  /* this method is used to initialize a new list element node */
  typedef FT_Error
  (*FT_LruNode_InitFunc)( FT_LruNode  node,
                          FT_LruKey   key,
                          FT_Pointer  data );

  /* this method is used to finalize a given list element node */
  typedef void
  (*FT_LruNode_DoneFunc)( FT_LruNode  node,
                          FT_Pointer  data );

  /* If defined, this method is called when the list if full        */
  /* during the lookup process -- it is used to change the contents */
  /* of a list element node instead of calling `done_element()',    */
  /* then `init_element()'.  Set it to 0 for default behaviour.     */
  typedef FT_Error
  (*FT_LruNode_FlushFunc)( FT_LruNode  node,
                           FT_LruKey   new_key,
                           FT_Pointer  data );

  /* If defined, this method is used to compare a list element node */
  /* with a given key during a lookup.  If set to 0, the `key'      */
  /* fields will be directly compared instead.                      */
  typedef FT_Bool
  (*FT_LruNode_CompareFunc)( FT_LruNode  node,
                             FT_LruKey   key,
                             FT_Pointer  data );

  /* A selector is used to indicate whether a given list element node */
  /* is part of a selection for FT_LruList_Remove_Selection().  The   */
  /* functrion must return true (i.e., non-null) to indicate that the */
  /* node is part of it.                                              */
  typedef FT_Bool
  (*FT_LruNode_SelectFunc)( FT_LruNode  node,
                            FT_Pointer  data,
                            FT_Pointer  list_data );

  /* LRU class */
  typedef struct  FT_LruList_ClassRec_
  {
    FT_UInt                 list_size;
    FT_LruList_InitFunc     list_init;      /* optional */
    FT_LruList_DoneFunc     list_done;      /* optional */

    FT_UInt                 node_size;
    FT_LruNode_InitFunc     node_init;     /* MANDATORY */
    FT_LruNode_DoneFunc     node_done;     /* optional  */
    FT_LruNode_FlushFunc    node_flush;    /* optional  */
    FT_LruNode_CompareFunc  node_compare;  /* optional  */

  } FT_LruList_ClassRec;


  /* The following functions must be exported in the case where */
  /* applications would want to write their own cache classes.  */

  FT_EXPORT( FT_Error )
  FT_LruList_New( FT_LruList_Class  clazz,
                  FT_UInt           max_elements,
                  FT_Pointer        user_data,
                  FT_Memory         memory,
                  FT_LruList       *alist );

  FT_EXPORT( void )
  FT_LruList_Reset( FT_LruList  list );

  FT_EXPORT( void )
  FT_LruList_Destroy ( FT_LruList  list );

  FT_EXPORT( FT_Error )
  FT_LruList_Lookup( FT_LruList  list,
                     FT_LruKey   key,
                     FT_LruNode *anode );

  FT_EXPORT( void )
  FT_LruList_Remove( FT_LruList  list,
                     FT_LruNode  node );

  FT_EXPORT( void )
  FT_LruList_Remove_Selection( FT_LruList             list,
                               FT_LruNode_SelectFunc  select_func,
                               FT_Pointer             select_data );

 /* */

FT_END_HEADER


#endif /* __FTLRU_H__ */


/* END */