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