diff options
Diffstat (limited to 'source3/ubiqx')
| -rw-r--r-- | source3/ubiqx/ubi_AVLtree.c | 15 | ||||
| -rw-r--r-- | source3/ubiqx/ubi_AVLtree.h | 3 | ||||
| -rw-r--r-- | source3/ubiqx/ubi_Cache.c | 490 | ||||
| -rw-r--r-- | source3/ubiqx/ubi_Cache.h | 398 |
4 files changed, 903 insertions, 3 deletions
diff --git a/source3/ubiqx/ubi_AVLtree.c b/source3/ubiqx/ubi_AVLtree.c index 6ad4053dfa..a864b160b5 100644 --- a/source3/ubiqx/ubi_AVLtree.c +++ b/source3/ubiqx/ubi_AVLtree.c @@ -9,6 +9,12 @@ * This module provides an implementation of AVL height balanced binary * trees. (Adelson-Velskii, Landis 1962) * + * This header file contains the basic AVL structure and pointer typedefs + * as well as the prototypes needed to access the functions in the AVL + * module ubi_AVLtree. The .c file implements the low-level height balancing + * routines that manage the AVL tree, plus all of the basic primops for + * adding, searching for, and deleting nodes. + * * -------------------------------------------------------------------------- ** * * This library is free software; you can redistribute it and/or @@ -28,6 +34,9 @@ * -------------------------------------------------------------------------- ** * * Log: ubi_AVLtree.c,v + * Revision 3.1 1997/12/18 06:26:51 crh + * Fixed some comment bugs. + * * Revision 3.0 1997/12/08 05:38:55 crh * This is a new major revision level. The handling of the pointers in the * ubi_trNode structure was redesigned. The result is that there are fewer @@ -36,7 +45,7 @@ * * Revision 2; 1995/03/05 - 1997/12/07: * An overhaul to the node delete process. I had gotten it wrong in a - * couple of places, thought I'd fixed it, and then found that I'd missing + * couple of places, thought I'd fixed it, and then found that I'd missed * something more. Thanks to Andrew Leppard for the bug report! * * Revision 1; 93/10/15 - 95/03/05: @@ -55,8 +64,8 @@ */ static char ModuleID[] = "ubi_AVLtree\n\ -\tRevision: 3.0\n\ -\tDate: 1997/12/08 05:38:55\n\ +\tRevision: 3.1\n\ +\tDate: 1997/12/18 06:26:51 GMT\n\ \tAuthor: crh\n"; /* ========================================================================== ** diff --git a/source3/ubiqx/ubi_AVLtree.h b/source3/ubiqx/ubi_AVLtree.h index 61aaf99348..c7cac0ed1e 100644 --- a/source3/ubiqx/ubi_AVLtree.h +++ b/source3/ubiqx/ubi_AVLtree.h @@ -35,6 +35,9 @@ * * -------------------------------------------------------------------------- ** * Log: ubi_AVLtree.h,v + * Revision 3.1 1997/12/18 06:27:01 crh + * Fixed some comment bugs. + * * Revision 3.0 1997/12/08 05:39:01 crh * This is a new major revision level. The handling of the pointers in the * ubi_trNode structure was redesigned. The result is that there are fewer diff --git a/source3/ubiqx/ubi_Cache.c b/source3/ubiqx/ubi_Cache.c new file mode 100644 index 0000000000..4b65e3eda6 --- /dev/null +++ b/source3/ubiqx/ubi_Cache.c @@ -0,0 +1,490 @@ +/* ========================================================================== ** + * ubi_Cache.c + * + * Copyright (C) 1997 by Christopher R. Hertel + * + * Email: crh@ubiqx.mn.org + * -------------------------------------------------------------------------- ** + * + * This module implements a generic cache. + * + * -------------------------------------------------------------------------- ** + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Library General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with this library; if not, write to the Free + * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + * -------------------------------------------------------------------------- ** + * + * This module uses a splay tree to implement a simple cache. The cache + * module adds a thin layer of functionality to the splay tree. In + * particular: + * + * - The tree (cache) may be limited in size by the number of + * entries permitted or the amount of memory used. When either + * limit is exceeded cache entries are removed until the cache + * conforms. + * - Some statistical information is kept so that an approximate + * "hit ratio" can be calculated. + * - There are several functions available that provide access to + * and management of cache size limits, hit ratio, and tree + * trimming. + * + * The splay tree is used because recently accessed items tend toward the + * top of the tree and less recently accessed items tend toward the bottom. + * This makes it easy to purge less recently used items should the cache + * exceed its limits. + * + * To use this module, you will need to supply a comparison function of + * type ubi_trCompFunc and a node-freeing function of type + * ubi_trKillNodeTrn. See ubi_BinTree.h for more information on + * these. (This is all basic ubiqx tree management stuff.) + * + * Notes: + * + * - Cache performance will start to suffer dramatically if the + * cache becomes large enough to force the OS to start swapping + * memory to disk. This is because the nodes of the underlying tree + * will be scattered across memory in an order that is completely + * unrelated to their traversal order. As more and more of the + * cache is placed into swap space, more and more swaps will be + * required for a simple traversal (...and then there's the splay + * operation). + * + * In one simple test under Linux, the load and dump of a cache of + * 400,000 entries took only 1min, 40sec of real time. The same + * test with 450,000 records took 2 *hours* and eight minutes. + * + * - In an effort to save memory, I considered using an unsigned + * short to save the per-entry entry size. I would have tucked this + * value into some unused space in the tree node structure. On + * 32-bit word aligned systems this would have saved an additional + * four bytes per entry. I may revisit this issue, but for now I've + * decided against it. + * + * Using an unsigned short would limit the size of an entry to 64K + * bytes. That's probably more than enough for most applications. + * The key word in that last sentence, however, is "probably". I + * really dislike imposing such limits on things. + * + * - Each entry keeps track of the amount of memory it used and the + * cache header keeps the total. This information is provided via + * the EntrySize parameter in ubi_cachePut(), so it is up to you to + * make sure that the numbers are accurate. (The numbers don't even + * have to represent bytes used.) + * + * As you consider this, note that the strdup() function--as an + * example--will call malloc(). The latter generally allocates a + * multiple of the system word size, which may be more than the + * number of bytes needed to store the string. + * + * -------------------------------------------------------------------------- ** + * + * Log: ubi_Cache.c,v + * Revision 0.0 1997/12/18 06:24:33 crh + * Initial Revision. + * + * ========================================================================== ** + */ + +#include <stdlib.h> /* Defines NULL. */ +#include "ubi_Cache.h" /* Header for *this* module. */ + +/* -------------------------------------------------------------------------- ** + * Static data... + */ + +static char ModuleID[] = +"ubi_Cache\n\ +\tRevision: 0.0\n\ +\tDate: 1997/12/18 06:24:33 GMT\n\ +\tAuthor: crh\n"; + +/* -------------------------------------------------------------------------- ** + * Internal functions... + */ + +static void free_entry( ubi_cacheRootPtr CachePtr, ubi_cacheEntryPtr EntryPtr ) + /* ------------------------------------------------------------------------ ** + * Free a ubi_cacheEntry, and adjust the mem_used counter accordingly. + * + * Input: CachePtr - A pointer to the cache from which the entry has + * been removed. + * EntryPtr - A pointer to the already removed entry. + * + * Output: none. + * + * Notes: The entry must be removed from the cache *before* this function + * is called!!!! + * ------------------------------------------------------------------------ ** + */ + { + CachePtr->mem_used -= EntryPtr->entry_size; + (*CachePtr->free_func)( (void *)EntryPtr ); + } /* free_entry */ + +static void cachetrim( ubi_cacheRootPtr crptr ) + /* ------------------------------------------------------------------------ ** + * Remove entries from the cache until the number of entries and the amount + * of memory used are *both* below or at the maximum. + * + * Input: crptr - pointer to the cache to be trimmed. + * + * Output: None. + * + * ------------------------------------------------------------------------ ** + */ + { + while( ( crptr->max_entries && (crptr->max_entries < crptr->root.count) ) + || ( crptr->max_memory && (crptr->max_memory < crptr->mem_used) ) ) + { + if( !ubi_cacheReduce( crptr, 1 ) ) + return; + } + } /* cachetrim */ + + +/* -------------------------------------------------------------------------- ** + * Exported functions... + */ + +ubi_cacheRootPtr ubi_cacheInit( ubi_cacheRootPtr CachePtr, + ubi_trCompFunc CompFunc, + ubi_trKillNodeRtn FreeFunc, + unsigned long MaxEntries, + unsigned long MaxMemory ) + /* ------------------------------------------------------------------------ ** + * Initialize a cache header structure. + * + * Input: CachePtr - A pointer to a ubi_cacheRoot structure that is + * to be initialized. + * CompFunc - A pointer to the function that will be called + * to compare two cache values. See the module + * comments, above, for more information. + * FreeFunc - A pointer to a function that will be called + * to free a cache entry. If you allocated + * the cache entry using malloc(), then this + * will likely be free(). If you are allocating + * cache entries from a free list, then this will + * likely be a function that returns memory to the + * free list, etc. + * MaxEntries - The maximum number of entries that will be + * allowed to exist in the cache. If this limit + * is exceeded, then existing entries will be + * removed from the cache. A value of zero + * indicates that there is no limit on the number + * of cache entries. See ubi_cachePut(). + * MaxMemory - The maximum amount of memory, in bytes, to be + * allocated to the cache (excluding the cache + * header). If this is exceeded, existing entries + * in the cache will be removed until enough memory + * has been freed to meet the condition. See + * ubi_cachePut(). + * + * Output: A pointer to the initialized cache (i.e., the same as CachePtr). + * + * Notes: Both MaxEntries and MaxMemory may be changed after the cache + * has been created. See + * ubi_cacheSetMaxEntries() + * ubi_cacheSetMaxMemory() + * ubi_cacheGetMaxEntries() + * ubi_cacheGetMaxMemory() (the latter two are macros). + * + * - Memory is allocated in multiples of the word size. The + * return value of the strlen() function does not reflect + * this; it will allways be less than or equal to the amount + * of memory actually allocated. Keep this in mind when + * choosing a value for MaxMemory. + * + * ------------------------------------------------------------------------ ** + */ + { + if( CachePtr ) + { + (void)ubi_trInitTree( CachePtr, CompFunc, ubi_trOVERWRITE ); + CachePtr->free_func = FreeFunc; + CachePtr->max_entries = MaxEntries; + CachePtr->max_memory = MaxMemory; + CachePtr->mem_used = 0; + CachePtr->cache_hits = 0; + CachePtr->cache_trys = 0; + } + return( CachePtr ); + } /* ubi_cacheInit */ + +ubi_cacheRootPtr ubi_cacheClear( ubi_cacheRootPtr CachePtr ) + /* ------------------------------------------------------------------------ ** + * Remove and free all entries in an existing cache. + * + * Input: CachePtr - A pointer to the cache that is to be cleared. + * + * Output: A pointer to the cache header (i.e., the same as CachePtr). + * This function re-initializes the cache header. + * + * ------------------------------------------------------------------------ ** + */ + { + if( CachePtr ) + { + (void)ubi_trKillTree( CachePtr, CachePtr->free_func ); + CachePtr->mem_used = 0; + CachePtr->cache_hits = 0; + CachePtr->cache_trys = 0; + } + return( CachePtr ); + } /* ubi_cacheClear */ + +void ubi_cachePut( ubi_cacheRootPtr CachePtr, + unsigned long EntrySize, + ubi_cacheEntryPtr EntryPtr, + ubi_trItemPtr Key ) + /* ------------------------------------------------------------------------ ** + * Add an entry to the cache. + * + * Input: CachePtr - A pointer to the cache into which the entry + * will be added. + * EntrySize - The size, in bytes, of the memory block indicated + * by EntryPtr. This will be copied into the + * EntryPtr->entry_size field. + * EntryPtr - A pointer to a memory block that begins with a + * ubi_cacheEntry structure. The entry structure + * should be followed immediately by the data to be + * cached (even if that is a pointer to yet more data). + * Key - Pointer used to identify the lookup key within the + * Entry. + * + * Output: None. + * + * Notes: After adding the new node, the cache is "trimmed". This + * removes extra nodes if the tree has exceeded it's memory or + * entry count limits. It is unlikely that the newly added node + * will be purged from the cache (assuming a reasonably large + * cache), since new nodes in a splay tree (which is what this + * module was designed to use) are moved to the top of the tree + * and the cache purge process removes nodes from the bottom of + * the tree. + * - The underlying splay tree is opened in OVERWRITE mode. If + * the input key matches an existing key, the existing entry will + * be politely removed from the tree and freed. + * - Memory is allocated in multiples of the word size. The + * return value of the strlen() function does not reflect + * this; it will allways be less than or equal to the amount + * of memory actually allocated. + * + * ------------------------------------------------------------------------ ** + */ + { + ubi_trNodePtr OldNode; + + EntryPtr->entry_size = EntrySize; + CachePtr->mem_used += EntrySize; + (void)ubi_trInsert( CachePtr, EntryPtr, Key, &OldNode ); + if( OldNode ) + free_entry( CachePtr, (ubi_cacheEntryPtr)OldNode ); + + cachetrim( CachePtr ); + } /* ubi_cachePut */ + +ubi_cacheEntryPtr ubi_cacheGet( ubi_cacheRootPtr CachePtr, + ubi_trItemPtr FindMe ) + /* ------------------------------------------------------------------------ ** + * Attempt to retrieve an entry from the cache. + * + * Input: CachePtr - A ponter to the cache that is to be searched. + * FindMe - A ubi_trItemPtr that indicates the key for which + * to search. + * + * Output: A pointer to the cache entry that was found, or NULL if no + * matching entry was found. + * + * Notes: This function also updates the hit ratio counters. + * The counters are unsigned short. If the number of cache tries + * reaches 32768, then both the number of tries and the number of + * hits are divided by two. This prevents the counters from + * overflowing. See the comments in ubi_cacheHitRatio() for + * additional notes. + * + * ------------------------------------------------------------------------ ** + */ + { + ubi_trNodePtr FoundPtr; + + FoundPtr = ubi_trFind( CachePtr, FindMe ); + + if( FoundPtr ) + CachePtr->cache_hits++; + CachePtr->cache_trys++; + + if( CachePtr->cache_trys & 0x8000 ) + { + CachePtr->cache_hits = CachePtr->cache_hits / 2; + CachePtr->cache_trys = CachePtr->cache_trys / 2; + } + + return( (ubi_cacheEntryPtr)FoundPtr ); + } /* ubi_cacheGet */ + +ubi_trBool ubi_cacheDelete( ubi_cacheRootPtr CachePtr, ubi_trItemPtr DeleteMe ) + /* ------------------------------------------------------------------------ ** + * Find and delete the specified cache entry. + * + * Input: CachePtr - A pointer to the cache. + * DeleteMe - The key of the entry to be deleted. + * + * Output: TRUE if the entry was found & freed, else FALSE. + * + * ------------------------------------------------------------------------ ** + */ + { + ubi_trNodePtr FoundPtr; + + FoundPtr = ubi_trFind( CachePtr, DeleteMe ); + if( FoundPtr ) + { + (void)ubi_trRemove( CachePtr, FoundPtr ); + free_entry( CachePtr, (ubi_cacheEntryPtr)FoundPtr ); + return( ubi_trTRUE ); + } + return( ubi_trFALSE ); + } /* ubi_cacheDelete */ + +ubi_trBool ubi_cacheReduce( ubi_cacheRootPtr CachePtr, unsigned long count ) + /* ------------------------------------------------------------------------ ** + * Remove <count> entries from the bottom of the cache. + * + * Input: CachePtr - A pointer to the cache which is to be reduced in + * size. + * count - The number of entries to remove. + * + * Output: The function will return TRUE if <count> entries were removed, + * else FALSE. A return value of FALSE should indicate that + * there were less than <count> entries in the cache, and that the + * cache is now empty. + * + * Notes: This function forces a reduction in the number of cache entries + * without requiring that the MaxMemory or MaxEntries values be + * changed. + * + * ------------------------------------------------------------------------ ** + */ + { + ubi_trNodePtr NodePtr; + + while( count ) + { + NodePtr = ubi_trLeafNode( CachePtr->root.root ); + if( NULL == NodePtr ) + return( ubi_trFALSE ); + else + { + (void)ubi_trRemove( CachePtr, NodePtr ); + free_entry( CachePtr, (ubi_cacheEntryPtr)NodePtr ); + } + count--; + } + return( ubi_trTRUE ); + } /* ubi_cacheReduce */ + +unsigned long ubi_cacheSetMaxEntries( ubi_cacheRootPtr CachePtr, + unsigned long NewSize ) + /* ------------------------------------------------------------------------ ** + * Change the maximum number of entries allowed to exist in the cache. + * + * Input: CachePtr - A pointer to the cache to be modified. + * NewSize - The new maximum number of cache entries. + * + * Output: The maximum number of entries previously allowed to exist in + * the cache. + * + * Notes: If the new size is less than the old size, this function will + * trim the cache (remove excess entries). + * - A value of zero indicates an unlimited number of entries. + * + * ------------------------------------------------------------------------ ** + */ + { + unsigned long oldsize = CachePtr->max_entries; /* Save the old value. */ + + CachePtr->max_entries = NewSize; /* Apply the new value. */ + if( (NewSize < oldsize) || (NewSize && !oldsize) ) /* If size is smaller, */ + cachetrim( CachePtr ); /* remove excess. */ + return( oldsize ); + } /* ubi_cacheSetMaxEntries */ + +unsigned long ubi_cacheSetMaxMemory( ubi_cacheRootPtr CachePtr, + unsigned long NewSize ) + /* ------------------------------------------------------------------------ ** + * Change the maximum amount of memory to be used for storing cache + * entries. + * + * Input: CachePtr - A pointer to the cache to be modified. + * NewSize - The new cache memory size. + * + * Output: The previous maximum memory size. + * + * Notes: If the new size is less than the old size, this function will + * trim the cache (remove excess entries). + * - A value of zero indicates that the cache has no memory limit. + * + * ------------------------------------------------------------------------ ** + */ + { + unsigned long oldsize = CachePtr->max_memory; /* Save the old value. */ + + CachePtr->max_memory = NewSize; /* Apply the new value. */ + if( (NewSize < oldsize) || (NewSize && !oldsize) ) /* If size is smaller, */ + cachetrim( CachePtr ); /* remove excess. */ + return( oldsize ); + } /* ubi_cacheSetMaxMemory */ + +int ubi_cacheHitRatio( ubi_cacheRootPtr CachePtr ) + /* ------------------------------------------------------------------------ ** + * Returns a value that is 10,000 times the slightly weighted average hit + * ratio for the cache. + * + * Input: CachePtr - Pointer to the cache to be queried. + * + * Output: An integer that is 10,000 times the number of successful + * cache hits divided by the number of cache lookups, or: + * (10000 * hits) / trys + * You can easily convert this to a float, or do something + * like this (where i is the return value of this function): + * + * printf( "Hit rate : %d.%02d%%\n", (i/100), (i%100) ); + * + * Notes: I say "slightly-weighted", because the numerator and + * denominator are both accumulated in locations of type + * 'unsigned short'. If the number of cache trys becomes + * large enough, both are divided by two. (See function + * ubi_cacheGet().) + * Dividing both numerator and denominator by two does not + * change the ratio (much...it is an integer divide), but it + * does mean that subsequent increments to either counter will + * have twice as much significance as previous ones. + * + * - The value returned by this function will be in the range + * [0..10000] because ( 0 <= cache_hits <= cache_trys ) will + * always be true. + * + * ------------------------------------------------------------------------ ** + */ + { + int tmp = 0; + + if( CachePtr->cache_trys ) + tmp = (int)( (10000 * (long)(CachePtr->cache_hits) ) + / (long)(CachePtr->cache_trys) ); + return( tmp ); + } /* ubi_cacheHitRatio */ + +/* -------------------------------------------------------------------------- */ diff --git a/source3/ubiqx/ubi_Cache.h b/source3/ubiqx/ubi_Cache.h new file mode 100644 index 0000000000..eddd6a4bf8 --- /dev/null +++ b/source3/ubiqx/ubi_Cache.h @@ -0,0 +1,398 @@ +#ifndef UBI_CACHE_H +#define UBI_CACHE_H +/* ========================================================================== ** + * ubi_Cache.h + * + * Copyright (C) 1997 by Christopher R. Hertel + * + * Email: crh@ubiqx.mn.org + * -------------------------------------------------------------------------- ** + * + * This module implements a generic cache. + * + * -------------------------------------------------------------------------- ** + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Library General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with this library; if not, write to the Free + * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + * -------------------------------------------------------------------------- ** + * + * This module uses a splay tree to implement a simple cache. The cache + * module adds a thin layer of functionality to the splay tree. In + * particular: + * + * - The tree (cache) may be limited in size by the number of + * entries permitted or the amount of memory used. When either + * limit is exceeded cache entries are removed until the cache + * conforms. + * - Some statistical information is kept so that an approximate + * "hit ratio" can be calculated. + * - There are several functions available that provide access to + * and management of cache size limits, hit ratio, and tree + * trimming. + * + * The splay tree is used because recently accessed items tend toward the + * top of the tree and less recently accessed items tend toward the bottom. + * This makes it easy to purge less recently used items should the cache + * exceed its limits. + * + * To use this module, you will need to supply a comparison function of + * type ubi_trCompFunc and a node-freeing function of type + * ubi_trKillNodeTrn. See ubi_BinTree.h for more information on + * these. (This is all basic ubiqx tree management stuff.) + * + * Notes: + * + * - Cache performance will start to suffer dramatically if the + * cache becomes large enough to force the OS to start swapping + * memory to disk. This is because the nodes of the underlying tree + * will be scattered across memory in an order that is completely + * unrelated to their traversal order. As more and more of the + * cache is placed into swap space, more and more swaps will be + * required for a simple traversal (...and then there's the splay + * operation). + * + * In one simple test under Linux, the load and dump of a cache of + * 400,000 entries took only 1min, 40sec of real time. The same + * test with 450,000 records took 2 *hours* and eight minutes. + * + * - In an effort to save memory, I considered using an unsigned + * short to save the per-entry entry size. I would have tucked this + * value into some unused space in the tree node structure. On + * 32-bit word aligned systems this would have saved an additional + * four bytes per entry. I may revisit this issue, but for now I've + * decided against it. + * + * Using an unsigned short would limit the size of an entry to 64K + * bytes. That's probably more than enough for most applications. + * The key word in that last sentence, however, is "probably". I + * really dislike imposing such limits on things. + * + * - Each entry keeps track of the amount of memory it used and the + * cache header keeps the total. This information is provided via + * the EntrySize parameter in ubi_cachePut(), so it is up to you to + * make sure that the numbers are accurate. (The numbers don't even + * have to represent bytes used.) + * + * As you consider this, note that the strdup() function--as an + * example--will call malloc(). The latter generally allocates a + * multiple of the system word size, which may be more than the + * number of bytes needed to store the string. + * + * -------------------------------------------------------------------------- ** + * + * Log: ubi_Cache.h,v + * Revision 0.0 1997/12/18 06:25:23 crh + * Initial Revision. + * + * ========================================================================== ** + */ + +#include "ubi_SplayTree.h" + +/* -------------------------------------------------------------------------- ** + * Typedefs... + * + * ubi_cacheRoot - Cache header structure, which consists of a binary + * tree root and other required housekeeping fields, as + * listed below. + * ubi_cacheRootPtr - Pointer to a Cache. + * + * ubi_cacheEntry - A cache Entry, which consists of a tree node + * structure and the size (in bytes) of the entry + * data. The entry size should be supplied via + * the EntrySize parameter of the ubi_cachePut() + * function. + * + * ubi_cacheEntryPtr - Pointer to a ubi_cacheEntry. + * + */ + +typedef struct + { + ubi_trRoot root; /* Splay tree control structure. */ + ubi_trKillNodeRtn free_func; /* Function used to free entries. */ + unsigned long max_entries; /* Max cache entries. 0 == unlimited */ + unsigned long max_memory; /* Max memory to use. 0 == unlimited */ + unsigned long mem_used; /* Memory currently in use (bytes). */ + unsigned short cache_hits; /* Incremented on succesful find. */ + unsigned short cache_trys; /* Incremented on cache lookup. */ + } ubi_cacheRoot; + +typedef ubi_cacheRoot *ubi_cacheRootPtr; + + +typedef struct + { + ubi_trNode node; /* Tree node structure. */ + unsigned long entry_size; /* Entry size. Used when managing + * caches with maximum memory limits. + */ + } ubi_cacheEntry; + +typedef ubi_cacheEntry *ubi_cacheEntryPtr; + + +/* -------------------------------------------------------------------------- ** + * Macros... + * + * ubi_cacheGetMaxEntries() - Report the current maximum number of entries + * allowed in the cache. Zero indicates no + * maximum. + * ubi_cacheGetMaxMemory() - Report the current maximum amount of memory + * that may be used in the cache. Zero + * indicates no maximum. + * ubi_cacheGetEntryCount() - Report the current number of entries in the + * cache. + * ubi_cacheGetMemUsed() - Report the amount of memory currently in use + * by the cache. + */ + +#define ubi_cacheGetMaxEntries( Cptr ) (((ubi_cacheRootPtr)(Cptr))->max_entries) +#define ubi_cacheGetMaxMemory( Cptr ) (((ubi_cacheRootPtr)(Cptr))->max_memory) + +#define ubi_cacheGetEntryCount( Cptr ) (((ubi_cacheRootPtr)(Cptr))->root.count) +#define ubi_cacheGetMemUsed( Cptr ) (((ubi_cacheRootPtr)(Cptr))->mem_used) + +/* -------------------------------------------------------------------------- ** + * Prototypes... + */ + +ubi_cacheRootPtr ubi_cacheInit( ubi_cacheRootPtr CachePtr, + ubi_trCompFunc CompFunc, + ubi_trKillNodeRtn FreeFunc, + unsigned long MaxEntries, + unsigned long MaxMemory ); + /* ------------------------------------------------------------------------ ** + * Initialize a cache header structure. + * + * Input: CachePtr - A pointer to a ubi_cacheRoot structure that is + * to be initialized. + * CompFunc - A pointer to the function that will be called + * to compare two cache values. See the module + * comments, above, for more information. + * FreeFunc - A pointer to a function that will be called + * to free a cache entry. If you allocated + * the cache entry using malloc(), then this + * will likely be free(). If you are allocating + * cache entries from a free list, then this will + * likely be a function that returns memory to the + * free list, etc. + * MaxEntries - The maximum number of entries that will be + * allowed to exist in the cache. If this limit + * is exceeded, then existing entries will be + * removed from the cache. A value of zero + * indicates that there is no limit on the number + * of cache entries. See ubi_cachePut(). + * MaxMemory - The maximum amount of memory, in bytes, to be + * allocated to the cache (excluding the cache + * header). If this is exceeded, existing entries + * in the cache will be removed until enough memory + * has been freed to meet the condition. See + * ubi_cachePut(). + * + * Output: A pointer to the initialized cache (i.e., the same as CachePtr). + * + * Notes: Both MaxEntries and MaxMemory may be changed after the cache + * has been created. See + * ubi_cacheSetMaxEntries() + * ubi_cacheSetMaxMemory() + * ubi_cacheGetMaxEntries() + * ubi_cacheGetMaxMemory() (the latter two are macros). + * + * - Memory is allocated in multiples of the word size. The + * return value of the strlen() function does not reflect + * this; it will allways be less than or equal to the amount + * of memory actually allocated. Keep this in mind when + * choosing a value for MaxMemory. + * + * ------------------------------------------------------------------------ ** + */ + +ubi_cacheRootPtr ubi_cacheClear( ubi_cacheRootPtr CachePtr ); + /* ------------------------------------------------------------------------ ** + * Remove and free all entries in an existing cache. + * + * Input: CachePtr - A pointer to the cache that is to be cleared. + * + * Output: A pointer to the cache header (i.e., the same as CachePtr). + * This function re-initializes the cache header. + * + * ------------------------------------------------------------------------ ** + */ + +void ubi_cachePut( ubi_cacheRootPtr CachePtr, + unsigned long EntrySize, + ubi_cacheEntryPtr EntryPtr, + ubi_trItemPtr Key ); + /* ------------------------------------------------------------------------ ** + * Add an entry to the cache. + * + * Input: CachePtr - A pointer to the cache into which the entry + * will be added. + * EntrySize - The size, in bytes, of the memory block indicated + * by EntryPtr. This will be copied into the + * EntryPtr->entry_size field. + * EntryPtr - A pointer to a memory block that begins with a + * ubi_cacheEntry structure. The entry structure + * should be followed immediately by the data to be + * cached (even if that is a pointer to yet more data). + * Key - Pointer used to identify the lookup key within the + * Entry. + * + * Output: None. + * + * Notes: After adding the new node, the cache is "trimmed". This + * removes extra nodes if the tree has exceeded it's memory or + * entry count limits. It is unlikely that the newly added node + * will be purged from the cache (assuming a reasonably large + * cache), since new nodes in a splay tree (which is what this + * module was designed to use) are moved to the top of the tree + * and the cache purge process removes nodes from the bottom of + * the tree. + * - The underlying splay tree is opened in OVERWRITE mode. If + * the input key matches an existing key, the existing entry will + * be politely removed from the tree and freed. + * - Memory is allocated in multiples of the word size. The + * return value of the strlen() function does not reflect + * this; it will allways be less than or equal to the amount + * of memory actually allocated. + * + * ------------------------------------------------------------------------ ** + */ + +ubi_cacheEntryPtr ubi_cacheGet( ubi_cacheRootPtr CachePtr, + ubi_trItemPtr FindMe ); + /* ------------------------------------------------------------------------ ** + * Attempt to retrieve an entry from the cache. + * + * Input: CachePtr - A ponter to the cache that is to be searched. + * FindMe - A ubi_trItemPtr that indicates the key for which + * to search. + * + * Output: A pointer to the cache entry that was found, or NULL if no + * matching entry was found. + * + * Notes: This function also updates the hit ratio counters. + * The counters are unsigned short. If the number of cache tries + * reaches 32768, then both the number of tries and the number of + * hits are divided by two. This prevents the counters from + * overflowing. See the comments in ubi_cacheHitRatio() for + * additional notes. + * + * ------------------------------------------------------------------------ ** + */ + +ubi_trBool ubi_cacheDelete( ubi_cacheRootPtr CachePtr, ubi_trItemPtr DeleteMe ); + /* ------------------------------------------------------------------------ ** + * Find and delete the specified cache entry. + * + * Input: CachePtr - A pointer to the cache. + * DeleteMe - The key of the entry to be deleted. + * + * Output: TRUE if the entry was found & freed, else FALSE. + * + * ------------------------------------------------------------------------ ** + */ + +ubi_trBool ubi_cacheReduce( ubi_cacheRootPtr CachePtr, unsigned long count ); + /* ------------------------------------------------------------------------ ** + * Remove <count> entries from the bottom of the cache. + * + * Input: CachePtr - A pointer to the cache which is to be reduced in + * size. + * count - The number of entries to remove. + * + * Output: The function will return TRUE if <count> entries were removed, + * else FALSE. A return value of FALSE should indicate that + * there were less than <count> entries in the cache, and that the + * cache is now empty. + * + * Notes: This function forces a reduction in the number of cache entries + * without requiring that the MaxMemory or MaxEntries values be + * changed. + * + * ------------------------------------------------------------------------ ** + */ + +unsigned long ubi_cacheSetMaxEntries( ubi_cacheRootPtr CachePtr, + unsigned long NewSize ); + /* ------------------------------------------------------------------------ ** + * Change the maximum number of entries allowed to exist in the cache. + * + * Input: CachePtr - A pointer to the cache to be modified. + * NewSize - The new maximum number of cache entries. + * + * Output: The maximum number of entries previously allowed to exist in + * the cache. + * + * Notes: If the new size is less than the old size, this function will + * trim the cache (remove excess entries). + * - A value of zero indicates an unlimited number of entries. + * + * ------------------------------------------------------------------------ ** + */ + +unsigned long ubi_cacheSetMaxMemory( ubi_cacheRootPtr CachePtr, + unsigned long NewSize ); + /* ------------------------------------------------------------------------ ** + * Change the maximum amount of memory to be used for storing cache + * entries. + * + * Input: CachePtr - A pointer to the cache to be modified. + * NewSize - The new cache memory size. + * + * Output: The previous maximum memory size. + * + * Notes: If the new size is less than the old size, this function will + * trim the cache (remove excess entries). + * - A value of zero indicates that the cache has no memory limit. + * + * ------------------------------------------------------------------------ ** + */ + +int ubi_cacheHitRatio( ubi_cacheRootPtr CachePtr ); + /* ------------------------------------------------------------------------ ** + * Returns a value that is 10,000 times the slightly weighted average hit + * ratio for the cache. + * + * Input: CachePtr - Pointer to the cache to be queried. + * + * Output: An integer that is 10,000 times the number of successful + * cache hits divided by the number of cache lookups, or: + * (10000 * hits) / trys + * You can easily convert this to a float, or do something + * like this (where i is the return value of this function): + * + * printf( "Hit rate : %d.%02d%%\n", (i/100), (i%100) ); + * + * Notes: I say "slightly-weighted", because the numerator and + * denominator are both accumulated in locations of type + * 'unsigned short'. If the number of cache trys becomes + * large enough, both are divided by two. (See function + * ubi_cacheGet().) + * Dividing both numerator and denominator by two does not + * change the ratio (much...it is an integer divide), but it + * does mean that subsequent increments to either counter will + * have twice as much significance as previous ones. + * + * - The value returned by this function will be in the range + * [0..10000] because ( 0 <= cache_hits <= cache_trys ) will + * always be true. + * + * ------------------------------------------------------------------------ ** + */ + +/* -------------------------------------------------------------------------- */ +#endif /* ubi_CACHE_H */ |