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