1 /***************************************************************************/ 2 /* */ 3 /* ftlru.c */ 4 /* */ 5 /* Simple LRU list-cache (body). */ 6 /* */ 7 /* Copyright 2000-2001, 2002 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 #include <ft2build.h> 20 #include FT_CACHE_H 21 #include FT_CACHE_INTERNAL_LRU_H 22 #include FT_LIST_H 23 #include FT_INTERNAL_OBJECTS_H 24 25 #include "ftcerror.h" 26 27 28 FT_EXPORT_DEF( FT_Error ) 29 FT_LruList_New( FT_LruList_Class clazz, 30 FT_UInt max_nodes, 31 FT_Pointer user_data, 32 FT_Memory memory, 33 FT_LruList *alist ) 34 { 35 FT_Error error; 36 FT_LruList list; 37 38 39 if ( !alist || !clazz ) 40 return FTC_Err_Invalid_Argument; 41 42 *alist = NULL; 43 if ( !FT_ALLOC( list, clazz->list_size ) ) 44 { 45 /* initialize common fields */ 46 list->clazz = clazz; 47 list->memory = memory; 48 list->max_nodes = max_nodes; 49 list->data = user_data; 50 51 if ( clazz->list_init ) 52 { 53 error = clazz->list_init( list ); 54 if ( error ) 55 { 56 if ( clazz->list_done ) 57 clazz->list_done( list ); 58 59 FT_FREE( list ); 60 } 61 } 62 63 *alist = list; 64 } 65 66 return error; 67 } 68 69 70 FT_EXPORT_DEF( void ) 71 FT_LruList_Destroy( FT_LruList list ) 72 { 73 FT_Memory memory; 74 FT_LruList_Class clazz; 75 76 77 if ( !list ) 78 return; 79 80 memory = list->memory; 81 clazz = list->clazz; 82 83 FT_LruList_Reset( list ); 84 85 if ( clazz->list_done ) 86 clazz->list_done( list ); 87 88 FT_FREE( list ); 89 } 90 91 92 FT_EXPORT_DEF( void ) 93 FT_LruList_Reset( FT_LruList list ) 94 { 95 FT_LruNode node; 96 FT_LruList_Class clazz; 97 FT_Memory memory; 98 99 100 if ( !list ) 101 return; 102 103 node = list->nodes; 104 clazz = list->clazz; 105 memory = list->memory; 106 107 while ( node ) 108 { 109 FT_LruNode next = node->next; 110 111 112 if ( clazz->node_done ) 113 clazz->node_done( node, list->data ); 114 115 FT_FREE( node ); 116 node = next; 117 } 118 119 list->nodes = NULL; 120 list->num_nodes = 0; 121 } 122 123 124 FT_EXPORT_DEF( FT_Error ) 125 FT_LruList_Lookup( FT_LruList list, 126 FT_LruKey key, 127 FT_LruNode *anode ) 128 { 129 FT_Error error = 0; 130 FT_LruNode node, *pnode; 131 FT_LruList_Class clazz; 132 FT_LruNode* plast; 133 FT_LruNode result = NULL; 134 FT_Memory memory; 135 136 137 if ( !list || !key || !anode ) 138 return FTC_Err_Invalid_Argument; 139 140 pnode = &list->nodes; 141 plast = pnode; 142 node = NULL; 143 clazz = list->clazz; 144 memory = list->memory; 145 146 if ( clazz->node_compare ) 147 { 148 for (;;) 149 { 150 node = *pnode; 151 if ( node == NULL ) 152 break; 153 154 if ( clazz->node_compare( node, key, list->data ) ) 155 break; 156 157 plast = pnode; 158 pnode = &(*pnode)->next; 159 } 160 } 161 else 162 { 163 for (;;) 164 { 165 node = *pnode; 166 if ( node == NULL ) 167 break; 168 169 if ( node->key == key ) 170 break; 171 172 plast = pnode; 173 pnode = &(*pnode)->next; 174 } 175 } 176 177 if ( node ) 178 { 179 /* move element to top of list */ 180 if ( list->nodes != node ) 181 { 182 *pnode = node->next; 183 node->next = list->nodes; 184 list->nodes = node; 185 } 186 result = node; 187 goto Exit; 188 } 189 190 /* we haven't found the relevant element. We will now try */ 191 /* to create a new one. */ 192 /* */ 193 194 /* first, check if our list if full, when appropriate */ 195 if ( list->max_nodes > 0 && list->num_nodes >= list->max_nodes ) 196 { 197 /* this list list is full; we will now flush */ 198 /* the oldest node, if there's one! */ 199 FT_LruNode last = *plast; 200 201 202 if ( last ) 203 { 204 if ( clazz->node_flush ) 205 { 206 error = clazz->node_flush( last, key, list->data ); 207 } 208 else 209 { 210 if ( clazz->node_done ) 211 clazz->node_done( last, list->data ); 212 213 last->key = key; 214 error = clazz->node_init( last, key, list->data ); 215 } 216 217 if ( !error ) 218 { 219 /* move it to the top of the list */ 220 *plast = NULL; 221 last->next = list->nodes; 222 list->nodes = last; 223 224 result = last; 225 goto Exit; 226 } 227 228 /* in case of error during the flush or done/init cycle, */ 229 /* we need to discard the node */ 230 if ( clazz->node_done ) 231 clazz->node_done( last, list->data ); 232 233 *plast = NULL; 234 list->num_nodes--; 235 236 FT_FREE( last ); 237 goto Exit; 238 } 239 } 240 241 /* otherwise, simply allocate a new node */ 242 if ( FT_ALLOC( node, clazz->node_size ) ) 243 goto Exit; 244 245 node->key = key; 246 error = clazz->node_init( node, key, list->data ); 247 if ( error ) 248 { 249 FT_FREE( node ); 250 goto Exit; 251 } 252 253 result = node; 254 node->next = list->nodes; 255 list->nodes = node; 256 list->num_nodes++; 257 258 Exit: 259 *anode = result; 260 return error; 261 } 262 263 264 FT_EXPORT_DEF( void ) 265 FT_LruList_Remove( FT_LruList list, 266 FT_LruNode node ) 267 { 268 FT_LruNode *pnode; 269 270 271 if ( !list || !node ) 272 return; 273 274 pnode = &list->nodes; 275 for (;;) 276 { 277 if ( *pnode == node ) 278 { 279 FT_Memory memory = list->memory; 280 FT_LruList_Class clazz = list->clazz; 281 282 283 *pnode = node->next; 284 node->next = NULL; 285 286 if ( clazz->node_done ) 287 clazz->node_done( node, list->data ); 288 289 FT_FREE( node ); 290 list->num_nodes--; 291 break; 292 } 293 294 pnode = &(*pnode)->next; 295 } 296 } 297 298 299 FT_EXPORT_DEF( void ) 300 FT_LruList_Remove_Selection( FT_LruList list, 301 FT_LruNode_SelectFunc select_func, 302 FT_Pointer select_data ) 303 { 304 FT_LruNode *pnode, node; 305 FT_LruList_Class clazz; 306 FT_Memory memory; 307 308 309 if ( !list || !select_func ) 310 return; 311 312 memory = list->memory; 313 clazz = list->clazz; 314 pnode = &list->nodes; 315 316 for (;;) 317 { 318 node = *pnode; 319 if ( node == NULL ) 320 break; 321 322 if ( select_func( node, select_data, list->data ) ) 323 { 324 *pnode = node->next; 325 node->next = NULL; 326 327 if ( clazz->node_done ) 328 clazz->node_done( node, list ); 329 330 FT_FREE( node ); 331 } 332 else 333 pnode = &(*pnode)->next; 334 } 335 } 336 337 338 /* END */ 339