modules/freetype2/src/cache/ftcmru.h

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  ftcmru.h                                                               */
   4 /*                                                                         */
   5 /*    Simple MRU list-cache (specification).                               */
   6 /*                                                                         */
   7 /*  Copyright 2000-2001, 2003, 2004, 2005, 2006 by                         */
   8 /*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
   9 /*                                                                         */
  10 /*  This file is part of the FreeType project, and may only be used,       */
  11 /*  modified, and distributed under the terms of the FreeType project      */
  12 /*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */
  13 /*  this file you indicate that you have read the license and              */
  14 /*  understand and accept it fully.                                        */
  15 /*                                                                         */
  16 /***************************************************************************/
  17
  18
  19   /*************************************************************************/
  20   /*                                                                       */
  21   /* An MRU is a list that cannot hold more than a certain number of       */
  22   /* elements (`max_elements').  All elements in the list are sorted in    */
  23   /* least-recently-used order, i.e., the `oldest' element is at the tail  */
  24   /* of the list.                                                          */
  25   /*                                                                       */
  26   /* When doing a lookup (either through `Lookup()' or `Lookup_Node()'),   */
  27   /* the list is searched for an element with the corresponding key.  If   */
  28   /* it is found, the element is moved to the head of the list and is      */
  29   /* returned.                                                             */
  30   /*                                                                       */
  31   /* If no corresponding element is found, the lookup routine will try to  */
  32   /* obtain a new element with the relevant key.  If the list is already   */
  33   /* full, the oldest element from the list is discarded and replaced by a */
  34   /* new one; a new element is added to the list otherwise.                */
  35   /*                                                                       */
  36   /* Note that it is possible to pre-allocate the element list nodes.      */
  37   /* This is handy if `max_elements' is sufficiently small, as it saves    */
  38   /* allocations/releases during the lookup process.                       */
  39   /*                                                                       */
  40   /*************************************************************************/
  41
  42
  43 #ifndef __FTCMRU_H__
  44 #define __FTCMRU_H__
  45
  46
  47 #include <ft2build.h>
  48 #include FT_FREETYPE_H
  49
  50 #ifdef FREETYPE_H
  51 #error "freetype.h of FreeType 1 has been loaded!"
  52 #error "Please fix the directory search order for header files"
  53 #error "so that freetype.h of FreeType 2 is found first."
  54 #endif
  55
  56 #define  xxFT_DEBUG_ERROR
  57 #define  FTC_INLINE
  58
  59 FT_BEGIN_HEADER
  60
  61   typedef struct FTC_MruNodeRec_*  FTC_MruNode;
  62
  63   typedef struct  FTC_MruNodeRec_
  64   {
  65     FTC_MruNode  next;
  66     FTC_MruNode  prev;
  67
  68   } FTC_MruNodeRec;
  69
  70
  71   FT_LOCAL( void )
  72   FTC_MruNode_Prepend( FTC_MruNode  *plist,
  73                        FTC_MruNode   node );
  74
  75   FT_LOCAL( void )
  76   FTC_MruNode_Up( FTC_MruNode  *plist,
  77                   FTC_MruNode   node );
  78
  79   FT_LOCAL( void )
  80   FTC_MruNode_Remove( FTC_MruNode  *plist,
  81                       FTC_MruNode   node );
  82
  83
  84   typedef struct FTC_MruListRec_*              FTC_MruList;
  85
  86   typedef struct FTC_MruListClassRec_ const *  FTC_MruListClass;
  87
  88
  89   typedef FT_Bool
  90   (*FTC_MruNode_CompareFunc)( FTC_MruNode  node,
  91                               FT_Pointer   key );
  92
  93   typedef FT_Error
  94   (*FTC_MruNode_InitFunc)( FTC_MruNode  node,
  95                            FT_Pointer   key,
  96                            FT_Pointer   data );
  97
  98   typedef FT_Error
  99   (*FTC_MruNode_ResetFunc)( FTC_MruNode  node,
 100                             FT_Pointer   key,
 101                             FT_Pointer   data );
 102
 103   typedef void
 104   (*FTC_MruNode_DoneFunc)( FTC_MruNode  node,
 105                            FT_Pointer   data );
 106
 107
 108   typedef struct  FTC_MruListClassRec_
 109   {
 110     FT_UInt                  node_size;
 111     FTC_MruNode_CompareFunc  node_compare;
 112     FTC_MruNode_InitFunc     node_init;
 113     FTC_MruNode_ResetFunc    node_reset;
 114     FTC_MruNode_DoneFunc     node_done;
 115
 116   } FTC_MruListClassRec;
 117
 118   typedef struct  FTC_MruListRec_
 119   {
 120     FT_UInt              num_nodes;
 121     FT_UInt              max_nodes;
 122     FTC_MruNode          nodes;
 123     FT_Pointer           data;
 124     FTC_MruListClassRec  clazz;
 125     FT_Memory            memory;
 126
 127   } FTC_MruListRec;
 128
 129
 130   FT_LOCAL( void )
 131   FTC_MruList_Init( FTC_MruList       list,
 132                     FTC_MruListClass  clazz,
 133                     FT_UInt           max_nodes,
 134                     FT_Pointer        data,
 135                     FT_Memory         memory );
 136
 137   FT_LOCAL( void )
 138   FTC_MruList_Reset( FTC_MruList  list );
 139
 140
 141   FT_LOCAL( void )
 142   FTC_MruList_Done( FTC_MruList  list );
 143
 144
 145   FT_LOCAL( FT_Error )
 146   FTC_MruList_New( FTC_MruList   list,
 147                    FT_Pointer    key,
 148                    FTC_MruNode  *anode );
 149
 150   FT_LOCAL( void )
 151   FTC_MruList_Remove( FTC_MruList  list,
 152                       FTC_MruNode  node );
 153
 154   FT_LOCAL( void )
 155   FTC_MruList_RemoveSelection( FTC_MruList              list,
 156                                FTC_MruNode_CompareFunc  selection,
 157                                FT_Pointer               key );
 158
 159
 160 #ifdef FTC_INLINE
 161
 162 #define FTC_MRULIST_LOOKUP_CMP( list, key, compare, node, error )           \
 163   FT_BEGIN_STMNT                                                            \
 164     FTC_MruNode*             _pfirst  = &(list)->nodes;                     \
 165     FTC_MruNode_CompareFunc  _compare = (FTC_MruNode_CompareFunc)(compare); \
 166     FTC_MruNode              _first, _node, *_pnode;                        \
 167                                                                             \
 168                                                                             \
 169     error  = 0;                                                             \
 170     _first = *(_pfirst);                                                    \
 171     _node  = NULL;                                                          \
 172                                                                             \
 173     if ( _first )                                                           \
 174     {                                                                       \
 175       _node = _first;                                                       \
 176       do                                                                    \
 177       {                                                                     \
 178         if ( _compare( _node, (key) ) )                                     \
 179         {                                                                   \
 180           if ( _node != _first )                                            \
 181             FTC_MruNode_Up( _pfirst, _node );                               \
 182                                                                             \
 183           _pnode = (FTC_MruNode*)(void*)&(node);                            \
 184           *_pnode = _node;                                                  \
 185           goto _MruOk;                                                      \
 186         }                                                                   \
 187         _node = _node->next;                                                \
 188                                                                             \
 189       } while ( _node != _first) ;                                          \
 190     }                                                                       \
 191                                                                             \
 192     error = FTC_MruList_New( (list), (key), (FTC_MruNode*)(void*)&(node) ); \
 193   _MruOk:                                                                   \
 194     ;                                                                       \
 195   FT_END_STMNT
 196
 197 #define FTC_MRULIST_LOOKUP( list, key, node, error ) \
 198   FTC_MRULIST_LOOKUP_CMP( list, key, (list)->clazz.node_compare, node, error )
 199
 200 #else  /* !FTC_INLINE */
 201
 202   FT_LOCAL( FTC_MruNode )
 203   FTC_MruList_Find( FTC_MruList  list,
 204                     FT_Pointer   key );
 205
 206   FT_LOCAL( FT_Error )
 207   FTC_MruList_Lookup( FTC_MruList   list,
 208                       FT_Pointer    key,
 209                       FTC_MruNode  *pnode );
 210
 211 #define FTC_MRULIST_LOOKUP( list, key, node, error ) \
 212   error = FTC_MruList_Lookup( (list), (key), (FTC_MruNode*)&(node) )
 213
 214 #endif /* !FTC_INLINE */
 215
 216
 217 #define FTC_MRULIST_LOOP( list, node )        \
 218   FT_BEGIN_STMNT                              \
 219     FTC_MruNode  _first = (list)->nodes;      \
 220                                               \
 221                                               \
 222     if ( _first )                             \
 223     {                                         \
 224       FTC_MruNode  _node = _first;            \
 225                                               \
 226                                               \
 227       do                                      \
 228       {                                       \
 229         *(FTC_MruNode*)&(node) = _node;
 230
 231
 232 #define FTC_MRULIST_LOOP_END()               \
 233         _node = _node->next;                 \
 234                                              \
 235       } while ( _node != _first );           \
 236     }                                        \
 237   FT_END_STMNT
 238
 239  /* */
 240
 241 FT_END_HEADER
 242
 243
 244 #endif /* __FTCMRU_H__ */
 245
 246
 247 /* END */