summaryrefslogtreecommitdiffstats
path: root/src/cache/ftcmru.h
blob: c8f0c6ef6e3fc1c344f92f74ce751a00c63fb098 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
/***************************************************************************/
/*                                                                         */
/*  ftcmru.h                                                               */
/*                                                                         */
/*    Simple MRU list-cache (specification).                               */
/*                                                                         */
/*  Copyright 2000-2001, 2003, 2004, 2005, 2006 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_UInt                  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, *_pnode;                        \
                                                                            \
                                                                            \
    error  = 0;                                                             \
    _first = *(_pfirst);                                                    \
    _node  = NULL;                                                          \
                                                                            \
    if ( _first )                                                           \
    {                                                                       \
      _node = _first;                                                       \
      do                                                                    \
      {                                                                     \
        if ( _compare( _node, (key) ) )                                     \
        {                                                                   \
          if ( _node != _first )                                            \
            FTC_MruNode_Up( _pfirst, _node );                               \
                                                                            \
          _pnode = (FTC_MruNode*)(void*)&(node);                            \
          *_pnode = _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 */