Add in a bunch of junk. Busybox now compiles (except for mkfs.minix and

fsck.minix).  Of course, it doesn't link yet due to missing functions, but
hey...  At least it is now easy to see what isn't working. :-)
 -Erik

2 files changed, 7539 insertions, 0 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;