path: root/source/ubiqx/ubi_Cache.c

/* ========================================================================== **
 *                                 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_trKillNodeRtn.  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.4  1999/09/22 03:42:24  crh
 *  Fixed a minor typo.
 *
 *  Revision 0.3  1998/06/03 18:00:15  crh
 *  Further fiddling with sys_include.h, which is no longer explicitly
 *  included by this module since it is inherited from ubi_BinTree.h.
 *
 *  Revision 0.2  1998/06/02 01:36:18  crh
 *  Changed include name from ubi_null.h to sys_include.h to make it
 *  more generic.
 *
 *  Revision 0.1  1998/05/20 04:36:02  crh
 *  The C file now includes ubi_null.h.  See ubi_null.h for more info.
 *
 *  Revision 0.0  1997/12/18 06:24:33  crh
 *  Initial Revision.
 *
 * ========================================================================== **
 */

#include "ubi_Cache.h"    /* Header for *this* module. */

/* -------------------------------------------------------------------------- **
 * Static data...
 */

/*  commented out until I make use of it...
static char ModuleID[] = 
"ubi_Cache\n\
\tRevision: 0.4 \n\
\tDate: 1999/09/22 03:42:24 \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 */

/* -------------------------------------------------------------------------- */