home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / gnurx.zip / rx / _rx.h next >
C/C++ Source or Header  |  1995-12-31  |  6KB  |  195 lines
  1. /* classes: h_files */
  2.  
  3. #ifndef _RXH
  4. #define _RXH
  5. /***********************************************************
  6.  
  7. Copyright 1995 by Tom Lord
  8.  
  9.                         All Rights Reserved
  10.  
  11. Permission to use, copy, modify, and distribute this software and its 
  12. documentation for any purpose and without fee is hereby granted, 
  13. provided that the above copyright notice appear in all copies and that
  14. both that copyright notice and this permission notice appear in 
  15. supporting documentation, and that the name of the copyright holder not be
  16. used in advertising or publicity pertaining to distribution of the
  17. software without specific, written prior permission.  
  18.  
  19. Tom Lord DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  20. INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  21. EVENT SHALL TOM LORD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  22. CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
  23. USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
  24. OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  25. PERFORMANCE OF THIS SOFTWARE.
  26.  
  27. ******************************************************************/
  28.  
  29.  
  30.  
  31. #include <sys/types.h>
  32. #include "rxhash.h"
  33. #include "rxcset.h"
  34.  
  35.  
  36.  
  37. struct rx_cache;
  38. struct rx_superset;
  39. struct rx;
  40. struct rx_se_list;
  41.  
  42.  
  43.  
  44. /* Suppose that from some NFA state and next character, more than one
  45.  * path through side-effect edges is possible.  In what order should
  46.  * the paths be tried?  A function of type rx_se_list_order answers
  47.  * that question.  It compares two lists of side effects, and says
  48.  * which list comes first.
  49.  */
  50.  
  51. #ifdef __STDC__
  52. typedef int (*rx_se_list_order) (struct rx *,
  53.                  struct rx_se_list *, 
  54.                  struct rx_se_list *);
  55. #else
  56. typedef int (*rx_se_list_order) ();
  57. #endif
  58.  
  59.  
  60.  
  61. /* Struct RX holds an NFA and cache state for the corresponding super NFA.
  62.  */
  63. struct rx
  64. {
  65.   /* The compiler assigns a unique id to every pattern.
  66.    * Like sequence numbers in X, there is a subtle bug here
  67.    * if you use Rx in a system that runs for a long time.
  68.    * But, because of the way the caches work out, it is almost
  69.    * impossible to trigger the Rx version of this bug.
  70.    *
  71.    * The id is used to validate superstates found in a cache
  72.    * of superstates.  It isn't sufficient to let a superstate
  73.    * point back to the rx for which it was compiled -- the caller
  74.    * may be re-using a `struct rx' in which case the superstate
  75.    * is not really valid.  So instead, superstates are validated
  76.    * by checking the sequence number of the pattern for which
  77.    * they were built.
  78.    */
  79.   int rx_id;
  80.  
  81.   /* This is memory mgt. state for superstates.  This may be 
  82.    * shared by more than one struct rx.
  83.    */
  84.   struct rx_cache * cache;
  85.  
  86.   /* Every nfa defines the size of its own character set. 
  87.    * Each superstate has an array of this size, with each element
  88.    * a `struct rx_inx'.  So, don't make this number too large.
  89.    * In particular, don't make it 2^16.
  90.    */
  91.   int local_cset_size;
  92.  
  93.   /* Lists of side effects as stored in the NFA are `hash consed'..meaning
  94.    * that lists with the same elements are ==.  During compilation, 
  95.    * this table facilitates hash-consing.
  96.    */
  97.   struct rx_hash se_list_memo;
  98.  
  99.   /* Lists of NFA states are also hashed. 
  100.    */
  101.   struct rx_hash set_list_memo;
  102.  
  103.  
  104.  
  105.   /* The compiler and matcher must build a number of instruction frames.
  106.    * The format of these frames is fixed (c.f. struct rx_inx).  The values
  107.    * of the instruction opcodes is not fixed.
  108.    *
  109.    * An enumerated type (enum rx_opcode) defines the set of instructions
  110.    * that the compiler or matcher might generate.  When filling an instruction
  111.    * frame, the INX field is found by indexing this instruction table
  112.    * with an opcode:
  113.    */
  114.   void ** instruction_table;
  115.  
  116.   /* The list of all states in an NFA.
  117.    * The NEXT field of NFA states links this list.
  118.    */
  119.   struct rx_nfa_state *nfa_states;
  120.   struct rx_nfa_state *start_nfa_states;
  121.   struct rx_superset * start_set;
  122.  
  123.   /* This orders the search through super-nfa paths.
  124.    * See the comment near the typedef of rx_se_list_order.
  125.    */
  126.   rx_se_list_order se_list_cmp;
  127.  
  128.   int next_nfa_id;
  129. };
  130.  
  131.  
  132.  
  133. /* Type for byte offsets within the string.  POSIX mandates this.  */
  134. typedef int regoff_t;
  135.  
  136. /* This is the structure we store register match data in.  See
  137.  * regex.texinfo for a full description of what registers match.
  138.  */
  139. struct re_registers
  140. {
  141.   unsigned num_regs;
  142.   regoff_t *start;
  143.   regoff_t *end;
  144. };
  145.  
  146. /* If `regs_allocated' is REGS_UNALLOCATED in the pattern buffer,
  147.  * `re_match_2' returns information about at least this many registers
  148.  * the first time a `regs' structure is passed. 
  149.  *
  150.  * Also, this is the greatest number of backreferenced subexpressions
  151.  * allowed in a pattern being matched without caller-supplied registers.
  152.  */
  153. #ifndef RE_NREGS
  154. #define RE_NREGS 30
  155. #endif
  156.  
  157.  
  158. #ifndef emacs
  159. #define CHARBITS 8
  160. #define CHAR_SET_SIZE (1 << CHARBITS)
  161. #define Sword 1
  162. #define SYNTAX(c) re_syntax_table[c]
  163. extern char re_syntax_table[CHAR_SET_SIZE];
  164. #endif
  165.  
  166.  
  167. /* Should we use malloc or alloca?  If REGEX_MALLOC is not defined, we
  168.  * use `alloca' instead of `malloc' for the backtracking stack.
  169.  *
  170.  * Emacs will die miserably if we don't do this.
  171.  */
  172.  
  173. #ifdef REGEX_MALLOC
  174. #define REGEX_ALLOCATE malloc
  175. #else /* not REGEX_MALLOC  */
  176. #define REGEX_ALLOCATE alloca
  177. #endif /* not REGEX_MALLOC */
  178.  
  179. #undef MAX
  180. #undef MIN
  181. #define MAX(a, b) ((a) > (b) ? (a) : (b))
  182. #define MIN(a, b) ((a) < (b) ? (a) : (b))
  183. extern void * rx_id_instruction_table[];
  184. extern struct rx_cache * rx_default_cache;
  185.  
  186.  
  187. #ifdef __STDC__
  188.  
  189. #else /* STDC */
  190.  
  191. #endif /* STDC */
  192.  
  193.  
  194. #endif  /* _RXH */
  195.