rx/_rx.h

   1 /* classes: h_files */
   2
   3 #ifndef _RXH
   4 #define _RXH
   5
   6 /*      Copyright (C) 1995, 1996 Tom Lord
   7  *
   8  * This program is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU Library General Public License as published by
  10  * the Free Software Foundation; either version 2, or (at your option)
  11  * any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU Library General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Library General Public License
  19  * along with this software; see the file COPYING.  If not, write to
  20  * the Free Software Foundation, 59 Temple Place - Suite 330,
  21  * Boston, MA 02111-1307, USA.
  22  */
  23
  24 \f
  25
  26 #include <sys/types.h>
  27 #include "rxhash.h"
  28 #include "rxcset.h"
  29
  30 \f
  31
  32 struct rx_cache;
  33 struct rx_superset;
  34 struct rx;
  35 struct rx_se_list;
  36
  37 \f
  38
  39 /* Suppose that from some NFA state and next character, more than one
  40  * path through side-effect edges is possible.  In what order should
  41  * the paths be tried?  A function of type rx_se_list_order answers
  42  * that question.  It compares two lists of side effects, and says
  43  * which list comes first.
  44  */
  45
  46 #ifdef __STDC__
  47 typedef int (*rx_se_list_order) (struct rx *,
  48                                  struct rx_se_list *,
  49                                  struct rx_se_list *);
  50 #else
  51 typedef int (*rx_se_list_order) ();
  52 #endif
  53
  54
  55
  56 /* Struct RX holds an NFA and cache state for the corresponding super NFA.
  57  */
  58 struct rx
  59 {
  60   /* The compiler assigns a unique id to every pattern.
  61    * Like sequence numbers in X, there is a subtle bug here
  62    * if you use Rx in a system that runs for a long time.
  63    * But, because of the way the caches work out, it is almost
  64    * impossible to trigger the Rx version of this bug.
  65    *
  66    * The id is used to validate superstates found in a cache
  67    * of superstates.  It isn't sufficient to let a superstate
  68    * point back to the rx for which it was compiled -- the caller
  69    * may be re-using a `struct rx' in which case the superstate
  70    * is not really valid.  So instead, superstates are validated
  71    * by checking the sequence number of the pattern for which
  72    * they were built.
  73    */
  74   int rx_id;
  75
  76   /* This is memory mgt. state for superstates.  This may be
  77    * shared by more than one struct rx.
  78    */
  79   struct rx_cache * cache;
  80
  81   /* Every nfa defines the size of its own character set.
  82    * Each superstate has an array of this size, with each element
  83    * a `struct rx_inx'.  So, don't make this number too large.
  84    * In particular, don't make it 2^16.
  85    */
  86   int local_cset_size;
  87
  88   /* Lists of side effects as stored in the NFA are `hash consed'..meaning
  89    * that lists with the same elements are ==.  During compilation,
  90    * this table facilitates hash-consing.
  91    */
  92   struct rx_hash se_list_memo;
  93
  94   /* Lists of NFA states are also hashed.
  95    */
  96   struct rx_hash set_list_memo;
  97
  98
  99
 100   /* The compiler and matcher must build a number of instruction frames.
 101    * The format of these frames is fixed (c.f. struct rx_inx).  The values
 102    * of the instruction opcodes is not fixed.
 103    *
 104    * An enumerated type (enum rx_opcode) defines the set of instructions
 105    * that the compiler or matcher might generate.  When filling an instruction
 106    * frame, the INX field is found by indexing this instruction table
 107    * with an opcode:
 108    */
 109   void ** instruction_table;
 110
 111   /* The list of all states in an NFA.
 112    * The NEXT field of NFA states links this list.
 113    */
 114   struct rx_nfa_state *nfa_states;
 115   struct rx_nfa_state *start_nfa_states;
 116   struct rx_superset * start_set;
 117
 118   /* This orders the search through super-nfa paths.
 119    * See the comment near the typedef of rx_se_list_order.
 120    */
 121   rx_se_list_order se_list_cmp;
 122
 123   int next_nfa_id;
 124 };
 125
 126
 127
 128 /* If `regs_allocated' is REGS_UNALLOCATED in the pattern buffer,
 129  * `re_match_2' returns information about at least this many registers
 130  * the first time a `regs' structure is passed.
 131  *
 132  * Also, this is the greatest number of backreferenced subexpressions
 133  * allowed in a pattern being matched without caller-supplied registers.
 134  */
 135 #ifndef RE_NREGS
 136 #define RE_NREGS 30
 137 #endif
 138
 139
 140 #ifndef emacs
 141 #define CHARBITS 8
 142 #define CHAR_SET_SIZE (1 << CHARBITS)
 143 #define Sword 1
 144 #define SYNTAX(c) re_syntax_table[c]
 145 extern char re_syntax_table[CHAR_SET_SIZE];
 146 #endif
 147
 148
 149 /* Should we use malloc or alloca?  If REGEX_MALLOC is not defined, we
 150  * use `alloca' instead of `malloc' for the backtracking stack.
 151  *
 152  * Emacs will die miserably if we don't do this.
 153  */
 154
 155 #ifdef REGEX_MALLOC
 156 #define REGEX_ALLOCATE malloc
 157 #else /* not REGEX_MALLOC  */
 158 #define REGEX_ALLOCATE alloca
 159 #endif /* not REGEX_MALLOC */
 160
 161 #undef MAX
 162 #undef MIN
 163 #define MAX(a, b) ((a) > (b) ? (a) : (b))
 164 #define MIN(a, b) ((a) < (b) ? (a) : (b))
 165 extern void * rx_id_instruction_table[];
 166 extern struct rx_cache * rx_default_cache;
 167
 168 \f
 169 #ifdef __STDC__
 170
 171 #else /* STDC */
 172
 173 #endif /* STDC */
 174
 175
 176 #endif  /* _RXH */