diff options
Diffstat (limited to 'libc')
| -rw-r--r-- | libc/misc/regex/Makefile | 17 | ||||
| -rw-r--r-- | libc/misc/regex/rx.c | 7522 | ||||
| -rw-r--r-- | libc/stdlib/Makefile | 2 | ||||
| -rw-r--r-- | libc/stdlib/realpath.c | 168 |
4 files changed, 7708 insertions, 1 deletions
diff --git a/libc/misc/regex/Makefile b/libc/misc/regex/Makefile new file mode 100644 index 000000000..c6c8d8e52 --- /dev/null +++ b/libc/misc/regex/Makefile @@ -0,0 +1,17 @@ +TOPDIR=../ +include $(TOPDIR)Rules.make + +LIBC=../libc.a + +OBJ=rx.o + +all: $(LIBC) + +$(LIBC): $(LIBC)($(OBJ)) + +$(LIBC)(rx.o): rx.c + $(CC) $(CFLAGS) -DL_$* $< -c -o $*.o + $(AR) $(ARFLAGS) $@ $*.o + +clean: + rm -f libc.a *.o core mon.out timer.t.h dMakefile dtr try timer diff --git a/libc/misc/regex/rx.c b/libc/misc/regex/rx.c new file mode 100644 index 000000000..8e85782f2 --- /dev/null +++ b/libc/misc/regex/rx.c @@ -0,0 +1,7522 @@ +/* Copyright (C) 1992, 1993, 1994, 1995 Free Software Foundation, Inc. + +This file is part of the librx library. + +Librx is free software; you can redistribute it and/or modify it under +the terms of the GNU Library General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +Librx is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU Library General Public +License along with this software; see the file COPYING.LIB. If not, +write to the Free Software Foundation, 675 Mass Ave, Cambridge, MA +02139, USA. */ + +/* NOTE!!! AIX is so losing it requires this to be the first thing in the + * file. + * Do not put ANYTHING before it! + */ +#if !defined (__GNUC__) && defined (_AIX) + #pragma alloca +#endif + +/* To make linux happy? */ +#ifndef _GNU_SOURCE +#define _GNU_SOURCE +#endif + + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <ctype.h> +#ifndef isgraph +#define isgraph(c) (isprint (c) && !isspace (c)) +#endif +#ifndef isblank +#define isblank(c) ((c) == ' ' || (c) == '\t') +#endif + +#include <sys/types.h> + +#undef MAX +#undef MIN +#define MAX(a, b) ((a) > (b) ? (a) : (b)) +#define MIN(a, b) ((a) < (b) ? (a) : (b)) + +typedef char boolean; +#define false 0 +#define true 1 + +#ifndef __GCC__ +#undef __inline__ +#define __inline__ +#endif + +/* Emacs already defines alloca, sometimes. */ +#ifndef alloca + +/* Make alloca work the best possible way. */ +#ifdef __GNUC__ +#define alloca __builtin_alloca +#else /* not __GNUC__ */ +#if HAVE_ALLOCA_H +#include <alloca.h> +#else /* not __GNUC__ or HAVE_ALLOCA_H */ +#ifndef _AIX /* Already did AIX, up at the top. */ +char *alloca (); +#endif /* not _AIX */ +#endif /* not HAVE_ALLOCA_H */ +#endif /* not __GNUC__ */ + +#endif /* not alloca */ + +/* Memory management and stuff for emacs. */ + +#define CHARBITS 8 +#define remalloc(M, S) (M ? realloc (M, S) : malloc (S)) + + +/* Should we use malloc or alloca? If REGEX_MALLOC is not defined, we + * use `alloca' instead of `malloc' for the backtracking stack. + * + * Emacs will die miserably if we don't do this. + */ + +#ifdef REGEX_MALLOC +#define REGEX_ALLOCATE malloc +#else /* not REGEX_MALLOC */ +#define REGEX_ALLOCATE alloca +#endif /* not REGEX_MALLOC */ + + +#ifdef RX_WANT_RX_DEFS +#define RX_DECL extern +#define RX_DEF_QUAL +#else +#define RX_WANT_RX_DEFS +#define RX_DECL static +#define RX_DEF_QUAL static +#endif + +#include <regex.h> +#undef RX_DECL +#define RX_DECL RX_DEF_QUAL + + +/* + * Prototypes. + */ +#ifdef __STDC__ +RX_DECL struct rx_hash_item + *rx_hash_find (struct rx_hash *, unsigned long, + void *, struct rx_hash_rules *); +RX_DECL struct rx_hash_item + *rx_hash_find (struct rx_hash *, unsigned long, + void *, struct rx_hash_rules *); +RX_DECL struct rx_hash_item + *rx_hash_store (struct rx_hash *, unsigned long, + void *, struct rx_hash_rules *); +RX_DECL void rx_hash_free (struct rx_hash_item *, + struct rx_hash_rules *); +RX_DECL void rx_free_hash_table (struct rx_hash *, rx_hash_freefn, + struct rx_hash_rules *); +RX_DECL rx_Bitset + rx_cset (struct rx *); +RX_DECL rx_Bitset + rx_copy_cset (struct rx *, rx_Bitset); +RX_DECL void rx_free_cset (struct rx *, rx_Bitset); +static struct rx_hash_item + *compiler_hash_item_alloc (struct rx_hash_rules *, void *); +static struct rx_hash + *compiler_hash_alloc (struct rx_hash_rules *); +static void compiler_free_hash (struct rx_hash *, + struct rx_hash_rules *); +static void compiler_free_hash_item (struct rx_hash_item *, + struct rx_hash_rules *); +RX_DECL struct rexp_node + *rexp_node (struct rx *, enum rexp_node_type); +RX_DECL struct rexp_node + *rx_mk_r_cset (struct rx *, rx_Bitset); +RX_DECL struct rexp_node + *rx_mk_r_concat (struct rx *, struct rexp_node *, + struct rexp_node *); +RX_DECL struct rexp_node + *rx_mk_r_alternate (struct rx *, struct rexp_node *, + struct rexp_node *); +RX_DECL struct rexp_node + *rx_mk_r_alternate (struct rx *, struct rexp_node *, + struct rexp_node *); +RX_DECL struct rexp_node + *rx_mk_r_opt (struct rx *, struct rexp_node *); +RX_DECL struct rexp_node + *rx_mk_r_star (struct rx *, struct rexp_node *); +RX_DECL struct rexp_node + *rx_mk_r_2phase_star (struct rx *, struct rexp_node *, + struct rexp_node *); +RX_DECL struct rexp_node + *rx_mk_r_side_effect (struct rx *, rx_side_effect); +RX_DECL struct rexp_node + *rx_mk_r_data (struct rx *, void *); +RX_DECL void rx_free_rexp (struct rx *, struct rexp_node *); +RX_DECL struct rexp_node + *rx_copy_rexp (struct rx *, struct rexp_node *); +RX_DECL struct rx_nfa_state + *rx_nfa_state (struct rx *); +RX_DECL void rx_free_nfa_state (struct rx_nfa_state *); +RX_DECL struct rx_nfa_state + *rx_id_to_nfa_state (struct rx *, int); +RX_DECL struct rx_nfa_edge + *rx_nfa_edge (struct rx *, enum rx_nfa_etype, + struct rx_nfa_state *, + struct rx_nfa_state *); +RX_DECL void rx_free_nfa_edge (struct rx_nfa_edge *); +static struct rx_possible_future + *rx_possible_future (struct rx *, struct rx_se_list *); +static void rx_free_possible_future (struct rx_possible_future *); +RX_DECL void rx_free_nfa (struct rx *); +RX_DECL int rx_build_nfa (struct rx *, struct rexp_node *, + struct rx_nfa_state **, + struct rx_nfa_state **); +RX_DECL void rx_name_nfa_states (struct rx *); +static int se_list_cmp (void *, void *); +static int se_list_equal (void *, void *); +static struct rx_se_list + *hash_cons_se_prog (struct rx *, struct rx_hash *, + void *, struct rx_se_list *); +static struct rx_se_list + *hash_se_prog (struct rx *, struct rx_hash *, + struct rx_se_list *); +static int nfa_set_cmp (void *, void *); +static int nfa_set_equal (void *, void *); +static struct rx_nfa_state_set + *nfa_set_cons (struct rx *, struct rx_hash *, + struct rx_nfa_state *, + struct rx_nfa_state_set *); +static struct rx_nfa_state_set + *nfa_set_enjoin (struct rx *, struct rx_hash *, + struct rx_nfa_state *, + struct rx_nfa_state_set *); +#endif + +#ifndef emacs + +#ifdef SYNTAX_TABLE +extern char *re_syntax_table; +#else /* not SYNTAX_TABLE */ + +#ifndef RX_WANT_RX_DEFS +RX_DECL char re_syntax_table[CHAR_SET_SIZE]; +#endif + +#ifdef __STDC__ +static void +init_syntax_once (void) +#else +static void +init_syntax_once () +#endif +{ + register int c; + static int done = 0; + + if (done) + return; + + bzero (re_syntax_table, sizeof re_syntax_table); + + for (c = 'a'; c <= 'z'; c++) + re_syntax_table[c] = Sword; + + for (c = 'A'; c <= 'Z'; c++) + re_syntax_table[c] = Sword; + + for (c = '0'; c <= '9'; c++) + re_syntax_table[c] = Sword; + + re_syntax_table['_'] = Sword; + + done = 1; +} +#endif /* not SYNTAX_TABLE */ +#endif /* not emacs */ + +/* Compile with `-DRX_DEBUG' and use the following flags. + * + * Debugging flags: + * rx_debug - print information as a regexp is compiled + * rx_debug_trace - print information as a regexp is executed + */ + +#ifdef RX_DEBUG + +int rx_debug_compile = 0; +int rx_debug_trace = 0; +static struct re_pattern_buffer * dbug_rxb = 0; + + +/* + * More Prototypes + */ +#ifdef __STDC__ +typedef void (*side_effect_printer) (struct rx *, void *, FILE *); +static void print_cset (struct rx *, rx_Bitset, FILE *); +static void print_rexp (struct rx *, struct rexp_node *, int, + side_effect_printer, FILE *); +static void print_nfa (struct rx *, struct rx_nfa_state *, + side_effect_printer, FILE *); +static void re_seprint (struct rx *, void *, FILE *); +void print_compiled_pattern (struct re_pattern_buffer *); +void print_fastmap (char *); +#else +typedef void (*side_effect_printer) (); +static void print_cset (); +#endif + +#ifdef __STDC__ +static void +print_rexp (struct rx *rx, + struct rexp_node *node, int depth, + side_effect_printer seprint, FILE * fp) +#else +static void +print_rexp (rx, node, depth, seprint, fp) + struct rx *rx; + struct rexp_node *node; + int depth; + side_effect_printer seprint; + FILE * fp; +#endif +{ + if (!node) + return; + else + { + switch (node->type) + { + case r_cset: + { + fprintf (fp, "%*s", depth, ""); + print_cset (rx, node->params.cset, fp); + fputc ('\n', fp); + break; + } + + case r_opt: + case r_star: + fprintf (fp, "%*s%s\n", depth, "", + node->type == r_opt ? "opt" : "star"); + print_rexp (rx, node->params.pair.left, depth + 3, seprint, fp); + break; + + case r_2phase_star: + fprintf (fp, "%*s2phase star\n", depth, ""); + print_rexp (rx, node->params.pair.right, depth + 3, seprint, fp); + print_rexp (rx, node->params.pair.left, depth + 3, seprint, fp); + break; + + + case r_alternate: + case r_concat: + fprintf (fp, "%*s%s\n", depth, "", + node->type == r_alternate ? "alt" : "concat"); + print_rexp (rx, node->params.pair.left, depth + 3, seprint, fp); + print_rexp (rx, node->params.pair.right, depth + 3, seprint, fp); + break; + case r_side_effect: + fprintf (fp, "%*sSide effect: ", depth, ""); + seprint (rx, node->params.side_effect, fp); + fputc ('\n', fp); + } + } +} + +#ifdef __STDC__ +static void +print_nfa (struct rx * rx, + struct rx_nfa_state * n, + side_effect_printer seprint, FILE * fp) +#else +static void +print_nfa (rx, n, seprint, fp) + struct rx * rx; + struct rx_nfa_state * n; + side_effect_printer seprint; + FILE * fp; +#endif +{ + while (n) + { + struct rx_nfa_edge *e = n->edges; + struct rx_possible_future *ec = n->futures; + fprintf (fp, "node %d %s\n", n->id, + n->is_final ? "final" : (n->is_start ? "start" : "")); + while (e) + { + fprintf (fp, " edge to %d, ", e->dest->id); + switch (e->type) + { + case ne_epsilon: + fprintf (fp, "epsilon\n"); + break; + case ne_side_effect: + fprintf (fp, "side effect "); + seprint (rx, e->params.side_effect, fp); + fputc ('\n', fp); + break; + case ne_cset: + fprintf (fp, "cset "); + print_cset (rx, e->params.cset, fp); + fputc ('\n', fp); + break; + } + e = e->next; + } + + while (ec) + { + int x; + struct rx_nfa_state_set * s; + struct rx_se_list * l; + fprintf (fp, " eclosure to {"); + for (s = ec->destset; s; s = s->cdr) + fprintf (fp, "%d ", s->car->id); + fprintf (fp, "} ("); + for (l = ec->effects; l; l = l->cdr) + { + seprint (rx, l->car, fp); + fputc (' ', fp); + } + fprintf (fp, ")\n"); + ec = ec->next; + } + n = n->next; + } +} + +static char * efnames [] = +{ + "bogon", + "re_se_try", + "re_se_pushback", + "re_se_push0", + "re_se_pushpos", + "re_se_chkpos", + "re_se_poppos", + "re_se_at_dot", + "re_se_syntax", + "re_se_not_syntax", + "re_se_begbuf", + "re_se_hat", + "re_se_wordbeg", + "re_se_wordbound", + "re_se_notwordbound", + "re_se_wordend", + "re_se_endbuf", + "re_se_dollar", + "re_se_fail", +}; + +static char * efnames2[] = +{ + "re_se_win", + "re_se_lparen", + "re_se_rparen", + "re_se_backref", + "re_se_iter", + "re_se_end_iter", + "re_se_tv" +}; + +static char * inx_names[] = +{ + "rx_backtrack_point", + "rx_do_side_effects", + "rx_cache_miss", + "rx_next_char", + "rx_backtrack", + "rx_error_inx", + "rx_num_instructions" +}; + + +#ifdef __STDC__ +static void +re_seprint (struct rx * rx, void * effect, FILE * fp) +#else +static void +re_seprint (rx, effect, fp) + struct rx * rx; + void * effect; + FILE * fp; +#endif +{ + if ((int)effect < 0) + fputs (efnames[-(int)effect], fp); + else if (dbug_rxb) + { + struct re_se_params * p = &dbug_rxb->se_params[(int)effect]; + fprintf (fp, "%s(%d,%d)", efnames2[p->se], p->op1, p->op2); + } + else + fprintf (fp, "[complex op # %d]", (int)effect); +} + +/* These are so the regex.c regression tests will compile. */ +void +print_compiled_pattern (rxb) + struct re_pattern_buffer * rxb; +{ +} + +void +print_fastmap (fm) + char * fm; +{ +} + +#endif /* RX_DEBUG */ + + + +/* This page: Bitsets. Completely unintersting. */ + +RX_DECL int rx_bitset_is_equal (int, rx_Bitset, rx_Bitset); +RX_DECL int rx_bitset_is_subset (int, rx_Bitset, rx_Bitset); +RX_DECL int rx_bitset_empty (int, rx_Bitset); +RX_DECL void rx_bitset_null (int, rx_Bitset); +RX_DECL void rx_bitset_complement (int, rx_Bitset); +RX_DECL void rx_bitset_complement (int, rx_Bitset); +RX_DECL void rx_bitset_assign (int, rx_Bitset, rx_Bitset); +RX_DECL void rx_bitset_union (int, rx_Bitset, rx_Bitset); +RX_DECL void rx_bitset_intersection (int, rx_Bitset, rx_Bitset); +RX_DECL void rx_bitset_difference (int, rx_Bitset, rx_Bitset); +RX_DECL void rx_bitset_revdifference (int, rx_Bitset, rx_Bitset); +RX_DECL void rx_bitset_xor (int, rx_Bitset, rx_Bitset); +RX_DECL unsigned long + rx_bitset_hash (int, rx_Bitset); + +#ifdef __STDC__ +RX_DECL int +rx_bitset_is_equal (int size, rx_Bitset a, rx_Bitset b) +#else +RX_DECL int +rx_bitset_is_equal (size, a, b) + int size; + rx_Bitset a; + rx_Bitset b; +#endif +{ + int x; + RX_subset s = b[0]; + b[0] = ~a[0]; + + for (x = rx_bitset_numb_subsets(size) - 1; a[x] == b[x]; --x) + ; + + b[0] = s; + return !x && s == a[0]; +} + +#ifdef __STDC__ +RX_DECL int +rx_bitset_is_subset (int size, rx_Bitset a, rx_Bitset b) +#else +RX_DECL int +rx_bitset_is_subset (size, a, b) + int size; + rx_Bitset a; + rx_Bitset b; +#endif +{ + int x = rx_bitset_numb_subsets(size) - 1; + while (x-- && (a[x] & b[x]) == a[x]); + return x == -1; +} + + +#ifdef __STDC__ +RX_DECL int +rx_bitset_empty (int size, rx_Bitset set) +#else +RX_DECL int +rx_bitset_empty (size, set) + int size; + rx_Bitset set; +#endif +{ + int x; + RX_subset s = set[0]; + set[0] = 1; + for (x = rx_bitset_numb_subsets(size) - 1; !set[x]; --x) + ; + set[0] = s; + return !s; +} + +#ifdef __STDC__ +RX_DECL void +rx_bitset_null (int size, rx_Bitset b) +#else +RX_DECL void +rx_bitset_null (size, b) + int size; + rx_Bitset b; +#endif +{ + bzero (b, rx_sizeof_bitset(size)); +} + + +#ifdef __STDC__ +RX_DECL void +rx_bitset_universe (int size, rx_Bitset b) +#else +RX_DECL void +rx_bitset_universe (size, b) + int size; + rx_Bitset b; +#endif +{ + int x = rx_bitset_numb_subsets (size); + while (x--) + *b++ = ~(RX_subset)0; +} + + +#ifdef __STDC__ +RX_DECL void +rx_bitset_complement (int size, rx_Bitset b) +#else +RX_DECL void +rx_bitset_complement (size, b) + int size; + rx_Bitset b; +#endif +{ + int x = rx_bitset_numb_subsets (size); + while (x--) + { + *b = ~*b; + ++b; + } +} + + +#ifdef __STDC__ +RX_DECL void +rx_bitset_assign (int size, rx_Bitset a, rx_Bitset b) +#else +RX_DECL void +rx_bitset_assign (size, a, b) + int size; + rx_Bitset a; + rx_Bitset b; +#endif +{ + int x; + for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) + a[x] = b[x]; +} + +#ifdef __STDC__ +RX_DECL void +rx_bitset_union (int size, rx_Bitset a, rx_Bitset b) +#else +RX_DECL void +rx_bitset_union (size, a, b) + int size; + rx_Bitset a; + rx_Bitset b; +#endif +{ + int x; + for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) + a[x] |= b[x]; +} + + +#ifdef __STDC__ +RX_DECL void +rx_bitset_intersection (int size, + rx_Bitset a, rx_Bitset b) +#else +RX_DECL void +rx_bitset_intersection (size, a, b) + int size; + rx_Bitset a; + rx_Bitset b; +#endif +{ + int x; + for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) + a[x] &= b[x]; +} + + +#ifdef __STDC__ +RX_DECL void +rx_bitset_difference (int size, rx_Bitset a, rx_Bitset b) +#else +RX_DECL void +rx_bitset_difference (size, a, b) + int size; + rx_Bitset a; + rx_Bitset b; +#endif +{ + int x; + for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) + a[x] &= ~ b[x]; +} + + +#ifdef __STDC__ +RX_DECL void +rx_bitset_revdifference (int size, + rx_Bitset a, rx_Bitset b) +#else +RX_DECL void +rx_bitset_revdifference (size, a, b) + int size; + rx_Bitset a; + rx_Bitset b; +#endif +{ + int x; + for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) + a[x] = ~a[x] & b[x]; +} + +#ifdef __STDC__ +RX_DECL void +rx_bitset_xor (int size, rx_Bitset a, rx_Bitset b) +#else +RX_DECL void +rx_bitset_xor (size, a, b) + int size; + rx_Bitset a; + rx_Bitset b; +#endif +{ + int x; + for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) + a[x] ^= b[x]; +} + + +#ifdef __STDC__ +RX_DECL unsigned long +rx_bitset_hash (int size, rx_Bitset b) +#else +RX_DECL unsigned long +rx_bitset_hash (size, b) + int size; + rx_Bitset b; +#endif +{ + int x; + unsigned long hash = (unsigned long)rx_bitset_hash; + + for (x = rx_bitset_numb_subsets(size) - 1; x >= 0; --x) + hash ^= rx_bitset_subset_val(b, x); + + return hash; +} + +RX_DECL RX_subset rx_subset_singletons [RX_subset_bits] = +{ + 0x1, + 0x2, + 0x4, + 0x8, + 0x10, + 0x20, + 0x40, + 0x80, + 0x100, + 0x200, + 0x400, + 0x800, + 0x1000, + 0x2000, + 0x4000, + 0x8000, + 0x10000, + 0x20000, + 0x40000, + 0x80000, + 0x100000, + 0x200000, + 0x400000, + 0x800000, + 0x1000000, + 0x2000000, + 0x4000000, + 0x8000000, + 0x10000000, + 0x20000000, + 0x40000000, + 0x80000000 +}; + +#ifdef RX_DEBUG + +#ifdef __STDC__ +static void +print_cset (struct rx *rx, rx_Bitset cset, FILE * fp) +#else +static void +print_cset (rx, cset, fp) + struct rx *rx; + rx_Bitset cset; + FILE * fp; +#endif +{ + int x; + fputc ('[', fp); + for (x = 0; x < rx->local_cset_size; ++x) + if (RX_bitset_member (cset, x)) + { + if (isprint(x)) + fputc (x, fp); + else + fprintf (fp, "\\0%o ", x); + } + fputc (']', fp); +} + +#endif /* RX_DEBUG */ + + + +static unsigned long rx_hash_masks[4] = +{ + 0x12488421, + 0x96699669, + 0xbe7dd7eb, + 0xffffffff +}; + + +/* Hash tables */ +#ifdef __STDC__ +RX_DECL struct rx_hash_item * +rx_hash_find (struct rx_hash * table, + unsigned long hash, + void * value, + struct rx_hash_rules * rules) +#else +RX_DECL struct rx_hash_item * +rx_hash_find (table, hash, value, rules) + struct rx_hash * table; + unsigned long hash; + void * value; + struct rx_hash_rules * rules; +#endif +{ + rx_hash_eq eq = rules->eq; + int maskc = 0; + long mask = rx_hash_masks [0]; + int bucket = (hash & mask) % 13; + + while (table->children [bucket]) + { + table = table->children [bucket]; + ++maskc; + mask = rx_hash_masks[maskc]; + bucket = (hash & mask) % 13; + } + + { + struct rx_hash_item * it = table->buckets[bucket]; + while (it) + if (eq (it->data, value)) + return it; + else + it = it->next_same_hash; + } + + return 0; +} + +#ifdef __STDC__ +RX_DECL struct rx_hash_item * +rx_hash_store (struct rx_hash * table, + unsigned long hash, + void * value, + struct rx_hash_rules * rules) +#else +RX_DECL struct rx_hash_item * +rx_hash_store (table, hash, value, rules) + struct rx_hash * table; + unsigned long hash; + void * value; + struct rx_hash_rules * rules; +#endif +{ + rx_hash_eq eq = rules->eq; + int maskc = 0; + long mask = rx_hash_masks[0]; + int bucket = (hash & mask) % 13; + int depth = 0; + + while (table->children [bucket]) + { + table = table->children [bucket]; + ++maskc; + mask = rx_hash_masks[maskc]; + bucket = (hash & mask) % 13; + ++depth; + } + + { + struct rx_hash_item * it = table->buckets[bucket]; + while (it) + if (eq (it->data, value)) + return it; + else + it = it->next_same_hash; + } + + { + if ( (depth < 3) + && (table->bucket_size [bucket] >= 4)) + { + struct rx_hash * newtab = ((struct rx_hash *) + rules->hash_alloc (rules)); + if (!newtab) + goto add_to_bucket; + bzero (newtab, sizeof (*newtab)); + newtab->parent = table; + { + struct rx_hash_item * them = table->buckets[bucket]; + unsigned long newmask = rx_hash_masks[maskc + 1]; + while (them) + { + struct rx_hash_item * save = them->next_same_hash; + int new_buck = (them->hash & newmask) % 13; + them->next_same_hash = newtab->buckets[new_buck]; + newtab->buckets[new_buck] = them; + them->table = newtab; + them = save; + ++newtab->bucket_size[new_buck]; + ++newtab->refs; + } + table->refs = (table->refs - table->bucket_size[bucket] + 1); + table->bucket_size[bucket] = 0; + table->buckets[bucket] = 0; + table->children[bucket] = newtab; + table = newtab; + bucket = (hash & newmask) % 13; + } + } + } + add_to_bucket: + { + struct rx_hash_item * it = ((struct rx_hash_item *) + rules->hash_item_alloc (rules, value)); + if (!it) + return 0; + it->hash = hash; + it->table = table; + /* DATA and BINDING are to be set in hash_item_alloc */ + it->next_same_hash = table->buckets [bucket]; + table->buckets[bucket] = it; + ++table->bucket_size [bucket]; + ++table->refs; + return it; + } +} + + +#ifdef __STDC__ +RX_DECL void +rx_hash_free (struct rx_hash_item * it, struct rx_hash_rules * rules) +#else +RX_DECL void +rx_hash_free (it, rules) + struct rx_hash_item * it; + struct rx_hash_rules * rules; +#endif +{ + if (it) + { + struct rx_hash * table = it->table; + unsigned long hash = it->hash; + int depth = (table->parent + ? (table->parent->parent + ? (table->parent->parent->parent + ? 3 + : 2) + : 1) + : 0); + int bucket = (hash & rx_hash_masks [depth]) % 13; + struct rx_hash_item ** pos = &table->buckets [bucket]; + + while (*pos != it) + pos = &(*pos)->next_same_hash; + *pos = it->next_same_hash; + rules->free_hash_item (it, rules); + --table->bucket_size[bucket]; + --table->refs; + while (!table->refs && depth) + { + struct rx_hash * save = table; + table = table->parent; + --depth; + bucket = (hash & rx_hash_masks [depth]) % 13; + --table->refs; + table->children[bucket] = 0; + rules->free_hash (save, rules); + } + } +} + +#ifdef __STDC__ +RX_DECL void +rx_free_hash_table (struct rx_hash * tab, rx_hash_freefn freefn, + struct rx_hash_rules * rules) +#else +RX_DECL void +rx_free_hash_table (tab, freefn, rules) + struct rx_hash * tab; + rx_hash_freefn freefn; + struct rx_hash_rules * rules; +#endif +{ + int x; + + for (x = 0; x < 13; ++x) + if (tab->children[x]) + { + rx_free_hash_table (tab->children[x], freefn, rules); + rules->free_hash (tab->children[x], rules); + } + else + { + struct rx_hash_item * them = tab->buckets[x]; + while (them) + { + struct rx_hash_item * that = them; + them = that->next_same_hash; + freefn (that); + rules->free_hash_item (that, rules); + } + } +} + + + +/* Utilities for manipulating bitset represntations of characters sets. */ + +#ifdef __STDC__ +RX_DECL rx_Bitset +rx_cset (struct rx *rx) +#else +RX_DECL rx_Bitset +rx_cset (rx) + struct rx *rx; +#endif +{ + rx_Bitset b = (rx_Bitset) malloc (rx_sizeof_bitset (rx->local_cset_size)); + if (b) + rx_bitset_null (rx->local_cset_size, b); + return b; +} + + +#ifdef __STDC__ +RX_DECL rx_Bitset +rx_copy_cset (struct rx *rx, rx_Bitset a) +#else +RX_DECL rx_Bitset +rx_copy_cset (rx, a) + struct rx *rx; + rx_Bitset a; +#endif +{ + rx_Bitset cs = rx_cset (rx); + + if (cs) + rx_bitset_union (rx->local_cset_size, cs, a); + + return cs; +} + + +#ifdef __STDC__ +RX_DECL void +rx_free_cset (struct rx * rx, rx_Bitset c) +#else +RX_DECL void +rx_free_cset (rx, c) + struct rx * rx; + rx_Bitset c; +#endif +{ + if (c) + free ((char *)c); +} + + +/* Hash table memory allocation policy for the regexp compiler */ + +#ifdef __STDC__ +static struct rx_hash * +compiler_hash_alloc (struct rx_hash_rules * rules) +#else +static struct rx_hash * +compiler_hash_alloc (rules) + struct rx_hash_rules * rules; +#endif +{ + return (struct rx_hash *)malloc (sizeof (struct rx_hash)); +} + + +#ifdef __STDC__ +static struct rx_hash_item * +compiler_hash_item_alloc (struct rx_hash_rules * rules, void * value) +#else +static struct rx_hash_item * +compiler_hash_item_alloc (rules, value) + struct rx_hash_rules * rules; + void * value; +#endif +{ + struct rx_hash_item * it; + it = (struct rx_hash_item *)malloc (sizeof (*it)); + if (it) + { + it->data = value; + it->binding = 0; + } + return it; +} + +#ifdef __STDC__ +static void +compiler_free_hash (struct rx_hash * tab, + struct rx_hash_rules * rules) +#else +static void +compiler_free_hash (tab, rules) + struct rx_hash * tab; + struct rx_hash_rules * rules; +#endif +{ + free ((char *)tab); +} + + +#ifdef __STDC__ +static void +compiler_free_hash_item (struct rx_hash_item * item, + struct rx_hash_rules * rules) +#else +static void +compiler_free_hash_item (item, rules) + struct rx_hash_item * item; + struct rx_hash_rules * rules; +#endif +{ + free ((char *)item); +} + + +/* This page: REXP_NODE (expression tree) structures. */ + +#ifdef __STDC__ +RX_DECL struct rexp_node * +rexp_node (struct rx *rx, + enum rexp_node_type type) +#else +RX_DECL struct rexp_node * +rexp_node (rx, type) + struct rx *rx; + enum rexp_node_type type; +#endif +{ + struct rexp_node *n; + + n = (struct rexp_node *)malloc (sizeof (*n)); + if (n) + { + bzero (n, sizeof (*n)); + n->type = type; + } + return n; +} + + +/* free_rexp_node assumes that the bitset passed to rx_mk_r_cset + * can be freed using rx_free_cset. + */ +#ifdef __STDC__ +RX_DECL struct rexp_node * +rx_mk_r_cset (struct rx * rx, + rx_Bitset b) +#else +RX_DECL struct rexp_node * +rx_mk_r_cset (rx, b) + struct rx * rx; + rx_Bitset b; +#endif +{ + struct rexp_node * n = rexp_node (rx, r_cset); + if (n) + n->params.cset = b; + return n; +} + +#ifdef __STDC__ +RX_DECL struct rexp_node * +rx_mk_r_concat (struct rx * rx, + struct rexp_node * a, + struct rexp_node * b) +#else +RX_DECL struct rexp_node * +rx_mk_r_concat (rx, a, b) + struct rx * rx; + struct rexp_node * a; + struct rexp_node * b; +#endif +{ + struct rexp_node * n = rexp_node (rx, r_concat); + if (n) + { + n->params.pair.left = a; + n->params.pair.right = b; + } + return n; +} + + +#ifdef __STDC__ +RX_DECL struct rexp_node * +rx_mk_r_alternate (struct rx * rx, + struct rexp_node * a, + struct rexp_node * b) +#else +RX_DECL struct rexp_node * +rx_mk_r_alternate (rx, a, b) + struct rx * rx; + struct rexp_node * a; + struct rexp_node * b; +#endif +{ + struct rexp_node * n = rexp_node (rx, r_alternate); + if (n) + { + n->params.pair.left = a; + n->params.pair.right = b; + } + return n; +} + + +#ifdef __STDC__ +RX_DECL struct rexp_node * +rx_mk_r_opt (struct rx * rx, + struct rexp_node * a) +#else +RX_DECL struct rexp_node * +rx_mk_r_opt (rx, a) + struct rx * rx; + struct rexp_node * a; +#endif +{ + struct rexp_node * n = rexp_node (rx, r_opt); + if (n) + { + n->params.pair.left = a; + n->params.pair.right = 0; + } + return n; +} + +#ifdef __STDC__ +RX_DECL struct rexp_node * +rx_mk_r_star (struct rx * rx, + struct rexp_node * a) +#else +RX_DECL struct rexp_node * +rx_mk_r_star (rx, a) + struct rx * rx; + struct rexp_node * a; +#endif +{ + struct rexp_node * n = rexp_node (rx, r_star); + if (n) + { + n->params.pair.left = a; + n->params.pair.right = 0; + } + return n; +} + + +#ifdef __STDC__ +RX_DECL struct rexp_node * +rx_mk_r_2phase_star (struct rx * rx, |