src/cache/ftcmru.h

   1 /****************************************************************************
   2  *
   3  * ftcmru.h
   4  *
   5  *   Simple MRU list-cache (specification).
   6  *
   7  * Copyright (C) 2000-2020 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 <freetype/freetype.h>
  48 #include <freetype/internal/compiler-macros.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_Offset                node_size;
 111
 112     FTC_MruNode_CompareFunc  node_compare;
 113     FTC_MruNode_InitFunc     node_init;
 114     FTC_MruNode_ResetFunc    node_reset;
 115     FTC_MruNode_DoneFunc     node_done;
 116
 117   } FTC_MruListClassRec;
 118
 119
 120   typedef struct  FTC_MruListRec_
 121   {
 122     FT_UInt              num_nodes;
 123     FT_UInt              max_nodes;
 124     FTC_MruNode          nodes;
 125     FT_Pointer           data;
 126     FTC_MruListClassRec  clazz;
 127     FT_Memory            memory;
 128
 129   } FTC_MruListRec;
 130
 131
 132   FT_LOCAL( void )
 133   FTC_MruList_Init( FTC_MruList       list,
 134                     FTC_MruListClass  clazz,
 135                     FT_UInt           max_nodes,
 136                     FT_Pointer        data,
 137                     FT_Memory         memory );
 138
 139   FT_LOCAL( void )
 140   FTC_MruList_Reset( FTC_MruList  list );
 141
 142
 143   FT_LOCAL( void )
 144   FTC_MruList_Done( FTC_MruList  list );
 145
 146
 147   FT_LOCAL( FT_Error )
 148   FTC_MruList_New( FTC_MruList   list,
 149                    FT_Pointer    key,
 150                    FTC_MruNode  *anode );
 151
 152   FT_LOCAL( void )
 153   FTC_MruList_Remove( FTC_MruList  list,
 154                       FTC_MruNode  node );
 155
 156   FT_LOCAL( void )
 157   FTC_MruList_RemoveSelection( FTC_MruList              list,
 158                                FTC_MruNode_CompareFunc  selection,
 159                                FT_Pointer               key );
 160
 161
 162 #ifdef FTC_INLINE
 163
 164 #define FTC_MRULIST_LOOKUP_CMP( list, key, compare, node, error )           \
 165   FT_BEGIN_STMNT                                                            \
 166     FTC_MruNode*             _pfirst  = &(list)->nodes;                     \
 167     FTC_MruNode_CompareFunc  _compare = (FTC_MruNode_CompareFunc)(compare); \
 168     FTC_MruNode              _first, _node;                                 \
 169                                                                             \
 170                                                                             \
 171     error  = FT_Err_Ok;                                                     \
 172     _first = *(_pfirst);                                                    \
 173     _node  = NULL;                                                          \
 174                                                                             \
 175     if ( _first )                                                           \
 176     {                                                                       \
 177       _node = _first;                                                       \
 178       do                                                                    \
 179       {                                                                     \
 180         if ( _compare( _node, (key) ) )                                     \
 181         {                                                                   \
 182           if ( _node != _first )                                            \
 183             FTC_MruNode_Up( _pfirst, _node );                               \
 184                                                                             \
 185           node = _node;                                                     \
 186           goto MruOk_;                                                      \
 187         }                                                                   \
 188         _node = _node->next;                                                \
 189                                                                             \
 190       } while ( _node != _first);                                           \
 191     }                                                                       \
 192                                                                             \
 193     error = FTC_MruList_New( (list), (key), (FTC_MruNode*)(void*)&(node) ); \
 194   MruOk_:                                                                   \
 195     ;                                                                       \
 196   FT_END_STMNT
 197
 198 #define FTC_MRULIST_LOOKUP( list, key, node, error ) \
 199   FTC_MRULIST_LOOKUP_CMP( list, key, (list)->clazz.node_compare, node, error )
 200
 201 #else  /* !FTC_INLINE */
 202
 203   FT_LOCAL( FTC_MruNode )
 204   FTC_MruList_Find( FTC_MruList  list,
 205                     FT_Pointer   key );
 206
 207   FT_LOCAL( FT_Error )
 208   FTC_MruList_Lookup( FTC_MruList   list,
 209                       FT_Pointer    key,
 210                       FTC_MruNode  *pnode );
 211
 212 #define FTC_MRULIST_LOOKUP( list, key, node, error ) \
 213   error = FTC_MruList_Lookup( (list), (key), (FTC_MruNode*)&(node) )
 214
 215 #endif /* !FTC_INLINE */
 216
 217
 218 #define FTC_MRULIST_LOOP( list, node )        \
 219   FT_BEGIN_STMNT                              \
 220     FTC_MruNode  _first = (list)->nodes;      \
 221                                               \
 222                                               \
 223     if ( _first )                             \
 224     {                                         \
 225       FTC_MruNode  _node = _first;            \
 226                                               \
 227                                               \
 228       do                                      \
 229       {                                       \
 230         *(FTC_MruNode*)&(node) = _node;
 231
 232
 233 #define FTC_MRULIST_LOOP_END()               \
 234         _node = _node->next;                 \
 235                                              \
 236       } while ( _node != _first );           \
 237     }                                        \
 238   FT_END_STMNT
 239
 240  /* */
 241
 242 FT_END_HEADER
 243
 244
 245 #endif /* FTCMRU_H_ */
 246
 247
 248 /* END */