1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
/***************************************************************************/
/* */
/* ftlru.h */
/* */
/* Simple LRU list-cache (specification). */
/* */
/* Copyright 2000 by */
/* David Turner, Robert Wilhelm, and Werner Lemberg. */
/* */
/* This file is part of the FreeType project, and may only be used, */
/* modified, and distributed under the terms of the FreeType project */
/* license, LICENSE.TXT. By continuing to use, modify, or distribute */
/* this file you indicate that you have read the license and */
/* understand and accept it fully. */
/* */
/***************************************************************************/
/*************************************************************************/
/* */
/* An LRU is a list that cannot hold more than a certain number of */
/* elements (`max_elements'). All elements on the list are sorted in */
/* least-recently-used order, i.e., the `oldest' element is at the tail */
/* of the list. */
/* */
/* When doing a lookup (either through `Lookup()' or `Lookup_Node()'), */
/* the list is searched for an element with the corresponding key. If */
/* it is found, the element is moved to the head of the list and is */
/* returned. */
/* */
/* If no corresponding element is found, the lookup routine will try to */
/* obtain a new element with the relevant key. If the list is already */
/* full, the oldest element from the list is discarded and replaced by a */
/* new one; a new element is added to the list otherwise. */
/* */
/* Note that it is possible to pre-allocate the element list nodes. */
/* This is handy if `max_elements' is sufficiently small, as it saves */
/* allocations/releases during the lookup process. */
/* */
/*************************************************************************/
/*************************************************************************/
/*************************************************************************/
/*************************************************************************/
/*************************************************************************/
/*************************************************************************/
/********* *********/
/********* WARNING, THIS IS ALPHA CODE, THIS API *********/
/********* IS DUE TO CHANGE UNTIL STRICTLY NOTIFIED BY THE *********/
/********* FREETYPE DEVELOPMENT TEAM *********/
/********* *********/
/*************************************************************************/
/*************************************************************************/
/*************************************************************************/
/*************************************************************************/
/*************************************************************************/
#ifndef FTLRU_H
#define FTLRU_H
#include <freetype/freetype.h>
#ifdef __cplusplus
extern "C" {
#endif
/* generic key type */
typedef FT_Pointer FT_LruKey;
/* an lru node -- root.data points to the element */
typedef struct FT_LruNodeRec_
{
FT_ListNodeRec root;
FT_LruKey key;
} FT_LruNodeRec, *FT_LruNode;
/* forward declaration */
typedef struct FT_LruRec_* FT_Lru;
/* LRU clazz */
typedef struct FT_Lru_Class_
{
FT_UInt lru_size; /* object size in bytes */
/* this method is used to initialize a new list element node */
FT_Error (*init_element)( FT_Lru lru,
FT_LruNode node );
/* this method is used to finalize a given list element node */
void (*done_element)( FT_Lru lru,
FT_LruNode node );
/* If defined, this method is called when the list if full */
/* during the lookup process -- it is used to change the contents */
/* of a list element node, instead of calling `done_element()', */
/* then `init_element'. Set it to 0 for default behaviour. */
FT_Error (*flush_element)( FT_Lru lru,
FT_LruNode node,
FT_LruKey new_key );
/* If defined, this method is used to compare a list element node */
/* with a given key during a lookup. If set to 0, the `key' */
/* fields will be directly compared instead. */
FT_Bool (*compare_element)( FT_LruNode node,
FT_LruKey key );
} FT_Lru_Class;
/* A selector is used to indicate whether a given list element node */
/* is part of a selection for FT_Lru_Remove_Selection(). The function */
/* must return true (i.e., non-null) to indicate that the node is part */
/* of it. */
typedef FT_Bool (*FT_Lru_Selector)( FT_Lru lru,
FT_LruNode node,
FT_Pointer data );
typedef struct FT_LruRec_
{
FT_Lru_Class* clazz;
FT_UInt max_elements;
FT_UInt num_elements;
FT_ListRec elements;
FT_Memory memory;
FT_Pointer user_data;
/* the following fields are only meaningful for static lru containers */
FT_ListRec free_nodes;
FT_LruNode nodes;
} FT_LruRec;
FT_EXPORT( FT_Error ) FT_Lru_New( const FT_Lru_Class* clazz,
FT_UInt max_elements,
FT_Pointer user_data,
FT_Memory memory,
FT_Bool pre_alloc,
FT_Lru* alru );
FT_EXPORT( void ) FT_Lru_Reset( FT_Lru lru );
FT_EXPORT( void ) FT_Lru_Done ( FT_Lru lru );
FT_EXPORT( FT_Error ) FT_Lru_Lookup_Node( FT_Lru lru,
FT_LruKey key,
FT_LruNode* anode );
FT_EXPORT( FT_Error ) FT_Lru_Lookup( FT_Lru lru,
FT_LruKey key,
FT_Pointer* aobject );
FT_EXPORT( void ) FT_Lru_Remove_Node( FT_Lru lru,
FT_LruNode node );
FT_EXPORT( void ) FT_Lru_Remove_Selection( FT_Lru lru,
FT_Lru_Selector selector,
FT_Pointer data );
#ifdef __cplusplus
}
#endif
#endif /* FTLRU_H */
/* END */
|