/* tag: Tom Lord Tue Dec  4 14:41:37 2001 (dfa-cache.c)
 */
/* dfa-cache.c -
 *
 ****************************************************************
 * Copyright (C) 2000 Tom Lord
 * 
 * See the file "COPYING" for further information about
 * the copyright and warranty status of this work.
 */


#include "hackerlab/mem/alloc-limits.h"
#include "hackerlab/rx/super.h"
#include "hackerlab/rx/dfa-cache.h"



/************************************************************************
 *(h1 "Tuning the DFA Cache Size"
 *    :includes ("hackerlab/rx/dfa-cache.h"))
 * 
 * |DFA cache|
 * |cache (DFA)|
 * |deterministic finite automata|
 * When Rx compiles a regexp or regular expression, it builds a tree
 * structure that describes the syntax of the expression.  Later, some
 * or all of the tree is converted to a graph, representing a
 * non-deterministic finite automata (NFA).  During matching, NFA are
 * incrementally converted to deterministic finite automata (DFA).
 * 
 * Rx maintains a cache of DFA fragments.  When part of a DFA is
 * needed, the cache is used to avoid redundant construction.  Because
 * DFA can be quite large, DFA fragments are sometimes flushed from
 * the cache to make room.
 * 
 * Note that the DFA cache can preserve DFA fragments beyond the
 * lifetime of a single compiled expression.  If an expression is
 * compiled, then matched, then freed, then recompiled, the recompiled
 * expression will sometimes re-use DFA fragments cached from the
 * first compile.
 * 
 * This chapter presents functions which are used to monitor and tune
 * the performance of the DFA cache.  Be sure to also read
 * xref:"The Impact of NFA and DFA Cache Sizes".
 */


/************************************************************************
 *(h2 "The DFA Cache Replacement Strategy")
 * 
 * |cache replacement strategy (DFA)|
 * |DFA cache replacement strategy|
 * DFA cache entries are approximately sorted from most to least
 * recently used.  When cache space is exhausted, the least recently
 * used entries are discarded.
 * 
 */

/************************************************************************
 *(h2 "The advisory DFA cache Limit")
 * 
 * |DFA cache limit|
 * |cache limit (DFA)|
 * |advisory limit|
 * |DFA cache threshold|
 * |cache threshold (DFA)|
 * The size of the DFA cache is regulated by an advisory limit called
 * the "cache threshold".  The threshold is a size (expressed in bytes)
 * which represents an ideal limit on the amount of memory used by the
 * DFA cache.
 * 
 * If an allocation within the DFA cache would cause the total amount
 * of memory used by the cache to exceed the threshold, Rx attempts to
 * discard sufficient cache entries to avoid exceeding the threshold.
 * This is not always possible.  When necessary for correct operation,
 * Rx will exceed the cache threshold: usually by a small amount;
 * sometimes by a large amount.  (That is why the threshold is called an
 * ^advisory^ limit.)
 * 
 * The default threshold is `1MB'.
 */

/*(c rx_set_dfa_cache_threshold)
 * void rx_set_dfa_cache_threshold (size_t n);
 * 
 * Set the advisory DFA cache limit to `n'.
 */
void
rx_set_dfa_cache_threshold (size_t n)
{
  rx__init_dfa_alloc_limits ();
  lim_set_threshold (rx__dfa_alloc_limits, n);
}


/*(c rx_dfa_cache_threshold)
 * size_t rx_dfa_cache_threshold (void);
 * 
 * Return the current DFA cache limit.
 */
size_t
rx_dfa_cache_threshold (void)
{
  rx__init_dfa_alloc_limits ();
  return lim_threshold (rx__dfa_alloc_limits);
}



/************************************************************************
 *(h2 "DFA Cache Statistics")
 * 
 * |DFA cache statistics|
 * |cache statistics (DFA)|
 * These functions report statistics about the DFA cache.
 * 
 */

/*(c rx_dfa_cache_in_use)
 * size_t rx_dfa_cache_in_use (void);
 * 
 * Return the amount of memory currently in use by the DFA cache.
 */
size_t
rx_dfa_cache_in_use (void)
{
  rx__init_dfa_alloc_limits ();
  return lim_in_use (rx__dfa_alloc_limits);
}


/*(c rx_dfa_cache_high_water_mark)
 * size_t rx_dfa_cache_high_water_mark (void);
 * 
 * Return the largest amount of memory ever used at one time by the
 * DFA cache.
 */
size_t
rx_dfa_cache_high_water_mark (void)
{
  rx__init_dfa_alloc_limits ();
  return lim_high_water_mark (rx__dfa_alloc_limits);
}


/*(c rx_dfa_cache_statistics)
 * void rx_dfa_cache_statistics (size_t * threshold,
 *                               size_t * ign,
 *                               size_t * in_use,
 *                               size_t * high_water_mark,
 *                               int * hits,
 *                               int * misses,
 *                               int * total_hits,
 *                               int * total_misses);
 * 
 * Return statistics about the effectiveness of the DFA cache.
 * 
 * All parameters are used to return values.  Any parameter may be 0.
 *
 * `threshold' returns the DFA cache threshold.
 *
 * `ign' is reserved for future use and should be ignored.
 *
 * `in_use' returns the number of bytes currently used by the DFA cache.
 *
 * `high_water_mark' returns the largest number of bytes ever used by the
 *  DFA cache.
 *
 * `hits' returns an indication of the number of cache hits that have
 * occured within the DFA cache.  (See below.)
 * 
 * `misses' returns an indication the number of cache misses that have
 * occured within the DFA cache. (See below.)
 * 
 * Note: The values returned in `hits' and `misses' are scaled to give
 * greater weight to recent cache activity, and reduced weight to older
 * cache activity.  It is the ratio of `hits' to `misses', not their
 * absolute values, that is interesting.
 * 
 * `total_hits' returns the exact number of cache hits that have occured
 * within the DFA cache over the lifetime of the process.
 * 
 * `total_misses' returns the exact number of cache misses that have occured
 * within the DFA cache over the lifetime of the process.
 *
 */
void
rx_dfa_cache_statistics (size_t * threshold,
			 size_t * ign,
			 size_t * in_use,
			 size_t * high_water_mark,
			 int * hits,
			 int * misses,
			 int * total_hits,
			 int * total_misses)
{
  rx__dfa_cache_statistics (threshold,
			    ign,
			    in_use,
			    high_water_mark,
			    hits,
			    misses,
			    total_hits,
			    total_misses);
}



/************************************************************************
 *(h2 "Flushing the DFA Cache")
 * 
 * |cache flushing (DFA)|
 * |DFA cache flushing|
 */


/*(c rx_flush_dfa_cache)
 * size_t rx_flush_dfa_cache ();
 * 
 * Attempt to flush all entries from the DFA cache.  If there exist
 * locked DFA states, it may not be possible to entirely empty the DFA
 * cache.  (It is not possible to create locked DFA states using only
 * the portion of the interface to Rx that is currently documented.)
 * 
 * Return the number of bytes still allocated to the DFA cache after
 * the flush.
 */
size_t
rx_flush_dfa_cache (void)
{
  rx__init_dfa_alloc_limits ();
  while (!rx__really_free_superstate ())
    ;

  return lim_in_use (rx__dfa_alloc_limits);
}