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