ubi_cache.h

samba-3.0.22.tar.gz 编译smb服务器的源码

#ifndef UBI_CACHE_H
#define UBI_CACHE_H
/* ========================================================================== **
 *                                 ubi_Cache.h
 *
 *  Copyright (C) 1997 by Christopher R. Hertel
 *
 *  Email: [e-mail]
 * -------------------------------------------------------------------------- **
 *
 *  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.h,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: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