ftcmru.h (8322B)
1 /**************************************************************************** 2 * 3 * ftcmru.h 4 * 5 * Simple MRU list-cache (specification). 6 * 7 * Copyright (C) 2000-2025 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 void 99 (*FTC_MruNode_DoneFunc)( FTC_MruNode node, 100 FT_Pointer data ); 101 102 103 typedef struct FTC_MruListClassRec_ 104 { 105 FT_Offset node_size; 106 107 FTC_MruNode_CompareFunc node_compare; 108 FTC_MruNode_InitFunc node_init; 109 FTC_MruNode_DoneFunc node_done; 110 111 } FTC_MruListClassRec; 112 113 114 typedef struct FTC_MruListRec_ 115 { 116 FT_UInt num_nodes; 117 FT_UInt max_nodes; 118 FTC_MruNode nodes; 119 FT_Pointer data; 120 FTC_MruListClassRec clazz; 121 FT_Memory memory; 122 123 } FTC_MruListRec; 124 125 126 FT_LOCAL( void ) 127 FTC_MruList_Init( FTC_MruList list, 128 FTC_MruListClass clazz, 129 FT_UInt max_nodes, 130 FT_Pointer data, 131 FT_Memory memory ); 132 133 FT_LOCAL( void ) 134 FTC_MruList_Reset( FTC_MruList list ); 135 136 137 FT_LOCAL( void ) 138 FTC_MruList_Done( FTC_MruList list ); 139 140 141 FT_LOCAL( FT_Error ) 142 FTC_MruList_New( FTC_MruList list, 143 FT_Pointer key, 144 FTC_MruNode *anode ); 145 146 FT_LOCAL( void ) 147 FTC_MruList_Remove( FTC_MruList list, 148 FTC_MruNode node ); 149 150 FT_LOCAL( void ) 151 FTC_MruList_RemoveSelection( FTC_MruList list, 152 FTC_MruNode_CompareFunc selection, 153 FT_Pointer key ); 154 155 156 #ifdef FTC_INLINE 157 158 #define FTC_MRULIST_LOOKUP_CMP( list, key, compare, node, error ) \ 159 FT_BEGIN_STMNT \ 160 FTC_MruNode* _pfirst = &(list)->nodes; \ 161 FTC_MruNode_CompareFunc _compare = (FTC_MruNode_CompareFunc)(compare); \ 162 FTC_MruNode _first, _node; \ 163 \ 164 \ 165 error = FT_Err_Ok; \ 166 _first = *(_pfirst); \ 167 _node = NULL; \ 168 \ 169 if ( _first ) \ 170 { \ 171 _node = _first; \ 172 do \ 173 { \ 174 if ( _compare( _node, (key) ) ) \ 175 { \ 176 if ( _node != _first ) \ 177 FTC_MruNode_Up( _pfirst, _node ); \ 178 \ 179 node = _node; \ 180 goto MruOk_; \ 181 } \ 182 _node = _node->next; \ 183 \ 184 } while ( _node != _first); \ 185 } \ 186 \ 187 error = FTC_MruList_New( (list), (key), (FTC_MruNode*)(void*)&(node) ); \ 188 MruOk_: \ 189 ; \ 190 FT_END_STMNT 191 192 #define FTC_MRULIST_LOOKUP( list, key, node, error ) \ 193 FTC_MRULIST_LOOKUP_CMP( list, key, (list)->clazz.node_compare, node, error ) 194 195 #else /* !FTC_INLINE */ 196 197 FT_LOCAL( FTC_MruNode ) 198 FTC_MruList_Find( FTC_MruList list, 199 FT_Pointer key ); 200 201 FT_LOCAL( FT_Error ) 202 FTC_MruList_Lookup( FTC_MruList list, 203 FT_Pointer key, 204 FTC_MruNode *pnode ); 205 206 #define FTC_MRULIST_LOOKUP( list, key, node, error ) \ 207 error = FTC_MruList_Lookup( (list), (key), (FTC_MruNode*)&(node) ) 208 209 #endif /* !FTC_INLINE */ 210 211 212 #define FTC_MRULIST_LOOP( list, node ) \ 213 FT_BEGIN_STMNT \ 214 FTC_MruNode _first = (list)->nodes; \ 215 \ 216 \ 217 if ( _first ) \ 218 { \ 219 FTC_MruNode _node = _first; \ 220 \ 221 \ 222 do \ 223 { \ 224 *(FTC_MruNode*)&(node) = _node; 225 226 227 #define FTC_MRULIST_LOOP_END() \ 228 _node = _node->next; \ 229 \ 230 } while ( _node != _first ); \ 231 } \ 232 FT_END_STMNT 233 234 /* */ 235 236 FT_END_HEADER 237 238 239 #endif /* FTCMRU_H_ */ 240 241 242 /* END */