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 /***************************************************************************/
19 /*************************************************************************/
20 /* */
21 /* An LRU is a list that cannot hold more than a certain number of */
22 /* elements (`max_elements'). All elements on 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 /*************************************************************************/
43 /*************************************************************************/
44 /*************************************************************************/
45 /*************************************************************************/
46 /*************************************************************************/
47 /*************************************************************************/
48 /********* *********/
49 /********* WARNING, THIS IS BETA CODE. *********/
50 /********* *********/
51 /*************************************************************************/
52 /*************************************************************************/
53 /*************************************************************************/
54 /*************************************************************************/
55 /*************************************************************************/
58 #ifndef __FTLRU_H__
59 #define __FTLRU_H__
62 #include <ft2build.h>
63 #include FT_FREETYPE_H
66 FT_BEGIN_HEADER
69 /* generic key type */
70 typedef FT_Pointer FT_LruKey;
73 /* an lru node -- root.data points to the element */
74 typedef struct FT_LruNodeRec_
75 {
76 FT_ListNodeRec root;
77 FT_LruKey key;
79 } FT_LruNodeRec, *FT_LruNode;
82 /* forward declaration */
83 typedef struct FT_LruRec_* FT_Lru;
86 /* LRU class */
87 typedef struct FT_Lru_Class_
88 {
89 FT_UInt lru_size; /* object size in bytes */
91 /* this method is used to initialize a new list element node */
92 FT_Error
93 (*init_element)( FT_Lru lru,
94 FT_LruNode node );
96 /* this method is used to finalize a given list element node */
97 void
98 (*done_element)( FT_Lru lru,
99 FT_LruNode node );
101 /* If defined, this method is called when the list if full */
102 /* during the lookup process -- it is used to change the contents */
103 /* of a list element node, instead of calling `done_element()', */
104 /* then `init_element'. Set it to 0 for default behaviour. */
105 FT_Error
106 (*flush_element)( FT_Lru lru,
107 FT_LruNode node,
108 FT_LruKey new_key );
110 /* If defined, this method is used to compare a list element node */
111 /* with a given key during a lookup. If set to 0, the `key' */
112 /* fields will be directly compared instead. */
113 FT_Bool
114 (*compare_element)( FT_LruNode node,
115 FT_LruKey key );
117 } FT_Lru_Class;
120 /* A selector is used to indicate whether a given list element node */
121 /* is part of a selection for FT_Lru_Remove_Selection(). The function */
122 /* must return true (i.e., non-null) to indicate that the node is part */
123 /* of it. */
124 typedef FT_Bool
125 (*FT_Lru_Selector)( FT_Lru lru,
126 FT_LruNode node,
127 FT_Pointer data );
130 typedef struct FT_LruRec_
131 {
132 FT_Lru_Class* clazz;
133 FT_UInt max_elements;
134 FT_UInt num_elements;
135 FT_ListRec elements;
136 FT_Memory memory;
137 FT_Pointer user_data;
139 /* the following fields are only meaningful for static lru containers */
140 FT_ListRec free_nodes;
141 FT_LruNode nodes;
143 } FT_LruRec;
146 FT_EXPORT( FT_Error )
147 FT_Lru_New( const FT_Lru_Class* clazz,
148 FT_UInt max_elements,
149 FT_Pointer user_data,
150 FT_Memory memory,
151 FT_Bool pre_alloc,
152 FT_Lru *anlru );
154 FT_EXPORT( void )
155 FT_Lru_Reset( FT_Lru lru );
157 FT_EXPORT( void )
158 FT_Lru_Done ( FT_Lru lru );
160 FT_EXPORT( FT_Error )
161 FT_Lru_Lookup_Node( FT_Lru lru,
162 FT_LruKey key,
163 FT_LruNode *anode );
165 FT_EXPORT( FT_Error )
166 FT_Lru_Lookup( FT_Lru lru,
167 FT_LruKey key,
168 FT_Pointer *anobject );
170 FT_EXPORT( void )
171 FT_Lru_Remove_Node( FT_Lru lru,
172 FT_LruNode node );
174 FT_EXPORT( void )
175 FT_Lru_Remove_Selection( FT_Lru lru,
176 FT_Lru_Selector selector,
177 FT_Pointer data );
180 FT_END_HEADER
182 #endif /* __FTLRU_H__ */
185 /* END */