Home | History | Annotate | Line # | Download | only in lib 
      1 This code is structured roughly as follows:
      2 
      3 xmalloc.c:
      4   - Wrappers for the malloc() functions, for error generation and
      5     memory leak checking purposes.
      6 
      7 tre-mem.c:
      8   - A simple and efficient memory allocator.
      9 
     10 tre-stack.c:
     11   - Implements a simple stack data structure.
     12 
     13 tre-ast.c:
     14   - Abstract syntax tree (AST) definitions.
     15 
     16 tre-parse.c:
     17   - Regexp parser.  Parses a POSIX regexp (with TRE extensions) into
     18     an abstract syntax tree (AST).
     19 
     20 tre-compile.c:
     21   - Compiles ASTs to ready-to-use regex objects.  Comprised of two parts:
     22     * Routine to convert an AST to a tagged AST.  A tagged AST has
     23       appropriate minimized or maximized tags added to keep track of
     24       submatches.
     25     * Routine to convert tagged ASTs to tagged nondeterministic state
     26       machines (TNFAs) without epsilon transitions (transitions on
     27       empty strings).
     28 
     29 tre-match-parallel.c:
     30   - Parallel TNFA matcher.
     31     * The matcher basically takes a string and a TNFA and finds the
     32       leftmost longest match and submatches in one pass over the input
     33       string.  Only the beginning of the input string is scanned until
     34       a leftmost match and longest match is found.
     35     * The matcher cannot handle back references, but the worst case
     36       time consumption is O(l) where l is the length of the input
     37       string.  The space consumption is constant.
     38 
     39 tre-match-backtrack.c:
     40   - A traditional backtracking matcher.
     41     * Like the parallel matcher, takes a string and a TNFA and finds
     42       the leftmost longest match and submatches.  Portions of the
     43       input string may (and usually are) scanned multiple times.
     44     * Can handle back references.  The worst case time consumption,
     45       however, is O(k^l) where k is some constant and l is the length
     46       of the input string.  The worst case space consumption is O(l).
     47 
     48 tre-match-approx.c:
     49   - Approximate parallel TNFA matcher.
     50     * Finds the leftmost and longest match and submatches in one pass
     51       over the input string.  The match may contain errors.  Each
     52       missing, substituted, or extra character in the match increases
     53       the cost of the match.  A maximum cost for the returned match
     54       can be given.  The cost of the found match is returned.
     55     * Cannot handle back references.  The space and time consumption
     56       bounds are the same as for the parallel exact matcher, but
     57       in general this matcher is slower than the exact matcher.
     58 
     59 regcomp.c:
     60   - Implementation of the regcomp() family of functions as simple
     61     wrappers for tre_compile().
     62 
     63 regexec.c:
     64   - Implementation of the regexec() family of functions.
     65     * The appropriate matcher is dispatched according to the
     66       features used in the compiled regex object.
     67 
     68 regerror.c:
     69   - Implements the regerror() function.
     70