xref: /dports/devel/tla/tla-1.3.5/src/hackerlab/rx/super.c

/* super.c - lazilly constructed DFAs
 *
 ****************************************************************
 * Copyright (C) 1998, 2000 Thomas Lord
 *
 * See the file "COPYING" for further information about
 * the copyright and warranty status of this work.
 */



#include "hackerlab/bugs/panic.h"
#include "hackerlab/mem/mem.h"
#include "hackerlab/rx/bits-tree-rules.h"
#include "hackerlab/rx/dfa-cache.h"
#include "hackerlab/rx/super.h"


/* __STDC__ prototypes for static functions */
static void free_some_dfa_memory (void * ign, size_t needed);
static int rx_dfa_cache_prepare (size_t amt);
static void * rx_dfa_cache_malloc (size_t size);
static void * rx_dfa_cache_soft_malloc (size_t size);
static void rx_dfa_cache_free (void * mem);
static struct rx_superset * rx_protect_superset (struct rx_nfa * rx, struct rx_superset * set);
static void rx_release_superset (struct rx_superset *set);
static struct rx_superset * rx_superset_cons (struct rx_nfa * rx,
					      struct rx_nfa_state *car,
					      struct rx_superset *cdr);
static struct hashtree_item * superset_allocator (void * val, struct hashtree_rules * rules);
static struct rx_superset * rx_superstate_eclosure_union (struct rx_nfa * rx,
							  struct rx_superset *set,
							  struct rx_nfa_state_set *ecl) ;
static int supersetcmp (void * va, void * vb, struct hashtree_rules * rules);
static struct hashtree * super_hash_allocator (struct hashtree_rules * rules);
static void super_hash_liberator (struct hashtree * hash, struct hashtree_rules * rules);
static void superset_hash_item_liberator (struct hashtree_item * it,
					  struct hashtree_rules * rules);
static void install_cache_miss_transition (struct rx_super_edge * e);
static void semifree_superstate ();
static void refresh_semifree_superstate (struct rx_superstate * super);
static void rx_refresh_this_superstate (struct rx_superstate * superstate);
static struct rx_superstate * rx_superstate (struct rx_nfa *rx,
					     struct rx_superset *set,
					     int storage_unit_size);
static int solve_destination (struct rx_nfa * rx,
			      struct rx_inx * inx_out,
			      struct rx_super_edge * e,
			      int storage_unit_size);
static int compute_super_edge_cset (struct rx_nfa *rx,
				    bits csetout,
				    struct rx_superstate * superstate,
				    unsigned int chr);
static struct rx_super_edge * rx_super_edge (struct rx_nfa *rx, struct rx_superstate *super, bits cset);
static int install_partial_transition  (struct rx_superstate *super,
					struct rx_inx *answer,
					struct rx_super_edge * edge,
					bitset_subset set,
					int chr);


#define COPIES_32	\
  X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X


#define COPIES_64	\
  X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X, \
  X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X

#define COPIES_256 \
  X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X, \
  X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X, \
  X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X, \
  X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X, \
  X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X, \
  X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X, \
  X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X, \
  X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X

#if rx_page1_size21 == 256
#  define COPIES_PAGE1_21_SIZE  COPIES_256
#elif rx_page1_size21 == 32
#  define COPIES_PAGE1_21_SIZE  COPIES_32
#else
#  error you broke fragile code
#endif

#if rx_page2_size21 == 256
#  define COPIES_PAGE2_21_SIZE  COPIES_256
#elif rx_page2_size21 == 32
#  define COPIES_PAGE2_21_SIZE  COPIES_32
#else
#  error you broke fragile code
#endif


#if bits_per_subset == 32
#  define COPIES_BPS COPIES_32
#  define COPIES_PAGE2_SIZE X, X, X, X, X, X, X, X
#  define COPIES_PAGE3_21_SIZE X, X, X, X, X, X, X, X
#elif bits_per_subset == 64
#  define COPIES_BPS COPIES_64
#  define COPIES_PAGE2_SIZE X, X, X, X
#  define COPIES_PAGE3_21_SIZE X, X, X, X
#else
#  error "odd bits_per_subset in super.c"
#endif


/* Default value for leaf nodes of multi-level transition tables:
 */
#undef X
#define X {0, 0, (void *)rx_cache_miss, 0}
static struct rx_inx rx_shared_cache_miss_page[256] = {COPIES_256};

/* Fixed backtrack page for leaf nodes of multi-level transition tables:
 */
#undef X
#define X {0, 0, (void *)rx_backtrack, 0}
static struct rx_inx rx_shared_backtrack_page[256] = {COPIES_256};

/* Fixed value for high-surrogate leaf nodes of 16-bit tables:
 */
#undef X
#define X {0, 0, (void *)rx_huge_char, 0}
static struct rx_inx rx_huge_char_page[256] = {COPIES_256};

#ifdef RX_LARGE_TABLES

/* Default value for page2 of 21-bit tables:
 */
#undef X
#define X rx_shared_cache_miss_page
static struct rx_inx * rx_huge_char_second_level_page[rx_page2_size21] = { COPIES_256 };

/* Default value for huge_char_transitions:
 */
#undef X
#define X rx_huge_char_second_level_page
static struct rx_inx ** rx_default_huge_char_transitions[rx_page1_size21] = { COPIES_32 };

#else /* ndef RX_LARGE_TABLES */

#undef X
#define X rx_shared_cache_miss_page
static struct rx_inx * rx_default_small_table_page2[rx_page2_size] = { COPIES_PAGE2_SIZE };

#undef X
#define X rx_shared_backtrack_page
static struct rx_inx * rx_small_table_backtrack_page2[rx_page2_size] = { COPIES_PAGE2_SIZE };

#undef X
#define X rx_huge_char_page
static struct rx_inx * rx_huge_char_page2[rx_page2_size] = { COPIES_PAGE2_SIZE };


#undef X
#define X rx_shared_cache_miss_page
static struct rx_inx * rx_huge_char_third_level_page[rx_page3_size21] = { COPIES_PAGE3_21_SIZE };

#undef X
#define X rx_huge_char_third_level_page
static struct rx_inx ** rx_huge_char_second_level_page[rx_page2_size21] = { COPIES_PAGE2_21_SIZE };

#undef X
#define X rx_huge_char_second_level_page
static struct rx_inx *** rx_default_huge_char_transitions[rx_page1_size21] = { COPIES_PAGE1_21_SIZE };

#endif


/************************************************************************
 *(h0 "The Superstate DFA"
 *    :subtitle "rx/super.c"
 *    :includes ("rx/super.h"))
 *
 * It is well known that there is a mapping from non-deterministic
 * finite-state automata to equivalent deterministic finite-state
 * automata (a good text book about compiler construction explains
 * this). That mapping is important to applications which use regular
 * expressions for efficient pattern matching.  When a regular
 * expression comparison is implemented using a single pass with a
 * non-deterministic automata with `K' states, the comparison
 * algorithm may run for a number of steps which is proportional to
 * `K*N' for a length `N' input string (where each step is relatively
 * expensive).  When implemented using backtracking, `N**K'
 * (relatively inexpensive) steps may be required.  On the other hand,
 * when regular expression comparison is implemented using a
 * deterministic automata, the algorithm requires a number of
 * instructions which is linear in the length of the input string
 * (order `N' (inexpensive) steps).
 *
 * The catch is that, using brute force, it is expensive (in time and
 * space) to build a DFA from a typical regular expression NFA.  An
 * NFA with `K' states can yield a DFA with order `2^K' states.
 *
 * The trick is that, during most matches using typical regexps, only
 * a small portion of the total potential number of DFA states are
 * actually needed -- time and space can be saved by building DFA
 * states on-demand.  During any match, only two DFA states are needed
 * at a time -- if the total number of DFA states encountered during a
 * match is very large, space can be saved (at the expense of time) by
 * discarding less frequently used DFA states and reconstructing them
 * on demand.
 *
 * The functions in this chapter do the trick: they build a DFA on
 * demand, keeping a cache of frequently used states, and discarding
 * infrequently used states if the cache grows too large.
 *
 * As a result, DFA-style matching using the functions here provide
 * matching in order `N' (inexpensive) steps for most patterns (by
 * acting like a DFA match).  In the worst case (when the cache is not
 * effective), these functions provide matching in order `N*K'
 * (relatively expensive) steps (by acting like a one-pass NFA match).
 *
 */
/*(menu)
 */

/*(h1 "The DFA Virtual Machine")
 *
 * The view taken by the design of Rx is that a DFA built from a
 * regexp is a kind of program which can be interpreted by a
 * virtual machine.
 *
 * The basic operation of this machine is that it has one register: a
 * DFA state.  In each cycle, it reads one input character and
 * tries to advance to the next DFA state by looking that character up
 * in the transition table for the current state.
 *
 * The machine's outputs are the state label of the current DFA state,
 * a flag that indicates whether or not the current state has outgoing
 * edges (whether or not any input characters are valid), and a signal
 * that occurs when there is no transition for an input character.
 *
 * Implementing this virtual machine is complicated by the fact that
 * its program, the DFA, is not constructed all at once and might not
 * exist in its entirety at any one time.  The virtual machine interpreter
 * has to be able to handle the case when the next state reached after
 * some input character hasn't been built yet or has been flushed
 * from the DFA cache.
 */



/*(include-documentation "super.h")
 */

/************************************************************************
 * The Rx DFA Cache
 *
 * The DFA state cache is kept in a structure referenced through
 * the global pointer `rx_default_cache'.  In the future, this
 * may be exposed as an interface to the library: allowing separate
 * caches for regexps with different priorities.
 */

struct rx_cache;

struct rx_cache
{
  struct hashtree_rules superset_hashtree_rules;

  struct rx_superstate * lru_superstate;
  /*
   * The least recently used live superstate.  This is the next
   * superstate that will become semifree.  Superstates are linked on
   * this queue by `next_recyclable' and `prev_recyclable'.
   */

  struct rx_superstate * semifree_superstate;
  /*
   * The least recently used semifree superstate.  This is the next
   * superstate that will become completely freed.  Superstates are
   * linked on this queue by `next_recyclable' and `prev_recyclable'.
   */

  /* Allocation counts.  The number of various kinds of objects
   * currently allocated.  This is used for debugging and for tuning
   * the rate at which states are semifreed.
   */
  int hash_tables;
  int supersets;
  int super_edges;
  int superstates;
  int semifree_superstates;

  /* The ratio of cache hits to cache misses when searching for
   * superstates.  This ratio is weighted in favor of recent
   * cache probes.
   */
  int hits;
  int misses;
  int total_hits;
  int total_misses;

  /* A hash table mapping `car' and `cdr' to NFA states.
   */
  struct hashtree superset_table;
};

static struct rx_cache * rx_default_cache;


int rx_superstate_counter = 0;



/************************************************************************
 * DFA Cache Allocation
 *
 * These malloc-like functions add or subtract from the `bytes_used' field
 * of the DFA state cache.  They discard states from an over-full cache.
 */

#ifndef RX_DEFAULT_DFA_CACHE_SIZE
/* This is an upper bound on the number of bytes that may (normally)
 * be allocated for DFA states.  If this threshold would be exceeded,
 * Rx tries to flush some DFA states from the cache.
 */
#define RX_DEFAULT_DFA_CACHE_SIZE (sizeof (void *) * (1 << 16))
#endif

alloc_limits rx__dfa_alloc_limits;


static void
free_some_dfa_memory (void * ign, size_t needed)
{
  while (   (lim_in_use (rx__dfa_alloc_limits) + needed > lim_threshold (rx__dfa_alloc_limits))
	 && (0 <= rx__really_free_superstate ()))
    ;
}


void
rx__init_dfa_alloc_limits (void)
{
  static int init = 1;

  if (init)
    {
      rx__dfa_alloc_limits = make_alloc_limits ("Rx DFA cache",
						RX_DEFAULT_DFA_CACHE_SIZE,
						0,
						0,
						free_some_dfa_memory,
						0);
      init = 0;
    }
}


size_t
rx_dfa_cache_failure_pt (void)
{
  rx__init_dfa_alloc_limits ();
  return lim_failure_pt (rx__dfa_alloc_limits);
}

void
rx__dfa_cache_statistics (size_t * threshold,
			 size_t * failure_pt,
			 size_t * in_use,
			 size_t * high_water_mark,
			 int * hits,
			 int * misses,
			 int * total_hits,
			 int * total_misses)
{
  rx__init_dfa_alloc_limits ();
  if (threshold)
    *threshold = rx_dfa_cache_threshold ();
  if (failure_pt)
    *failure_pt = rx_dfa_cache_failure_pt ();
  if (in_use)
    *in_use = rx_dfa_cache_in_use ();
  if (high_water_mark)
    *high_water_mark = rx_dfa_cache_high_water_mark ();
  if (hits)
    *hits = rx_default_cache->hits;
  if (misses)
    *misses = rx_default_cache->misses;
  if (total_hits)
    *total_hits = rx_default_cache->total_hits;
  if (total_misses)
    *total_misses = rx_default_cache->total_misses;
}


void
rx_set_dfa_cache_failure_pt (size_t n)
{
  rx__init_dfa_alloc_limits ();
  lim_set_failure_pt (rx__dfa_alloc_limits, n);
}


static int
rx_dfa_cache_prepare (size_t amt)
{
  rx__init_dfa_alloc_limits ();
  return lim_prepare (rx__dfa_alloc_limits, amt);
}

/* static char * rx_dfa_cache_malloc (int size);
 *
 * Allocate memory for the DFA state cache.  If this allocation would
 * overflow the cache then this function first tries to reduce the cache
 * size by flushing old DFA statess.
 */
static void *
rx_dfa_cache_malloc (size_t size)
{
  void * answer;

  rx__init_dfa_alloc_limits ();
  answer = lim_malloc (rx__dfa_alloc_limits, size);
  return answer;
}


static void *
rx_dfa_cache_soft_malloc (size_t size)
{
  void * answer;

  rx__init_dfa_alloc_limits ();
  answer = lim_soft_malloc (rx__dfa_alloc_limits, size);
  return answer;
}


/* static void rx_dfa_cache_free (char * mem);
 *
 * Free memory for the DFA state cache.
 */
static void
rx_dfa_cache_free (void * mem)
{
  lim_free (rx__dfa_alloc_limits, mem);
}


/************************************************************************
 * The NFA State Set Cache
 *
 * Each DFA state points to a set of NFA states.  That set is stored
 * in the NFA state set cache which is part of the DFA state cache.
 *
 * These are the hash-table hook functions for the NFA state set
 * cache.
 */


/*  (c rx_protect_superset)
 * struct rx_superset * rx_protect_superset (struct rx_nfa * rx, struct rx_superset * set);
 *
 * Increment the reference count of a superset.  See xref:"struct
 * rx_superset" and xref:"rx_release_superset".
 */
static struct rx_superset *
rx_protect_superset (struct rx_nfa * rx, struct rx_superset * set)
{
  if (set)
    ++set->refs;
  return set;
}


/*  (c rx_release_superset)
 * void rx_release_superset (struct rx_superset *set);
 *
 * Decrement the reference count on a superset.  If it becomes 0,
 * then free storage used by the set.
 */
static void
rx_release_superset (struct rx_superset *set)
{
  if (set && !--set->refs)
    {
      if (set->nfa_state)
	set->nfa_state->superstate_set = 0;
      rx_release_superset (set->cdr);
      hashtree_delete (&set->hash_item, &rx_default_cache->superset_hashtree_rules);
      rx_dfa_cache_free ((char *)set);
      --rx_default_cache->supersets;
    }
}


/* This adds an element to a superstate set.  These sets are lists, such
 * that lists with == elements are ==.
 *
 *
 * on entry:
 *   	CDR has at least one reference which is taken over by this
 * 	function (becomes the reference of the set returned to its cdr)
 *
 * on exit:
 * 	set returned has one reference which is for the caller.
 */

static struct rx_superset *
rx_superset_cons (struct rx_nfa * rx,
		  struct rx_nfa_state *car,
		  struct rx_superset *cdr)
{
  struct rx_cache * cache = rx_default_cache;
  if (!car && !cdr)
    return 0;
  {
    struct rx_superset template;
    struct hashtree_item * hit;
    struct rx_superset * answer;

    template.car = car;
    template.cdr = cdr;
    template.id = rx->rx_id;

    rx_dfa_cache_prepare (4 * sizeof (struct hashtree *) + sizeof (struct rx_superset));
    hit = hashtree_store (&cache->superset_table,
			  (unsigned long)car ^ car->id ^ (unsigned long)cdr,
			  (void *)&template,
			  &cache->superset_hashtree_rules);
    if (!hit)
      return 0;
    answer = (struct rx_superset *)hit->key;
    rx_protect_superset (rx, answer);
    if (answer->refs != 1)
      rx_release_superset (cdr);
    return answer;
  }
}


#define rx_abs(A) (((A) > 0) ? (A) : -(A))

/*
 * static int superset_allocator (int * errn,
 *                                struct hashtree_item ** retv,
 *                                void * val,
 *                                struct hashtree_rules * rules);
 *
 * Hash tree allocation function for supersets.
 *
 * on entry:
 *   	CDR of `val' at least one reference which is taken over by this
 * 	function (becomes the reference of the set returned to its cdr)
 *
 * on exit:
 * 	Set returned has a reference count of 0.
 */
static struct hashtree_item *
superset_allocator (void * val, struct hashtree_rules * rules)
{
  struct rx_cache * cache;
  struct rx_superset * template;
  struct rx_superset * newset;

  cache = ((struct rx_cache *)
	   ((char *)rules
	    - (unsigned long)(&((struct rx_cache *)0)->superset_hashtree_rules)));
  template = (struct rx_superset *)val;
  newset = ((struct rx_superset *)
	    rx_dfa_cache_soft_malloc (sizeof (*template)));
  if (!newset)
    return 0;
  ++cache->supersets;

  {
    long cdrfinal;
    long cdredges;

    cdrfinal = (template->cdr ? template->cdr->state_label : 0);
    cdredges = (template->cdr ? template->cdr->has_cset_edges : 0);

    if (!template->car->state_label)
      newset->state_label = cdrfinal;
    else if (rx_abs (template->car->state_label) < rx_abs (cdrfinal))
      newset->state_label = template->car->state_label;
    else if (template->car->state_label > 0)
      newset->state_label = template->car->state_label;
    else
      newset->state_label = cdrfinal;

    newset->has_cset_edges = (template->car->has_cset_edges || cdredges);
  }

  newset->refs = 0;
  newset->id = template->id;
  newset->car = template->car;
  newset->cdr = template->cdr;
  newset->superstate[0] = 0;
  newset->superstate[1] = 0;
  newset->nfa_state = 0;
  newset->hash_item.key = (void *)newset;
  newset->hash_item.binding = 0;
  return &newset->hash_item;
}


/* This computes a union of two NFA state sets.  The sets do not have the
 * same representation though.  One is a RX_SUPERSET structure (part
 * of the superstate NFA) and the other is an NFA_STATE_SET (part of the NFA).
 *
 * On exit, `set' has at least one reference which is for the caller.
 */
static struct rx_superset *
rx_superstate_eclosure_union (struct rx_nfa * rx,
			      struct rx_superset *set,
			      struct rx_nfa_state_set *ecl)
{
  if (!ecl)
    {
      rx_protect_superset (rx, set);
      return set;
    }

  if (!set)
    return rx_superset_cons (rx, ecl->car,
			     rx_superstate_eclosure_union (rx, 0, ecl->cdr));

  if (set->car == ecl->car)
    return rx_superstate_eclosure_union (rx, set, ecl->cdr);

  {
    struct rx_superset * tail;
    struct rx_nfa_state * first;

    if (set->car->id < ecl->car->id)
      {
	tail = rx_superstate_eclosure_union (rx, set->cdr, ecl);
	if (!tail)
	  return 0;
	first = set->car;
      }
    else
      {
	tail = rx_superstate_eclosure_union (rx, set, ecl->cdr);
	if (!tail)
	  return 0;
	first = ecl->car;
      }

    {
      struct rx_superset * answer;
      answer = rx_superset_cons (rx, first, tail);
      if (!answer)
	{
	  rx_release_superset (tail);
	  return 0;
	}
      return answer;
    }
  }
}


static int
supersetcmp (void * va, void * vb, struct hashtree_rules * rules)
{
  struct rx_superset * a = (struct rx_superset *)va;
  struct rx_superset * b = (struct rx_superset *)vb;

  a = (struct rx_superset *)va;
  b = (struct rx_superset *)vb;
  return (   (a == b)
	  || (   a
	      && b
	      && (a->id == b->id)
	      && (a->car == b->car)
	      && (a->cdr == b->cdr)));
}


static struct hashtree *
super_hash_allocator (struct hashtree_rules * rules)
{
  struct rx_cache * cache;
  struct hashtree * it;

  cache = ((struct rx_cache *)
	   ((char *)rules
	    - (unsigned long)(&((struct rx_cache *)0)->superset_hashtree_rules)));
  it = ((struct hashtree *)
 	rx_dfa_cache_soft_malloc (sizeof (struct hashtree)));
  if (!it)
    return 0;
  ++cache->hash_tables;
  return it;
}


static void
super_hash_liberator (struct hashtree * hash, struct hashtree_rules * rules)
{
  rx_dfa_cache_free ((char *)hash);
  --rx_default_cache->hash_tables;
}

static void
superset_hash_item_liberator (struct hashtree_item * it,
			      struct hashtree_rules * rules)
{
}


/************************************************************************
 * The Default DFA State Cache
 *
 *
 *
 */

static struct rx_cache default_cache =
{
  {
    supersetcmp,
    super_hash_allocator,
    super_hash_liberator,
    superset_allocator,
    superset_hash_item_liberator,
  },
  0,				/* lru_superstate */
  0,				/* semifree_superstate */
  0,				/* hash_tables */
  0,				/* super_edges */
  0,				/* supersets */
  0,				/* superstates */
  0,				/* semifree_superstates */
  0,				/* hits */
  0,				/* misses */
  0,				/* total hits */
  0,				/* total misses */
  {				/* hash table */
    0,
    0,
    0,
    {0}
  }
};


static struct rx_cache * rx_default_cache = &default_cache;

/************************************************************************
 * Making DFA States Semifree and Restoring Them to Live State
 *
 */

/* static void install_cache_miss_transition (struct rx_super_edge * e);
 *
 * Install the instruction `answer' in the transition table of `super'
 * for all instructions built for `e'.
 */
static void
install_cache_miss_transition (struct rx_super_edge * e)
{
  struct rx_inx * transitions;

  transitions = e->inx_list;
  while (transitions)
    {
      transitions->inx = (void *)rx_cache_miss;
      transitions->data = 0;
      transitions->data_2 = (void *)e;
      transitions = transitions->next_same_edge;
    }

  e->inx_list = 0;
}


/* static void semifree_superstate ();
 *
 * Select the most recently used live superstate that is not locked and
 * make it semifree.
 *
 * This function makes all incoming instruction frames cache miss
 * instructions.  It moves the state from the `lru_superstate' queue
 * of the cache to the `semifree_superstate' queue.
 */
static void
semifree_superstate ()
{
  struct rx_cache * cache = rx_default_cache;
  int disqualified;

  disqualified = cache->semifree_superstates;
  if (disqualified == cache->superstates)
    return;

  while (cache->lru_superstate->locks)
    {
      cache->lru_superstate = cache->lru_superstate->next_recyclable;
      ++disqualified;
      if (disqualified == cache->superstates)
	return;
    }

  {
    struct rx_superstate * it;

    it = cache->lru_superstate;
    it->next_recyclable->prev_recyclable = it->prev_recyclable;
    it->prev_recyclable->next_recyclable = it->next_recyclable;

    cache->lru_superstate = (it == it->next_recyclable
			     ? 0
			     : it->next_recyclable);

    if (!cache->semifree_superstate)
      {
	cache->semifree_superstate = it;
	it->next_recyclable = it;
	it->prev_recyclable = it;
      }
    else
      {
	it->prev_recyclable = cache->semifree_superstate->prev_recyclable;
	it->next_recyclable = cache->semifree_superstate;
	it->prev_recyclable->next_recyclable = it;
	it->next_recyclable->prev_recyclable = it;
      }
    {
      struct rx_super_edge *e;

      it->is_semifree = 1;
      ++cache->semifree_superstates;

      e = it->incoming_edges;
      if (e)
	{
	  e->prev_same_dest->next_same_dest = 0;
	  while (e)
	    {
	      install_cache_miss_transition (e);
	      e = e->next_same_dest;
	    }
	  e = it->incoming_edges;
	  e->prev_same_dest->next_same_dest = e;
	}
    }
  }
}


/* static void refresh_semifree_superstate (struct rx_superstate * super);
 *
 * Make `super', which may or may not be in a semifree state, a live
 * superstate.
 *
 * This moves the state to the back of the `lru_superstate' queue.
 */
static void
refresh_semifree_superstate (struct rx_superstate * super)
{
  struct rx_cache * cache = rx_default_cache;

  if (cache->semifree_superstate == super)
    cache->semifree_superstate = (super->prev_recyclable == super
				  ? 0
				  : super->prev_recyclable);
  else if (cache->lru_superstate == super)
    cache->lru_superstate = (super->prev_recyclable == super
			     ? 0
			     : super->prev_recyclable);

  super->next_recyclable->prev_recyclable = super->prev_recyclable;
  super->prev_recyclable->next_recyclable = super->next_recyclable;

  if (!cache->lru_superstate)
    (cache->lru_superstate
     = super->next_recyclable
     = super->prev_recyclable
     = super);
  else
    {
      super->next_recyclable = cache->lru_superstate;
      super->prev_recyclable = cache->lru_superstate->prev_recyclable;
      super->next_recyclable->prev_recyclable = super;
      super->prev_recyclable->next_recyclable = super;
    }
  if (super->is_semifree)
    {
      super->is_semifree = 0;
      --cache->semifree_superstates;
    }
}



/* void rx_refresh_this_superstate (struct rx_superstate * superstate);
 *
 * If this state is semifree, pass it to `refresh_semifree_superstate'.
 * Otherwise, move this state to the rear of the `lru_superstate' queue.
 */
static void
rx_refresh_this_superstate (struct rx_superstate * superstate)
{
  struct rx_cache * cache = rx_default_cache;
  if (superstate->is_semifree)
    refresh_semifree_superstate (superstate);
  else if (cache->lru_superstate == superstate)
    cache->lru_superstate = superstate->next_recyclable;
  else if (superstate != cache->lru_superstate->prev_recyclable)
    {
      superstate->next_recyclable->prev_recyclable
	= superstate->prev_recyclable;
      superstate->prev_recyclable->next_recyclable
	= superstate->next_recyclable;
      superstate->next_recyclable = cache->lru_superstate;
      superstate->prev_recyclable = cache->lru_superstate->prev_recyclable;
      superstate->next_recyclable->prev_recyclable = superstate;
      superstate->prev_recyclable->next_recyclable = superstate;
    }
}


/************************************************************************
 * Really Freeing DFA States
 *
 * After becoming semifree, a DFA state may eventually be freed for
 * real -- meaning that the memory it occupies is recycled.
 *
 */

/* This tries to add a new superstate to the superstate freelist.
 * It might, as a result, free some edge pieces or hash tables.
 * If nothing can be freed because too many locks are being held, fail.
 */

/* int rx__really_free_superstate ();
 *
 * Attempt to reduce memory usage of the DFA state cache by truly
 * freeing one superstate.  Return -1 if no state could be freed, 0
 * otherwise.
 */
int
rx__really_free_superstate (void)
{
  struct rx_cache * cache = rx_default_cache;
  struct rx_superstate * it;

  if (!cache->superstates)
    return -1;

  /* If the rate of cache misses is high, we semifree superstates at a
   * rate proportional to our need to truly free states, but greater.
   * That way the total amount of work done freeing states remains
   * proportional to the work needed, but a spike in demand for memory
   * will cause a larger spike in the amount of effort put into
   * rescuing the most desirable states in the cache.
   *
   * For example, as this is written, when the cache miss rate is
   * high, states are semifreed at a rate 3x the rate at which they
   * are truly freed.  If, after a period of running mostly out of the
   * cache, we suddenly have to free 1/3 of the states in the cache to
   * make room for new states, the remaining 2/3 of the old states
   * will all have been marked semifree and thus the most useful of
   * those states will have a high probability of being rescued even
   * if the demand for memory continues.  They will have a fighting
   * chance against those new states which were needed once but which
   * aren't otherwise very useful.
   *
   * We semifree states at this accelerated rate when the cache miss
   * rate is high because in that case, we expect the cache miss rate
   * to remain high, and so we expect the high demand on memory to
   * continue.
   *
   * When the cache miss rate is low, we look at the number of
   * semifree states compared to the total number of states.  If that
   * ratio is low (there aren't many semifree states), then we again
   * semifree states at an accelerated rate.  If that ratio is high
   * (there are quite a few semifree states), then we only semifree
   * one state for every state truly freed.  The idea is that a low
   * cache miss rate predicts a low demand on memory.  When demand on
   * memory is low, we want to maintain a constant sized queue of
   * semifree states which is a fraction of the total number of
   * states.  The existence of that queue helps us from throwing away
   * useful DFA states while demand on memory is low while the fixed
   * size of that queue means that the overhead of maintaining it is a
   * small constant multiple of the time spent truly freeing states.
   */
  if (   (cache->misses < cache->hits)
      || (3 * cache->semifree_superstates >= cache->superstates))
    semifree_superstate (cache);
  else
    {
      semifree_superstate (cache);
      semifree_superstate (cache);
      semifree_superstate (cache);
    }


  /* At this point, if no states are semifree, then all states are
   * locked and no states can be freed.
   */
  if (!cache->semifree_superstate)
    return -1;

  /* Remove the oldest semifree state from the queue of all semifree
   * states.  Correct the counters that count DFA states.
   */
  {
    it = cache->semifree_superstate;
    it->next_recyclable->prev_recyclable = it->prev_recyclable;
    it->prev_recyclable->next_recyclable = it->next_recyclable;
    cache->semifree_superstate = ((it == it->next_recyclable)
				  ? 0
				  : it->next_recyclable);
    --cache->semifree_superstates;
    --cache->superstates;
  }


  /* Unlink the queue of incoming edges and clear the `future' field
   * of those edges which otherwise points to this state.
   */
  if (it->incoming_edges)
    {
      struct rx_super_edge * e;
      it->incoming_edges->prev_same_dest->next_same_dest = 0;
      e = it->incoming_edges;
      while (e)
	{
	  struct rx_super_edge * et;
	  et = e;
	  e = e->next_same_dest;
	  et->prev_same_dest = et->next_same_dest = 0;
	  et->future = 0;
	}
    }


  /* Free all outgoing edges and remove them from the `incoming_edges'
   * queue of their destination states.
   */
  {
    struct rx_super_edge *tc;
    tc = it->outgoing_edges;
    while (tc)
      {
	struct rx_super_edge *tct;

	tct = tc;
	tc = tc->next_same_present;

	if (tct->future)
	  {
	    if (tct->future->incoming_edges == tct)
	      {
		tct->future->incoming_edges = tct->next_same_dest;
		if (tct->future->incoming_edges == tct)
		  tct->future->incoming_edges = 0;
	      }
	    tct->next_same_dest->prev_same_dest = tct->prev_same_dest;
	    tct->prev_same_dest->next_same_dest = tct->next_same_dest;
	  }
	bits_free (tct->cset);
	rx_dfa_cache_free ((char *)tct);
	--cache->super_edges;
      }
  }

#ifdef RX_LARGE_TABLES
  {
    /* free second level transition tables */
    if (it->storage_unit_size == 2)
      {
	int x;

	for (x = 0; x < 256; ++x)
	  {
	    if (   (((struct rx_inx **)it->transitions)[x] != rx_shared_cache_miss_page)
		&& (((struct rx_inx **)it->transitions)[x] != rx_shared_backtrack_page)
		&& (((struct rx_inx **)it->transitions)[x] != rx_huge_char_page))
	      rx_dfa_cache_free ((void *)((struct rx_inx **)it->transitions)[x]);
	  }
      }
  }
#else
  {
    /* free second level transition tables */
    if (it->storage_unit_size == 2)
      {
	int x;

	for (x = 0; x < 256; ++x)
	  {
	    if (   (((struct rx_inx ***)it->transitions)[x] != rx_default_small_table_page2)
		&& (((struct rx_inx ***)it->transitions)[x] != rx_small_table_backtrack_page2)
		&& (((struct rx_inx ***)it->transitions)[x] != rx_huge_char_page2))
	      {
		int y;
		struct rx_inx ** page2;

		page2 = ((struct rx_inx ***)it->transitions)[x];
		for (y = 0; y < rx_page2_size; ++y)
		  {
		    if (page2[y] != rx_shared_cache_miss_page)
		      {
			rx_dfa_cache_free ((void *)page2[y]);
		      }
		  }
		rx_dfa_cache_free ((void *)page2);
	      }
	  }
      }
  }
#endif

  if (it->huge_char_transitions != rx_default_huge_char_transitions)
    {
      int x;

#ifdef RX_LARGE_TABLES
      for (x = 0; x < rx_page1_size21; ++x)
	{
	  struct rx_inx ** sub;

	  sub = it->huge_char_transitions[x];
	  if (sub != rx_huge_char_second_level_page)
	    {
	      int z;

	      for (z = 0; z < rx_page2_size21; ++z)
		{
		  struct rx_inx * leaf;

		  leaf = sub[z];
		  if (leaf != rx_shared_cache_miss_page)
		    rx_dfa_cache_free ((void *)leaf);
		}
	      rx_dfa_cache_free ((void *)sub);
	    }
	}
#else
      for (x = 0; x < rx_page1_size21; ++x)
	{
	  struct rx_inx *** sub;

	  sub = it->huge_char_transitions[x];
	  if (sub != rx_huge_char_second_level_page)
	    {
	      int z;

	      for (z = 0; z < rx_page2_size21; ++z)
		{
		  struct rx_inx ** subsub;

		  subsub = sub[z];

		  if (subsub != rx_huge_char_third_level_page)
		    {
		      int zz;

		      for (zz = 0; zz < rx_page3_size21; ++zz)
			{
			  struct rx_inx * leaf;

			  leaf = subsub[zz];
			  if (leaf != rx_shared_cache_miss_page)
			    rx_dfa_cache_free ((void *)leaf);
			}
		      rx_dfa_cache_free ((void *)subsub);
		    }
		}
	      rx_dfa_cache_free ((void *)sub);
	    }
	}
#endif
      rx_dfa_cache_free ((void *)it->huge_char_transitions);
    }

  /* Clear the pointer to this state in the NFA set of this state.
   */
  if (it->members->superstate[0] == it)
    it->members->superstate[0] = 0;
  if (it->members->superstate[1] == it)
    it->members->superstate[1] = 0;

  /* Release the NFA set.
   */
  rx_release_superset (it->members);

  /* Free the memory of this DFA state.
   */
  rx_dfa_cache_free ((char *)it);

  return 0;
}


/************************************************************************
 *(h1 "Building DFA States")
 *
 *
 *
 */

/* struct rx_superstate * rx_superstate (struct rx_nfa *rx,
 *					 struct rx_superset *set,
 *					 int storage_unit_size);
 *
 * Retrieve a DFA state from the cache or construct a new state for a
 * give NFA state set.
 *
 * This may cause old states to be flushed from the DFA state cache.
 */
static struct rx_superstate *
rx_superstate (struct rx_nfa *rx,
	       struct rx_superset *set,
	       int storage_unit_size)
{
  struct rx_cache * cache;
  struct rx_superstate * superstate;
  int has_huge_table;

  has_huge_table = 0;

  if (rx->local_cset_size == 256)
    has_huge_table = 0;
  else if (rx->local_cset_size == (1 << 21))
    has_huge_table = 1;
  else
    panic ("odd sized cset in rx_superstate");

  cache = rx_default_cache;
  superstate = 0;

  /* Does the superstate already exist in the cache? */
  if (set->superstate[storage_unit_size - 1])
    {
      ++cache->hits;
      ++cache->total_hits;
      while ((cache->hits + cache->misses) > 256)
	{
	  cache->hits >>= 1;
	  cache->misses >>= 1;
	}

      superstate = set->superstate[storage_unit_size - 1];
      rx_refresh_this_superstate (superstate);
      return superstate;
    }


  /* This point reached only for cache misses. */
  ++cache->misses;
  ++cache->total_misses;
  while ((cache->hits + cache->misses) > 256)
    {
      cache->hits >>= 1;
      cache->misses >>= 1;
    }


  if (!has_huge_table)
    {
      int superstate_size;
      superstate_size = (sizeof (*superstate) + (sizeof (struct rx_inx) * 256));
      superstate = ((struct rx_superstate *) rx_dfa_cache_malloc (superstate_size));

      if (!superstate)
	return 0;

      superstate->storage_unit_size = storage_unit_size;
      superstate->has_huge_table = 0;

      mem_set0 ((void *)&superstate->transitions, sizeof (rx_shared_cache_miss_page));
      /* mem_move ((void *)&superstate->transitions, (void *)rx_shared_cache_miss_page, sizeof (rx_shared_cache_miss_page)); */
    }
  else
    {
      int x;
      int superstate_size;

      superstate_size = 0;

      if (storage_unit_size == 2)
	superstate_size = (sizeof (*superstate) + (sizeof (struct rx_inx *) * 256));
      else if (storage_unit_size == 1)
	superstate_size = (sizeof (*superstate) + (sizeof (struct rx_inx) * 256));
      else
	panic ("odd storage unit size in rx_superstate");

      superstate = ((struct rx_superstate *) rx_dfa_cache_malloc (superstate_size));
      if (!superstate)
	return 0;

      superstate->storage_unit_size = storage_unit_size;
      superstate->has_huge_table = 1;

      if (storage_unit_size == 2)
	{
#ifdef RX_LARGE_TABLES
	  {
	    for (x = 0; x < 0xd8; ++x)
	      ((struct rx_inx **)superstate->transitions)[x] = rx_shared_cache_miss_page;
	    for (x = 0xd8; x < 0xdc; ++x)
	      ((struct rx_inx **)superstate->transitions)[x] = rx_huge_char_page;
	    for (x = 0xdc; x < 0xe0; ++x)
	      ((struct rx_inx **)superstate->transitions)[x] = rx_shared_backtrack_page;
	    for (x = 0xe0; x < 256; ++x)
	      ((struct rx_inx **)superstate->transitions)[x] = rx_shared_cache_miss_page;
	  }
#else
	  {
	    for (x = 0; x < 0xd8; ++x)
	      ((struct rx_inx ***)superstate->transitions)[x] = rx_default_small_table_page2;
	    for (x = 0xd8; x < 0xdc; ++x)
	      ((struct rx_inx ***)superstate->transitions)[x] = rx_huge_char_page2;
	    for (x = 0xdc; x < 0xe0; ++x)
	      ((struct rx_inx ***)superstate->transitions)[x] = rx_small_table_backtrack_page2;
	    for (x = 0xe0; x < 256; ++x)
	      ((struct rx_inx ***)superstate->transitions)[x] = rx_default_small_table_page2;
	  }
#endif
	}
      else if (storage_unit_size == 1)
	{
	  mem_move ((void *)&superstate->transitions, (void *)rx_shared_cache_miss_page, 128 * sizeof (struct rx_inx));

	  /* no valid multi-byte encodings begin with 80..c1
	   */
	  for (x = 0x80; x < 0xc2; ++x)
	    {
	      ((struct rx_inx *)&superstate->transitions)[x].data = (void *)0;
	      ((struct rx_inx *)&superstate->transitions)[x].data_2 = (void *)0;
	      ((struct rx_inx *)&superstate->transitions)[x].inx = (void *)rx_bogus_utf8;
	      ((struct rx_inx *)&superstate->transitions)[x].next_same_edge = (struct rx_inx *)0;
	    }
	  /* valid 2 byte encodings begin with c2..df
	   */
	  for (x = 0xc2; x < 0xe0; ++x)
	    {
	      ((struct rx_inx *)&superstate->transitions)[x].data = (void *)0;
	      ((struct rx_inx *)&superstate->transitions)[x].data_2 = (void *)0;
	      ((struct rx_inx *)&superstate->transitions)[x].inx = (void *)rx_2byte_utf8;
	      ((struct rx_inx *)&superstate->transitions)[x].next_same_edge = (struct rx_inx *)0;
	    }
	  /* valid 3 byte encodings begin with e0..ef
	   */
	  for (x = 0xe0; x < 0xf0; ++x)
	    {
	      ((struct rx_inx *)&superstate->transitions)[x].data = (void *)0;
	      ((struct rx_inx *)&superstate->transitions)[x].data_2 = (void *)0;
	      ((struct rx_inx *)&superstate->transitions)[x].inx = (void *)rx_3byte_utf8;
	      ((struct rx_inx *)&superstate->transitions)[x].next_same_edge = (struct rx_inx *)0;
	    }
	  /* valid 4 byte encodings begin with f0..f4
	   */
	  for (x = 0xf0; x < 0xf5; ++x)
	    {
	      ((struct rx_inx *)&superstate->transitions)[x].data = (void *)0;
	      ((struct rx_inx *)&superstate->transitions)[x].data_2 = (void *)0;
	      ((struct rx_inx *)&superstate->transitions)[x].inx = (void *)rx_4byte_utf8;
	      ((struct rx_inx *)&superstate->transitions)[x].next_same_edge = (struct rx_inx *)0;
	    }
	  /* no valid multi-byte encodings begin with f5..ff
	   */
	  for (x = 0xf5; x <= 0xff; ++x)
	    {
	      ((struct rx_inx *)&superstate->transitions)[x].data = (void *)0;
	      ((struct rx_inx *)&superstate->transitions)[x].data_2 = (void *)0;
	      ((struct rx_inx *)&superstate->transitions)[x].inx = (void *)rx_bogus_utf8;
	      ((struct rx_inx *)&superstate->transitions)[x].next_same_edge = (struct rx_inx *)0;
	    }
	}
      else
	panic ("odd storage unit size in rx_superstate");
    }

  superstate->huge_char_transitions = rx_default_huge_char_transitions;
  ++cache->superstates;
  superstate->seq = rx_superstate_counter++;
  superstate->table_id = -1;

  if (!cache->lru_superstate)
    (cache->lru_superstate
     = superstate->next_recyclable
     = superstate->prev_recyclable
     = superstate);
  else
    {
      superstate->next_recyclable = cache->lru_superstate;
      superstate->prev_recyclable = cache->lru_superstate->prev_recyclable;
      (  superstate->prev_recyclable->next_recyclable
       = superstate->next_recyclable->prev_recyclable
       = superstate);
    }
  superstate->outgoing_edges = 0;
  superstate->incoming_edges = 0;
  superstate->members = set;
  set->superstate[storage_unit_size - 1] = superstate;
  rx_protect_superset (rx, set);
  superstate->is_semifree = 0;
  superstate->rx_id = rx->rx_id;
  superstate->locks = 0;
  return superstate;
}


/*(c rx_nfa_state_to_superstate)
 * struct rx_superstate *
 * rx_nfa_state_to_superstate (struct rx_nfa * rx,
 *			       struct rx_nfa_state * nfa_state,
 * 			       int storage_unit_size);
 *
 * Construct the DFA state whose NFA state set is the epsilon closure
 * of `nfa_state' in the NFA `rx'.  Return that superstate, with no
 * new locks applied to it.
 */
struct rx_superstate *
rx_nfa_state_to_superstate (struct rx_nfa * rx,
			    struct rx_nfa_state * nfa_state,
			    int storage_unit_size)
{
  struct rx_nfa_state_set * epsilon_closure;
  struct rx_superset * contents;
  struct rx_superstate * answer;

  /* Compute the superstate set for this NFA state and
   * aquire a reference count for it.
   *
   * Ensure that a reference to this set is cached in
   * the NFA state.
   */
  if (nfa_state->superstate_set)
    {
      contents = nfa_state->superstate_set;
      rx_protect_superset (rx, contents);
    }
  else
    {
      epsilon_closure = rx_state_closure (rx, nfa_state);
      if (!epsilon_closure)
	return 0;

      contents = rx_superstate_eclosure_union (rx,
					       0,
					       epsilon_closure);
      if (!contents)
	return 0;

      /* rx_superstate_eclosure_union gives us a reference count
       */
      nfa_state->superstate_set = contents;
      contents->nfa_state = nfa_state;
    }

  /* Aquire a superstate for this superstate_set and drop
   * the reference count on the set.
   */
  if (   contents->superstate[storage_unit_size - 1]
      && (contents->superstate[storage_unit_size - 1]->rx_id == rx->rx_id))
    {
      answer = contents->superstate[storage_unit_size - 1];
      /* Treat this as a cache hit that contributes longevity
       * to the cache entry and that turns a semifree state
       * into a live state:
       */
      rx_refresh_this_superstate (answer);
      rx_release_superset (contents);
      return answer;
    }
  else
    {
      answer = rx_superstate (rx, contents, storage_unit_size);
      rx_release_superset (contents);
      return answer;		/* might be 0 */
    }
}




/* void rx_clear_superstate_table_ids (struct rx_nfa * nfa);
 *
 * SHOULD BE VOID?
 */
void
rx_clear_superstate_table_ids (struct rx_nfa * nfa)
{
  struct rx_superstate * qs[2];
  int x;

  qs[0] = rx_default_cache->semifree_superstate;
  qs[1] = rx_default_cache->lru_superstate;
  for (x = 0; x < 2; ++x)
    {
      struct rx_superstate * q;
      struct rx_superstate * it;

      q = qs[x];
      it = q;
      if (q)
	do
	  {
	    it->table_id = -1;
	    it = it->next_recyclable;
	  }
	while (it != q);
    }
}


/************************************************************************
 * Low Level Support for Handling Cache Misses in the Dfa State Cache
 *
 *
 */

/*(c solve_destination)
 * static void solve_destination (struct rx_nfa * rx,
 *                                struct rx_inx * inx_out,
 *                                struct rx_super_edge * e,
 *                                int storage_unit_size);
 *
 * Compute the destination state for DFA edge `e'.
 *
 * As a side effect, set the `future' field of `e'.
 *
 * Return an `rx_next_char' instruction frame in `inx_out'.  The
 * `data' field of the instruction will point to the destination
 * state.  This instruction can be copied into transition table
 * entries for edge `e'.
 */
static int
solve_destination (struct rx_nfa * rx,
		   struct rx_inx * inx_out,
		   struct rx_super_edge * e,
		   int storage_unit_size)
{
  struct rx_superset * nfa_state;
  struct rx_superset * solution;
  struct rx_superstate *dest;

  if (e->is_backtrack)
    {
      inx_out->inx = (void *) rx_backtrack;
      inx_out->data = 0;
      inx_out->data_2 = 0;
      return 0;
    }

  solution = 0;

  /* Iterate over all NFA states in the state set of this superstate. */
  for (nfa_state = e->present->members; nfa_state; nfa_state = nfa_state->cdr)
    {
      struct rx_nfa_edge * ne;

      /* Iterate over all edges of each NFA state. */
      for (ne = nfa_state->car->edges; ne; ne = ne->next)

        /* If we find an edge that is labeled with
	 * the characters we are solving for.....
	 */
	if ((ne->type == ne_cset) && bits_is_subset (ne->cset, e->cset))
	  {
	    struct rx_nfa_state * n;
	    struct rx_superset * old_sol;

	    n = ne->dest;
	    old_sol = solution;
	    {
	      struct rx_nfa_state_set * set;
	      set = rx_state_closure (rx, n);

	      if (!set)
		{
		  rx_release_superset (old_sol);
		  return -1;
		}

	      solution = rx_superstate_eclosure_union (rx, solution, set);

	      if (!solution)
		{
		  rx_release_superset (old_sol);
		  return -1;
		}
	    }
	    rx_release_superset (old_sol);
	  }
    }

  if (solution == 0)
    {
      e->is_backtrack = 1;
      inx_out->inx = (void *) rx_backtrack;
      inx_out->data = 0;
      inx_out->data_2 = 0;
      return 0;
    }

  dest = rx_superstate (rx, solution, storage_unit_size);
  rx_release_superset (solution);
  if (!dest)
    return -1;
  e->future = dest;

  if (!dest->incoming_edges)
    {
      dest->incoming_edges = e;
      e->next_same_dest = e->prev_same_dest = e;
    }
  else
    {
      e->next_same_dest = dest->incoming_edges;
      e->prev_same_dest = dest->incoming_edges->prev_same_dest;
      e->next_same_dest->prev_same_dest = e;
      e->prev_same_dest->next_same_dest = e;
    }
  inx_out->data = (void *)&dest->transitions;
  inx_out->data_2 = (void *) dest->members->state_label;
  inx_out->inx = (void *) rx_next_char;
  return 0;
}


/* static int compute_super_edge_cset (struct rx_nfa *rx,
 *				       bits csetout,
 *				       struct rx_superstate * superstate,
 *				       t_uchar chr);
 *
 * For DFA state `superstate' and character `chr', compute a character
 * set which is the label of the DFA edge defining transitions out of
 * `superstate' on input character `chr'.
 *
 * This character set can then be used to compute the NFA state set of
 * the destination state of the transition.  See `solve_destination'.
 *
 * 0 == backtrack
 * n > 0 == n_nfa_edges
 * n < 0 == ESPACE
 */
static int
compute_super_edge_cset (struct rx_nfa *rx,
			 bits csetout,
			 struct rx_superstate * superstate,
			 unsigned int chr)
{
  int n_nfa_edges;
  struct rx_superset * stateset;

  stateset = superstate->members;

  if (bits_fill (csetout))
    return -1;

  n_nfa_edges = 0;
  while (stateset)
    {
      struct rx_nfa_edge *e;

      for (e = stateset->car->edges; e; e = e->next)
	if (e->type == ne_cset)
	  {
	    if (!bits_is_member (e->cset, chr))
	      {
		if (bits_difference (csetout, e->cset))
		  return -1;
	      }
	    else
	      {
		if (bits_intersection (csetout, e->cset))
		  return -1;
	      }
	    ++n_nfa_edges;
	  }
      stateset = stateset->cdr;
    }
  return n_nfa_edges;
}


/* static struct rx_super_edge * rx_super_edge (struct rx_nfa *rx, struct rx_superstate *super, bits cset);
 *
 * Construct a new DFA edge, originating in state `super', and
 * defining transitions for characters in `cset'.
 */
static struct rx_super_edge *
rx_super_edge (struct rx_nfa *rx, struct rx_superstate *super, bits cset)
{
  struct rx_super_edge *tc;

  tc = ((struct rx_super_edge *) rx_dfa_cache_malloc (sizeof (struct rx_super_edge)));
  if (!tc)
    return 0;
  mem_set0 ((void *)tc, sizeof (struct rx_super_edge));
  ++rx_default_cache->super_edges;
  tc->next_same_present = super->outgoing_edges;
  super->outgoing_edges = tc;
  tc->cset = cset;
  tc->present = super;
  tc->inx_list = 0;
  tc->is_backtrack = 0;
  return tc;
}



/* static void install_partial_transition (struct rx_superstate *super,
 *					   struct rx_inx *answer,
 *					   struct rx_super_edge * edge,
 *					   bitset_subset set,
 *					   int offset);
 *
 * Fill in entries in the transition table of `super'.
 *
 * Entry `N' is filled if `N' is in the range:
 *
 *	offset .. offset + bits_per_subset
 *
 * and:
 *
 *	 set & (1 << (N - offset))
 *
 * is not 0.
 *
 * Filled entries are filled with a copy of `*answer'.
 *
 * This function is useful when handling a cache miss.  It is
 * expensive to fill in the entire transition table and often, only a
 * few entries in a narrow range (such as lower case letters) will
 * every be needed.  When a missing entry is discovered, we fill in
 * only a narrow region of the table around the missing entry.
 */
static int
install_partial_transition  (struct rx_superstate *super,
			     struct rx_inx *answer,
			     struct rx_super_edge * edge,
			     bitset_subset set,
			     int chr)
{
  int x;
  bitset_subset pos;
  struct rx_inx * inxs;

  if (!super->has_huge_table || ((super->storage_unit_size == 1) && (chr < 0x80)))
    inxs = rx_subset_transitions8 (super->transitions, chr);
  else
    {
      if ((super->storage_unit_size == 1) || (chr > 0xffff))
	{

#ifdef RX_LARGE_TABLES
	  {
	    struct rx_inx ** page2_21;
	    struct rx_inx * page3_21;
	    if (super->huge_char_transitions == rx_default_huge_char_transitions)
	      {
		struct rx_inx *** ht;
		ht = (struct rx_inx ***)rx_dfa_cache_malloc (rx_page1_size21 * sizeof (struct rx_inx **));
		if (!ht)
		  return -1;
		super->huge_char_transitions = ht;
		mem_move ((t_uchar *)super->huge_char_transitions, (t_uchar *)rx_default_huge_char_transitions, sizeof (rx_default_huge_char_transitions));
	      }

	    page2_21 = rx_page2_21 (super->huge_char_transitions, chr);

	    if (page2_21 == rx_huge_char_second_level_page)
	      {
		page2_21 = (struct rx_inx **)rx_dfa_cache_malloc (rx_page2_size21 * sizeof (struct rx_inx *));
		if (!page2_21)
		  return -1;
		mem_move ((t_uchar *)page2_21, (t_uchar *)rx_huge_char_second_level_page, rx_page2_size21 * sizeof (struct rx_inx *));
		rx_page2_21 (super->huge_char_transitions, chr) = page2_21;
	      }

	    page3_21 = rx_page3_21 (super->huge_char_transitions, chr);

	    if (page3_21 == rx_shared_cache_miss_page)
	      {
		page3_21 = (struct rx_inx *)rx_dfa_cache_malloc (256 * sizeof (struct rx_inx));
		if (!page3_21)
		  return -1;
		mem_move ((t_uchar *)page3_21, (t_uchar *)rx_shared_cache_miss_page, 256 * sizeof (struct rx_inx));
		rx_page3_21(super->huge_char_transitions, chr) = page3_21;
	      }
	  }
#else
	  {
	    struct rx_inx ***  page2_21;
	    struct rx_inx ** page3_21;
	    struct rx_inx * page4_21;

	    if (super->huge_char_transitions == rx_default_huge_char_transitions)
	      {
		struct rx_inx **** ht;
		ht = (struct rx_inx ****)rx_dfa_cache_malloc (rx_page1_size21 * sizeof (struct rx_inx ***));
		if (!ht)
		  return -1;
		super->huge_char_transitions = ht;
		mem_move ((t_uchar *)super->huge_char_transitions, (t_uchar *)rx_default_huge_char_transitions, sizeof (rx_default_huge_char_transitions));
	      }

	    page2_21 = rx_page2_21 (super->huge_char_transitions, chr);

	    if (page2_21 == rx_huge_char_second_level_page)
	      {
		page2_21 = (struct rx_inx ***)rx_dfa_cache_malloc (rx_page2_size21 * sizeof (struct rx_inx **));
		if (!page2_21)
		  return -1;
		mem_move ((t_uchar *)page2_21, (t_uchar *)rx_huge_char_second_level_page, rx_page2_size21 * sizeof (struct rx_inx **));
		rx_page2_21 (super->huge_char_transitions, chr) = page2_21;
	      }

	    page3_21 = rx_page3_21 (super->huge_char_transitions, chr);

	    if (page3_21 == rx_huge_char_third_level_page)
	      {
		page3_21 = (struct rx_inx **)rx_dfa_cache_malloc (rx_page3_size21 * sizeof (struct rx_inx *));
		if (!page3_21)
		  return -1;
		mem_move ((t_uchar *)page3_21, (t_uchar *)rx_huge_char_third_level_page, rx_page3_size21 * sizeof (struct rx_inx *));
		rx_page3_21(super->huge_char_transitions, chr) = page3_21;
	      }

	    page4_21 = rx_page4_21 (super->huge_char_transitions, chr);
	    if (page4_21 == rx_shared_cache_miss_page)
	      {
		page4_21 = (struct rx_inx *)rx_dfa_cache_malloc (rx_page4_size21 * sizeof (struct rx_inx));
		if (!page4_21)
		  return -1;
		mem_move ((t_uchar *)page4_21, (t_uchar *)rx_shared_cache_miss_page, rx_page4_size21 * sizeof (struct rx_inx));
		rx_page4_21 (super->huge_char_transitions, chr) = page4_21;
	      }
	  }
#endif
	  inxs = rx_subset_transition21 (super->huge_char_transitions, chr);
	}
      else
	{
	  /* (storage_unit_size == 2) && (chr > 0xffff)
	   */
#ifdef RX_LARGE_TABLES
	  {
	    struct rx_inx * page2_16;

	    page2_16 = rx_page2_16 (super->transitions, chr);
	    if (page2_16 == rx_shared_cache_miss_page)
	      {
		page2_16 = (struct rx_inx *)rx_dfa_cache_malloc (256 * sizeof (struct rx_inx));
		if (!page2_16)
		  return -1;
		mem_move ((t_uchar *)page2_16, (t_uchar *)rx_shared_cache_miss_page, 256 * sizeof (struct rx_inx));
		rx_page2_16(super->transitions, chr) = page2_16;
	      }

	    inxs = rx_subset_transitions16 (super->transitions, chr);
	  }
#else

	  {
	    struct rx_inx ** page2_16;
	    struct rx_inx * page3_16;

	    page2_16 = rx_page2_16 (super->transitions, chr);
	    if (page2_16 == rx_default_small_table_page2)
	      {
		page2_16 = (struct rx_inx **)rx_dfa_cache_malloc (rx_page2_size * sizeof (struct rx_inx *));
		if (!page2_16)
		  return -1;
		mem_move ((t_uchar *)page2_16, (t_uchar *)rx_default_small_table_page2, rx_page2_size * sizeof (struct rx_inx *));
		rx_page2_16(super->transitions, chr) = page2_16;
	      }

	    page3_16 = rx_page3_16 (super->transitions, chr);
	    if (page3_16 == rx_shared_cache_miss_page)
	      {
		page3_16 = (struct rx_inx *)rx_dfa_cache_malloc (rx_page3_size * sizeof (struct rx_inx));
		if (!page3_16)
		  return -1;
		mem_move ((t_uchar *)page3_16, (t_uchar *)rx_shared_cache_miss_page, rx_page3_size * sizeof (struct rx_inx));
		rx_page3_16(super->transitions, chr) = page3_16;
	      }

	    inxs = rx_subset_transitions16 (super->transitions, chr);
	  }

#endif
	}
    }


  for (x = 0, pos = 1; x < bits_per_subset; ++x, pos <<= 1)
    {
      if (set & pos)
	{
	  inxs[x] = *answer;
	  inxs[x].next_same_edge = edge->inx_list;
	  edge->inx_list = &inxs[x];
	}
    }
  return 0;
}




/************************************************************************
 *(h1 "DFA State Transition Cache Misses")
 *
 *
 */


/*(c rx_handle_cache_miss)
 * struct rx_inx * rx_handle_cache_miss (struct rx_nfa * rx,
 *					 struct rx_superstate * super,
 *					 t_uchar chr,
 *					 void * data_2);
 *
 * Recover from an `rx_cache_miss' instruction.
 *
 * `rx' and `super' are the NFA and superstate.  `chr' is the input
 * character for which the transition table of `super' contains
 * an `rx_cache_miss' instruction.
 *
 * `data_2' is the `data_2' field of the `rx_cache_miss' instruction
 * that caused us to call `rx_handle_cache_miss'.
 *
 * We return a pointer to another instruction (perhaps the corrected
 * transition table entry) which replaces the cache miss instruction.
 * The caller of this function can continue by re-dispatching on the
 * new instruction (which is permitted to be another cache miss
 * instruction).
 */
struct rx_inx *
rx_handle_cache_miss (struct rx_nfa * rx,
		      struct rx_superstate * super,
		      unsigned int chr,
		      void * data_2)
{
  struct rx_super_edge * e;

  /* There are three kinds of cache miss.
   *
   * The first occurs when a transition is taken that has never been
   * computed during the lifetime of the source superstate.  In this
   * case, no DFA edge exists for this transition.  The cache miss is
   * handled by calling `compute_super_edge_cset' and building a new
   * DFA edge.  If `compute_super_edge_cset' tells us that no
   * transition is defined, we fill in the transition table with
   * `rx_backtrack' instructions and return one of those.
   *
   * The second kind of cache miss occurs when we have a DFA edge
   * (pointed to by `data_2') but the destination superstate of that
   * edge isn't known.  `solve_destination' is used to construct the
   * destination superstate or find it in the DFA cache.  We return a
   * `rx_next_char' instruction.
   *
   * Finally, the third kind of cache miss occurs when the destination
   * superstate of a transition is known but is or was in a `semi-free
   * state'.  That case is handled by `refresh_semifree_superstate'.
   * We return an `rx_next_char' instruction.
   *
   */



  /* If the `rx_cache_miss' instruction contained a pointer to an
   * existing DFA edge, that pointer was passed to us as `data_2'.
   */
  e = data_2;

 retry:

  if (!e)
    {
      /* A missing DFA edge.  Look for it in the cache.
       */
      for (e = super->outgoing_edges; e; e = e->next_same_present)
	if (bits_is_member (e->cset, chr))
	  goto retry;

      /* A DFA edge missing from the cache.  Try to build it now.
       */
      {
	bits trcset;

	rx_lock_superstate (rx, super);

	if (super->has_huge_table)
	  trcset = bits_alloc (rx__dfa_alloc_limits, uni_bits_tree_rule);
	else
	  trcset = bits_alloc (rx__dfa_alloc_limits, rx_8bit_bits_tree_rule);

	if (!trcset)
	  {
	    rx_unlock_superstate (rx, super);
	    return 0;
	  }

	{
	  int nfa_edges;

	  nfa_edges = compute_super_edge_cset (rx, trcset, super, chr);
	  if (nfa_edges < 0)
	    {
	      rx_unlock_superstate (rx, super);
	      return 0;
	    }
#if 0
	  else if (!nfa_edges)
	    {
	      static struct rx_inx backtrack = { 0, 0, (void *)rx_backtrack, 0 };
	      rx_unlock_superstate (rx, super);
	      bits_free (trcset);
	      return &backtrack;
	    }
#endif
	  else
	    {
	      e = rx_super_edge (rx, super, trcset);
	      rx_unlock_superstate (rx, super);
	      if (!e)
		return 0;
	      goto retry;
	    }
	}
      }
    }
  else if (e->future)
    {
      struct rx_inx inx;

      /* We know the superstate edge and its destination state, but
       * the instruction frame contained a stale `rx_cache_miss'
       * instruction (the instruction itself, not the state, was the
       * stale part of the cache).  We must now replace the
       * instruction with an `rx_next_char' instruction.
       *
       * Its possible that the destination state is in a semifree
       * state and must be refreshed.
       */
      refresh_semifree_superstate (e->future);
      rx_lock_superstate (rx, super);

      inx.data = (void *)&e->future->transitions;
      inx.data_2 = (void *)e->future->members->state_label;
      inx.inx = (void *)rx_next_char;

      {
	bitset_subset s;
	if (   bits_get_subset (&s, e->cset, chr)
	    || install_partial_transition (super, &inx, e, s, chr))
	  {
	    rx_unlock_superstate (rx, super);
	    return 0;
	  }
      }
      rx_unlock_superstate (rx, super);

      if (!super->has_huge_table || ((super->storage_unit_size == 1) && (chr < 0x80)))
	return rx_transition8 (&super->transitions, chr);
      else if ((super->storage_unit_size == 2) && (chr < (1 << 16)))
	return rx_transition16 (&super->transitions, chr);
      else
	return rx_transition21 (super->huge_char_transitions, chr);
    }
  else
    {
      struct rx_inx inx;

      /* A DFA edge with no known destination state.  We must now
       * compute the destination state and fill in transition table
       * entries with `rx_next_char' instructions.
       */
      rx_lock_superstate (rx, super);
      {
	bitset_subset s;
	struct rx_superstate * destination;

	if (solve_destination (rx, &inx, e, super->storage_unit_size))
	  {
	    rx_unlock_superstate (rx, super);
	    return 0;
	  }

	if (inx.inx == (void *)rx_next_char)
	  {
	    destination = rx_transitions_to_suprestate ((rx_transition_table)(inx.data));
	    rx_lock_superstate (rx, destination);
	  }
	else
	  destination = 0;

	if (bits_get_subset (&s, e->cset, chr)
	    || install_partial_transition (super, &inx, e, s, chr))
	  {
	    if (destination)
	      rx_unlock_superstate (rx, destination);
	    rx_unlock_superstate (rx, super);
	    return 0;
	  }
	if (destination)
	  rx_unlock_superstate (rx, destination);
      }
      rx_unlock_superstate (rx, super);
      if (!super->has_huge_table || ((super->storage_unit_size == 1) && (chr < 0x80)))
	return rx_transition8 (&super->transitions, chr);
      else if ((super->storage_unit_size == 2) && (chr < (1 << 16)))
	return rx_transition16 (&super->transitions, chr);
      else
	return rx_transition21 (super->huge_char_transitions, chr);
    }
}


/************************************************************************
 * DFA Cache Debugging Tools
 *
 * I sometimes use this code to debug this file.
 */

#if 0
static int
qlen (struct rx_superstate * q)
{
  int count = 1;
  struct rx_superstate * it;
  if (!q)
    return 0;
  for (it = q->next_recyclable; it != q; it = it->next_recyclable)
    ++count;
  return count;
}


static void
check_cache ()
{
  struct rx_cache * cache = rx_default_cache;
  int total = cache->superstates;
  int semi = cache->semifree_superstates;


  total = cache->superstates;
  semi = cache->semifree_superstates;

  if (semi != qlen (cache->semifree_superstate))
    panic ("failed cache check in rx");

  if ((total - semi) != qlen (cache->lru_superstate))
    panic ("failed cache check in rx (2)");
}


#endif