1 /****************************************************************************
2 *
3 * ftcmru.h
4 *
5 * Simple MRU list-cache (specification).
6 *
7 * Copyright (C) 2000-2023 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 */