/***************************************************************************/

/*                                                                         */

/*  ftcmru.h                                                               */

/*                                                                         */

/*    Simple MRU list-cache (specification).                               */

/*                                                                         */

/*  Copyright 2000-2001, 2003, 2004, 2005, 2006, 2010 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  = FTC_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 */

