source3/ubiqx/ubi_Cache.h

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