1#ifndef UBI_CACHE_H 2#define UBI_CACHE_H 3/* ========================================================================== ** 4 * ubi_Cache.h 5 * 6 * Copyright (C) 1997 by Christopher R. Hertel 7 * 8 * Email: crh@ubiqx.mn.org 9 * -------------------------------------------------------------------------- ** 10 * 11 * This module implements a generic cache. 12 * 13 * -------------------------------------------------------------------------- ** 14 * 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. 19 * 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. 24 * 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. 28 * 29 * -------------------------------------------------------------------------- ** 30 * 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: 34 * 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. 44 * 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. 49 * 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_trKillNodeTrn. See ubi_BinTree.h for more information on 53 * these. (This is all basic ubiqx tree management stuff.) 54 * 55 * Notes: 56 * 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). 65 * 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. 69 * 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. 76 * 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. 81 * 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.) 87 * 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. 92 * 93 * -------------------------------------------------------------------------- ** 94 * 95 * Log: ubi_Cache.h,v 96 * Revision 0.3 1998/06/03 18:00:15 crh 97 * Further fiddling with sys_include.h, which is no longer explicitly 98 * included by this module since it is inherited from ubi_BinTree.h. 99 * 100 * Revision 0.2 1998/06/02 01:36:18 crh 101 * Changed include name from ubi_null.h to sys_include.h to make it 102 * more generic. 103 * 104 * Revision 0.1 1998/05/20 04:36:02 crh 105 * The C file now includes ubi_null.h. See ubi_null.h for more info. 106 * 107 * Revision 0.0 1997/12/18 06:25:23 crh 108 * Initial Revision. 109 * 110 * ========================================================================== ** 111 */ 112 113#include "ubi_SplayTree.h" 114 115/* -------------------------------------------------------------------------- ** 116 * Typedefs... 117 * 118 * ubi_cacheRoot - Cache header structure, which consists of a binary 119 * tree root and other required housekeeping fields, as 120 * listed below. 121 * ubi_cacheRootPtr - Pointer to a Cache. 122 * 123 * ubi_cacheEntry - A cache Entry, which consists of a tree node 124 * structure and the size (in bytes) of the entry 125 * data. The entry size should be supplied via 126 * the EntrySize parameter of the ubi_cachePut() 127 * function. 128 * 129 * ubi_cacheEntryPtr - Pointer to a ubi_cacheEntry. 130 * 131 */ 132 133typedef struct 134 { 135 ubi_trRoot root; /* Splay tree control structure. */ 136 ubi_trKillNodeRtn free_func; /* Function used to free entries. */ 137 unsigned long max_entries; /* Max cache entries. 0 == unlimited */ 138 unsigned long max_memory; /* Max memory to use. 0 == unlimited */ 139 unsigned long mem_used; /* Memory currently in use (bytes). */ 140 unsigned short cache_hits; /* Incremented on succesful find. */ 141 unsigned short cache_trys; /* Incremented on cache lookup. */ 142 } ubi_cacheRoot; 143 144typedef ubi_cacheRoot *ubi_cacheRootPtr; 145 146 147typedef struct 148 { 149 ubi_trNode node; /* Tree node structure. */ 150 unsigned long entry_size; /* Entry size. Used when managing 151 * caches with maximum memory limits. 152 */ 153 } ubi_cacheEntry; 154 155typedef ubi_cacheEntry *ubi_cacheEntryPtr; 156 157 158/* -------------------------------------------------------------------------- ** 159 * Macros... 160 * 161 * ubi_cacheGetMaxEntries() - Report the current maximum number of entries 162 * allowed in the cache. Zero indicates no 163 * maximum. 164 * ubi_cacheGetMaxMemory() - Report the current maximum amount of memory 165 * that may be used in the cache. Zero 166 * indicates no maximum. 167 * ubi_cacheGetEntryCount() - Report the current number of entries in the 168 * cache. 169 * ubi_cacheGetMemUsed() - Report the amount of memory currently in use 170 * by the cache. 171 */ 172 173#define ubi_cacheGetMaxEntries( Cptr ) (((ubi_cacheRootPtr)(Cptr))->max_entries) 174#define ubi_cacheGetMaxMemory( Cptr ) (((ubi_cacheRootPtr)(Cptr))->max_memory) 175 176#define ubi_cacheGetEntryCount( Cptr ) (((ubi_cacheRootPtr)(Cptr))->root.count) 177#define ubi_cacheGetMemUsed( Cptr ) (((ubi_cacheRootPtr)(Cptr))->mem_used) 178 179/* -------------------------------------------------------------------------- ** 180 * Prototypes... 181 */ 182 183ubi_cacheRootPtr ubi_cacheInit( ubi_cacheRootPtr CachePtr, 184 ubi_trCompFunc CompFunc, 185 ubi_trKillNodeRtn FreeFunc, 186 unsigned long MaxEntries, 187 unsigned long MaxMemory ); 188 /* ------------------------------------------------------------------------ ** 189 * Initialize a cache header structure. 190 * 191 * Input: CachePtr - A pointer to a ubi_cacheRoot structure that is 192 * to be initialized. 193 * CompFunc - A pointer to the function that will be called 194 * to compare two cache values. See the module 195 * comments, above, for more information. 196 * FreeFunc - A pointer to a function that will be called 197 * to free a cache entry. If you allocated 198 * the cache entry using malloc(), then this 199 * will likely be free(). If you are allocating 200 * cache entries from a free list, then this will 201 * likely be a function that returns memory to the 202 * free list, etc. 203 * MaxEntries - The maximum number of entries that will be 204 * allowed to exist in the cache. If this limit 205 * is exceeded, then existing entries will be 206 * removed from the cache. A value of zero 207 * indicates that there is no limit on the number 208 * of cache entries. See ubi_cachePut(). 209 * MaxMemory - The maximum amount of memory, in bytes, to be 210 * allocated to the cache (excluding the cache 211 * header). If this is exceeded, existing entries 212 * in the cache will be removed until enough memory 213 * has been freed to meet the condition. See 214 * ubi_cachePut(). 215 * 216 * Output: A pointer to the initialized cache (i.e., the same as CachePtr). 217 * 218 * Notes: Both MaxEntries and MaxMemory may be changed after the cache 219 * has been created. See 220 * ubi_cacheSetMaxEntries() 221 * ubi_cacheSetMaxMemory() 222 * ubi_cacheGetMaxEntries() 223 * ubi_cacheGetMaxMemory() (the latter two are macros). 224 * 225 * - Memory is allocated in multiples of the word size. The 226 * return value of the strlen() function does not reflect 227 * this; it will allways be less than or equal to the amount 228 * of memory actually allocated. Keep this in mind when 229 * choosing a value for MaxMemory. 230 * 231 * ------------------------------------------------------------------------ ** 232 */ 233 234ubi_cacheRootPtr ubi_cacheClear( ubi_cacheRootPtr CachePtr ); 235 /* ------------------------------------------------------------------------ ** 236 * Remove and free all entries in an existing cache. 237 * 238 * Input: CachePtr - A pointer to the cache that is to be cleared. 239 * 240 * Output: A pointer to the cache header (i.e., the same as CachePtr). 241 * This function re-initializes the cache header. 242 * 243 * ------------------------------------------------------------------------ ** 244 */ 245 246void ubi_cachePut( ubi_cacheRootPtr CachePtr, 247 unsigned long EntrySize, 248 ubi_cacheEntryPtr EntryPtr, 249 ubi_trItemPtr Key ); 250 /* ------------------------------------------------------------------------ ** 251 * Add an entry to the cache. 252 * 253 * Input: CachePtr - A pointer to the cache into which the entry 254 * will be added. 255 * EntrySize - The size, in bytes, of the memory block indicated 256 * by EntryPtr. This will be copied into the 257 * EntryPtr->entry_size field. 258 * EntryPtr - A pointer to a memory block that begins with a 259 * ubi_cacheEntry structure. The entry structure 260 * should be followed immediately by the data to be 261 * cached (even if that is a pointer to yet more data). 262 * Key - Pointer used to identify the lookup key within the 263 * Entry. 264 * 265 * Output: None. 266 * 267 * Notes: After adding the new node, the cache is "trimmed". This 268 * removes extra nodes if the tree has exceeded it's memory or 269 * entry count limits. It is unlikely that the newly added node 270 * will be purged from the cache (assuming a reasonably large 271 * cache), since new nodes in a splay tree (which is what this 272 * module was designed to use) are moved to the top of the tree 273 * and the cache purge process removes nodes from the bottom of 274 * the tree. 275 * - The underlying splay tree is opened in OVERWRITE mode. If 276 * the input key matches an existing key, the existing entry will 277 * be politely removed from the tree and freed. 278 * - Memory is allocated in multiples of the word size. The 279 * return value of the strlen() function does not reflect 280 * this; it will allways be less than or equal to the amount 281 * of memory actually allocated. 282 * 283 * ------------------------------------------------------------------------ ** 284 */ 285 286ubi_cacheEntryPtr ubi_cacheGet( ubi_cacheRootPtr CachePtr, 287 ubi_trItemPtr FindMe ); 288 /* ------------------------------------------------------------------------ ** 289 * Attempt to retrieve an entry from the cache. 290 * 291 * Input: CachePtr - A ponter to the cache that is to be searched. 292 * FindMe - A ubi_trItemPtr that indicates the key for which 293 * to search. 294 * 295 * Output: A pointer to the cache entry that was found, or NULL if no 296 * matching entry was found. 297 * 298 * Notes: This function also updates the hit ratio counters. 299 * The counters are unsigned short. If the number of cache tries 300 * reaches 32768, then both the number of tries and the number of 301 * hits are divided by two. This prevents the counters from 302 * overflowing. See the comments in ubi_cacheHitRatio() for 303 * additional notes. 304 * 305 * ------------------------------------------------------------------------ ** 306 */ 307 308ubi_trBool ubi_cacheDelete( ubi_cacheRootPtr CachePtr, ubi_trItemPtr DeleteMe ); 309 /* ------------------------------------------------------------------------ ** 310 * Find and delete the specified cache entry. 311 * 312 * Input: CachePtr - A pointer to the cache. 313 * DeleteMe - The key of the entry to be deleted. 314 * 315 * Output: TRUE if the entry was found & freed, else FALSE. 316 * 317 * ------------------------------------------------------------------------ ** 318 */ 319 320ubi_trBool ubi_cacheReduce( ubi_cacheRootPtr CachePtr, unsigned long count ); 321 /* ------------------------------------------------------------------------ ** 322 * Remove <count> entries from the bottom of the cache. 323 * 324 * Input: CachePtr - A pointer to the cache which is to be reduced in 325 * size. 326 * count - The number of entries to remove. 327 * 328 * Output: The function will return TRUE if <count> entries were removed, 329 * else FALSE. A return value of FALSE should indicate that 330 * there were less than <count> entries in the cache, and that the 331 * cache is now empty. 332 * 333 * Notes: This function forces a reduction in the number of cache entries 334 * without requiring that the MaxMemory or MaxEntries values be 335 * changed. 336 * 337 * ------------------------------------------------------------------------ ** 338 */ 339 340unsigned long ubi_cacheSetMaxEntries( ubi_cacheRootPtr CachePtr, 341 unsigned long NewSize ); 342 /* ------------------------------------------------------------------------ ** 343 * Change the maximum number of entries allowed to exist in the cache. 344 * 345 * Input: CachePtr - A pointer to the cache to be modified. 346 * NewSize - The new maximum number of cache entries. 347 * 348 * Output: The maximum number of entries previously allowed to exist in 349 * the cache. 350 * 351 * Notes: If the new size is less than the old size, this function will 352 * trim the cache (remove excess entries). 353 * - A value of zero indicates an unlimited number of entries. 354 * 355 * ------------------------------------------------------------------------ ** 356 */ 357 358unsigned long ubi_cacheSetMaxMemory( ubi_cacheRootPtr CachePtr, 359 unsigned long NewSize ); 360 /* ------------------------------------------------------------------------ ** 361 * Change the maximum amount of memory to be used for storing cache 362 * entries. 363 * 364 * Input: CachePtr - A pointer to the cache to be modified. 365 * NewSize - The new cache memory size. 366 * 367 * Output: The previous maximum memory size. 368 * 369 * Notes: If the new size is less than the old size, this function will 370 * trim the cache (remove excess entries). 371 * - A value of zero indicates that the cache has no memory limit. 372 * 373 * ------------------------------------------------------------------------ ** 374 */ 375 376int ubi_cacheHitRatio( ubi_cacheRootPtr CachePtr ); 377 /* ------------------------------------------------------------------------ ** 378 * Returns a value that is 10,000 times the slightly weighted average hit 379 * ratio for the cache. 380 * 381 * Input: CachePtr - Pointer to the cache to be queried. 382 * 383 * Output: An integer that is 10,000 times the number of successful 384 * cache hits divided by the number of cache lookups, or: 385 * (10000 * hits) / trys 386 * You can easily convert this to a float, or do something 387 * like this (where i is the return value of this function): 388 * 389 * printf( "Hit rate : %d.%02d%%\n", (i/100), (i%100) ); 390 * 391 * Notes: I say "slightly-weighted", because the numerator and 392 * denominator are both accumulated in locations of type 393 * 'unsigned short'. If the number of cache trys becomes 394 * large enough, both are divided by two. (See function 395 * ubi_cacheGet().) 396 * Dividing both numerator and denominator by two does not 397 * change the ratio (much...it is an integer divide), but it 398 * does mean that subsequent increments to either counter will 399 * have twice as much significance as previous ones. 400 * 401 * - The value returned by this function will be in the range 402 * [0..10000] because ( 0 <= cache_hits <= cache_trys ) will 403 * always be true. 404 * 405 * ------------------------------------------------------------------------ ** 406 */ 407 408/* -------------------------------------------------------------------------- */ 409#endif /* ubi_CACHE_H */ 410