rx.h

ac3的解码程序

   * and we need a way to validate it.
   *
   * Fortunately, even if this set is flushed from the cache, it is
   * not freed.  It just goes on the free-list of supersets.
   * So we can still examine it.  
   *
   * So to validate a starting set memo, check to see if the
   * starts_for field still points back to the struct rx in question,
   * and if the ID matches the rx sequence number.
   */
  struct rx * starts_for;

  /* This is used to link into a hash bucket so these objects can
   * be `hash-consed'.
   */
  struct rx_hash_item hash_item;
};

#define rx_protect_superset(RX,CON) (++(CON)->refs)

/* The terminology may be confusing (rename this structure?).
 * Every character occurs in at most one rx_super_edge per super-state.
 * But, that structure might have more than one option, indicating a point
 * of non-determinism. 
 *
 * In other words, this structure holds a list of superstate edges
 * sharing a common starting state and character label.  The edges
 * are in the field OPTIONS.  All superstate edges sharing the same
 * starting state and character are in this list.
 */
struct rx_super_edge
{
  struct rx_super_edge *next;
  struct rx_inx rx_backtrack_frame;
  int cset_size;
  rx_Bitset cset;
  struct rx_distinct_future *options;
};

/* A superstate is a set of nfa states (RX_SUPERSET) along
 * with a transition table.  Superstates are built on demand and reclaimed
 * without warning.  To protect a superstate from this ghastly fate,
 * use LOCK_SUPERSTATE. 
 */
struct rx_superstate
{
  int rx_id;			/* c.f. the id field of rx_superset */
  int locks;			/* protection from reclamation */

  /* Within a superstate cache, all the superstates are kept in a big
   * queue.  The tail of the queue is the state most likely to be
   * reclaimed.  The *recyclable fields hold the queue position of 
   * this state.
   */
  struct rx_superstate * next_recyclable;
  struct rx_superstate * prev_recyclable;

  /* The supernfa edges that exist in the cache and that have
   * this state as their destination are kept in this list:
   */
  struct rx_distinct_future * transition_refs;

  /* The list of nfa states corresponding to this superstate: */
  struct rx_superset * contents;

  /* The list of edges in the cache beginning from this state. */
  struct rx_super_edge * edges;

  /* A tail of the recyclable queue is marked as semifree.  A semifree
   * state has no incoming next_char transitions -- any transition
   * into a semifree state causes a complex dispatch with the side
   * effect of rescuing the state from its semifree state.
   *
   * An alternative to this might be to make next_char more expensive,
   * and to move a state to the head of the recyclable queue whenever
   * it is entered.  That way, popular states would never be recycled.
   *
   * But unilaterally making next_char more expensive actually loses.
   * So, incoming transitions are only made expensive for states near
   * the tail of the recyclable queue.  The more cache contention
   * there is, the more frequently a state will have to prove itself
   * and be moved back to the front of the queue.  If there is less 
   * contention, then popular states just aggregate in the front of 
   * the queue and stay there.
   */
  int is_semifree;


  /* This keeps track of the size of the transition table for this
   * state.  There is a half-hearted attempt to support variable sized
   * superstates.
   */
  int trans_size;

  /* Indexed by characters... */
  struct rx_inx transitions[RX_TAIL_ARRAY];
};


/* A list of distinct futures define the edges that leave from a 
 * given superstate on a given character.  c.f. rx_super_edge.
 */

struct rx_distinct_future
{
  struct rx_distinct_future * next_same_super_edge[2];
  struct rx_distinct_future * next_same_dest;
  struct rx_distinct_future * prev_same_dest;
  struct rx_superstate * present;	/* source state */
  struct rx_superstate * future;	/* destination state */
  struct rx_super_edge * edge;


  /* The future_frame holds the instruction that should be executed
   * after all the side effects are done, when it is time to complete
   * the transition to the next state.
   *
   * Normally this is a next_char instruction, but it may be a
   * cache_miss instruction as well, depending on whether or not
   * the superstate is in the cache and semifree.
   * 
   * If this is the only future for a given superstate/char, and
   * if there are no side effects to be performed, this frame is
   * not used (directly) at all.  Instead, its contents are copied
   * into the transition table of the starting state of this dist. future.
   */
  struct rx_inx future_frame;

  struct rx_inx side_effects_frame;
  struct rx_se_list * effects;
};

#define rx_lock_superstate(R,S)  ((S)->locks++)
#define rx_unlock_superstate(R,S) (--(S)->locks)


/* This page destined for rx.h */

struct rx_blocklist
{
  struct rx_blocklist * next;
  int bytes;
};

struct rx_freelist
{
  struct rx_freelist * next;
};

struct rx_cache;

#ifdef __STDC__
typedef void (*rx_morecore_fn)(struct rx_cache *);
#else
typedef void (*rx_morecore_fn)();
#endif

/* You use this to control the allocation of superstate data 
 * during matching.  Most of it should be initialized to 0.
 *
 * A MORECORE function is necessary.  It should allocate
 * a new block of memory or return 0.
 * A default that uses malloc is called `rx_morecore'.
 *
 * The number of SUPERSTATES_ALLOWED indirectly limits how much memory
 * the system will try to allocate.  The default is 128.  Batch style
 * applications that are very regexp intensive should use as high a number
 * as possible without thrashing.
 * 
 * The LOCAL_CSET_SIZE is the number of characters in a character set.
 * It is therefore the number of entries in a superstate transition table.
 * Generally, it should be 256.  If your character set has 16 bits, 
 * it is better to translate your regexps into equivalent 8 bit patterns.
 */

struct rx_cache
{
  struct rx_hash_rules superset_hash_rules;

  /* Objects are allocated by incrementing a pointer that 
   * scans across rx_blocklists.
   */
  struct rx_blocklist * memory;
  struct rx_blocklist * memory_pos;
  int bytes_left;
  char * memory_addr;
  rx_morecore_fn morecore;

  /* Freelists. */
  struct rx_freelist * free_superstates;
  struct rx_freelist * free_transition_classes;
  struct rx_freelist * free_discernable_futures;
  struct rx_freelist * free_supersets;
  struct rx_freelist * free_hash;

  /* Two sets of superstates -- those that are semifreed, and those
   * that are being used.
   */
  struct rx_superstate * lru_superstate;
  struct rx_superstate * semifree_superstate;

  struct rx_superset * empty_superset;

  int superstates;
  int semifree_superstates;
  int hits;
  int misses;
  int superstates_allowed;

  int local_cset_size;
  void ** instruction_table;

  struct rx_hash superset_table;
};



/* The lowest-level search function supports arbitrarily fragmented
 * strings and (optionally) suspendable/resumable searches.
 *
 * Callers have to provide a few hooks.
 */

#ifndef __GNUC__
#ifdef __STDC__
#define __const__ const
#else
#define __const__
#endif
#endif

/* This holds a matcher position */
struct rx_string_position
{
  __const__ unsigned char * pos;	/* The current pos. */
  __const__ unsigned char * string; /* The current string burst. */
  __const__ unsigned char * end;	/* First invalid position >= POS. */
  int offset;			/* Integer address of the current burst. */
  int size;			/* Current string's size. */
  int search_direction;		/* 1 or -1 */
  int search_end;		/* First position to not try. */
};


enum rx_get_burst_return
{
  rx_get_burst_continuation,
  rx_get_burst_error,
  rx_get_burst_ok,
  rx_get_burst_no_more
};


/* A call to get burst should make POS valid.  It might be invalid
 * if the STRING field doesn't point to a burst that actually
 * contains POS.
 *
 * GET_BURST should take a clue from SEARCH_DIRECTION (1 or -1) as to
 * whether or not to pad to the left.  Padding to the right is always
 * appropriate, but need not go past the point indicated by STOP.
 *
 * If a continuation is returned, then the reentering call to
 * a search function will retry the get_burst.
 */

#ifdef __STDC__
typedef enum rx_get_burst_return
  (*rx_get_burst_fn) (struct rx_string_position * pos,
		      void * app_closure,
		      int stop);
					       
#else
typedef enum rx_get_burst_return (*rx_get_burst_fn) ();
#endif


enum rx_back_check_return
{
  rx_back_check_continuation,
  rx_back_check_error,
  rx_back_check_pass,
  rx_back_check_fail
};

/* Back_check should advance the position it is passed 
 * over rparen - lparen characters and return pass iff
 * the characters starting at POS match those indexed
 * by [LPAREN..RPAREN].
 *
 * If a continuation is returned, then the reentering call to
 * a search function will retry the back_check.
 */

#ifdef __STDC__
typedef enum rx_back_check_return
  (*rx_back_check_fn) (struct rx_string_position * pos,
		       int lparen,
		       int rparen,
		       unsigned char * translate,
		       void * app_closure,
		       int stop);
					       
#else
typedef enum rx_back_check_return (*rx_back_check_fn) ();
#endif




/* A call to fetch_char should return the character at POS or POS + 1.
 * Returning continuations here isn't supported.  OFFSET is either 0 or 1
 * and indicates which characters is desired.
 */

#ifdef __STDC__
typedef int (*rx_fetch_char_fn) (struct rx_string_position * pos,
				 int offset,
				 void * app_closure,
				 int stop);
#else
typedef int (*rx_fetch_char_fn) ();
#endif


enum rx_search_return
{
  rx_search_continuation = -4,
  rx_search_error = -3,
  rx_search_soft_fail = -2,	/* failed by running out of string */
  rx_search_fail = -1		/* failed only by reaching failure states */
  /* return values >= 0 indicate the position of a successful match */
};






/* regex.h
 * 
 * The remaining declarations replace regex.h.
 */

/* This is an array of error messages corresponding to the error codes.
 */
extern __const__ char *re_error_msg[];

/* If any error codes are removed, changed, or added, update the
   `re_error_msg' table in regex.c.  */
typedef enum
{
  REG_NOERROR = 0,	/* Success.  */
  REG_NOMATCH,		/* Didn't find a match (for regexec).  */

  /* POSIX regcomp return error codes.  (In the order listed in the
     standard.)  */
  REG_BADPAT,		/* Invalid pattern.  */
  REG_ECOLLATE,		/* Not implemented.  */
  REG_ECTYPE,		/* Invalid character class name.  */
  REG_EESCAPE,		/* Trailing backslash.  */
  REG_ESUBREG,		/* Invalid back reference.  */
  REG_EBRACK,		/* Unmatched left bracket.  */
  REG_EPAREN,		/* Parenthesis imbalance.  */ 
  REG_EBRACE,		/* Unmatched \{.  */
  REG_BADBR,		/* Invalid contents of \{\}.  */
  REG_ERANGE,		/* Invalid range end.  */
  REG_ESPACE,		/* Ran out of memory.  */
  REG_BADRPT,		/* No preceding re for repetition op.  */

  /* Error codes we've added.  */
  REG_EEND,		/* Premature end.  */
  REG_ESIZE,		/* Compiled pattern bigger than 2^16 bytes.  */
  REG_ERPAREN		/* Unmatched ) or \); not returned from regcomp.  */
} reg_errcode_t;

/* The regex.c support, as a client of rx, defines a set of possible
 * side effects that can be added to the edge lables of nfa edges.
 * Here is the list of sidef effects in use.
 */

enum re_side_effects
{
#define RX_WANT_SE_DEFS 1
#undef RX_DEF_SE
#undef RX_DEF_CPLX_SE
#define RX_DEF_SE(IDEM, NAME, VALUE)	      NAME VALUE,
#define RX_DEF_CPLX_SE(IDEM, NAME, VALUE)     NAME VALUE,
#include "rx.h"
#undef RX_DEF_SE
#undef RX_DEF_CPLX_SE
#undef RX_WANT_SE_DEFS
   re_floogle_flap = 65533
};

/* These hold paramaters for the kinds of side effects that are possible
 * in the supported pattern languages.  These include things like the 
 * numeric bounds of {} operators and the index of paren registers for