Adding the cache module.

I'll be using the cache module to replace the name cache in mangle.c.  The
new one should be much faster and should require less memory.
Another feature is that the cache size can be limited by the amount of
memory used in addition to the number of entries allowed.  With the
current cache, the default is to allocate 12800 bytes representing 50
entries (256 bytes each).  With the same amount of memory, I should be able
to load over around two hundred entries.
Changes to the AVL trees were minor (missing comments).
Chris -)-----
(This used to be commit 45962779a658b0b78895ae08ad394e870ce6ed10)

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 */