/* 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 (void);
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 ();
else
{
semifree_superstate ();
semifree_superstate ();
semifree_superstate ();
}
/* 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
syntax highlighted by Code2HTML, v. 0.9.1