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