1 /***************************************************************************/ 2 /* */ 3 /* ftlru.h */ 4 /* */ 5 /* Simple LRU list-cache (specification). */ 6 /* */ 7 /* Copyright 2000-2001, 2003 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 LRU 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 /*************************************************************************/ 44 /*************************************************************************/ 45 /*************************************************************************/ 46 /*************************************************************************/ 47 /*************************************************************************/ 48 /********* *********/ 49 /********* WARNING, THIS IS BETA CODE. *********/ 50 /********* *********/ 51 /*************************************************************************/ 52 /*************************************************************************/ 53 /*************************************************************************/ 54 /*************************************************************************/ 55 /*************************************************************************/ 56 57 58 #ifndef __FTLRU_H__ 59 #define __FTLRU_H__ 60 61 62 #include <ft2build.h> 63 #include FT_FREETYPE_H 64 65 #ifdef FREETYPE_H 66 #error "freetype.h of FreeType 1 has been loaded!" 67 #error "Please fix the directory search order for header files" 68 #error "so that freetype.h of FreeType 2 is found first." 69 #endif 70 71 72 FT_BEGIN_HEADER 73 74 75 /* generic list key type */ 76 typedef FT_Pointer FT_LruKey; 77 78 /* a list list handle */ 79 typedef struct FT_LruListRec_* FT_LruList; 80 81 /* a list class handle */ 82 typedef const struct FT_LruList_ClassRec_* FT_LruList_Class; 83 84 /* a list node handle */ 85 typedef struct FT_LruNodeRec_* FT_LruNode; 86 87 /* the list node structure */ 88 typedef struct FT_LruNodeRec_ 89 { 90 FT_LruNode next; 91 FT_LruKey key; 92 93 } FT_LruNodeRec; 94 95 96 /* the list structure */ 97 typedef struct FT_LruListRec_ 98 { 99 FT_Memory memory; 100 FT_LruList_Class clazz; 101 FT_LruNode nodes; 102 FT_UInt max_nodes; 103 FT_UInt num_nodes; 104 FT_Pointer data; 105 106 } FT_LruListRec; 107 108 109 /* initialize a list list */ 110 typedef FT_Error 111 (*FT_LruList_InitFunc)( FT_LruList list ); 112 113 /* finalize a list list */ 114 typedef void 115 (*FT_LruList_DoneFunc)( FT_LruList list ); 116 117 /* this method is used to initialize a new list element node */ 118 typedef FT_Error 119 (*FT_LruNode_InitFunc)( FT_LruNode node, 120 FT_LruKey key, 121 FT_Pointer data ); 122 123 /* this method is used to finalize a given list element node */ 124 typedef void 125 (*FT_LruNode_DoneFunc)( FT_LruNode node, 126 FT_Pointer data ); 127 128 /* If defined, this method is called when the list if full */ 129 /* during the lookup process -- it is used to change the contents */ 130 /* of a list element node instead of calling `done_element()', */ 131 /* then `init_element()'. Set it to 0 for default behaviour. */ 132 typedef FT_Error 133 (*FT_LruNode_FlushFunc)( FT_LruNode node, 134 FT_LruKey new_key, 135 FT_Pointer data ); 136 137 /* If defined, this method is used to compare a list element node */ 138 /* with a given key during a lookup. If set to 0, the `key' */ 139 /* fields will be directly compared instead. */ 140 typedef FT_Bool 141 (*FT_LruNode_CompareFunc)( FT_LruNode node, 142 FT_LruKey key, 143 FT_Pointer data ); 144 145 /* A selector is used to indicate whether a given list element node */ 146 /* is part of a selection for FT_LruList_Remove_Selection(). The */ 147 /* functrion must return true (i.e., non-null) to indicate that the */ 148 /* node is part of it. */ 149 typedef FT_Bool 150 (*FT_LruNode_SelectFunc)( FT_LruNode node, 151 FT_Pointer data, 152 FT_Pointer list_data ); 153 154 /* LRU class */ 155 typedef struct FT_LruList_ClassRec_ 156 { 157 FT_UInt list_size; 158 FT_LruList_InitFunc list_init; /* optional */ 159 FT_LruList_DoneFunc list_done; /* optional */ 160 161 FT_UInt node_size; 162 FT_LruNode_InitFunc node_init; /* MANDATORY */ 163 FT_LruNode_DoneFunc node_done; /* optional */ 164 FT_LruNode_FlushFunc node_flush; /* optional */ 165 FT_LruNode_CompareFunc node_compare; /* optional */ 166 167 } FT_LruList_ClassRec; 168 169 170 /* The following functions must be exported in the case where */ 171 /* applications would want to write their own cache classes. */ 172 173 FT_EXPORT( FT_Error ) 174 FT_LruList_New( FT_LruList_Class clazz, 175 FT_UInt max_elements, 176 FT_Pointer user_data, 177 FT_Memory memory, 178 FT_LruList *alist ); 179 180 FT_EXPORT( void ) 181 FT_LruList_Reset( FT_LruList list ); 182 183 FT_EXPORT( void ) 184 FT_LruList_Destroy ( FT_LruList list ); 185 186 FT_EXPORT( FT_Error ) 187 FT_LruList_Lookup( FT_LruList list, 188 FT_LruKey key, 189 FT_LruNode *anode ); 190 191 FT_EXPORT( void ) 192 FT_LruList_Remove( FT_LruList list, 193 FT_LruNode node ); 194 195 FT_EXPORT( void ) 196 FT_LruList_Remove_Selection( FT_LruList list, 197 FT_LruNode_SelectFunc select_func, 198 FT_Pointer select_data ); 199 200 /* */ 201 202 FT_END_HEADER 203 204 205 #endif /* __FTLRU_H__ */ 206 207 208 /* END */ 209