r11704: methods->alternate_name is not used anymore -- remove it
[Samba/nascimento.git] / source3 / ubiqx / ubi_Cache.h
blob0fc3a074f72c8e01f684b10ca74bb20bdecbf9ff
1 #ifndef UBI_CACHE_H
2 #define UBI_CACHE_H
3 /* ========================================================================== **
4 * ubi_Cache.h
6 * Copyright (C) 1997 by Christopher R. Hertel
8 * Email: crh@ubiqx.mn.org
9 * -------------------------------------------------------------------------- **
11 * This module implements a generic cache.
13 * -------------------------------------------------------------------------- **
15 * This library is free software; you can redistribute it and/or
16 * modify it under the terms of the GNU Library General Public
17 * License as published by the Free Software Foundation; either
18 * version 2 of the License, or (at your option) any later version.
20 * This library is distributed in the hope that it will be useful,
21 * but WITHOUT ANY WARRANTY; without even the implied warranty of
22 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
23 * Library General Public License for more details.
25 * You should have received a copy of the GNU Library General Public
26 * License along with this library; if not, write to the Free
27 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
29 * -------------------------------------------------------------------------- **
31 * This module uses a splay tree to implement a simple cache. The cache
32 * module adds a thin layer of functionality to the splay tree. In
33 * particular:
35 * - The tree (cache) may be limited in size by the number of
36 * entries permitted or the amount of memory used. When either
37 * limit is exceeded cache entries are removed until the cache
38 * conforms.
39 * - Some statistical information is kept so that an approximate
40 * "hit ratio" can be calculated.
41 * - There are several functions available that provide access to
42 * and management of cache size limits, hit ratio, and tree
43 * trimming.
45 * The splay tree is used because recently accessed items tend toward the
46 * top of the tree and less recently accessed items tend toward the bottom.
47 * This makes it easy to purge less recently used items should the cache
48 * exceed its limits.
50 * To use this module, you will need to supply a comparison function of
51 * type ubi_trCompFunc and a node-freeing function of type
52 * ubi_trKillNodeRtn. See ubi_BinTree.h for more information on
53 * these. (This is all basic ubiqx tree management stuff.)
55 * Notes:
57 * - Cache performance will start to suffer dramatically if the
58 * cache becomes large enough to force the OS to start swapping
59 * memory to disk. This is because the nodes of the underlying tree
60 * will be scattered across memory in an order that is completely
61 * unrelated to their traversal order. As more and more of the
62 * cache is placed into swap space, more and more swaps will be
63 * required for a simple traversal (...and then there's the splay
64 * operation).
66 * In one simple test under Linux, the load and dump of a cache of
67 * 400,000 entries took only 1min, 40sec of real time. The same
68 * test with 450,000 records took 2 *hours* and eight minutes.
70 * - In an effort to save memory, I considered using an unsigned
71 * short to save the per-entry entry size. I would have tucked this
72 * value into some unused space in the tree node structure. On
73 * 32-bit word aligned systems this would have saved an additional
74 * four bytes per entry. I may revisit this issue, but for now I've
75 * decided against it.
77 * Using an unsigned short would limit the size of an entry to 64K
78 * bytes. That's probably more than enough for most applications.
79 * The key word in that last sentence, however, is "probably". I
80 * really dislike imposing such limits on things.
82 * - Each entry keeps track of the amount of memory it used and the
83 * cache header keeps the total. This information is provided via
84 * the EntrySize parameter in ubi_cachePut(), so it is up to you to
85 * make sure that the numbers are accurate. (The numbers don't even
86 * have to represent bytes used.)
88 * As you consider this, note that the strdup() function--as an
89 * example--will call malloc(). The latter generally allocates a
90 * multiple of the system word size, which may be more than the
91 * number of bytes needed to store the string.
93 * -------------------------------------------------------------------------- **
95 * Log: ubi_Cache.h,v
96 * Revision 0.4 1999/09/22 03:42:24 crh
97 * Fixed a minor typo.
99 * Revision 0.3 1998/06/03 18:00:15 crh
100 * Further fiddling with sys_include.h, which is no longer explicitly
101 * included by this module since it is inherited from ubi_BinTree.h.
103 * Revision 0.2 1998/06/02 01:36:18 crh
104 * Changed include name from ubi_null.h to sys_include.h to make it
105 * more generic.
107 * Revision 0.1 1998/05/20 04:36:02 crh
108 * The C file now includes ubi_null.h. See ubi_null.h for more info.
110 * Revision 0.0 1997/12/18 06:25:23 crh
111 * Initial Revision.
113 * ========================================================================== **
116 #include "ubi_SplayTree.h"
118 /* -------------------------------------------------------------------------- **
119 * Typedefs...
121 * ubi_cacheRoot - Cache header structure, which consists of a binary
122 * tree root and other required housekeeping fields, as
123 * listed below.
124 * ubi_cacheRootPtr - Pointer to a Cache.
126 * ubi_cacheEntry - A cache Entry, which consists of a tree node
127 * structure and the size (in bytes) of the entry
128 * data. The entry size should be supplied via
129 * the EntrySize parameter of the ubi_cachePut()
130 * function.
132 * ubi_cacheEntryPtr - Pointer to a ubi_cacheEntry.
136 typedef struct
138 ubi_trRoot root; /* Splay tree control structure. */
139 ubi_trKillNodeRtn free_func; /* Function used to free entries. */
140 unsigned long max_entries; /* Max cache entries. 0 == unlimited */
141 unsigned long max_memory; /* Max memory to use. 0 == unlimited */
142 unsigned long mem_used; /* Memory currently in use (bytes). */
143 unsigned short cache_hits; /* Incremented on succesful find. */
144 unsigned short cache_trys; /* Incremented on cache lookup. */
145 } ubi_cacheRoot;
147 typedef ubi_cacheRoot *ubi_cacheRootPtr;
150 typedef struct
152 ubi_trNode node; /* Tree node structure. */
153 unsigned long entry_size; /* Entry size. Used when managing
154 * caches with maximum memory limits.
156 } ubi_cacheEntry;
158 typedef ubi_cacheEntry *ubi_cacheEntryPtr;
161 /* -------------------------------------------------------------------------- **
162 * Macros...
164 * ubi_cacheGetMaxEntries() - Report the current maximum number of entries
165 * allowed in the cache. Zero indicates no
166 * maximum.
167 * ubi_cacheGetMaxMemory() - Report the current maximum amount of memory
168 * that may be used in the cache. Zero
169 * indicates no maximum.
170 * ubi_cacheGetEntryCount() - Report the current number of entries in the
171 * cache.
172 * ubi_cacheGetMemUsed() - Report the amount of memory currently in use
173 * by the cache.
176 #define ubi_cacheGetMaxEntries( Cptr ) (((ubi_cacheRootPtr)(Cptr))->max_entries)
177 #define ubi_cacheGetMaxMemory( Cptr ) (((ubi_cacheRootPtr)(Cptr))->max_memory)
179 #define ubi_cacheGetEntryCount( Cptr ) (((ubi_cacheRootPtr)(Cptr))->root.count)
180 #define ubi_cacheGetMemUsed( Cptr ) (((ubi_cacheRootPtr)(Cptr))->mem_used)
182 /* -------------------------------------------------------------------------- **
183 * Prototypes...
186 ubi_cacheRootPtr ubi_cacheInit( ubi_cacheRootPtr CachePtr,
187 ubi_trCompFunc CompFunc,
188 ubi_trKillNodeRtn FreeFunc,
189 unsigned long MaxEntries,
190 unsigned long MaxMemory );
191 /* ------------------------------------------------------------------------ **
192 * Initialize a cache header structure.
194 * Input: CachePtr - A pointer to a ubi_cacheRoot structure that is
195 * to be initialized.
196 * CompFunc - A pointer to the function that will be called
197 * to compare two cache values. See the module
198 * comments, above, for more information.
199 * FreeFunc - A pointer to a function that will be called
200 * to free a cache entry. If you allocated
201 * the cache entry using malloc(), then this
202 * will likely be free(). If you are allocating
203 * cache entries from a free list, then this will
204 * likely be a function that returns memory to the
205 * free list, etc.
206 * MaxEntries - The maximum number of entries that will be
207 * allowed to exist in the cache. If this limit
208 * is exceeded, then existing entries will be
209 * removed from the cache. A value of zero
210 * indicates that there is no limit on the number
211 * of cache entries. See ubi_cachePut().
212 * MaxMemory - The maximum amount of memory, in bytes, to be
213 * allocated to the cache (excluding the cache
214 * header). If this is exceeded, existing entries
215 * in the cache will be removed until enough memory
216 * has been freed to meet the condition. See
217 * ubi_cachePut().
219 * Output: A pointer to the initialized cache (i.e., the same as CachePtr).
221 * Notes: Both MaxEntries and MaxMemory may be changed after the cache
222 * has been created. See
223 * ubi_cacheSetMaxEntries()
224 * ubi_cacheSetMaxMemory()
225 * ubi_cacheGetMaxEntries()
226 * ubi_cacheGetMaxMemory() (the latter two are macros).
228 * - Memory is allocated in multiples of the word size. The
229 * return value of the strlen() function does not reflect
230 * this; it will allways be less than or equal to the amount
231 * of memory actually allocated. Keep this in mind when
232 * choosing a value for MaxMemory.
234 * ------------------------------------------------------------------------ **
237 ubi_cacheRootPtr ubi_cacheClear( ubi_cacheRootPtr CachePtr );
238 /* ------------------------------------------------------------------------ **
239 * Remove and free all entries in an existing cache.
241 * Input: CachePtr - A pointer to the cache that is to be cleared.
243 * Output: A pointer to the cache header (i.e., the same as CachePtr).
244 * This function re-initializes the cache header.
246 * ------------------------------------------------------------------------ **
249 void ubi_cachePut( ubi_cacheRootPtr CachePtr,
250 unsigned long EntrySize,
251 ubi_cacheEntryPtr EntryPtr,
252 ubi_trItemPtr Key );
253 /* ------------------------------------------------------------------------ **
254 * Add an entry to the cache.
256 * Input: CachePtr - A pointer to the cache into which the entry
257 * will be added.
258 * EntrySize - The size, in bytes, of the memory block indicated
259 * by EntryPtr. This will be copied into the
260 * EntryPtr->entry_size field.
261 * EntryPtr - A pointer to a memory block that begins with a
262 * ubi_cacheEntry structure. The entry structure
263 * should be followed immediately by the data to be
264 * cached (even if that is a pointer to yet more data).
265 * Key - Pointer used to identify the lookup key within the
266 * Entry.
268 * Output: None.
270 * Notes: After adding the new node, the cache is "trimmed". This
271 * removes extra nodes if the tree has exceeded it's memory or
272 * entry count limits. It is unlikely that the newly added node
273 * will be purged from the cache (assuming a reasonably large
274 * cache), since new nodes in a splay tree (which is what this
275 * module was designed to use) are moved to the top of the tree
276 * and the cache purge process removes nodes from the bottom of
277 * the tree.
278 * - The underlying splay tree is opened in OVERWRITE mode. If
279 * the input key matches an existing key, the existing entry will
280 * be politely removed from the tree and freed.
281 * - Memory is allocated in multiples of the word size. The
282 * return value of the strlen() function does not reflect
283 * this; it will allways be less than or equal to the amount
284 * of memory actually allocated.
286 * ------------------------------------------------------------------------ **
289 ubi_cacheEntryPtr ubi_cacheGet( ubi_cacheRootPtr CachePtr,
290 ubi_trItemPtr FindMe );
291 /* ------------------------------------------------------------------------ **
292 * Attempt to retrieve an entry from the cache.
294 * Input: CachePtr - A ponter to the cache that is to be searched.
295 * FindMe - A ubi_trItemPtr that indicates the key for which
296 * to search.
298 * Output: A pointer to the cache entry that was found, or NULL if no
299 * matching entry was found.
301 * Notes: This function also updates the hit ratio counters.
302 * The counters are unsigned short. If the number of cache tries
303 * reaches 32768, then both the number of tries and the number of
304 * hits are divided by two. This prevents the counters from
305 * overflowing. See the comments in ubi_cacheHitRatio() for
306 * additional notes.
308 * ------------------------------------------------------------------------ **
311 ubi_trBool ubi_cacheDelete( ubi_cacheRootPtr CachePtr, ubi_trItemPtr DeleteMe );
312 /* ------------------------------------------------------------------------ **
313 * Find and delete the specified cache entry.
315 * Input: CachePtr - A pointer to the cache.
316 * DeleteMe - The key of the entry to be deleted.
318 * Output: TRUE if the entry was found & freed, else FALSE.
320 * ------------------------------------------------------------------------ **
323 ubi_trBool ubi_cacheReduce( ubi_cacheRootPtr CachePtr, unsigned long count );
324 /* ------------------------------------------------------------------------ **
325 * Remove <count> entries from the bottom of the cache.
327 * Input: CachePtr - A pointer to the cache which is to be reduced in
328 * size.
329 * count - The number of entries to remove.
331 * Output: The function will return TRUE if <count> entries were removed,
332 * else FALSE. A return value of FALSE should indicate that
333 * there were less than <count> entries in the cache, and that the
334 * cache is now empty.
336 * Notes: This function forces a reduction in the number of cache entries
337 * without requiring that the MaxMemory or MaxEntries values be
338 * changed.
340 * ------------------------------------------------------------------------ **
343 unsigned long ubi_cacheSetMaxEntries( ubi_cacheRootPtr CachePtr,
344 unsigned long NewSize );
345 /* ------------------------------------------------------------------------ **
346 * Change the maximum number of entries allowed to exist in the cache.
348 * Input: CachePtr - A pointer to the cache to be modified.
349 * NewSize - The new maximum number of cache entries.
351 * Output: The maximum number of entries previously allowed to exist in
352 * the cache.
354 * Notes: If the new size is less than the old size, this function will
355 * trim the cache (remove excess entries).
356 * - A value of zero indicates an unlimited number of entries.
358 * ------------------------------------------------------------------------ **
361 unsigned long ubi_cacheSetMaxMemory( ubi_cacheRootPtr CachePtr,
362 unsigned long NewSize );
363 /* ------------------------------------------------------------------------ **
364 * Change the maximum amount of memory to be used for storing cache
365 * entries.
367 * Input: CachePtr - A pointer to the cache to be modified.
368 * NewSize - The new cache memory size.
370 * Output: The previous maximum memory size.
372 * Notes: If the new size is less than the old size, this function will
373 * trim the cache (remove excess entries).
374 * - A value of zero indicates that the cache has no memory limit.
376 * ------------------------------------------------------------------------ **
379 int ubi_cacheHitRatio( ubi_cacheRootPtr CachePtr );
380 /* ------------------------------------------------------------------------ **
381 * Returns a value that is 10,000 times the slightly weighted average hit
382 * ratio for the cache.
384 * Input: CachePtr - Pointer to the cache to be queried.
386 * Output: An integer that is 10,000 times the number of successful
387 * cache hits divided by the number of cache lookups, or:
388 * (10000 * hits) / trys
389 * You can easily convert this to a float, or do something
390 * like this (where i is the return value of this function):
392 * printf( "Hit rate : %d.%02d%%\n", (i/100), (i%100) );
394 * Notes: I say "slightly-weighted", because the numerator and
395 * denominator are both accumulated in locations of type
396 * 'unsigned short'. If the number of cache trys becomes
397 * large enough, both are divided by two. (See function
398 * ubi_cacheGet().)
399 * Dividing both numerator and denominator by two does not
400 * change the ratio (much...it is an integer divide), but it
401 * does mean that subsequent increments to either counter will
402 * have twice as much significance as previous ones.
404 * - The value returned by this function will be in the range
405 * [0..10000] because ( 0 <= cache_hits <= cache_trys ) will
406 * always be true.
408 * ------------------------------------------------------------------------ **
411 /* -------------------------------------------------------------------------- */
412 #endif /* ubi_CACHE_H */