1 /***************************************************************************/ |
|
2 /* */ |
|
3 /* ftcmru.h */ |
|
4 /* */ |
|
5 /* Simple MRU list-cache (specification). */ |
|
6 /* */ |
|
7 /* Copyright 2000-2001, 2003, 2004, 2005, 2006, 2010 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_Offset 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; \ |
|
167 \ |
|
168 \ |
|
169 error = FTC_Err_Ok; \ |
|
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 node = _node; \ |
|
184 goto _MruOk; \ |
|
185 } \ |
|
186 _node = _node->next; \ |
|
187 \ |
|
188 } while ( _node != _first) ; \ |
|
189 } \ |
|
190 \ |
|
191 error = FTC_MruList_New( (list), (key), (FTC_MruNode*)(void*)&(node) ); \ |
|
192 _MruOk: \ |
|
193 ; \ |
|
194 FT_END_STMNT |
|
195 |
|
196 #define FTC_MRULIST_LOOKUP( list, key, node, error ) \ |
|
197 FTC_MRULIST_LOOKUP_CMP( list, key, (list)->clazz.node_compare, node, error ) |
|
198 |
|
199 #else /* !FTC_INLINE */ |
|
200 |
|
201 FT_LOCAL( FTC_MruNode ) |
|
202 FTC_MruList_Find( FTC_MruList list, |
|
203 FT_Pointer key ); |
|
204 |
|
205 FT_LOCAL( FT_Error ) |
|
206 FTC_MruList_Lookup( FTC_MruList list, |
|
207 FT_Pointer key, |
|
208 FTC_MruNode *pnode ); |
|
209 |
|
210 #define FTC_MRULIST_LOOKUP( list, key, node, error ) \ |
|
211 error = FTC_MruList_Lookup( (list), (key), (FTC_MruNode*)&(node) ) |
|
212 |
|
213 #endif /* !FTC_INLINE */ |
|
214 |
|
215 |
|
216 #define FTC_MRULIST_LOOP( list, node ) \ |
|
217 FT_BEGIN_STMNT \ |
|
218 FTC_MruNode _first = (list)->nodes; \ |
|
219 \ |
|
220 \ |
|
221 if ( _first ) \ |
|
222 { \ |
|
223 FTC_MruNode _node = _first; \ |
|
224 \ |
|
225 \ |
|
226 do \ |
|
227 { \ |
|
228 *(FTC_MruNode*)&(node) = _node; |
|
229 |
|
230 |
|
231 #define FTC_MRULIST_LOOP_END() \ |
|
232 _node = _node->next; \ |
|
233 \ |
|
234 } while ( _node != _first ); \ |
|
235 } \ |
|
236 FT_END_STMNT |
|
237 |
|
238 /* */ |
|
239 |
|
240 FT_END_HEADER |
|
241 |
|
242 |
|
243 #endif /* __FTCMRU_H__ */ |
|
244 |
|
245 |
|
246 /* END */ |
|