Useful add-on libraries

10 files changed, 4490 insertions, 0 deletions

diff --git a/avl-1.4.0/ChangeLog b/avl-1.4.0/ChangeLog
new file mode 100644
index 0000000..e31a7c2
--- /dev/null
+++ b/avl-1.4.0/ChangeLog
@@ -0,0 +1,181 @@
+Sat Aug  7 18:32:43 1999  Ben Pfaff  <blp@gnu.org>
+
+	Implemented red-black tree library.	
+	* Makefile.am: Add rb.c, rb.h in appropriate places.
+	* README: Update.
+	* rb.c: New file.
+	* rb.h: Ditto.
+	* avl.texinfo: Revised.
+
+	* THANKS: Update.
+	* TODO: Update.
+	
+	* avl.c: In several places, replaced usage of comma operator with
+	a proper statement block.
+	* avlt.c: Ditto.
+	* avltr.c: Ditto.
+
+	* avl.h: (AVL_TRAVERSER_INIT) New macro.
+	(avl_init_traverser) New function-like macro.
+	* avlt.h: (AVLT_TRAVERSER_INIT) New macro.
+	(avlt_init_traverser) New function-like macro.
+	* avltr.h: (AVLTR_TRAVERSER_INIT) New macro.
+	(avltr_init_traverser) New function-like macro.
+	* thread-test.c: (main) Use AVL_TRAVERSER_INIT.
+
+	* Made version 1.4.0.
+
+Sat Jul 31 12:39:54 1999  Ben Pfaff  <blp@gnu.org>
+
+	* avl.texinfo: Update suggested by Jonathan Roy <roy@idle.com>.
+
+Tue May 25 12:20:43 1999  Ben Pfaff  <blp@gnu.org>
+
+	* avl.c: (avl_delete) Make work properly for empty tree.  Furrfu!
+	I should have noticed this before.
+
+Mon May 17 11:32:56 1999  Ben Pfaff  <blp@gnu.org>
+
+	* Makefile.am: Don't require texi2html.  Use $(MAKEINFO)
+	variable.  Thanks to Alexandre Oliva <oliva@dcc.unicamp.br>.
+
+Sat May 15 23:47:14 1999  Ben Pfaff  <blp@gnu.org>
+
+	* Updated copyright dates in several files.
+
+	* Made version 1.3.0.
+
+Sat May 15 21:44:54 1999  Ben Pfaff  <blp@gnu.org>
+
+	* avl.c, avlt.c, avltr.c: In many places replaced assert (p) by
+	assert (p != NULL).  Believe it or not, the former is not valid
+	ANSI C.
+
+	Thanks to "Ficarra, David W, NNAD" <dficarra@att.com> for pointing
+	out the following two sets of bugs.
+	* avl.c: (avl_probe) Fix order of assignment and assertion.
+	* avlt.c: (avlt_walk, avlt_probe, avlt_find) Ditto.
+	* avltr.c: (avltr_probe, avltr_find) Ditto.
+	
+	* avlt.c: (avlt_find, avlt_delete) Check for empty tree.
+	* avltr.c: (avltr_probe) Ditto.
+	
+	* avl.c, avlt.c, avltr.c, thread-test.c: Change test code to only
+	perform a limited number of iterations to facilitate automated
+	testing.
+
+	* avl.c: (avl_find_close) New function contributed by Thomas
+	Binder <binder@iue.tuwien.ac.at>.
+	* avlt.c: (avlt_find_close) Ditto.
+	* avltr.c: (avltr_find_close) Ditto.
+
+	* avl.texinfo: Update.
+
+	libavl is now automake/autoconfiscated.  Contributed by Alexandre
+	Oliva <oliva@dcc.unicamp.br>.
+	* AUTHORS: New file.
+	* Makefile: Now automake-generated.
+	* INSTALL: New file.
+	* Makefile.am: New file.
+	* Makefile.in: New file.
+	* THANKS: New file.
+	* config.h.in: New file.
+	* configure.in: New file.
+	* configure: New file.
+	* install-sh: New file.
+	* missing: New file.
+	* mkinstalldirs: New file.
+	* texinfo.tex: New file.
+	
+Tue May 11 13:33:20 1999  Ben Pfaff  <blp@gnu.org>
+
+	* avl.texinfo: Fix typos.  Thanks to onTy Toom <onty@yahoo.com>
+	for pointing these out.
+
+	* Made version 1.2.9.
+	
+Sun Mar 14 13:39:16 1999  Ben Pfaff  <blp@gnu.org>
+
+	* avl.c: Fixed two occurrences of = that should have been == in
+	assertions.  Thanks to Girish Zambre <gzambre@sprynet.com> for
+	pointing out this problem.
+
+	* avl.c, avlt.c, avltr.c: __attribute__ must follow declarations
+	for gcc 2.7.x.
+
+	* Made version 1.2.8.
+
+Sun Mar 14 13:38:29 1999  Ben Pfaff  <blp@gnu.org>
+
+	* TODO: Add some comments from David Kastrup
+	<dak@neuroinformatik.ruhr-uni-bochum.de>.
+
+	* Made version 1.2.7.
+
+Tue Jan 12 10:16:05 1999  Ben Pfaff  <blp@gnu.org>
+
+	* avl.texinfo: Add skip lists as alternative to AVL trees.  Thanks
+	to Ron Pfeifle <rpfeifle@aw.sgi.com>.
+
+	* Made version 1.2.6.
+
+Sun Jan 10 15:37:57 1999  Ben Pfaff  <blp@gnu.org>
+
+	* avl.texinfo: Elaborated description of distinction between
+	threaded and unthreaded trees at request of several.
+
+	* Made version 1.2.5.
+
+Sun Nov 22 13:36:58 1998  Ben Pfaff  <blp@gnu.org>
+
+	* avl.texinfo: Updates suggested by Jason Eisner
+	<jeisner@linc.cis.upenn.edu>.
+
+	* Made version 1.2.4.
+
+Sun Oct 18 10:26:08 1998  Ben Pfaff  <pfaffben@pilot.msu.edu>
+
+	* TODO: New file.
+
+	* avl.c: (xmalloc) Don't declare xmalloc if HAVE_XMALLOC is
+	defined.  By default on error, print a message to stderr and exit,
+	rather than calling abort() as before.
+	* avlt.c: (xmalloc) Same.
+	* avltr.c: (xmalloc) Same.
+
+	* Made version 1.2.3.
+
+Thu Sep  3 13:58:55 1998  Ben Pfaff  <pfaffben@pilot.msu.edu>
+
+	* README: Update.
+
+	* avl.c: (avl_delete) Minor efficiency fixes; removed redundant
+	comparison.
+
+	* avlt.c: (avl_delete) Minor efficiency fix.
+	* avltr.c: (avl_delete) Same change.
+
+	* avl.texi: Update.
+
+	* Made version 1.2.2.
+
+Thu Jun 11 15:13:02 1998  Ben Pfaff  <pfaffben@pilot.msu.edu>
+
+	* avl.c: Don't #define unused when PSPP is defined.
+	(force_avl_delete) Rename avl_force_delete.
+
+	* avlt.c: (force_avlt_delete) Rename avlt_force_delete.
+
+	* avltr.c: (force_avltr_delete) Rename avltr_force_delete.
+
+	* Made version 1.2.1.
+
+Thu Jun 11 14:43:30 1998  Ben Pfaff  <pfaffben@pilot.msu.edu>
+
+	* Version 1.2.0: First GNU release.
+
+----------------------------------------------------------------------
+Local Variables:
+mode: change-log
+version-control: never
+End:
diff --git a/avl-1.4.0/Makefile.in b/avl-1.4.0/Makefile.in
new file mode 100644
index 0000000..2d041aa
--- /dev/null
+++ b/avl-1.4.0/Makefile.in
@@ -0,0 +1,572 @@
+# Makefile.in generated automatically by automake 1.4 from Makefile.am
+
+# Copyright (C) 1994, 1995-8, 1999 Free Software Foundation, Inc.
+# This Makefile.in is free software; the Free Software Foundation
+# gives unlimited permission to copy and/or distribute it,
+# with or without modifications, as long as this notice is preserved.
+
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY, to the extent permitted by law; without
+# even the implied warranty of MERCHANTABILITY or FITNESS FOR A
+# PARTICULAR PURPOSE.
+
+
+SHELL = @SHELL@
+
+srcdir = @srcdir@
+top_srcdir = @top_srcdir@
+VPATH = @srcdir@
+prefix = @prefix@
+exec_prefix = @exec_prefix@
+
+bindir = @bindir@
+sbindir = @sbindir@
+libexecdir = @libexecdir@
+datadir = @datadir@
+sysconfdir = @sysconfdir@
+sharedstatedir = @sharedstatedir@
+localstatedir = @localstatedir@
+libdir = @libdir@
+infodir = @infodir@
+mandir = @mandir@
+includedir = @includedir@
+oldincludedir = /usr/include
+
+DESTDIR =
+
+pkgdatadir = $(datadir)/@PACKAGE@
+pkglibdir = $(libdir)/@PACKAGE@
+pkgincludedir = $(includedir)/@PACKAGE@
+
+top_builddir = .
+
+ACLOCAL = @ACLOCAL@
+AUTOCONF = @AUTOCONF@
+AUTOMAKE = @AUTOMAKE@
+AUTOHEADER = @AUTOHEADER@
+
+INSTALL = @INSTALL@
+INSTALL_PROGRAM = @INSTALL_PROGRAM@ $(AM_INSTALL_PROGRAM_FLAGS)
+INSTALL_DATA = @INSTALL_DATA@
+INSTALL_SCRIPT = @INSTALL_SCRIPT@
+transform = @program_transform_name@
+
+NORMAL_INSTALL = :
+PRE_INSTALL = :
+POST_INSTALL = :
+NORMAL_UNINSTALL = :
+PRE_UNINSTALL = :
+POST_UNINSTALL = :
+CC = @CC@
+MAKEINFO = @MAKEINFO@
+PACKAGE = @PACKAGE@
+RANLIB = @RANLIB@
+VERSION = @VERSION@
+
+AUTOMAKE_OPTIONS = gnits 
+
+include_HEADERS = avl.h avlt.h avltr.h rb.h
+
+lib_LIBRARIES = libavl.a
+libavl_a_SOURCES = avl.c avlt.c avltr.c rb.c
+
+info_TEXINFOS = avl.texinfo
+noinst_DATA = avl.html avl.text
+
+EXTRA_PROGRAMS = avl-test avlt-test avltr-test thread-test rb-test
+DISTCLEANFILES = $(EXTRA_PROGRAMS) $(BUILT_SOURCES)
+
+BUILT_SOURCES = avl-test.c avlt-test.c avltr-test.c rb-test.c
+
+TESTS = avl-test avlt-test avltr-test thread-test rb-test
+
+thread_test_LDADD = libavl.a
+ACLOCAL_M4 = $(top_srcdir)/aclocal.m4
+mkinstalldirs = $(SHELL) $(top_srcdir)/mkinstalldirs
+CONFIG_CLEAN_FILES = 
+LIBRARIES =  $(lib_LIBRARIES)
+
+
+DEFS = @DEFS@ -I. -I$(srcdir) 
+CPPFLAGS = @CPPFLAGS@
+LDFLAGS = @LDFLAGS@
+LIBS = @LIBS@
+libavl_a_LIBADD = 
+libavl_a_OBJECTS =  avl.o avlt.o avltr.o rb.o
+AR = ar
+avl_test_SOURCES = avl-test.c
+avl_test_OBJECTS =  avl-test.o
+avl_test_LDADD = $(LDADD)
+avl_test_DEPENDENCIES = 
+avl_test_LDFLAGS = 
+avlt_test_SOURCES = avlt-test.c
+avlt_test_OBJECTS =  avlt-test.o
+avlt_test_LDADD = $(LDADD)
+avlt_test_DEPENDENCIES = 
+avlt_test_LDFLAGS = 
+avltr_test_SOURCES = avltr-test.c
+avltr_test_OBJECTS =  avltr-test.o
+avltr_test_LDADD = $(LDADD)
+avltr_test_DEPENDENCIES = 
+avltr_test_LDFLAGS = 
+thread_test_SOURCES = thread-test.c
+thread_test_OBJECTS =  thread-test.o
+thread_test_DEPENDENCIES =  libavl.a
+thread_test_LDFLAGS = 
+rb_test_SOURCES = rb-test.c
+rb_test_OBJECTS =  rb-test.o
+rb_test_LDADD = $(LDADD)
+rb_test_DEPENDENCIES = 
+rb_test_LDFLAGS = 
+CFLAGS = @CFLAGS@
+COMPILE = $(CC) $(DEFS) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS)
+CCLD = $(CC)
+LINK = $(CCLD) $(AM_CFLAGS) $(CFLAGS) $(LDFLAGS) -o $@
+TEXI2DVI = texi2dvi
+INFO_DEPS = avl.info
+DVIS = avl.dvi
+TEXINFOS = avl.texinfo
+DATA =  $(noinst_DATA)
+
+HEADERS =  $(include_HEADERS)
+
+DIST_COMMON =  README AUTHORS COPYING ChangeLog INSTALL Makefile.am \
+Makefile.in NEWS THANKS TODO aclocal.m4 configure configure.in \
+install-sh missing mkinstalldirs texinfo.tex
+
+
+DISTFILES = $(DIST_COMMON) $(SOURCES) $(HEADERS) $(TEXINFOS) $(EXTRA_DIST)
+
+TAR = tar
+GZIP_ENV = --best
+SOURCES = $(libavl_a_SOURCES) avl-test.c avlt-test.c avltr-test.c thread-test.c rb-test.c
+OBJECTS = $(libavl_a_OBJECTS) avl-test.o avlt-test.o avltr-test.o thread-test.o rb-test.o
+
+all: all-redirect
+.SUFFIXES:
+.SUFFIXES: .S .c .dvi .info .o .ps .s .texi .texinfo .txi
+$(srcdir)/Makefile.in: Makefile.am $(top_srcdir)/configure.in $(ACLOCAL_M4) 
+	cd $(top_srcdir) && $(AUTOMAKE) --gnits --include-deps Makefile
+
+Makefile: $(srcdir)/Makefile.in  $(top_builddir)/config.status
+	cd $(top_builddir) \
+	  && CONFIG_FILES=$@ CONFIG_HEADERS= $(SHELL) ./config.status
+
+$(ACLOCAL_M4):  configure.in 
+	cd $(srcdir) && $(ACLOCAL)
+
+config.status: $(srcdir)/configure $(CONFIG_STATUS_DEPENDENCIES)
+	$(SHELL) ./config.status --recheck
+$(srcdir)/configure: $(srcdir)/configure.in $(ACLOCAL_M4) $(CONFIGURE_DEPENDENCIES)
+	cd $(srcdir) && $(AUTOCONF)
+
+mostlyclean-libLIBRARIES:
+
+clean-libLIBRARIES:
+	-test -z "$(lib_LIBRARIES)" || rm -f $(lib_LIBRARIES)
+
+distclean-libLIBRARIES:
+
+maintainer-clean-libLIBRARIES:
+
+install-libLIBRARIES: $(lib_LIBRARIES)
+	@$(NORMAL_INSTALL)
+	$(mkinstalldirs) $(DESTDIR)$(libdir)
+	@list='$(lib_LIBRARIES)'; for p in $$list; do \
+	  if test -f $$p; then \
+	    echo " $(INSTALL_DATA) $$p $(DESTDIR)$(libdir)/$$p"; \
+	    $(INSTALL_DATA) $$p $(DESTDIR)$(libdir)/$$p; \
+	  else :; fi; \
+	done
+	@$(POST_INSTALL)
+	@list='$(lib_LIBRARIES)'; for p in $$list; do \
+	  if test -f $$p; then \
+	    echo " $(RANLIB) $(DESTDIR)$(libdir)/$$p"; \
+	    $(RANLIB) $(DESTDIR)$(libdir)/$$p; \
+	  else :; fi; \
+	done
+
+uninstall-libLIBRARIES:
+	@$(NORMAL_UNINSTALL)
+	list='$(lib_LIBRARIES)'; for p in $$list; do \
+	  rm -f $(DESTDIR)$(libdir)/$$p; \
+	done
+
+.c.o:
+	$(COMPILE) -c $<
+
+.s.o:
+	$(COMPILE) -c $<
+
+.S.o:
+	$(COMPILE) -c $<
+
+mostlyclean-compile:
+	-rm -f *.o core *.core
+
+clean-compile:
+
+distclean-compile:
+	-rm -f *.tab.c
+
+maintainer-clean-compile:
+
+libavl.a: $(libavl_a_OBJECTS) $(libavl_a_DEPENDENCIES)
+	-rm -f libavl.a
+	$(AR) cru libavl.a $(libavl_a_OBJECTS) $(libavl_a_LIBADD)
+	$(RANLIB) libavl.a
+
+avl-test: $(avl_test_OBJECTS) $(avl_test_DEPENDENCIES)
+	@rm -f avl-test
+	$(LINK) $(avl_test_LDFLAGS) $(avl_test_OBJECTS) $(avl_test_LDADD) $(LIBS)
+
+avlt-test: $(avlt_test_OBJECTS) $(avlt_test_DEPENDENCIES)
+	@rm -f avlt-test
+	$(LINK) $(avlt_test_LDFLAGS) $(avlt_test_OBJECTS) $(avlt_test_LDADD) $(LIBS)
+
+avltr-test: $(avltr_test_OBJECTS) $(avltr_test_DEPENDENCIES)
+	@rm -f avltr-test
+	$(LINK) $(avltr_test_LDFLAGS) $(avltr_test_OBJECTS) $(avltr_test_LDADD) $(LIBS)
+
+thread-test: $(thread_test_OBJECTS) $(thread_test_DEPENDENCIES)
+	@rm -f thread-test
+	$(LINK) $(thread_test_LDFLAGS) $(thread_test_OBJECTS) $(thread_test_LDADD) $(LIBS)
+
+rb-test: $(rb_test_OBJECTS) $(rb_test_DEPENDENCIES)
+	@rm -f rb-test
+	$(LINK) $(rb_test_LDFLAGS) $(rb_test_OBJECTS) $(rb_test_LDADD) $(LIBS)
+
+avl.info: avl.texinfo
+avl.dvi: avl.texinfo
+
+
+DVIPS = dvips
+
+.texi.info:
+	@cd $(srcdir) && rm -f $@ $@-[0-9] $@-[0-9][0-9]
+	cd $(srcdir) \
+	  && $(MAKEINFO) `echo $< | sed 's,.*/,,'`
+
+.texi.dvi:
+	TEXINPUTS=.:$$TEXINPUTS \
+	  MAKEINFO='$(MAKEINFO) -I $(srcdir)' $(TEXI2DVI) $<
+
+.texi:
+	@cd $(srcdir) && rm -f $@ $@-[0-9] $@-[0-9][0-9]
+	cd $(srcdir) \
+	  && $(MAKEINFO) `echo $< | sed 's,.*/,,'`
+
+.texinfo.info:
+	@cd $(srcdir) && rm -f $@ $@-[0-9] $@-[0-9][0-9]
+	cd $(srcdir) \
+	  && $(MAKEINFO) `echo $< | sed 's,.*/,,'`
+
+.texinfo:
+	@cd $(srcdir) && rm -f $@ $@-[0-9] $@-[0-9][0-9]
+	cd $(srcdir) \
+	  && $(MAKEINFO) `echo $< | sed 's,.*/,,'`
+
+.texinfo.dvi:
+	TEXINPUTS=.:$$TEXINPUTS \
+	  MAKEINFO='$(MAKEINFO) -I $(srcdir)' $(TEXI2DVI) $<
+
+.txi.info:
+	@cd $(srcdir) && rm -f $@ $@-[0-9] $@-[0-9][0-9]
+	cd $(srcdir) \
+	  && $(MAKEINFO) `echo $< | sed 's,.*/,,'`
+
+.txi.dvi:
+	TEXINPUTS=.:$$TEXINPUTS \
+	  MAKEINFO='$(MAKEINFO) -I $(srcdir)' $(TEXI2DVI) $<
+
+.txi:
+	@cd $(srcdir) && rm -f $@ $@-[0-9] $@-[0-9][0-9]
+	cd $(srcdir) \
+	  && $(MAKEINFO) `echo $< | sed 's,.*/,,'`
+.dvi.ps:
+	$(DVIPS) $< -o $@
+
+install-info-am: $(INFO_DEPS)
+	@$(NORMAL_INSTALL)
+	$(mkinstalldirs) $(DESTDIR)$(infodir)
+	@list='$(INFO_DEPS)'; \
+	for file in $$list; do \
+	  d=$(srcdir); \
+	  for ifile in `cd $$d && echo $$file $$file-[0-9] $$file-[0-9][0-9]`; do \
+	    if test -f $$d/$$ifile; then \
+	      echo " $(INSTALL_DATA) $$d/$$ifile $(DESTDIR)$(infodir)/$$ifile"; \
+	      $(INSTALL_DATA) $$d/$$ifile $(DESTDIR)$(infodir)/$$ifile; \
+	    else : ; fi; \
+	  done; \
+	done
+	@$(POST_INSTALL)
+	@if $(SHELL) -c 'install-info --version | sed 1q | fgrep -s -v -i debian' >/dev/null 2>&1; then \
+	  list='$(INFO_DEPS)'; \
+	  for file in $$list; do \
+	    echo " install-info --info-dir=$(DESTDIR)$(infodir) $(DESTDIR)$(infodir)/$$file";\
+	    install-info --info-dir=$(DESTDIR)$(infodir) $(DESTDIR)$(infodir)/$$file || :;\
+	  done; \
+	else : ; fi
+
+uninstall-info:
+	$(PRE_UNINSTALL)
+	@if $(SHELL) -c 'install-info --version | sed 1q | fgrep -s -v -i debian' >/dev/null 2>&1; then \
+	  ii=yes; \
+	else ii=; fi; \
+	list='$(INFO_DEPS)'; \
+	for file in $$list; do \
+	  test -z "$ii" \
+	    || install-info --info-dir=$(DESTDIR)$(infodir) --remove $$file; \
+	done
+	@$(NORMAL_UNINSTALL)
+	list='$(INFO_DEPS)'; \
+	for file in $$list; do \
+	  (cd $(DESTDIR)$(infodir) && rm -f $$file $$file-[0-9] $$file-[0-9][0-9]); \
+	done
+
+dist-info: $(INFO_DEPS)
+	list='$(INFO_DEPS)'; \
+	for base in $$list; do \
+	  d=$(srcdir); \
+	  for file in `cd $$d && eval echo $$base*`; do \
+	    test -f $(distdir)/$$file \
+	    || ln $$d/$$file $(distdir)/$$file 2> /dev/null \
+	    || cp -p $$d/$$file $(distdir)/$$file; \
+	  done; \
+	done
+
+mostlyclean-aminfo:
+	-rm -f avl.aux avl.cp avl.cps avl.dvi avl.fn avl.fns avl.ky avl.kys \
+	  avl.ps avl.log avl.pg avl.toc avl.tp avl.tps avl.vr avl.vrs \
+	  avl.op avl.tr avl.cv avl.cn
+
+clean-aminfo:
+
+distclean-aminfo:
+
+maintainer-clean-aminfo:
+	cd $(srcdir) && for i in $(INFO_DEPS); do \
+	  rm -f $$i; \
+	  if test "`echo $$i-[0-9]*`" != "$$i-[0-9]*"; then \
+	    rm -f $$i-[0-9]*; \
+	  fi; \
+	done
+
+install-includeHEADERS: $(include_HEADERS)
+	@$(NORMAL_INSTALL)
+	$(mkinstalldirs) $(DESTDIR)$(includedir)
+	@list='$(include_HEADERS)'; for p in $$list; do \
+	  if test -f "$$p"; then d= ; else d="$(srcdir)/"; fi; \
+	  echo " $(INSTALL_DATA) $$d$$p $(DESTDIR)$(includedir)/$$p"; \
+	  $(INSTALL_DATA) $$d$$p $(DESTDIR)$(includedir)/$$p; \
+	done
+
+uninstall-includeHEADERS:
+	@$(NORMAL_UNINSTALL)
+	list='$(include_HEADERS)'; for p in $$list; do \
+	  rm -f $(DESTDIR)$(includedir)/$$p; \
+	done
+
+tags: TAGS
+
+ID: $(HEADERS) $(SOURCES) $(LISP)
+	list='$(SOURCES) $(HEADERS)'; \
+	unique=`for i in $$list; do echo $$i; done | \
+	  awk '    { files[$$0] = 1; } \
+	       END { for (i in files) print i; }'`; \
+	here=`pwd` && cd $(srcdir) \
+	  && mkid -f$$here/ID $$unique $(LISP)
+
+TAGS:  $(HEADERS) $(SOURCES)  $(TAGS_DEPENDENCIES) $(LISP)
+	tags=; \
+	here=`pwd`; \
+	list='$(SOURCES) $(HEADERS)'; \
+	unique=`for i in $$list; do echo $$i; done | \
+	  awk '    { files[$$0] = 1; } \
+	       END { for (i in files) print i; }'`; \
+	test -z "$(ETAGS_ARGS)$$unique$(LISP)$$tags" \
+	  || (cd $(srcdir) && etags $(ETAGS_ARGS) $$tags  $$unique $(LISP) -o $$here/TAGS)
+
+mostlyclean-tags:
+
+clean-tags:
+
+distclean-tags:
+	-rm -f TAGS ID
+
+maintainer-clean-tags:
+
+distdir = $(PACKAGE)-$(VERSION)
+top_distdir = $(distdir)
+
+# This target untars the dist file and tries a VPATH configuration.  Then
+# it guarantees that the distribution is self-contained by making another
+# tarfile.
+distcheck: dist
+	-rm -rf $(distdir)
+	GZIP=$(GZIP_ENV) $(TAR) zxf $(distdir).tar.gz
+	mkdir $(distdir)/=build
+	mkdir $(distdir)/=inst
+	dc_install_base=`cd $(distdir)/=inst && pwd`; \
+	cd $(distdir)/=build \
+	  && ../configure --srcdir=.. --prefix=$$dc_install_base \
+	  && $(MAKE) $(AM_MAKEFLAGS) \
+	  && $(MAKE) $(AM_MAKEFLAGS) dvi \
+	  && $(MAKE) $(AM_MAKEFLAGS) check \
+	  && $(MAKE) $(AM_MAKEFLAGS) install \
+	  && $(MAKE) $(AM_MAKEFLAGS) installcheck \
+	  && $(MAKE) $(AM_MAKEFLAGS) dist
+	-rm -rf $(distdir)
+	@banner="$(distdir).tar.gz is ready for distribution"; \
+	dashes=`echo "$$banner" | sed s/./=/g`; \
+	echo "$$dashes"; \
+	echo "$$banner"; \
+	echo "$$dashes"
+dist: distdir
+	-chmod -R a+r $(distdir)
+	GZIP=$(GZIP_ENV) $(TAR) chozf $(distdir).tar.gz $(distdir)
+	-rm -rf $(distdir)
+dist-all: distdir
+	-chmod -R a+r $(distdir)
+	GZIP=$(GZIP_ENV) $(TAR) chozf $(distdir).tar.gz $(distdir)
+	-rm -rf $(distdir)
+distdir: $(DISTFILES)
+	@if sed 15q $(srcdir)/NEWS | fgrep -e "$(VERSION)" > /dev/null; then :; else \
+	  echo "NEWS not updated; not releasing" 1>&2; \
+	  exit 1; \
+	fi
+	-rm -rf $(distdir)
+	mkdir $(distdir)
+	-chmod 777 $(distdir)
+	@for file in $(DISTFILES); do \
+	  d=$(srcdir); \
+	  if test -d $$d/$$file; then \
+	    cp -pr $$d/$$file $(distdir)/$$file; \
+	  else \
+	    test -f $(distdir)/$$file \
+	    || ln $$d/$$file $(distdir)/$$file 2> /dev/null \
+	    || cp -p $$d/$$file $(distdir)/$$file || :; \
+	  fi; \
+	done
+	$(MAKE) $(AM_MAKEFLAGS) top_distdir="$(top_distdir)" distdir="$(distdir)" dist-info
+
+check-TESTS: $(TESTS)
+	@failed=0; all=0; \
+	srcdir=$(srcdir); export srcdir; \
+	for tst in $(TESTS); do \
+	  if test -f $$tst; then dir=.; \
+	  else dir="$(srcdir)"; fi; \
+	  if $(TESTS_ENVIRONMENT) $$dir/$$tst; then \
+	    all=`expr $$all + 1`; \
+	    echo "PASS: $$tst"; \
+	  elif test $$? -ne 77; then \
+	    all=`expr $$all + 1`; \
+	    failed=`expr $$failed + 1`; \
+	    echo "FAIL: $$tst"; \
+	  fi; \
+	done; \
+	if test "$$failed" -eq 0; then \
+	  banner="All $$all tests passed"; \
+	else \
+	  banner="$$failed of $$all tests failed"; \
+	fi; \
+	dashes=`echo "$$banner" | sed s/./=/g`; \
+	echo "$$dashes"; \
+	echo "$$banner"; \
+	echo "$$dashes"; \
+	test "$$failed" -eq 0
+info-am: $(INFO_DEPS)
+info: info-am
+dvi-am: $(DVIS)
+dvi: dvi-am
+check-am: all-am
+	$(MAKE) $(AM_MAKEFLAGS) check-TESTS
+check: check-am
+installcheck-am:
+installcheck: installcheck-am
+install-exec-am: install-libLIBRARIES
+install-exec: install-exec-am
+
+install-data-am: install-info-am install-includeHEADERS
+install-data: install-data-am
+
+install-am: all-am
+	@$(MAKE) $(AM_MAKEFLAGS) install-exec-am install-data-am
+install: install-am
+uninstall-am: uninstall-libLIBRARIES uninstall-info \
+		uninstall-includeHEADERS
+uninstall: uninstall-am
+all-am: Makefile $(INFO_DEPS) $(LIBRARIES) $(DATA) $(HEADERS)
+all-redirect: all-am
+install-strip:
+	$(MAKE) $(AM_MAKEFLAGS) AM_INSTALL_PROGRAM_FLAGS=-s install
+installdirs:
+	$(mkinstalldirs)  $(DESTDIR)$(libdir) $(DESTDIR)$(infodir) \
+		$(DESTDIR)$(includedir)
+
+
+mostlyclean-generic:
+
+clean-generic:
+
+distclean-generic:
+	-rm -f Makefile $(CONFIG_CLEAN_FILES)
+	-rm -f config.cache config.log stamp-h stamp-h[0-9]*
+	-test -z "$(DISTCLEANFILES)" || rm -f $(DISTCLEANFILES)
+
+maintainer-clean-generic:
+	-test -z "$(BUILT_SOURCES)" || rm -f $(BUILT_SOURCES)
+mostlyclean-am:  mostlyclean-libLIBRARIES mostlyclean-compile \
+		mostlyclean-aminfo mostlyclean-tags mostlyclean-generic
+
+mostlyclean: mostlyclean-am
+
+clean-am:  clean-libLIBRARIES clean-compile clean-aminfo clean-tags \
+		clean-generic mostlyclean-am
+
+clean: clean-am
+
+distclean-am:  distclean-libLIBRARIES distclean-compile distclean-aminfo \
+		distclean-tags distclean-generic clean-am
+
+distclean: distclean-am
+	-rm -f config.status
+
+maintainer-clean-am:  maintainer-clean-libLIBRARIES \
+		maintainer-clean-compile maintainer-clean-aminfo \
+		maintainer-clean-tags maintainer-clean-generic \
+		distclean-am
+	@echo "This command is intended for maintainers to use;"
+	@echo "it deletes files that may require special tools to rebuild."
+
+maintainer-clean: maintainer-clean-am
+	-rm -f config.status
+
+.PHONY: mostlyclean-libLIBRARIES distclean-libLIBRARIES \
+clean-libLIBRARIES maintainer-clean-libLIBRARIES uninstall-libLIBRARIES \
+install-libLIBRARIES mostlyclean-compile distclean-compile \
+clean-compile maintainer-clean-compile install-info-am uninstall-info \
+mostlyclean-aminfo distclean-aminfo clean-aminfo \
+maintainer-clean-aminfo uninstall-includeHEADERS install-includeHEADERS \
+tags mostlyclean-tags distclean-tags clean-tags maintainer-clean-tags \
+distdir check-TESTS info-am info dvi-am dvi check check-am \
+installcheck-am installcheck install-exec-am install-exec \
+install-data-am install-data install-am install uninstall-am uninstall \
+all-redirect all-am all installdirs mostlyclean-generic \
+distclean-generic clean-generic maintainer-clean-generic clean \
+mostlyclean distclean maintainer-clean
+
+
+avl.text : avl.texinfo
+	$(MAKEINFO) $(srcdir)/avl.texinfo -o avl.text --no-headers
+
+avl.html: avl.texinfo
+	-texi2html -monolithic $(srcdir)/avl.texinfo
+avl-test.c avlt-test.c avltr-test.c rb-test.c:
+	rm -f $@
+	echo '#define SELF_TEST 1' > $@
+	echo '#include "'`echo $@ | sed s/-test//`'"' >> $@
+
+# Tell versions [3.59,3.63) of GNU make to not export all variables.
+# Otherwise a system limit (for SysV at least) may be exceeded.
+.NOEXPORT:
diff --git a/avl-1.4.0/NEWS b/avl-1.4.0/NEWS
new file mode 100644
index 0000000..ecdc25d
--- /dev/null
+++ b/avl-1.4.0/NEWS
@@ -0,0 +1,98 @@
+libavl NEWS -- history of user-visible changes.  
+Time-stamp: <1999-08-15 21:52:15 blp>
+Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+See the end for copying conditions.
+
+Please send PSPP bug reports to bug-gnu-pspp@gnu.org.
+
+Changes for version 1.4.0:
+
+  Implemented red-black trees.
+
+  New functions, *_init_traverser(), to initialize a *_traverser
+  structure.  New macros *_TRAVERSER_INIT for same purpose.
+
+Changes for version 1.3.0:
+
+  Now uses Autoconf and Automake to configure.  Thanks to Alexandre
+  Oliva <oliva@dcc.unicamp.br>.
+
+  New: automated testing with `make check'.
+
+  Fixes for strict ANSI C compliance.
+
+  Fixed useless assertions.  Fixed bug regarding empty trees for some
+  operations with threaded and right-threaded trees.  Thanks to
+  "Ficarra, David W, NNAD" <dficarra@att.com>.
+
+  New functions, avl*_find_close(), for finding a node in the tree
+  with a value close to a specified value.  See documentation and
+  source code for more details.  Thanks to Thomas Binder
+  <binder@iue.tuwien.ac.at>.
+
+Changes for version 1.2.9:
+ 
+  Fix typos in documentation.  Thanks to onTy Toom <onty@yahoo.com>.
+
+Changes for version 1.2.8:
+
+  Fixed typos in assertions.  Thanks to Girish Zambre
+  <gzambre@sprynet.com>.
+
+  Better support for gcc 2.7.x.
+
+Changes for versions 1.2.4, 1.2.5, 1.2.6, 1.2.7:
+
+  Documentation updates.  Thanks to Ron Pfeifle <rpfeifle@aw.sgi.com>,
+  Jason Eisner <jeisner@linc.cis.upenn.edu>, and others.
+
+Changes for version 1.2.3:
+
+  The library's allocation function xmalloc() can easily be overridden
+  by the library's user.  Thanks to Clayton Weaver <cgweav@eskimo.com>
+  for the idea.
+
+Changes for version 1.2.2:
+
+  Documentation fixes.  Thanks to Akim Demaille <demaille@inf.enst.fr>
+  for pointing these out.
+
+Changes for version 1.2.1:
+
+  Bug fixes.
+
+Changes for version 1.2.0:
+
+  Implemented right-threaded trees.
+
+  Added functions to convert among AVL tree types.
+
+  First GNU release.
+
+Changes for version 1.1.0:
+
+  Implemented threaded trees.
+
+Changes for version 1.0:
+
+  First public release.
+
+----------------------------------------------------------------------
+Copyright information:
+
+Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+
+   Permission is granted to anyone to make or distribute verbatim
+   copies of this document as received, in any medium, provided that
+   the copyright notice and this permission notice are preserved, thus
+   giving the recipient permission to redistribute in turn.
+
+   Permission is granted to distribute modified versions of this
+   document, or of portions of it, under the above conditions,
+   provided also that they carry prominent notices stating who last
+   changed them.
+
+Local variables:
+version-control: never
+mode: indented-text
+end:
diff --git a/avl-1.4.0/TODO b/avl-1.4.0/TODO
new file mode 100644
index 0000000..0231395
--- /dev/null
+++ b/avl-1.4.0/TODO
@@ -0,0 +1,92 @@
+TODO
+----
+
+* Write `bare' no-rebalancing version for comparison purposes.
+
+* In avl_delete's D9 it may be faster to move the data instead of
+  moving around all the pointers.  Consider the situation carefully.
+
+* avl_traverse_{fwd,rev}; avl_find_traverse
+
+* Generalized testing framework; for instance, could compare with
+  kazlib and avllib implementations.
+
+* Merge algorithm paper into documentation.
+
+----------------------------------------------------------------------
+From: Akim Demaille <demaille@inf.enst.fr>
+Subject: Re: libavl
+To: pfaffben@pilot.msu.edu
+Date: 25 Sep 1998 16:04:03 +0200
+
+
+Sorry for the delays...
+
+Ben Pfaff <pfaffben@pilot.msu.edu> writes:
+
+> Akim Demaille <demaille@inf.enst.fr> writes:
+>
+>    And finaly, for the application I want to make of libavl, I have
+>    sometimes to merge two avls, say the second into the first, while
+>    specifying, when conflict, whether it is always the first or the
+>    second that wins.
+>
+>    I can easily make this using your api, nevertheless, I wanted to ask
+>    you whether you know none brute-force approaches, or even whether
+>    this kind of features might appear in the future.
+>
+> Knuth describes an elegant algorithm for merging two avls, but it only
+> works if all the values in one of them is smaller than all the values
+> in the other.
+>
+> If you do think of a clever algorithm for doing this, please let me
+> know and I'll incorporate it into the API.
+
+I know none.  but looking on the web, I found one in haskell :)
+I didn't look whether it was smart or not.
+
+http://www.cs.chalmers.se/pub/haskell/library/avl-tree.lgs
+
+There is not much material.  I think comp.compiler is a good place to
+ask for an algorithm...
+
+Akim
+----------------------------------------------------------------------
+From: David Kastrup <dak@neuroinformatik.ruhr-uni-bochum.de>
+Subject: Re: Your AVL tree page
+To: pfaffben@pilot.msu.edu
+Date: Mon, 23 Nov 1998 18:38:55 +0100
+
+   From: Ben Pfaff <pfaffben@pilot.msu.edu>
+   Date: 23 Nov 1998 12:12:31 -0500
+
+   David Kastrup <dak@neuroinformatik.ruhr-uni-bochum.de> writes:
+
+      You might want to take a look at the texts at
+      http://www-lsi.upc.es/www/dept/techreps/1998.html
+
+      In particular the paper
+      http://www-lsi.upc.es/dept/techreps/ps/R98-12.ps.gz
+
+      might be interesting, as it gives an AVL-tree mechanism for
+      multi-threaded, distributed access.
+
+   Thanks for the pointers.  It seems that connectivity to that machine
+   is really slow from here, at least right now, so I'll try to take a
+   look at them a little later.  Currently there is no multithread
+   support in libavl, but it might be nice to add it later.
+
+Well, the reference will probably not be what you think it is.  It is
+intended to not properly balance the tree during the access when that
+would mean locking the entire tree.  Instead, it does only local
+corrections that eventually probagate to the top.  One can also let a
+"garbage collect" thread run that will optimize the data structures
+at idle times, but will let them deteriorate a bit rather than fix
+them up properly under stress.  This is, of course, especially
+interesting for internal data structures of an operating system, where
+full balancing at the time of access will slow operations down, but
+there will be idle times when balancing can occur without overhead.
+
+David Kastrup                                     Phone: +49-234-700-5570
+Email: dak@neuroinformatik.ruhr-uni-bochum.de       Fax: +49-234-709-4209
+Institut für Neuroinformatik, Universitätsstr. 150, 44780 Bochum, Germany
diff --git a/avl-1.4.0/aclocal.m4 b/avl-1.4.0/aclocal.m4
new file mode 100644
index 0000000..9f8add8
--- /dev/null
+++ b/avl-1.4.0/aclocal.m4
@@ -0,0 +1,104 @@
+dnl aclocal.m4 generated automatically by aclocal 1.4
+
+dnl Copyright (C) 1994, 1995-8, 1999 Free Software Foundation, Inc.
+dnl This file is free software; the Free Software Foundation
+dnl gives unlimited permission to copy and/or distribute it,
+dnl with or without modifications, as long as this notice is preserved.
+
+dnl This program is distributed in the hope that it will be useful,
+dnl but WITHOUT ANY WARRANTY, to the extent permitted by law; without
+dnl even the implied warranty of MERCHANTABILITY or FITNESS FOR A
+dnl PARTICULAR PURPOSE.
+
+# Do all the work for Automake.  This macro actually does too much --
+# some checks are only needed if your package does certain things.
+# But this isn't really a big deal.
+
+# serial 1
+
+dnl Usage:
+dnl AM_INIT_AUTOMAKE(package,version, [no-define])
+
+AC_DEFUN(AM_INIT_AUTOMAKE,
+[AC_REQUIRE([AC_PROG_INSTALL])
+PACKAGE=[$1]
+AC_SUBST(PACKAGE)
+VERSION=[$2]
+AC_SUBST(VERSION)
+dnl test to see if srcdir already configured
+if test "`cd $srcdir && pwd`" != "`pwd`" && test -f $srcdir/config.status; then
+  AC_MSG_ERROR([source directory already configured; run "make distclean" there first])
+fi
+ifelse([$3],,
+AC_DEFINE_UNQUOTED(PACKAGE, "$PACKAGE", [Name of package])
+AC_DEFINE_UNQUOTED(VERSION, "$VERSION", [Version number of package]))
+AC_REQUIRE([AM_SANITY_CHECK])
+AC_REQUIRE([AC_ARG_PROGRAM])
+dnl FIXME This is truly gross.
+missing_dir=`cd $ac_aux_dir && pwd`
+AM_MISSING_PROG(ACLOCAL, aclocal, $missing_dir)
+AM_MISSING_PROG(AUTOCONF, autoconf, $missing_dir)
+AM_MISSING_PROG(AUTOMAKE, automake, $missing_dir)
+AM_MISSING_PROG(AUTOHEADER, autoheader, $missing_dir)
+AM_MISSING_PROG(MAKEINFO, makeinfo, $missing_dir)
+AC_REQUIRE([AC_PROG_MAKE_SET])])
+
+#
+# Check to make sure that the build environment is sane.
+#
+
+AC_DEFUN(AM_SANITY_CHECK,
+[AC_MSG_CHECKING([whether build environment is sane])
+# Just in case
+sleep 1
+echo timestamp > conftestfile
+# Do `set' in a subshell so we don't clobber the current shell's
+# arguments.  Must try -L first in case configure is actually a
+# symlink; some systems play weird games with the mod time of symlinks
+# (eg FreeBSD returns the mod time of the symlink's containing
+# directory).
+if (
+   set X `ls -Lt $srcdir/configure conftestfile 2> /dev/null`
+   if test "[$]*" = "X"; then
+      # -L didn't work.
+      set X `ls -t $srcdir/configure conftestfile`
+   fi
+   if test "[$]*" != "X $srcdir/configure conftestfile" \
+      && test "[$]*" != "X conftestfile $srcdir/configure"; then
+
+      # If neither matched, then we have a broken ls.  This can happen
+      # if, for instance, CONFIG_SHELL is bash and it inherits a
+      # broken ls alias from the environment.  This has actually
+      # happened.  Such a system could not be considered "sane".
+      AC_MSG_ERROR([ls -t appears to fail.  Make sure there is not a broken
+alias in your environment])
+   fi
+
+   test "[$]2" = conftestfile
+   )
+then
+   # Ok.
+   :
+else
+   AC_MSG_ERROR([newly created file is older than distributed files!
+Check your system clock])
+fi
+rm -f conftest*
+AC_MSG_RESULT(yes)])
+
+dnl AM_MISSING_PROG(NAME, PROGRAM, DIRECTORY)
+dnl The program must properly implement --version.
+AC_DEFUN(AM_MISSING_PROG,
+[AC_MSG_CHECKING(for working $2)
+# Run test in a subshell; some versions of sh will print an error if
+# an executable is not found, even if stderr is redirected.
+# Redirect stdin to placate older versions of autoconf.  Sigh.
+if ($2 --version) < /dev/null > /dev/null 2>&1; then
+   $1=$2
+   AC_MSG_RESULT(found)
+else
+   $1="$3/missing $2"
+   AC_MSG_RESULT(missing)
+fi
+AC_SUBST($1)])
+
diff --git a/avl-1.4.0/avl.c b/avl-1.4.0/avl.c
new file mode 100644
index 0000000..82cdb6e
--- /dev/null
+++ b/avl-1.4.0/avl.c
@@ -0,0 +1,1154 @@
+/* libavl - manipulates AVL trees.
+   Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License as
+   published by the Free Software Foundation; either version 2 of the
+   License, or (at your option) any later version.
+
+   This program 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 General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+   02111-1307, USA.
+
+   The author may be contacted at <pfaffben@pilot.msu.edu> on the
+   Internet, or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA
+   through more mundane means. */
+
+/* This is file avl.c in libavl. */
+
+#if HAVE_CONFIG_H
+#include <config.h>
+#endif
+#if PSPP
+#include "common.h"
+#include "arena.h"
+#define HAVE_XMALLOC 1
+#endif
+#if SELF_TEST 
+#include <limits.h>
+#include <time.h>
+#endif
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include "avl.h"
+
+#if !PSPP && !__GCC__
+#define inline
+#endif
+
+#if !PSPP
+#if __GNUC__ >= 2
+#define unused __attribute__ ((unused))
+#else
+#define unused
+#endif
+#endif
+
+#ifdef HAVE_XMALLOC
+void *xmalloc (size_t);
+#else /* !HAVE_XMALLOC */
+/* Allocates SIZE bytes of space using malloc().  Aborts if out of
+   memory. */
+static void *
+xmalloc (size_t size)
+{
+  void *vp;
+
+  if (size == 0)
+    return NULL;
+  vp = malloc (size);
+
+  assert (vp != NULL);
+  if (vp == NULL)
+    {
+      fprintf (stderr, "virtual memory exhausted\n");
+      exit (EXIT_FAILURE);
+    }
+  return vp;
+}
+#endif /* !HAVE_XMALLOC */
+
+/* Creates an AVL tree in arena OWNER (which can be NULL).  The arena
+   is owned by the caller, not by the AVL tree.  CMP is a order
+   function for the data to be stored in the tree.  PARAM is arbitrary
+   data that becomes an argument to the comparison function. */
+avl_tree *
+avl_create (MAYBE_ARENA avl_comparison_func cmp, void *param)
+{
+  avl_tree *tree;
+
+  assert (cmp != NULL);
+#if PSPP
+  if (owner)
+    tree = arena_alloc (owner, sizeof (avl_tree));
+  else
+#endif
+    tree = xmalloc (sizeof (avl_tree));
+
+#if PSPP
+  tree->owner = owner;
+#endif
+  tree->root.link[0] = NULL;
+  tree->root.link[1] = NULL; 
+  tree->cmp = cmp;
+  tree->count = 0;
+  tree->param = param;
+
+  return tree;
+}
+
+/* Destroy tree TREE.  Function FREE_FUNC is called for every node in
+   the tree as it is destroyed.  
+
+   No effect if the tree has an arena owner and free_func is NULL.
+   The caller owns the arena and must destroy it itself.
+
+   Do not attempt to reuse the tree after it has been freed.  Create a
+   new one.  */
+void
+avl_destroy (avl_tree *tree, avl_node_func free_func)
+{
+  assert (tree != NULL);
+  
+#if PSPP
+  if (free_func || tree->owner == NULL)
+#endif
+    {
+      /* Uses Knuth's Algorithm 2.3.1T as modified in exercise 13
+	 (postorder traversal). */
+      
+      /* T1. */
+      avl_node *an[AVL_MAX_HEIGHT];	/* Stack A: nodes. */
+      char ab[AVL_MAX_HEIGHT];		/* Stack A: bits. */
+      int ap = 0;			/* Stack A: height. */
+      avl_node *p = tree->root.link[0];
+
+      for (;;)
+	{
+	  /* T2. */
+	  while (p != NULL)
+	    {
+	      /* T3. */
+	      ab[ap] = 0;
+	      an[ap++] = p;
+	      p = p->link[0];
+	    }
+
+	  /* T4. */
+	  for (;;)
+	    {
+	      if (ap == 0)
+		goto done;
+
+	      p = an[--ap];
+	      if (ab[ap] == 0)
+		{
+		  ab[ap++] = 1;
+		  p = p->link[1];
+		  break;
+		}
+      
+	      if (free_func)
+		free_func (p->data, tree->param);
+#if PSPP
+	      if (tree->owner == NULL)
+#endif
+		free (p);
+	    }
+	}
+    }
+
+ done:
+#if PSPP
+  if (tree->owner == NULL)
+#endif
+    free (tree);
+}
+
+/* avl_destroy() with FREE_FUNC hardcoded as free(). */
+void
+avl_free (avl_tree *tree)
+{
+  avl_destroy (tree, (avl_node_func) free);
+}
+
+/* Return the number of nodes in TREE. */
+int
+avl_count (const avl_tree *tree)
+{
+  assert (tree != NULL);
+  return tree->count;
+}
+
+/* Allocates room for a new avl_node in arena OWNER, or using
+   xmalloc() if OWNER is NULL. */
+#if PSPP
+static inline avl_node *
+new_node (arena **owner)
+{
+  if (owner != NULL)
+    return arena_alloc (owner, sizeof (avl_node));
+  else
+    return xmalloc (sizeof (avl_node));
+}
+#else
+static inline avl_node *
+new_node (void)
+{
+  return xmalloc (sizeof (avl_node));
+}
+
+#define new_node(owner)				\
+	new_node ()
+#endif
+
+/* Copy the contents of TREE to a new tree in arena OWNER.  If COPY is
+   non-NULL, then each data item is passed to function COPY, and the
+   return values are inserted into the new tree; otherwise, the items
+   are copied verbatim from the old tree to the new tree.  Returns the
+   new tree. */
+avl_tree *
+avl_copy (MAYBE_ARENA const avl_tree *tree, avl_copy_func copy)
+{
+  /* This is a combination of Knuth's Algorithm 2.3.1C (copying a
+     binary tree) and Algorithm 2.3.1T as modified by exercise 12
+     (preorder traversal). */
+
+  avl_tree *new_tree;
+
+  /* PT1. */
+  const avl_node *pa[AVL_MAX_HEIGHT];	/* Stack PA: nodes. */
+  const avl_node **pp = pa;		/* Stack PA: stack pointer. */
+  const avl_node *p = &tree->root;
+  
+  /* QT1. */
+  avl_node *qa[AVL_MAX_HEIGHT];	/* Stack QA: nodes. */
+  avl_node **qp = qa;		/* Stack QA: stack pointer. */
+  avl_node *q;
+  
+  assert (tree != NULL);
+#if PSPP
+  new_tree = avl_create (owner, tree->cmp, tree->param);
+#else
+  new_tree = avl_create (tree->cmp, tree->param);
+#endif
+  new_tree->count = tree->count;
+  q = &new_tree->root;
+
+  for (;;)
+    {
+      /* C4. */
+      if (p->link[0] != NULL)
+	{
+	  avl_node *r = new_node (owner);
+	  r->link[0] = r->link[1] = NULL;
+	  q->link[0] = r;
+	}
+
+      /* C5: Find preorder successors of P and Q.  */
+      goto start;
+      for (;;)
+	{
+	  /* PT2. */
+	  while (p != NULL)
+	    {
+	      goto escape;
+	    start:
+	      /* PT3. */
+	      *pp++ = p;
+	      *qp++ = q;
+	      p = p->link[0];
+	      q = q->link[0];
+	    }
+      
+	  /* PT4. */
+	  if (pp == pa)
+	    {
+	      assert (qp == qa);
+	      return new_tree;
+	    }
+	      
+	  p = *--pp;
+	  q = *--qp;
+
+	  /* PT5. */
+	  p = p->link[1];
+	  q = q->link[1];
+	}
+    escape:
+
+      /* C2. */
+      if (p->link[1])
+	{
+	  avl_node *r = new_node (owner);
+	  r->link[0] = r->link[1] = NULL;
+	  q->link[1] = r;
+	}
+
+      /* C3. */
+      q->bal = p->bal;
+      if (copy == NULL)
+	q->data = p->data;
+      else
+	q->data = copy (p->data, tree->param);
+    }
+}
+
+/* Walk tree TREE in inorder, calling WALK_FUNC at each node.  Passes
+   PARAM to WALK_FUNC.  */
+void
+avl_walk (const avl_tree *tree, avl_node_func walk_func, void *param)
+{
+  /* Uses Knuth's algorithm 2.3.1T (inorder traversal). */
+  assert (tree && walk_func);
+  
+  {
+    /* T1. */
+    const avl_node *an[AVL_MAX_HEIGHT];	/* Stack A: nodes. */
+    const avl_node **ap = an;		/* Stack A: stack pointer. */
+    const avl_node *p = tree->root.link[0];
+
+    for (;;)
+      {
+	/* T2. */
+	while (p != NULL)
+	  {
+	    /* T3. */
+	    *ap++ = p;
+	    p = p->link[0];
+	  }
+      
+	/* T4. */
+	if (ap == an)
+	  return;
+	p = *--ap;
+
+	/* T5. */
+	walk_func (p->data, param);
+	p = p->link[1];
+      }
+  }
+}
+
+/* Each call to this function for a given TREE and TRAV return the
+   next item in the tree in inorder.  Initialize the first element of
+   TRAV (init) to 0 before calling the first time.  Returns NULL when
+   out of elements.  */
+void *
+avl_traverse (const avl_tree *tree, avl_traverser *trav)
+{
+  assert (tree && trav);
+
+  /* Uses Knuth's algorithm 2.3.1T (inorder traversal). */
+  if (trav->init == 0)
+    {
+      /* T1. */
+      trav->init = 1;
+      trav->nstack = 0;
+      trav->p = tree->root.link[0];
+    }
+  else
+    /* T5. */
+    trav->p = trav->p->link[1];
+
+  for (;;)
+    {
+      /* T2. */
+      while (trav->p != NULL)
+	{
+	  /* T3. */
+	  trav->stack[trav->nstack++] = trav->p;
+	  trav->p = trav->p->link[0];
+	}
+      
+      /* T4. */
+      if (trav->nstack == 0)
+	{
+	  trav->init = 0;
+	  return NULL;
+	}
+      trav->p = trav->stack[--trav->nstack];
+
+      /* T5. */
+      return trav->p->data;
+    }
+}
+
+/* Search TREE for an item matching ITEM.  If found, returns a pointer
+   to the address of the item.  If none is found, ITEM is inserted
+   into the tree, and a pointer to the address of ITEM is returned.
+   In either case, the pointer returned can be changed by the caller,
+   or the returned data item can be directly edited, but the key data
+   in the item must not be changed. */
+void **
+avl_probe (avl_tree *tree, void *item)
+{
+  /* Uses Knuth's Algorithm 6.2.3A (balanced tree search and
+     insertion), but caches results of comparisons.  In empirical
+     tests this eliminates about 25% of the comparisons seen under
+     random insertions.  */
+
+  /* A1. */
+  avl_node *t;
+  avl_node *s, *p, *q, *r;
+  
+  assert (tree != NULL);
+  t = &tree->root;
+  s = p = t->link[0];
+
+  if (s == NULL)
+    {
+      tree->count++;
+      assert (tree->count == 1);
+      q = t->link[0] = new_node (tree->owner);
+      q->data = item;
+      q->link[0] = q->link[1] = NULL;
+      q->bal = 0;
+      return &q->data;
+    }
+
+  for (;;)
+    {
+      /* A2. */
+      int diff = tree->cmp (item, p->data, tree->param);
+
+      /* A3. */
+      if (diff < 0)
+	{
+	  p->cache = 0;
+	  q = p->link[0];
+	  if (q == NULL)
+	    {
+	      p->link[0] = q = new_node (tree->owner);
+	      break;
+	    }
+	}
+      /* A4. */
+      else if (diff > 0)
+	{
+	  p->cache = 1;
+	  q = p->link[1];
+	  if (q == NULL)
+	    {
+	      p->link[1] = q = new_node (tree->owner);
+	      break;
+	    }
+	}
+      else
+	/* A2. */
+	return &p->data;
+
+      /* A3, A4. */
+      if (q->bal != 0)
+	t = p, s = q;
+      p = q;
+    }
+  
+  /* A5. */
+  tree->count++;
+  q->data = item;
+  q->link[0] = q->link[1] = NULL;
+  q->bal = 0;
+
+  /* A6. */
+  r = p = s->link[(int) s->cache];
+  while (p != q)
+    {
+      p->bal = p->cache * 2 - 1;
+      p = p->link[(int) p->cache];
+    }
+
+  /* A7. */
+  if (s->cache == 0)
+    {
+      /* a = -1. */
+      if (s->bal == 0)
+	{
+	  s->bal = -1;
+	  return &q->data;
+	}
+      else if (s->bal == +1)
+	{
+	  s->bal = 0;
+	  return &q->data;
+	}
+      
+      assert (s->bal == -1);
+      if (r->bal == -1)
+	{
+	  /* A8. */
+	  p = r;
+	  s->link[0] = r->link[1];
+	  r->link[1] = s;
+	  s->bal = r->bal = 0;
+	}
+      else
+	{
+	  /* A9. */
+	  assert (r->bal == +1);
+	  p = r->link[1];
+	  r->link[1] = p->link[0];
+	  p->link[0] = r;
+	  s->link[0] = p->link[1];
+	  p->link[1] = s;
+	  if (p->bal == -1)
+	    s->bal = 1, r->bal = 0;
+	  else if (p->bal == 0)
+	    s->bal = r->bal = 0;
+	  else 
+	    {
+	      assert (p->bal == +1);
+	      s->bal = 0, r->bal = -1;
+	    }
+	  p->bal = 0;
+	}
+    }
+  else
+    {
+      /* a == +1. */
+      if (s->bal == 0)
+	{
+	  s->bal = 1;
+	  return &q->data;
+	}
+      else if (s->bal == -1)
+	{
+	  s->bal = 0;
+	  return &q->data;
+	}
+
+      assert (s->bal == +1);
+      if (r->bal == +1)
+	{
+	  /* A8. */
+	  p = r;
+	  s->link[1] = r->link[0];
+	  r->link[0] = s;
+	  s->bal = r->bal = 0;
+	}
+      else
+	{
+	  /* A9. */
+	  assert (r->bal == -1);
+	  p = r->link[0];
+	  r->link[0] = p->link[1];
+	  p->link[1] = r;
+	  s->link[1] = p->link[0];
+	  p->link[0] = s;
+	  if (p->bal == +1)
+	    s->bal = -1, r->bal = 0;
+	  else if (p->bal == 0)
+	    s->bal = r->bal = 0;
+	  else 
+	    {
+	      assert (p->bal == -1);
+	      s->bal = 0, r->bal = 1;
+	    }
+	  p->bal = 0;
+	}
+    }
+		
+  /* A10. */
+  if (t != &tree->root && s == t->link[1])
+    t->link[1] = p;
+  else
+    t->link[0] = p;
+
+  return &q->data;
+}
+  
+/* Search TREE for an item matching ITEM, and return it if found. */
+void *
+avl_find (const avl_tree *tree, const void *item)
+{
+  const avl_node *p;
+
+  assert (tree != NULL);
+  for (p = tree->root.link[0]; p; )
+    {
+      int diff = tree->cmp (item, p->data, tree->param);
+
+      if (diff < 0)
+	p = p->link[0];
+      else if (diff > 0)
+	p = p->link[1];
+      else
+	return p->data;
+    }
+
+  return NULL;
+}
+
+/* Search TREE for an item close to the value of ITEM, and return it.
+   This function will return a null pointer only if TREE is empty. */
+void *
+avl_find_close (const avl_tree *tree, const void *item)
+{
+  const avl_node *p;
+
+  assert (tree != NULL);
+  p = tree->root.link[0];
+  if (p == NULL)
+    return NULL;
+  
+  for (;;)
+    {
+      int diff = tree->cmp (item, p->data, tree->param);
+      int t;
+
+      if (diff < 0)
+	t = 0;
+      else if (diff > 0)
+	t = 1;
+      else
+	return p->data;
+
+      if (p->link[t])
+	p = p->link[t];
+      else
+	return p->data;
+    }
+}
+
+/* Searches AVL tree TREE for an item matching ITEM.  If found, the
+   item is removed from the tree and the actual item found is returned
+   to the caller.  If no item matching ITEM exists in the tree,
+   returns NULL. */
+void *
+avl_delete (avl_tree *tree, const void *item)
+{
+  /* Uses my Algorithm D, which can be found at
+     http://www.msu.edu/user/pfaffben/avl.  Algorithm D is based on
+     Knuth's Algorithm 6.2.2D (Tree deletion) and 6.2.3A (Balanced
+     tree search and insertion), as well as the notes on pages 465-466
+     of Vol. 3. */
+
+  /* D1. */
+  avl_node *pa[AVL_MAX_HEIGHT];		/* Stack P: Nodes. */
+  char a[AVL_MAX_HEIGHT];		/* Stack P: Bits. */
+  int k = 1;				/* Stack P: Pointer. */
+  
+  avl_node **q;
+  avl_node *p;
+
+  assert (tree != NULL);
+
+  a[0] = 0;
+  pa[0] = &tree->root;
+  p = tree->root.link[0];
+  for (;;)
+    {
+      /* D2. */
+      int diff;
+
+      if (p == NULL)
+	return NULL;
+
+      diff = tree->cmp (item, p->data, tree->param);
+      if (diff == 0)
+	break;
+
+      /* D3, D4. */
+      pa[k] = p;
+      if (diff < 0)
+	{
+	  p = p->link[0];
+	  a[k] = 0;
+	}
+      else if (diff > 0)
+	{
+	  p = p->link[1];
+	  a[k] = 1;
+	}
+      k++;
+    }
+  tree->count--;
+  
+  item = p->data;
+
+  /* D5. */
+  q = &pa[k - 1]->link[(int) a[k - 1]];
+  if (p->link[1] == NULL)
+    {
+      *q = p->link[0];
+      if (*q)
+	(*q)->bal = 0;
+    }
+  else
+    {
+      /* D6. */
+      avl_node *r = p->link[1];
+      if (r->link[0] == NULL)
+	{
+	  r->link[0] = p->link[0];
+	  *q = r;
+	  r->bal = p->bal;
+	  a[k] = 1;
+	  pa[k++] = r;
+	}
+      else
+	{
+	  /* D7. */
+	  avl_node *s = r->link[0];
+	  int l = k++;
+
+	  a[k] = 0;
+	  pa[k++] = r;
+	    
+	  /* D8. */
+	  while (s->link[0] != NULL)
+	    {
+	      r = s;
+	      s = r->link[0];
+	      a[k] = 0;
+	      pa[k++] = r;
+	    }
+
+	  /* D9. */
+	  a[l] = 1;
+	  pa[l] = s;
+	  s->link[0] = p->link[0];
+	  r->link[0] = s->link[1];
+	  s->link[1] = p->link[1];
+	  s->bal = p->bal;
+	  *q = s;
+	}
+    }
+
+#if PSPP
+  if (tree->owner == NULL)
+#endif
+    free (p);
+
+  assert (k > 0);
+  /* D10. */
+  while (--k)
+    {
+      avl_node *s = pa[k], *r;
+
+      if (a[k] == 0)
+	{
+	  /* D10. */
+	  if (s->bal == -1)
+	    {
+	      s->bal = 0;
+	      continue;
+	    }
+	  else if (s->bal == 0)
+	    {
+	      s->bal = 1;
+	      break;
+	    }
+
+	  assert (s->bal == +1);
+	  r = s->link[1];
+
+	  assert (r != NULL);
+	  if (r->bal == 0)
+	    {
+	      /* D11. */
+	      s->link[1] = r->link[0];
+	      r->link[0] = s;
+	      r->bal = -1;
+	      pa[k - 1]->link[(int) a[k - 1]] = r;
+	      break;
+	    }
+	  else if (r->bal == +1)
+	    {
+	      /* D12. */
+	      s->link[1] = r->link[0];
+	      r->link[0] = s;
+	      s->bal = r->bal = 0;
+	      pa[k - 1]->link[(int) a[k - 1]] = r;
+	    }
+	  else 
+	    {
+	      /* D13. */
+	      assert (r->bal == -1);
+	      p = r->link[0];
+	      r->link[0] = p->link[1];
+	      p->link[1] = r;
+	      s->link[1] = p->link[0];
+	      p->link[0] = s;
+	      if (p->bal == +1)
+		s->bal = -1, r->bal = 0;
+	      else if (p->bal == 0)
+		s->bal = r->bal = 0;
+	      else
+		{
+		  assert (p->bal == -1);
+		  s->bal = 0, r->bal = +1;
+		}
+	      p->bal = 0;
+	      pa[k - 1]->link[(int) a[k - 1]] = p;
+	    }
+	}
+      else
+	{
+	  assert (a[k] == 1);
+
+	  /* D10. */
+	  if (s->bal == +1)
+	    {
+	      s->bal = 0;
+	      continue;
+	    }
+	  else if (s->bal == 0)
+	    {
+	      s->bal = -1;
+	      break;
+	    }
+
+	  assert (s->bal == -1);
+	  r = s->link[0];
+
+	  if (r == NULL || r->bal == 0)
+	    {
+	      /* D11. */
+	      s->link[0] = r->link[1];
+	      r->link[1] = s;
+	      r->bal = 1;
+	      pa[k - 1]->link[(int) a[k - 1]] = r;
+	      break;
+	    }
+	  else if (r->bal == -1)
+	    {
+	      /* D12. */
+	      s->link[0] = r->link[1];
+	      r->link[1] = s;
+	      s->bal = r->bal = 0;
+	      pa[k - 1]->link[(int) a[k - 1]] = r;
+	    }
+	  else if (r->bal == +1)
+	    {
+	      /* D13. */
+	      p = r->link[1];
+	      r->link[1] = p->link[0];
+	      p->link[0] = r;
+	      s->link[0] = p->link[1];
+	      p->link[1] = s;
+	      if (p->bal == -1)
+		s->bal = 1, r->bal = 0;
+	      else if (p->bal == 0)
+		s->bal = r->bal = 0;
+	      else
+		{
+		  assert (p->bal == 1);
+		  s->bal = 0, r->bal = -1;
+		}
+	      p->bal = 0;
+	      pa[k - 1]->link[(int) a[k - 1]] = p;
+	    }
+	}
+    }
+      
+  return (void *) item;
+}
+
+/* Inserts ITEM into TREE.  Returns NULL if the item was inserted,
+   otherwise a pointer to the duplicate item. */
+void *
+avl_insert (avl_tree *tree, void *item)
+{
+  void **p;
+  
+  assert (tree != NULL);
+  
+  p = avl_probe (tree, item);
+  return (*p == item) ? NULL : *p;
+}
+
+/* If ITEM does not exist in TREE, inserts it and returns NULL.  If a
+   matching item does exist, it is replaced by ITEM and the item
+   replaced is returned.  The caller is responsible for freeing the
+   item returned. */
+void *
+avl_replace (avl_tree *tree, void *item)
+{
+  void **p;
+
+  assert (tree != NULL);
+  
+  p = avl_probe (tree, item);
+  if (*p == item)
+    return NULL;
+  else
+    {
+      void *r = *p;
+      *p = item;
+      return r;
+    }
+}
+
+/* Delete ITEM from TREE when you know that ITEM must be in TREE.  For
+   debugging purposes. */
+void *
+(avl_force_delete) (avl_tree *tree, void *item)
+{
+  void *found = avl_delete (tree, item);
+  assert (found != NULL);
+  return found;
+}
+
+#if SELF_TEST
+
+/* Used to flag delayed aborting. */
+int done = 0;
+
+/* Print the structure of node NODE of an avl tree, which is LEVEL
+   levels from the top of the tree.  Uses different delimiters to
+   visually distinguish levels. */
+void
+print_structure (avl_node *node, int level)
+{
+  char lc[] = "([{`/";
+  char rc[] = ")]}'\\";
+
+  assert (level <= 10);
+  
+  if (node == NULL)
+    {
+      printf (" nil");
+      return;
+    }
+  printf (" %c%d", lc[level % 5], (int) node->data);
+  if (node->link[0] || node->link[1])
+    print_structure (node->link[0], level + 1);
+  if (node->link[1])
+    print_structure (node->link[1], level + 1);
+  printf ("%c", rc[level % 5]);
+}
+
+/* Compare two integers A and B and return a strcmp()-type result. */
+int
+compare_ints (const void *a, const void *b, void *param unused)
+{
+  return ((int) a) - ((int) b);
+}
+
+/* Print the value of integer A. */
+void
+print_int (void *a, void *param unused)
+{
+  printf (" %d", (int) a);
+}
+
+/* Linearly print contents of TREE. */
+void
+print_contents (avl_tree *tree)
+{
+  avl_walk (tree, print_int, NULL);
+  printf ("\n");
+}
+
+/* Examine NODE in a avl tree.  *COUNT is increased by the number of
+   nodes in the tree, including the current one.  If the node is the
+   root of the tree, PARENT should be INT_MIN, otherwise it should be
+   the parent node value.  DIR is the direction that the current node
+   is linked from the parent: -1 for left child, +1 for right child;
+   it is not used if PARENT is INT_MIN.  Returns the height of the
+   tree rooted at NODE. */
+int
+recurse_tree (avl_node *node, int *count, int parent, int dir)
+{
+  if (node) 
+    {
+      int d = (int) node->data;
+      int nl = node->link[0] ? recurse_tree (node->link[0], count, d, -1) : 0;
+      int nr = node->link[1] ? recurse_tree (node->link[1], count, d, 1) : 0;
+      (*count)++;
+
+      if (nr - nl != node->bal)
+	{
+	  printf (" Node %d is unbalanced: right height=%d, left height=%d, "
+		"difference=%d, but balance factor=%d.\n",
+		  d, nr, nl, nr - nl, node->bal);
+	  done = 1;
+	}
+      
+      if (parent != INT_MIN)
+	{
+	  assert (dir == -1 || dir == +1);
+	  if (dir == -1 && d > parent)
+	    {
+	      printf (" Node %d is smaller than its left child %d.\n",
+		      parent, d);
+	      done = 1;
+	    }
+	  else if (dir == +1 && d < parent)
+	    {
+	      printf (" Node %d is larger than its right child %d.\n",
+		      parent, d);
+	      done = 1;
+	    }
+	}
+      assert (node->bal >= -1 && node->bal <= 1);
+      return 1 + (nl > nr ? nl : nr);
+    }
+  else return 0;
+}
+
+/* Check that everything about TREE is kosher. */
+void
+verify_tree (avl_tree *tree)
+{
+  int count = 0;
+  recurse_tree (tree->root.link[0], &count, INT_MIN, 0);
+  if (count != tree->count)
+    {
+      printf (" Tree has %d nodes, but tree count is %d.\n",
+	      count, tree->count);
+      done = 1;
+    }
+  if (done)
+    abort ();
+}
+
+/* Arrange the N elements of ARRAY in random order. */
+void
+shuffle (int *array, int n)
+{
+  int i;
+  
+  for (i = 0; i < n; i++)
+    {
+      int j = i + rand () % (n - i);
+      int t = array[j];
+      array[j] = array[i];
+      array[i] = t;
+    }
+}
+
+/* Compares avl trees rooted at A and B, making sure that they are
+   identical. */
+void
+compare_trees (avl_node *a, avl_node *b)
+{
+  if (a == NULL || b == NULL)
+    {
+      assert (a == NULL && b == NULL);
+      return;
+    }
+  if (a->data != b->data || a->bal != b->bal
+      || ((a->link[0] != NULL) ^ (b->link[0] != NULL))
+      || ((a->link[1] != NULL) ^ (b->link[1] != NULL)))
+    {
+      printf (" Copied nodes differ: %d b=%d a->bal=%d b->bal=%d a:",
+	      (int) a->data, (int) b->data, a->bal, b->bal);
+      if (a->link[0])
+	printf ("l");
+      if (a->link[1])
+	printf ("r");
+      printf (" b:");
+      if (b->link[0])
+	printf ("l");
+      if (b->link[1])
+	printf ("r");
+      printf ("\n");
+      abort ();
+    }
+  if (a->link[0] != NULL)
+    compare_trees (a->link[0], b->link[0]);
+  if (a->link[1] != NULL)
+    compare_trees (a->link[1], b->link[1]);
+}
+
+/* Simple stress test procedure for the AVL tree routines.  Does the
+   following:
+
+   * Generate a random number seed.  By default this is generated from
+   the current time.  You can also pass a seed value on the command
+   line if you want to test the same case.  The seed value is
+   displayed.
+
+   * Create a tree and insert the integers from 0 up to TREE_SIZE - 1
+   into it, in random order.  Verify the tree structure after each
+   insertion.
+   
+   * Remove each integer from the tree, in a different random order.
+   After each deletion, verify the tree structure; also, make a copy
+   of the tree into a new tree, verify the copy and compare it to the
+   original, then destroy the copy.
+
+   * Destroy the tree, increment the random seed value, and start over.
+
+   If you make any modifications to the avl tree routines, then you
+   might want to insert some calls to print_structure() at strategic
+   places in order to be able to see what's really going on.  Also,
+   memory debuggers like Checker or Purify are very handy. */
+#define TREE_SIZE 1024
+#define N_ITERATIONS 16
+int
+main (int argc, char **argv)
+{
+  int array[TREE_SIZE];
+  int seed;
+  int iteration;
+  
+  if (argc == 2)
+    seed = atoi (argv[1]);
+  else
+    seed = time (0) * 257 % 32768;
+
+  fputs ("Testing avl...\n", stdout);
+  
+  for (iteration = 1; iteration <= N_ITERATIONS; iteration++)
+    {
+      avl_tree *tree;
+      int i;
+      
+      printf ("Iteration %4d/%4d: seed=%5d", iteration, N_ITERATIONS, seed);
+      fflush (stdout);
+      
+      srand (seed++);
+
+      for (i = 0; i < TREE_SIZE; i++)
+	array[i] = i;
+      shuffle (array, TREE_SIZE);
+      
+      tree = avl_create (compare_ints, NULL);
+      for (i = 0; i < TREE_SIZE; i++)
+	avl_force_insert (tree, (void *) (array[i]));
+      verify_tree (tree);
+
+      shuffle (array, TREE_SIZE);
+      for (i = 0; i < TREE_SIZE; i++)
+	{
+	  avl_tree *copy;
+
+	  avl_delete (tree, (void *) (array[i]));
+	  verify_tree (tree);
+
+	  copy = avl_copy (tree, NULL);
+	  verify_tree (copy);
+	  compare_trees (tree->root.link[0], copy->root.link[0]);
+	  avl_destroy (copy, NULL);
+
+	  if (i % 128 == 0)
+	    {
+	      putchar ('.');
+	      fflush (stdout);
+	    }
+	}
+      fputs (" good.\n", stdout);
+
+      avl_destroy (tree, NULL);
+    }
+  
+  return 0;
+}
+#endif /* SELF_TEST */
+
+/*
+  Local variables:
+  compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o ./avl-test avl.c"
+  End:
+*/
+
diff --git a/avl-1.4.0/avl.info b/avl-1.4.0/avl.info
new file mode 100644
index 0000000..8dd5330
--- /dev/null
+++ b/avl-1.4.0/avl.info
@@ -0,0 +1,708 @@
+This is avl.info, produced by makeinfo version 3.12n from avl.texinfo.
+
+   This file documents libavl, a library for the manipulation of
+balanced binary trees.
+
+   Copyright 1998, 1999 Free Software Foundation, Inc.
+
+   Permission is granted to make and distribute verbatim copies of this
+manual provided the copyright notice and this permission notice are
+preserved on all copies.
+
+   Permission is granted to copy and distribute modified versions of
+this manual under the conditions for verbatim copying, provided that the
+entire resulting derived work is distributed under the terms of a
+permission notice identical to this one.
+
+   Permission is granted to copy and distribute translations of this
+manual into another language, under the above conditions for modified
+versions, except that this permission notice may be stated in a
+translation approved by the Free Software Foundation.
+
+
+File: avl.info,  Node: Top,  Next: Introduction to balanced binary trees,  Prev: (dir),  Up: (dir)
+
+   This document describes libavl, a library for manipulation of
+balanced binary trees.
+
+   This document applies to libavl version 1.4.0.
+
+* Menu:
+
+* Introduction to balanced binary trees::
+* Introduction to threaded trees::
+* Types::
+* Functions::
+* Tree Creation::
+* Insertion::
+* Searching::
+* Iteration::
+* Conversion::
+* Author::
+* Index::
+
+
+File: avl.info,  Node: Introduction to balanced binary trees,  Next: Introduction to threaded trees,  Prev: Top,  Up: Top
+
+Introduction to balanced binary trees
+*************************************
+
+   Consider some techniques that can be used to find a particular item
+in a data set.  Typical methods include sequential searching, digital
+searching, hash tables, and binary searching.
+
+   Sequential searching is simple, but slow (O(n)).  Digital searching
+requires that the entire data set be known in advance, and memory
+efficient implementations are slow.
+
+   Hash tables are fast (O(1)) for static data sets, but they can be
+wasteful of memory.  It can be difficult to choose an effective hash
+function.  Some hash tables variants also make deletion an expensive
+operation.
+
+   Binary search techniques work almost as quickly (O(log(n)) on an
+ordered table, or on a binary tree.  Binary trees also allow easy
+iteration over the data in the tree in sorted order.  With hash tables
+it is necessary to sort the data before iterating, and after sorting
+the data is no longer in hash form.
+
+   Binary trees are efficient for insertion, deletion, and searching, if
+data are inserted in random order.  But, if data are inserted in order
+using a naive algorithm, binary search degenerates to sequential search.
+
+   In turn, this problem can be solved by "rebalancing" the tree after
+each insertion or deletion.  In rebalancing, nodes are rearranged via
+transformations called "rotations" using an algorithm that tends to
+minimize the tree's height.
+
+   There are several schemes for rebalancing binary trees.  The two most
+common types of balanced tree are "AVL trees" and "red-black trees".
+libavl implements both types:
+
+   * AVL trees, invented by Russian mathematicians G. M.
+     Adel'son-Velskii and E. M. Landis, ensure that, for each node, the
+     difference in height between its subtrees (the "balance factor")
+     is not greater than 1.
+
+   * Red-black trees, invented by R. Bayer and studied at length by L.
+     J. Guibas and R. Sedgewick, assign each node of a tree a color (red
+     or black), and specify a set of rules governing how red and black
+     nodes may be arranged.
+
+   The table below presents a comparison among unbalanced binary trees,
+AVL trees, and red-black trees.  In the table, N is the number of nodes
+in the tree and H is the tree's height before the operation.  "lg" is
+the base-2 logarithm function.
+
+Operation                                                 
+     Binary Tree            AVL Tree                  Red-Black Tree
+Time per insertion or deletion                                                 
+     O(H)                   O(lg N)                   O(lg N)
+Time for insertion of K nodes having sequential values                                                 
+     O(K^2)                 O(N lg N)                 O(N lg N)
+Time for insertion of K nodes having random values                                                 
+     O(N lg N)              O(N lg N)                 O(N lg N)
+Maximum number of rotations per insertion                                                 
+     0                      1                         lg N
+Maximum number of rotations per deletion                                                 
+     0                      lg N                      lg N
+Maximum H as a function of N                                                 
+     N                      1.44 lg (N + 2) - .328    2 lg (N + 1)
+Minimum N as a function of H                                                 
+     H                      2^((H + .328) / 1.44) - 2 2^(H / 2) - 1
+
+   There are alternatives to AVL trees that share some of their
+properties.  For instance, skip lists, 2-3 trees, and splay trees all
+allow O(log(n)) insertion and deletion.  The main disadvantage of these
+methods is that their operations are not as well documented in the
+literature.
+
+
+File: avl.info,  Node: Introduction to threaded trees,  Next: Types,  Prev: Introduction to balanced binary trees,  Up: Top
+
+Introduction to threaded trees
+******************************
+
+   "Threading" is a clever method that simplifies binary tree traversal.
+
+   Nodes in a unthreaded binary tree that have zero or one subnodes have
+two or one null subnode pointers, respectively.  In a threaded binary
+tree, a left child pointer that would otherwise be null is used to point
+to the node's inorder(1) predecessor, and in a null right child pointer
+points to its inorder successor.
+
+   In a threaded tree, it is always possible to find the next node and
+the previous node of a node, given only a pointer to the node in
+question.  In an unthreaded tree, it's also necessary to have a list of
+the nodes between the node in question and root of the tree.
+
+   Advantages of a threaded tree compared to an unthreaded one include:
+
+   * Faster traversal and less memory usage during traversal, since no
+     stack need be maintained.
+
+   * Greater generality, since one can go from a node to its successor
+     or predecessor given only the node, simplifying algorithms that
+     require moving forward and backward in a tree.
+
+   Some disadvantages of threaded trees are:
+
+   * Slower insertion and deletion, since threads need to be
+     maintained.  In somes cases, this can be alleviated by
+     constructing the tree as an unthreaded tree, then threading it
+     with a special libavl function.
+
+   * In theory, threaded trees need two extra bits per node to indicate
+     whether each child pointer points to an ordinary node or the node's
+     successor/predecessor node.  In libavl, however, these bits are
+     stored in a byte that is used for structure alignment padding in
+     unthreaded binary trees, so no extra storage is used.
+
+   A "right-threaded binary tree" is similar to a threaded binary tree,
+but threads are only maintained on the right side of each node.  This
+allows for traversal to the right (toward larger values) but not to the
+left (toward smaller values).  Right-threaded trees are convenient when
+the properties of a threaded tree are desirable, but traversal in
+reverse sort order is not necessary.  Not threading the left links saves
+time in insertions and deletions.
+
+   Left-threaded binary trees also exist, but they are not implemented
+by libavl.  The same effect can be obtained by sorting the tree in the
+opposite order.
+
+   ---------- Footnotes ----------
+
+   (1) In tree traversal, "inorder" refers to visiting the nodes in
+their sorted order from smallest to largest.
+
+
+File: avl.info,  Node: Types,  Next: Functions,  Prev: Introduction to threaded trees,  Up: Top
+
+Types
+*****
+
+   The following types are defined and used by libavl:
+
+ - Data Type: avl_tree
+ - Data Type: avlt_tree
+ - Data Type: avltr_tree
+ - Data Type: rb_tree
+     These are the data types used to represent a tree.  Although they
+     are defined in the libavl header files, it should never be
+     necessary to access them directly.  Instead, all accesses should
+     take place through libavl functions.
+
+ - Data Type: avl_node
+ - Data Type: avlt_node
+ - Data Type: avltr_node
+ - Data Type: rb_node
+     These are the data types used to represent individual nodes in a
+     tree.  Similar cautions apply as with `avl_tree' structures.
+
+ - Data Type: avl_traverser
+ - Data Type: avlt_traverser
+ - Data Type: avltr_traverser
+ - Data Type: rb_traverser
+     These are the data types used by the `avl_traverse' family of
+     functions to iterate across the tree.  Again, these are opaque
+     structures.
+
+ - Data Type: avl_comparison_func
+     Every tree must have an ordering defined by a function of this
+     type.  It must have the following signature:
+
+          int COMPARE (const void *A, const void *B, void *PARAM)
+
+     The return value is expected to be like that returned by `strcmp'
+     in the standard C library: negative if A < B, zero if A = B,
+     positive if A > B.  PARAM is an arbitrary value defined by the
+     user when the tree was created.
+
+ - Data Type: avl_node_func
+     This is a class of function called to perform an operation on a
+     data item.  Functions of this type have the following signature:
+
+          void OPERATE (void *DATA, void *PARAM)
+
+     DATA is the data item and PARAM is an arbitrary user-defined value
+     set when the tree was created.
+
+ - Data Type: avl_copy_func
+     This is a class of function called to make a new copy of a node's
+     data.  Functions of this type have the following signature:
+
+          void *COPY (void *DATA, void *PARAM)
+
+     The function should return a new copy of DATA.  PARAM is an
+     arbitrary user-defined value set when the tree was created.
+
+ - Macro: AVL_MAX_HEIGHT
+     This macro defines the maximum height of an AVL tree that can be
+     handled by functions that maintain a stack of nodes descended.
+     The default value is 32, which allows for AVL trees with a maximum
+     number of nodes between 5,704,880 and 4,294,967,295, depending on
+     order of insertion.  This macro may be defined by the user before
+     including any AVL tree header file, in which case libavl will
+     honor that value.
+
+ - Macro: RB_MAX_HEIGHT
+     This macro defines the maximum height of an AVL tree that can be
+     handled by functions that maintain a stack of nodes descended.
+     The default value is 32, which allows for red-black trees with a
+     maximum number of nodes of at least 65535.  This macro may be
+     defined by the user before including the red-black tree header
+     file, in which case libavl will honor that value.
+
+
+File: avl.info,  Node: Functions,  Next: Tree Creation,  Prev: Types,  Up: Top
+
+Functions
+*********
+
+   libavl is four libraries in one:
+
+   * An unthreaded AVL tree library.
+
+   * A threaded AVL tree library.
+
+   * A right-threaded AVL tree library.
+
+   * A red-black tree library.
+
+   Identifiers in these libraries are prefixed by `avl_', `avlt_',
+`avltr_', and `rb_', with corresponding header files `avl.h', `avlt.h',
+`avltr.h', and `rb.h', respectively.  The functions that they declare
+are defined in the `.c' files with the same names.
+
+   Most tree functions are implemented in all three libraries, but
+threading allows more generality of operation.  So, the threaded and
+right-threaded libraries offer a few additional functions for finding
+the next or previous node from a given node.  In addition, they offer
+functions for converting trees from threaded or right-threaded
+representations to unthreaded, and vice versa.(1)
+
+   ---------- Footnotes ----------
+
+   (1) In general, you should build the sort of tree that you need to
+use, but occasionally it is useful to convert between tree types.
+
+
+File: avl.info,  Node: Tree Creation,  Next: Insertion,  Prev: Functions,  Up: Top
+
+Tree Creation
+*************
+
+   These functions deal with creation and destruction of AVL trees.
+
+ - Function: avl_tree * avl_create (avl_comparison_func COMPARE, void
+          *PARAM)
+ - Function: avlt_tree * avlt_create (avlt_comparison_func COMPARE,
+          void *PARAM)
+ - Function: avltr_tree * avltr_create (avltr_comparison_func COMPARE,
+          void *PARAM)
+ - Function: rb_tree * rb_create (avl_comparison_func COMPARE, void
+          *PARAM)
+     Create a new, empty tree with comparison function COMPARE.
+     Arbitrary user data PARAM is saved so that it can be passed to
+     user callback functions.
+
+ - Function: void avl_destroy (avl_tree *TREE, avl_node_func FREE)
+ - Function: void avlt_destroy (avlt_tree *TREE, avl_node_func FREE)
+ - Function: void avltr_destroy (avltr_tree *TREE, avl_node_func FREE)
+ - Function: void rb_destroy (rb_tree *TREE, avl_node_func FREE)
+     Destroys TREE, releasing all of its storage.  If FREE is non-null,
+     then it is called for every node in postorder before that node is
+     freed.
+
+ - Function: void avl_free (avl_tree *TREE)
+ - Function: void avlt_free (avlt_tree *TREE)
+ - Function: void avltr_free (avltr_tree *TREE)
+ - Function: void rb_free (rb_tree *TREE)
+     Destroys TREE, releasing all of its storage.  The data in each
+     node is freed with a call to the standard C library function
+     `free'.
+
+ - Function: avl_tree * avl_copy (const avl_tree *TREE, avl_copy_func
+          COPY)
+ - Function: avlt_tree * avl_copy (const avlt_tree *TREE, avl_copy_func
+          COPY)
+ - Function: avltr_tree * avl_copy (const avltr_tree *TREE,
+          avl_copy_func COPY)
+ - Function: rb_tree * rb_copy (const rb_tree *TREE, avl_copy_func COPY)
+     Copies the contents of TREE into a new tree, and returns the new
+     tree.  If COPY is non-null, then it is called to make a new copy
+     of each node's data; otherwise, the node data is copied verbatim
+     into the new tree.
+
+ - Function: int avl_count (const avl_tree *TREE)
+ - Function: int avlt_count (const avlt_tree *TREE)
+ - Function: int avltr_count (const avltr_tree *TREE)
+ - Function: int rb_count (const rb_tree *TREE)
+     Returns the number of nodes in TREE.
+
+ - Function: void * xmalloc (size_t SIZE)
+     This is not a function defined by libavl.  Instead, it is a
+     function that the user program can define.  It must allocate SIZE
+     bytes using `malloc' and return it.  It can handle out-of-memory
+     errors however it chooses, but it may not ever return a null
+     pointer.
+
+     If there is an `xmalloc' function defined for use by libavl, the
+     source files (`avl.c', `avlt.c', `avltr.c', `rb.c') must be
+     compiled with `HAVE_XMALLOC' defined.  Otherwise, the library will
+     use its internal static `xmalloc', which handles out-of-memory
+     errors by printing a message `virtual memory exhausted' to stderr
+     and terminating the program with exit code `EXIT_FAILURE'.
+
+
+File: avl.info,  Node: Insertion,  Next: Searching,  Prev: Tree Creation,  Up: Top
+
+Insertion and Deletion
+**********************
+
+   These function insert nodes, delete nodes, and search for nodes in
+trees.
+
+ - Function: void ** avl_probe (avl_tree *TREE, void *DATA)
+ - Function: void ** avlt_probe (avlt_tree *TREE, void *DATA)
+ - Function: void ** avltr_probe (avltr_tree *TREE, void *DATA)
+ - Function: void ** rb_probe (rb_tree *TREE, void *DATA)
+     These are the workhorse functions for tree insertion.  They search
+     TREE for a node with data matching DATA.  If found, a pointer to
+     the matching data is returned.  Otherwise, a new node is created
+     for DATA, and a pointer to that data is returned.  In either case,
+     the pointer returned can be changed by the user, but the key data
+     used by the tree's comparison must not be changed(1).
+
+     It is usually easier to use one of the `avl_insert' or
+     `avl_replace' functions instead of `avl_probe' directly.
+
+     *Please note:* It's not a particularly good idea to insert a null
+     pointer as a data item into a tree, because several libavl
+     functions return a null pointer to indicate failure.  You can
+     sometimes avoid a problem by using functions that return a pointer
+     to a pointer instead of a plain pointer.  Also be wary of this
+     when casting an arithmetic type to a void pointer for
+     insertion--on typical architectures, 0's become null pointers when
+     this is done.
+
+ - Function: void * avl_insert (avl_tree *TREE, void *DATA)
+ - Function: void * avlt_insert (avlt_tree *TREE, void *DATA)
+ - Function: void * avltr_insert (avltr_tree *TREE, void *DATA)
+ - Function: void * rb_insert (rb_tree *TREE, void *DATA)
+     If a node with data matching DATA exists in TREE, returns the
+     matching data item.  Otherwise, inserts DATA into TREE and returns
+     a null pointer.
+
+ - Function: void avl_force_insert (avl_tree *TREE, void *DATA)
+ - Function: void avlt_force_insert (avlt_tree *TREE, void *DATA)
+ - Function: void avltr_force_insert (avltr_tree *TREE, void *DATA)
+ - Function: void rb_force_insert (rb_tree *TREE, void *DATA)
+     Inserts DATA into TREE.  If a node with data matching DATA exists
+     in TREE, aborts the program with an assertion violation.  This
+     function is implemented as a macro; if it is used, the standard C
+     header `assert.h' must also be included.  If macro `NDEBUG' is
+     defined when a libavl header is included, these functions are
+     short-circuited to a direct call to `avl_insert', and no check is
+     performed.
+
+ - Function: void * avl_replace (avl_tree *TREE, void *DATA)
+ - Function: void * avlt_replace (avlt_tree *TREE, void *DATA)
+ - Function: void * avltr_replace (avltr_tree *TREE, void *DATA)
+ - Function: void * rb_replace (rb_tree *TREE, void *DATA)
+     If a node with data matching DATA, such that the comparison
+     function returns 0, exists in TREE, replaces the node's data with
+     DATA and returns the node's former contents.  Otherwise, inserts
+     DATA into TREE and returns a null pointer.
+
+ - Function: void * avl_delete (avl_tree *TREE, const void *DATA)
+ - Function: void * avlt_delete (avlt_tree *TREE, const void *DATA)
+ - Function: void * avltr_delete (avltr_tree *TREE, const void *DATA)
+ - Function: void * rb_delete (rb_tree *TREE, const void *DATA)
+     Searches TREE for a node with data matching DATA.  If found, the
+     node is deleted and its data is returned.  Otherwise, returns a
+     null pointer.
+
+ - Function: void * avl_force_delete (avl_tree *TREE, const void *DATA)
+ - Function: void * avlt_force_delete (avlt_tree *TREE, const void
+          *DATA)
+ - Function: void * avltr_force_delete (avltr_tree *TREE, const void
+          *DATA)
+ - Function: void * rb_force_delete (rb_tree *TREE, const void *DATA)
+     Deletes a node with data matching DATA from TREE.  If no matching
+     node is found, aborts the program with an assertion violation.  If
+     macro `NDEBUG' is declared when a libavl header is included, these
+     functions are short-circuited to a direct call to `avl_delete',
+     and no check is performed.
+
+   ---------- Footnotes ----------
+
+   (1) It can be changed if this would not change the ordering of the
+nodes in the tree; i.e., if this would not cause the data in the node
+to be less than or equal to the previous node's data or greater than or
+equal to the next node's data.
+
+
+File: avl.info,  Node: Searching,  Next: Iteration,  Prev: Insertion,  Up: Top
+
+Searching
+*********
+
+   These function search a tree for an item without making an insertion
+or a deletion.
+
+ - Function: void * avl_find (avl_tree *TREE, const void *DATA)
+ - Function: void ** avlt_find (avlt_tree *TREE, const void *DATA)
+ - Function: void ** avltr_find (avltr_tree *TREE, const void *DATA)
+ - Function: void * rb_find (rb_tree *TREE, const void *DATA)
+     Searches TREE for a node with data matching DATA, If found,
+     returns the node's data (for threaded and right-threaded trees, a
+     pointer to the node's data).  Otherwise, returns a null pointer.
+
+ - Function: void * avl_find_close (avl_tree *TREE, const void *DATA)
+ - Function: void ** avlt_find_close (avlt_tree *TREE, const void *DATA)
+ - Function: void ** avltr_find_close (avltr_tree *TREE, const void
+          *DATA)
+ - Function: void * rb_find_close (rb_tree *TREE, const void *DATA)
+     Searches TREE for a node with data matching DATA.  If found,
+     returns the node's data (for threaded and right-threaded trees, a
+     pointer to the node's data).  If no matching item is found, then it
+     finds a node whose data is "close" to DATA; either the node
+     closest in value to DATA, or the node either before or after the
+     node with the closest value.  Returns a null pointer if the tree
+     does not contain any nodes.
+
+
+File: avl.info,  Node: Iteration,  Next: Conversion,  Prev: Searching,  Up: Top
+
+Iteration
+*********
+
+   These functions allow the caller to iterate across the items in a
+tree.
+
+ - Function: void avl_walk (const avl_tree *TREE, avl_node_func
+          OPERATE, void *PARAM)
+ - Function: void avlt_walk (const avlt_tree *TREE, avl_node_func
+          OPERATE, void *PARAM)
+ - Function: void avltr_walk (const avltr_tree *TREE, avl_node_func
+          OPERATE, void *PARAM)
+ - Function: void rb_walk (const rb_tree *TREE, avl_node_func OPERATE,
+          void *PARAM)
+     Walks through all the nodes in TREE, and calls function OPERATE
+     for each node in inorder.  PARAM overrides the value passed to
+     `avl_create' (and family) for this operation only.  OPERATE must
+     not change the key data in the nodes in a way that would reorder
+     the data values or cause two values to become equal.
+
+ - Function: void * avl_traverse (const avl_tree *TREE, avl_traverser
+          *TRAV)
+ - Function: void * avlt_traverse (const avlt_tree *TREE,
+          avlt_traverser *TRAV)
+ - Function: void * avltr_traverse (const avltr_tree *TREE,
+          avltr_traverser *TRAV)
+ - Function: void * rb_traverse (const rb_tree *TREE, rb_traverser
+          *TRAV)
+     Returns each of TREE's nodes' data values in sequence, then a null
+     pointer to indicate the last item.  TRAV must be initialized
+     before the first call, either in a declaration like that below, or
+     using one of the functions below.
+
+          avl_traverser trav = AVL_TRAVERSER_INIT;
+
+     Each `avl_traverser' (and family) is a separate, independent
+     iterator.
+
+     For threaded and right-threaded trees, `avlt_next' or
+     `avltr_next', respectively, are faster and more memory-efficient
+     than `avlt_traverse' or `avltr_traverse'.
+
+ - Function: void * avl_init_traverser (avl_traverser *TRAV)
+ - Function: void * avlt_init_traverser (avlt_traverser *TRAV)
+ - Function: void * avltr_init_traverser (avltr_traverser *TRAV)
+ - Function: void * rb_init_traverser (rb_traverser *TRAV)
+     Initializes the specified tree traverser structure.  After this
+     function is called, the next call to the corresponding
+     `*_traverse' function will return the smallest value in the
+     appropriate tree.
+
+ - Function: void ** avlt_next (const avlt_tree *TREE, void **DATA)
+ - Function: void ** avltr_next (const avltr_tree *TREE, void **DATA)
+     DATA must be a null pointer or a pointer to a data item in AVL
+     tree TREE.  Returns a pointer to the next data item after DATA in
+     TREE in inorder (this is the first item if DATA is a null
+     pointer), or a null pointer if DATA was the last item in TREE.
+
+ - Function: void ** avltr_prev (const avltr_tree *TREE, void **DATA)
+     DATA must be a null pointer or a pointer to a data item in AVL
+     tree TREE.  Returns a pointer to the previous data item before
+     DATA in TREE in inorder (this is the last, or greatest valued,
+     item if DATA is a null pointer), or a null pointer if DATA was the
+     first item in TREE.
+
+
+File: avl.info,  Node: Conversion,  Next: Author,  Prev: Iteration,  Up: Top
+
+Conversion
+**********
+
+ - Function: avlt_tree * avlt_thread (avl_tree *TREE)
+ - Function: avltr_tree * avltr_thread (avl_tree *TREE)
+     Adds symmetric threads or right threads, respectively, to
+     unthreaded AVL tree TREE and returns a pointer to TREE cast to the
+     appropriate type.  After one of these functions is called,
+     threaded or right-threaded functions, as appropriate, must be used
+     with TREE; unthreaded functions may not be used.
+
+ - Function: avl_tree * avlt_unthread (avlt_tree *TREE)
+ - Function: avl_tree * avltr_unthread (avltr_tree *TREE)
+     Cuts all threads in threaded or right-threaded, respectively, AVL
+     tree TREE and returns a pointer to TREE cast to `avl_tree *'.
+     After one of these functions is called, unthreaded functions must
+     be used with TREE; threaded or right-threaded functions may not be
+     used.
+
+
+File: avl.info,  Node: Author,  Next: Index,  Prev: Conversion,  Up: Top
+
+Author
+******
+
+   libavl was written by Ben Pfaff <blp@gnu.org>.
+
+   libavl's generic tree algorithms and AVL algorithms are based on
+those found in Donald Knuth's venerable `Art of Computer Programming'
+series from Addison-Wesley, primarily Volumes 1 and 3.  libavl's
+red-black tree algorithms are based on those found in Cormen et al.,
+`Introduction to Algorithms', 2nd ed., from MIT Press.
+
+
+File: avl.info,  Node: Index,  Prev: Author,  Up: Top
+
+Index
+*****
+
+* Menu:
+
+* `Art of Computer Programming':         Author.
+* Adel'son-Velskii, G. M.:               Introduction to balanced binary trees.
+* author:                                Author.
+* AVL tree:                              Introduction to balanced binary trees.
+* avl_comparison_func:                   Types.
+* avl_copy:                              Tree Creation.
+* avl_copy_func:                         Types.
+* avl_count:                             Tree Creation.
+* avl_create:                            Tree Creation.
+* avl_delete:                            Insertion.
+* avl_destroy:                           Tree Creation.
+* avl_find:                              Searching.
+* avl_find_close:                        Searching.
+* avl_force_delete:                      Insertion.
+* avl_force_insert:                      Insertion.
+* avl_free:                              Tree Creation.
+* avl_init_traverser:                    Iteration.
+* avl_insert:                            Insertion.
+* AVL_MAX_HEIGHT:                        Types.
+* avl_node:                              Types.
+* avl_node_func:                         Types.
+* avl_probe:                             Insertion.
+* avl_replace:                           Insertion.
+* avl_traverse:                          Iteration.
+* avl_traverser:                         Types.
+* avl_tree:                              Types.
+* avl_walk:                              Iteration.
+* avlt_count:                            Tree Creation.
+* avlt_create:                           Tree Creation.
+* avlt_delete:                           Insertion.
+* avlt_destroy:                          Tree Creation.
+* avlt_find:                             Searching.
+* avlt_find_close:                       Searching.
+* avlt_force_delete:                     Insertion.
+* avlt_force_insert:                     Insertion.
+* avlt_free:                             Tree Creation.
+* avlt_init_traverser:                   Iteration.
+* avlt_insert:                           Insertion.
+* avlt_next:                             Iteration.
+* avlt_node:                             Types.
+* avlt_probe:                            Insertion.
+* avlt_replace:                          Insertion.
+* avlt_thread:                           Conversion.
+* avlt_traverse:                         Iteration.
+* avlt_traverser:                        Types.
+* avlt_tree:                             Types.
+* avlt_unthread:                         Conversion.
+* avlt_walk:                             Iteration.
+* avltr_count:                           Tree Creation.
+* avltr_create:                          Tree Creation.
+* avltr_delete:                          Insertion.
+* avltr_destroy:                         Tree Creation.
+* avltr_find:                            Searching.
+* avltr_find_close:                      Searching.
+* avltr_force_delete:                    Insertion.
+* avltr_force_insert:                    Insertion.
+* avltr_free:                            Tree Creation.
+* avltr_init_traverser:                  Iteration.
+* avltr_insert:                          Insertion.
+* avltr_next:                            Iteration.
+* avltr_node:                            Types.
+* avltr_prev:                            Iteration.
+* avltr_probe:                           Insertion.
+* avltr_replace:                         Insertion.
+* avltr_thread:                          Conversion.
+* avltr_traverse:                        Iteration.
+* avltr_traverser:                       Types.
+* avltr_tree:                            Types.
+* avltr_unthread:                        Conversion.
+* avltr_walk:                            Iteration.
+* binary tree:                           Introduction to balanced binary trees.
+* hash table:                            Introduction to balanced binary trees.
+* Knuth, Donald Ervin:                   Author.
+* Landis, E. M.:                         Introduction to balanced binary trees.
+* Pfaff, Benjamin Levy:                  Author.
+* rb_copy:                               Tree Creation.
+* rb_count:                              Tree Creation.
+* rb_create:                             Tree Creation.
+* rb_delete:                             Insertion.
+* rb_destroy:                            Tree Creation.
+* rb_find:                               Searching.
+* rb_find_close:                         Searching.
+* rb_force_delete:                       Insertion.
+* rb_force_insert:                       Insertion.
+* rb_free:                               Tree Creation.
+* rb_init_traverser:                     Iteration.
+* rb_insert:                             Insertion.
+* RB_MAX_HEIGHT:                         Types.
+* rb_node:                               Types.
+* rb_probe:                              Insertion.
+* rb_replace:                            Insertion.
+* rb_traverse:                           Iteration.
+* rb_traverser:                          Types.
+* rb_tree:                               Types.
+* rb_walk:                               Iteration.
+* rebalancing:                           Introduction to balanced binary trees.
+* red-black tree:                        Introduction to balanced binary trees.
+* right threads:                         Functions.
+* threads:                               Functions.
+* unthreaded:                            Functions.
+* xmalloc:                               Tree Creation.
+
+
+
+Tag Table:
+Node: Top891
+Node: Introduction to balanced binary trees1340
+Node: Introduction to threaded trees5260
+Ref: Introduction to threaded trees-Footnote-17757
+Node: Types7871
+Node: Functions10904
+Ref: Functions-Footnote-111877
+Node: Tree Creation12014
+Node: Insertion15035
+Ref: Insertion-Footnote-119214
+Node: Searching19458
+Node: Iteration20863
+Node: Conversion23929
+Node: Author24875
+Node: Index25345
+
+End Tag Table
diff --git a/avl-1.4.0/avlt.h b/avl-1.4.0/avlt.h
new file mode 100644
index 0000000..94272b4
--- /dev/null
+++ b/avl-1.4.0/avlt.h
@@ -0,0 +1,142 @@
+/* libavl - manipulates AVL trees.
+   Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License as
+   published by the Free Software Foundation; either version 2 of the
+   License, or (at your option) any later version.
+
+   This program 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 General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+   02111-1307, USA.
+
+   The author may be contacted at <pfaffben@pilot.msu.edu> on the
+   Internet, or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA
+   through more mundane means. */
+
+/* This is file avlt.h in libavl. */
+
+#if !avlt_h
+#define avlt_h 1
+
+/* The default maximum height of 32 allows for AVL trees having
+   between 5,704,880 and 4,294,967,295 nodes, depending on order of
+   insertion.  You may change this compile-time constant as you
+   wish. */
+#ifndef AVL_MAX_HEIGHT
+#define AVL_MAX_HEIGHT	32
+#endif
+
+/* Structure for a node in a threaded AVL tree. */
+typedef struct avlt_node
+  {
+    void *data;			/* Pointer to data. */
+    struct avlt_node *link[2];	/* Subtrees or threads. */
+    signed char bal;		/* Balance factor. */
+    char cache;			/* Used during insertion. */
+    signed char tag[2];		/* Left and right thread tags. */
+  }
+avlt_node;
+
+/* Used for traversing a threaded AVL tree. */
+typedef struct avlt_traverser
+  {
+    int init;			/* Initialized? */
+    const avlt_node *p;		/* Last node returned. */
+  }
+avlt_traverser;
+
+/* Initializer for avlt_traverser. */
+#define AVLT_TRAVERSER_INIT {0}
+
+/* Function types. */
+#if !AVL_FUNC_TYPES
+#define AVL_FUNC_TYPES 1
+typedef int (*avl_comparison_func) (const void *a, const void *b, void *param);
+typedef void (*avl_node_func) (void *data, void *param);
+typedef void *(*avl_copy_func) (void *data, void *param);
+#endif
+
+/* Structure which holds information about a threaded AVL tree. */
+typedef struct avlt_tree
+  {
+    avlt_node root;		/* Tree root node. */
+    avl_comparison_func cmp;	/* Used to compare keys. */
+    int count;			/* Number of nodes in the tree. */
+    void *param;		/* Arbitary user data. */
+  }
+avlt_tree;
+
+/* General functions. */
+avlt_tree *avlt_create (avl_comparison_func, void *param);
+void avlt_destroy (avlt_tree *, avl_node_func);
+void avlt_free (avlt_tree *);
+int avlt_count (const avlt_tree *);
+avlt_tree *avlt_copy (const avlt_tree *, avl_copy_func);
+struct avl_tree;
+avlt_tree *avlt_thread (struct avl_tree *);
+struct avl_tree *avlt_unthread (avlt_tree *);
+
+/* Walk the tree. */
+void avlt_walk (const avlt_tree *, avl_node_func, void *param);
+void *avlt_traverse (const avlt_tree *, avlt_traverser *);
+#define avlt_init_traverser(TRAVERSER) ((TRAVERSER)->init = 0)
+void **avlt_next (const avlt_tree *tree, void **item);
+void **avlt_prev (const avlt_tree *tree, void **item);
+
+/* Search for a given item. */
+void **avlt_probe (avlt_tree *, void *);
+void *avlt_delete (avlt_tree *, const void *);
+void **avlt_find (const avlt_tree *, const void *);
+void **avlt_find_close (const avlt_tree *, const void *);
+
+#if __GCC__ >= 2
+extern inline void *
+avlt_insert (avlt_tree *tree, void *item)
+{
+  void **p = avlt_probe (tree, item);
+  return (*p == item) ? NULL : *p;
+}
+
+extern inline void *
+avlt_replace (avlt_tree *tree, void *item)
+{
+  void **p = avlt_probe (tree, item);
+  if (*p == item)
+    return NULL;
+  else
+    {
+      void *r = *p;
+      *p = item;
+      return r;
+    }
+}
+#else /* not gcc */
+void *avlt_insert (avlt_tree *tree, void *item);
+void *avlt_replace (avlt_tree *tree, void *item);
+#endif /* not gcc */
+
+/* Easy assertions on insertion & deletion. */
+#ifndef NDEBUG
+#define avlt_force_insert(A, B)			\
+	do					\
+	  {					\
+            void *r = avlt_insert (A, B);	\
+	    assert (r == NULL);			\
+	  }					\
+	while (0)
+void *avlt_force_delete (avlt_tree *, void *);
+#else
+#define avlt_force_insert(A, B)			\
+	avlt_insert (A, B)
+#define avlt_force_delete(A, B)			\
+	avlt_delete (A, B)
+#endif
+
+#endif /* avlt_h */
diff --git a/avl-1.4.0/configure b/avl-1.4.0/configure
new file mode 100755
index 0000000..5b955a9
--- /dev/null
+++ b/avl-1.4.0/configure
@@ -0,0 +1,1297 @@
+#! /bin/sh
+
+# Guess values for system-dependent variables and create Makefiles.
+# Generated automatically using autoconf version 2.13 
+# Copyright (C) 1992, 93, 94, 95, 96 Free Software Foundation, Inc.
+#
+# This configure script is free software; the Free Software Foundation
+# gives unlimited permission to copy, distribute and modify it.
+
+# Defaults:
+ac_help=
+ac_default_prefix=/usr/local
+# Any additions from configure.in:
+
+# Initialize some variables set by options.
+# The variables have the same names as the options, with
+# dashes changed to underlines.
+build=NONE
+cache_file=./config.cache
+exec_prefix=NONE
+host=NONE
+no_create=
+nonopt=NONE
+no_recursion=
+prefix=NONE
+program_prefix=NONE
+program_suffix=NONE
+program_transform_name=s,x,x,
+silent=
+site=
+srcdir=
+target=NONE
+verbose=
+x_includes=NONE
+x_libraries=NONE
+bindir='${exec_prefix}/bin'
+sbindir='${exec_prefix}/sbin'
+libexecdir='${exec_prefix}/libexec'
+datadir='${prefix}/share'
+sysconfdir='${prefix}/etc'
+sharedstatedir='${prefix}/com'
+localstatedir='${prefix}/var'
+libdir='${exec_prefix}/lib'
+includedir='${prefix}/include'
+oldincludedir='/usr/include'
+infodir='${prefix}/info'
+mandir='${prefix}/man'
+
+# Initialize some other variables.
+subdirs=
+MFLAGS= MAKEFLAGS=
+SHELL=${CONFIG_SHELL-/bin/sh}
+# Maximum number of lines to put in a shell here document.
+ac_max_here_lines=12
+
+ac_prev=
+for ac_option
+do
+
+  # If the previous option needs an argument, assign it.
+  if test -n "$ac_prev"; then
+    eval "$ac_prev=\$ac_option"
+    ac_prev=
+    continue
+  fi
+
+  case "$ac_option" in
+  -*=*) ac_optarg=`echo "$ac_option" | sed 's/[-_a-zA-Z0-9]*=//'` ;;
+  *) ac_optarg= ;;
+  esac
+
+  # Accept the important Cygnus configure options, so we can diagnose typos.
+
+  case "$ac_option" in
+
+  -bindir | --bindir | --bindi | --bind | --bin | --bi)
+    ac_prev=bindir ;;
+  -bindir=* | --bindir=* | --bindi=* | --bind=* | --bin=* | --bi=*)
+    bindir="$ac_optarg" ;;
+
+  -build | --build | --buil | --bui | --bu)
+    ac_prev=build ;;
+  -build=* | --build=* | --buil=* | --bui=* | --bu=*)
+    build="$ac_optarg" ;;
+
+  -cache-file | --cache-file | --cache-fil | --cache-fi \
+  | --cache-f | --cache- | --cache | --cach | --cac | --ca | --c)
+    ac_prev=cache_file ;;
+  -cache-file=* | --cache-file=* | --cache-fil=* | --cache-fi=* \
+  | --cache-f=* | --cache-=* | --cache=* | --cach=* | --cac=* | --ca=* | --c=*)
+    cache_file="$ac_optarg" ;;
+
+  -datadir | --datadir | --datadi | --datad | --data | --dat | --da)
+    ac_prev=datadir ;;
+  -datadir=* | --datadir=* | --datadi=* | --datad=* | --data=* | --dat=* \
+  | --da=*)
+    datadir="$ac_optarg" ;;
+
+  -disable-* | --disable-*)
+    ac_feature=`echo $ac_option|sed -e 's/-*disable-//'`
+    # Reject names that are not valid shell variable names.
+    if test -n "`echo $ac_feature| sed 's/[-a-zA-Z0-9_]//g'`"; then
+      { echo "configure: error: $ac_feature: invalid feature name" 1>&2; exit 1; }
+    fi
+    ac_feature=`echo $ac_feature| sed 's/-/_/g'`
+    eval "enable_${ac_feature}=no" ;;
+
+  -enable-* | --enable-*)
+    ac_feature=`echo $ac_option|sed -e 's/-*enable-//' -e 's/=.*//'`
+    # Reject names that are not valid shell variable names.
+    if test -n "`echo $ac_feature| sed 's/[-_a-zA-Z0-9]//g'`"; then
+      { echo "configure: error: $ac_feature: invalid feature name" 1>&2; exit 1; }
+    fi
+    ac_feature=`echo $ac_feature| sed 's/-/_/g'`
+    case "$ac_option" in
+      *=*) ;;
+      *) ac_optarg=yes ;;
+    esac
+    eval "enable_${ac_feature}='$ac_optarg'" ;;
+
+  -exec-prefix | --exec_prefix | --exec-prefix | --exec-prefi \
+  | --exec-pref | --exec-pre | --exec-pr | --exec-p | --exec- \
+  | --exec | --exe | --ex)
+    ac_prev=exec_prefix ;;
+  -exec-prefix=* | --exec_prefix=* | --exec-prefix=* | --exec-prefi=* \
+  | --exec-pref=* | --exec-pre=* | --exec-pr=* | --exec-p=* | --exec-=* \
+  | --exec=* | --exe=* | --ex=*)
+    exec_prefix="$ac_optarg" ;;
+
+  -gas | --gas | --ga | --g)
+    # Obsolete; use --with-gas.
+    with_gas=yes ;;
+
+  -help | --help | --hel | --he)
+    # Omit some internal or obsolete options to make the list less imposing.
+    # This message is too long to be a string in the A/UX 3.1 sh.
+    cat << EOF
+Usage: configure [options] [host]
+Options: [defaults in brackets after descriptions]
+Configuration:
+  --cache-file=FILE       cache test results in FILE
+  --help                  print this message
+  --no-create             do not create output files
+  --quiet, --silent       do not print \`checking...' messages
+  --version               print the version of autoconf that created configure
+Directory and file names:
+  --prefix=PREFIX         install architecture-independent files in PREFIX
+                          [$ac_default_prefix]
+  --exec-prefix=EPREFIX   install architecture-dependent files in EPREFIX
+                          [same as prefix]
+  --bindir=DIR            user executables in DIR [EPREFIX/bin]
+  --sbindir=DIR           system admin executables in DIR [EPREFIX/sbin]
+  --libexecdir=DIR        program executables in DIR [EPREFIX/libexec]
+  --datadir=DIR           read-only architecture-independent data in DIR
+                          [PREFIX/share]
+  --sysconfdir=DIR        read-only single-machine data in DIR [PREFIX/etc]
+  --sharedstatedir=DIR    modifiable architecture-independent data in DIR
+                          [PREFIX/com]
+  --localstatedir=DIR     modifiable single-machine data in DIR [PREFIX/var]
+  --libdir=DIR            object code libraries in DIR [EPREFIX/lib]
+  --includedir=DIR        C header files in DIR [PREFIX/include]
+  --oldincludedir=DIR     C header files for non-gcc in DIR [/usr/include]
+  --infodir=DIR           info documentation in DIR [PREFIX/info]
+  --mandir=DIR            man documentation in DIR [PREFIX/man]
+  --srcdir=DIR            find the sources in DIR [configure dir or ..]
+  --program-prefix=PREFIX prepend PREFIX to installed program names
+  --program-suffix=SUFFIX append SUFFIX to installed program names
+  --program-transform-name=PROGRAM
+                          run sed PROGRAM on installed program names
+EOF
+    cat << EOF
+Host type:
+  --build=BUILD           configure for building on BUILD [BUILD=HOST]
+  --host=HOST             configure for HOST [guessed]
+  --target=TARGET         configure for TARGET [TARGET=HOST]
+Features and packages:
+  --disable-FEATURE       do not include FEATURE (same as --enable-FEATURE=no)
+  --enable-FEATURE[=ARG]  include FEATURE [ARG=yes]
+  --with-PACKAGE[=ARG]    use PACKAGE [ARG=yes]
+  --without-PACKAGE       do not use PACKAGE (same as --with-PACKAGE=no)
+  --x-includes=DIR        X include files are in DIR
+  --x-libraries=DIR       X library files are in DIR
+EOF
+    if test -n "$ac_help"; then
+      echo "--enable and --with options recognized:$ac_help"
+    fi
+    exit 0 ;;
+
+  -host | --host | --hos | --ho)
+    ac_prev=host ;;
+  -host=* | --host=* | --hos=* | --ho=*)
+    host="$ac_optarg" ;;
+
+  -includedir | --includedir | --includedi | --included | --include \
+  | --includ | --inclu | --incl | --inc)
+    ac_prev=includedir ;;
+  -includedir=* | --includedir=* | --includedi=* | --included=* | --include=* \
+  | --includ=* | --inclu=* | --incl=* | --inc=*)
+    includedir="$ac_optarg" ;;
+
+  -infodir | --infodir | --infodi | --infod | --info | --inf)
+    ac_prev=infodir ;;
+  -infodir=* | --infodir=* | --infodi=* | --infod=* | --info=* | --inf=*)
+    infodir="$ac_optarg" ;;
+
+  -libdir | --libdir | --libdi | --libd)
+    ac_prev=libdir ;;
+  -libdir=* | --libdir=* | --libdi=* | --libd=*)
+    libdir="$ac_optarg" ;;
+
+  -libexecdir | --libexecdir | --libexecdi | --libexecd | --libexec \
+  | --libexe | --libex | --libe)
+    ac_prev=libexecdir ;;
+  -libexecdir=* | --libexecdir=* | --libexecdi=* | --libexecd=* | --libexec=* \
+  | --libexe=* | --libex=* | --libe=*)
+    libexecdir="$ac_optarg" ;;
+
+  -localstatedir | --localstatedir | --localstatedi | --localstated \
+  | --localstate | --localstat | --localsta | --localst \
+  | --locals | --local | --loca | --loc | --lo)
+    ac_prev=localstatedir ;;
+  -localstatedir=* | --localstatedir=* | --localstatedi=* | --localstated=* \
+  | --localstate=* | --localstat=* | --localsta=* | --localst=* \
+  | --locals=* | --local=* | --loca=* | --loc=* | --lo=*)
+    localstatedir="$ac_optarg" ;;
+
+  -mandir | --mandir | --mandi | --mand | --man | --ma | --m)
+    ac_prev=mandir ;;
+  -mandir=* | --mandir=* | --mandi=* | --mand=* | --man=* | --ma=* | --m=*)
+    mandir="$ac_optarg" ;;
+
+  -nfp | --nfp | --nf)
+    # Obsolete; use --without-fp.
+    with_fp=no ;;
+
+  -no-create | --no-create | --no-creat | --no-crea | --no-cre \
+  | --no-cr | --no-c)
+    no_create=yes ;;
+
+  -no-recursion | --no-recursion | --no-recursio | --no-recursi \
+  | --no-recurs | --no-recur | --no-recu | --no-rec | --no-re | --no-r)
+    no_recursion=yes ;;
+
+  -oldincludedir | --oldincludedir | --oldincludedi | --oldincluded \
+  | --oldinclude | --oldinclud | --oldinclu | --oldincl | --oldinc \
+  | --oldin | --oldi | --old | --ol | --o)
+    ac_prev=oldincludedir ;;
+  -oldincludedir=* | --oldincludedir=* | --oldincludedi=* | --oldincluded=* \
+  | --oldinclude=* | --oldinclud=* | --oldinclu=* | --oldincl=* | --oldinc=* \
+  | --oldin=* | --oldi=* | --old=* | --ol=* | --o=*)
+    oldincludedir="$ac_optarg" ;;
+
+  -prefix | --prefix | --prefi | --pref | --pre | --pr | --p)
+    ac_prev=prefix ;;
+  -prefix=* | --prefix=* | --prefi=* | --pref=* | --pre=* | --pr=* | --p=*)
+    prefix="$ac_optarg" ;;
+
+  -program-prefix | --program-prefix | --program-prefi | --program-pref \
+  | --program-pre | --program-pr | --program-p)
+    ac_prev=program_prefix ;;
+  -program-prefix=* | --program-prefix=* | --program-prefi=* \
+  | --program-pref=* | --program-pre=* | --program-pr=* | --program-p=*)
+    program_prefix="$ac_optarg" ;;
+
+  -program-suffix | --program-suffix | --program-suffi | --program-suff \
+  | --program-suf | --program-su | --program-s)
+    ac_prev=program_suffix ;;
+  -program-suffix=* | --program-suffix=* | --program-suffi=* \
+  | --program-suff=* | --program-suf=* | --program-su=* | --program-s=*)
+    program_suffix="$ac_optarg" ;;
+
+  -program-transform-name | --program-transform-name \
+  | --program-transform-nam | --program-transform-na \
+  | --program-transform-n | --program-transform- \
+  | --program-transform | --program-transfor \
+  | --program-transfo | --program-transf \
+  | --program-trans | --program-tran \
+  | --progr-tra | --program-tr | --program-t)
+    ac_prev=program_transform_name ;;
+  -program-transform-name=* | --program-transform-name=* \
+  | --program-transform-nam=* | --program-transform-na=* \
+  | --program-transform-n=* | --program-transform-=* \
+  | --program-transform=* | --program-transfor=* \
+  | --program-transfo=* | --program-transf=* \
+  | --program-trans=* | --program-tran=* \
+  | --progr-tra=* | --program-tr=* | --program-t=*)
+    program_transform_name="$ac_optarg" ;;
+
+  -q | -quiet | --quiet | --quie | --qui | --qu | --q \
+  | -silent | --silent | --silen | --sile | --sil)
+    silent=yes ;;
+
+  -sbindir | --sbindir | --sbindi | --sbind | --sbin | --sbi | --sb)
+    ac_prev=sbindir ;;
+  -sbindir=* | --sbindir=* | --sbindi=* | --sbind=* | --sbin=* \
+  | --sbi=* | --sb=*)
+    sbindir="$ac_optarg" ;;
+
+  -sharedstatedir | --sharedstatedir | --sharedstatedi \
+  | --sharedstated | --sharedstate | --sharedstat | --sharedsta \
+  | --sharedst | --shareds | --shared | --share | --shar \
+  | --sha | --sh)
+    ac_prev=sharedstatedir ;;
+  -sharedstatedir=* | --sharedstatedir=* | --sharedstatedi=* \
+  | --sharedstated=* | --sharedstate=* | --sharedstat=* | --sharedsta=* \
+  | --sharedst=* | --shareds=* | --shared=* | --share=* | --shar=* \
+  | --sha=* | --sh=*)
+    sharedstatedir="$ac_optarg" ;;
+
+  -site | --site | --sit)
+    ac_prev=site ;;
+  -site=* | --site=* | --sit=*)
+    site="$ac_optarg" ;;
+
+  -srcdir | --srcdir | --srcdi | --srcd | --src | --sr)
+    ac_prev=srcdir ;;
+  -srcdir=* | --srcdir=* | --srcdi=* | --srcd=* | --src=* | --sr=*)
+    srcdir="$ac_optarg" ;;
+
+  -sysconfdir | --sysconfdir | --sysconfdi | --sysconfd | --sysconf \
+  | --syscon | --sysco | --sysc | --sys | --sy)
+    ac_prev=sysconfdir ;;
+  -sysconfdir=* | --sysconfdir=* | --sysconfdi=* | --sysconfd=* | --sysconf=* \
+  | --syscon=* | --sysco=* | --sysc=* | --sys=* | --sy=*)
+    sysconfdir="$ac_optarg" ;;
+
+  -target | --target | --targe | --targ | --tar | --ta | --t)
+    ac_prev=target ;;
+  -target=* | --target=* | --targe=* | --targ=* | --tar=* | --ta=* | --t=*)
+    target="$ac_optarg" ;;
+
+  -v | -verbose | --verbose | --verbos | --verbo | --verb)
+    verbose=yes ;;
+
+  -version | --version | --versio | --versi | --vers)
+    echo "configure generated by autoconf version 2.13"
+    exit 0 ;;
+
+  -with-* | --with-*)
+    ac_package=`echo $ac_option|sed -e 's/-*with-//' -e 's/=.*//'`
+    # Reject names that are not valid shell variable names.
+    if test -n "`echo $ac_package| sed 's/[-_a-zA-Z0-9]//g'`"; then
+      { echo "configure: error: $ac_package: invalid package name" 1>&2; exit 1; }
+    fi
+    ac_package=`echo $ac_package| sed 's/-/_/g'`
+    case "$ac_option" in
+      *=*) ;;
+      *) ac_optarg=yes ;;
+    esac
+    eval "with_${ac_package}='$ac_optarg'" ;;
+
+  -without-* | --without-*)
+    ac_package=`echo $ac_option|sed -e 's/-*without-//'`
+    # Reject names that are not valid shell variable names.
+    if test -n "`echo $ac_package| sed 's/[-a-zA-Z0-9_]//g'`"; then
+      { echo "configure: error: $ac_package: invalid package name" 1>&2; exit 1; }
+    fi
+    ac_package=`echo $ac_package| sed 's/-/_/g'`
+    eval "with_${ac_package}=no" ;;
+
+  --x)
+    # Obsolete; use --with-x.
+    with_x=yes ;;
+
+  -x-includes | --x-includes | --x-include | --x-includ | --x-inclu \
+  | --x-incl | --x-inc | --x-in | --x-i)
+    ac_prev=x_includes ;;
+  -x-includes=* | --x-includes=* | --x-include=* | --x-includ=* | --x-inclu=* \
+  | --x-incl=* | --x-inc=* | --x-in=* | --x-i=*)
+    x_includes="$ac_optarg" ;;
+
+  -x-libraries | --x-libraries | --x-librarie | --x-librari \
+  | --x-librar | --x-libra | --x-libr | --x-lib | --x-li | --x-l)
+    ac_prev=x_libraries ;;
+  -x-libraries=* | --x-libraries=* | --x-librarie=* | --x-librari=* \
+  | --x-librar=* | --x-libra=* | --x-libr=* | --x-lib=* | --x-li=* | --x-l=*)
+    x_libraries="$ac_optarg" ;;
+
+  -*) { echo "configure: error: $ac_option: invalid option; use --help to show usage" 1>&2; exit 1; }
+    ;;
+
+  *)
+    if test -n "`echo $ac_option| sed 's/[-a-z0-9.]//g'`"; then
+      echo "configure: warning: $ac_option: invalid host type" 1>&2
+    fi
+    if test "x$nonopt" != xNONE; then
+      { echo "configure: error: can only configure for one host and one target at a time" 1>&2; exit 1; }
+    fi
+    nonopt="$ac_option"
+    ;;
+
+  esac
+done
+
+if test -n "$ac_prev"; then
+  { echo "configure: error: missing argument to --`echo $ac_prev | sed 's/_/-/g'`" 1>&2; exit 1; }
+fi
+
+trap 'rm -fr conftest* confdefs* core core.* *.core $ac_clean_files; exit 1' 1 2 15
+
+# File descriptor usage:
+# 0 standard input
+# 1 file creation
+# 2 errors and warnings
+# 3 some systems may open it to /dev/tty
+# 4 used on the Kubota Titan
+# 6 checking for... messages and results
+# 5 compiler messages saved in config.log
+if test "$silent" = yes; then
+  exec 6>/dev/null
+else
+  exec 6>&1
+fi
+exec 5>./config.log
+
+echo "\
+This file contains any messages produced by compilers while
+running configure, to aid debugging if configure makes a mistake.
+" 1>&5
+
+# Strip out --no-create and --no-recursion so they do not pile up.
+# Also quote any args containing shell metacharacters.
+ac_configure_args=
+for ac_arg
+do
+  case "$ac_arg" in
+  -no-create | --no-create | --no-creat | --no-crea | --no-cre \
+  | --no-cr | --no-c) ;;
+  -no-recursion | --no-recursion | --no-recursio | --no-recursi \
+  | --no-recurs | --no-recur | --no-recu | --no-rec | --no-re | --no-r) ;;
+  *" "*|*"	"*|*[\[\]\~\#\$\^\&\*\(\)\{\}\\\|\;\<\>\?]*)
+  ac_configure_args="$ac_configure_args '$ac_arg'" ;;
+  *) ac_configure_args="$ac_configure_args $ac_arg" ;;
+  esac
+done
+
+# NLS nuisances.
+# Only set these to C if already set.  These must not be set unconditionally
+# because not all systems understand e.g. LANG=C (notably SCO).
+# Fixing LC_MESSAGES prevents Solaris sh from translating var values in `set'!
+# Non-C LC_CTYPE values break the ctype check.
+if test "${LANG+set}"   = set; then LANG=C;   export LANG;   fi
+if test "${LC_ALL+set}" = set; then LC_ALL=C; export LC_ALL; fi
+if test "${LC_MESSAGES+set}" = set; then LC_MESSAGES=C; export LC_MESSAGES; fi
+if test "${LC_CTYPE+set}"    = set; then LC_CTYPE=C;    export LC_CTYPE;    fi
+
+# confdefs.h avoids OS command line length limits that DEFS can exceed.
+rm -rf conftest* confdefs.h
+# AIX cpp loses on an empty file, so make sure it contains at least a newline.
+echo > confdefs.h
+
+# A filename unique to this package, relative to the directory that
+# configure is in, which we can look for to find out if srcdir is correct.
+ac_unique_file=avl.c
+
+# Find the source files, if location was not specified.
+if test -z "$srcdir"; then
+  ac_srcdir_defaulted=yes
+  # Try the directory containing this script, then its parent.
+  ac_prog=$0
+  ac_confdir=`echo $ac_prog|sed 's%/[^/][^/]*$%%'`
+  test "x$ac_confdir" = "x$ac_prog" && ac_confdir=.
+  srcdir=$ac_confdir
+  if test ! -r $srcdir/$ac_unique_file; then
+    srcdir=..
+  fi
+else
+  ac_srcdir_defaulted=no
+fi
+if test ! -r $srcdir/$ac_unique_file; then
+  if test "$ac_srcdir_defaulted" = yes; then
+    { echo "configure: error: can not find sources in $ac_confdir or .." 1>&2; exit 1; }
+  else
+    { echo "configure: error: can not find sources in $srcdir" 1>&2; exit 1; }
+  fi
+fi
+srcdir=`echo "${srcdir}" | sed 's%\([^/]\)/*$%\1%'`
+
+# Prefer explicitly selected file to automatically selected ones.
+if test -z "$CONFIG_SITE"; then
+  if test "x$prefix" != xNONE; then
+    CONFIG_SITE="$prefix/share/config.site $prefix/etc/config.site"
+  else
+    CONFIG_SITE="$ac_default_prefix/share/config.site $ac_default_prefix/etc/config.site"
+  fi
+fi
+for ac_site_file in $CONFIG_SITE; do
+  if test -r "$ac_site_file"; then
+    echo "loading site script $ac_site_file"
+    . "$ac_site_file"
+  fi
+done
+
+if test -r "$cache_file"; then
+  echo "loading cache $cache_file"
+  . $cache_file
+else
+  echo "creating cache $cache_file"
+  > $cache_file
+fi
+
+ac_ext=c
+# CFLAGS is not in ac_cpp because -g, -O, etc. are not valid cpp options.
+ac_cpp='$CPP $CPPFLAGS'
+ac_compile='${CC-cc} -c $CFLAGS $CPPFLAGS conftest.$ac_ext 1>&5'
+ac_link='${CC-cc} -o conftest${ac_exeext} $CFLAGS $CPPFLAGS $LDFLAGS conftest.$ac_ext $LIBS 1>&5'
+cross_compiling=$ac_cv_prog_cc_cross
+
+ac_exeext=
+ac_objext=o
+if (echo "testing\c"; echo 1,2,3) | grep c >/dev/null; then
+  # Stardent Vistra SVR4 grep lacks -e, says ghazi@caip.rutgers.edu.
+  if (echo -n testing; echo 1,2,3) | sed s/-n/xn/ | grep xn >/dev/null; then
+    ac_n= ac_c='
+' ac_t='	'
+  else
+    ac_n=-n ac_c= ac_t=
+  fi
+else
+  ac_n= ac_c='\c' ac_t=
+fi
+
+
+ac_aux_dir=
+for ac_dir in $srcdir $srcdir/.. $srcdir/../..; do
+  if test -f $ac_dir/install-sh; then
+    ac_aux_dir=$ac_dir
+    ac_install_sh="$ac_aux_dir/install-sh -c"
+    break
+  elif test -f $ac_dir/install.sh; then
+    ac_aux_dir=$ac_dir
+    ac_install_sh="$ac_aux_dir/install.sh -c"
+    break
+  fi
+done
+if test -z "$ac_aux_dir"; then
+  { echo "configure: error: can not find install-sh or install.sh in $srcdir $srcdir/.. $srcdir/../.." 1>&2; exit 1; }
+fi
+ac_config_guess=$ac_aux_dir/config.guess
+ac_config_sub=$ac_aux_dir/config.sub
+ac_configure=$ac_aux_dir/configure # This should be Cygnus configure.
+
+# Find a good install program.  We prefer a C program (faster),
+# so one script is as good as another.  But avoid the broken or
+# incompatible versions:
+# SysV /etc/install, /usr/sbin/install
+# SunOS /usr/etc/install
+# IRIX /sbin/install
+# AIX /bin/install
+# AIX 4 /usr/bin/installbsd, which doesn't work without a -g flag
+# AFS /usr/afsws/bin/install, which mishandles nonexistent args
+# SVR4 /usr/ucb/install, which tries to use the nonexistent group "staff"
+# ./install, which can be erroneously created by make from ./install.sh.
+echo $ac_n "checking for a BSD compatible install""... $ac_c" 1>&6
+echo "configure:556: checking for a BSD compatible install" >&5
+if test -z "$INSTALL"; then
+if eval "test \"`echo '$''{'ac_cv_path_install'+set}'`\" = set"; then
+  echo $ac_n "(cached) $ac_c" 1>&6
+else
+    IFS="${IFS= 	}"; ac_save_IFS="$IFS"; IFS=":"
+  for ac_dir in $PATH; do
+    # Account for people who put trailing slashes in PATH elements.
+    case "$ac_dir/" in
+    /|./|.//|/etc/*|/usr/sbin/*|/usr/etc/*|/sbin/*|/usr/afsws/bin/*|/usr/ucb/*) ;;
+    *)
+      # OSF1 and SCO ODT 3.0 have their own names for install.
+      # Don't use installbsd from OSF since it installs stuff as root
+      # by default.
+      for ac_prog in ginstall scoinst install; do
+        if test -f $ac_dir/$ac_prog; then
+	  if test $ac_prog = install &&
+            grep dspmsg $ac_dir/$ac_prog >/dev/null 2>&1; then
+	    # AIX install.  It has an incompatible calling convention.
+	    :
+	  else
+	    ac_cv_path_install="$ac_dir/$ac_prog -c"
+	    break 2
+	  fi
+	fi
+      done
+      ;;
+    esac
+  done
+  IFS="$ac_save_IFS"
+
+fi
+  if test "${ac_cv_path_install+set}" = set; then
+    INSTALL="$ac_cv_path_install"
+  else
+    # As a last resort, use the slow shell script.  We don't cache a
+    # path for INSTALL within a source directory, because that will
+    # break other packages using the cache if that directory is
+    # removed, or if the path is relative.
+    INSTALL="$ac_install_sh"
+  fi
+fi
+echo "$ac_t""$INSTALL" 1>&6
+
+# Use test -z because SunOS4 sh mishandles braces in ${var-val}.
+# It thinks the first close brace ends the variable substitution.
+test -z "$INSTALL_PROGRAM" && INSTALL_PROGRAM='${INSTALL}'
+
+test -z "$INSTALL_SCRIPT" && INSTALL_SCRIPT='${INSTALL_PROGRAM}'
+
+test -z "$INSTALL_DATA" && INSTALL_DATA='${INSTALL} -m 644'
+
+echo $ac_n "checking whether build environment is sane""... $ac_c" 1>&6
+echo "configure:609: checking whether build environment is sane" >&5
+# Just in case
+sleep 1
+echo timestamp > conftestfile
+# Do `set' in a subshell so we don't clobber the current shell's
+# arguments.  Must try -L first in case configure is actually a
+# symlink; some systems play weird games with the mod time of symlinks
+# (eg FreeBSD returns the mod time of the symlink's containing
+# directory).
+if (
+   set X `ls -Lt $srcdir/configure conftestfile 2> /dev/null`
+   if test "$*" = "X"; then
+      # -L didn't work.
+      set X `ls -t $srcdir/configure conftestfile`
+   fi
+   if test "$*" != "X $srcdir/configure conftestfile" \
+      && test "$*" != "X conftestfile $srcdir/configure"; then
+
+      # If neither matched, then we have a broken ls.  This can happen
+      # if, for instance, CONFIG_SHELL is bash and it inherits a
+      # broken ls alias from the environment.  This has actually
+      # happened.  Such a system could not be considered "sane".
+      { echo "configure: error: ls -t appears to fail.  Make sure there is not a broken
+alias in your environment" 1>&2; exit 1; }
+   fi
+
+   test "$2" = conftestfile
+   )
+then
+   # Ok.
+   :
+else
+   { echo "configure: error: newly created file is older than distributed files!
+Check your system clock" 1>&2; exit 1; }
+fi
+rm -f conftest*
+echo "$ac_t""yes" 1>&6
+if test "$program_transform_name" = s,x,x,; then
+  program_transform_name=
+else
+  # Double any \ or $.  echo might interpret backslashes.
+  cat <<\EOF_SED > conftestsed
+s,\\,\\\\,g; s,\$,$$,g
+EOF_SED
+  program_transform_name="`echo $program_transform_name|sed -f conftestsed`"
+  rm -f conftestsed
+fi
+test "$program_prefix" != NONE &&
+  program_transform_name="s,^,${program_prefix},; $program_transform_name"
+# Use a double $ so make ignores it.
+test "$program_suffix" != NONE &&
+  program_transform_name="s,\$\$,${program_suffix},; $program_transform_name"
+
+# sed with no file args requires a program.
+test "$program_transform_name" = "" && program_transform_name="s,x,x,"
+
+echo $ac_n "checking whether ${MAKE-make} sets \${MAKE}""... $ac_c" 1>&6
+echo "configure:666: checking whether ${MAKE-make} sets \${MAKE}" >&5
+set dummy ${MAKE-make}; ac_make=`echo "$2" | sed 'y%./+-%__p_%'`
+if eval "test \"`echo '$''{'ac_cv_prog_make_${ac_make}_set'+set}'`\" = set"; then
+  echo $ac_n "(cached) $ac_c" 1>&6
+else
+  cat > conftestmake <<\EOF
+all:
+	@echo 'ac_maketemp="${MAKE}"'
+EOF
+# GNU make sometimes prints "make[1]: Entering...", which would confuse us.
+eval `${MAKE-make} -f conftestmake 2>/dev/null | grep temp=`
+if test -n "$ac_maketemp"; then
+  eval ac_cv_prog_make_${ac_make}_set=yes
+else
+  eval ac_cv_prog_make_${ac_make}_set=no
+fi
+rm -f conftestmake
+fi
+if eval "test \"`echo '$ac_cv_prog_make_'${ac_make}_set`\" = yes"; then
+  echo "$ac_t""yes" 1>&6
+  SET_MAKE=
+else
+  echo "$ac_t""no" 1>&6
+  SET_MAKE="MAKE=${MAKE-make}"
+fi
+
+
+PACKAGE=avl
+
+VERSION=1.4.0
+
+if test "`cd $srcdir && pwd`" != "`pwd`" && test -f $srcdir/config.status; then
+  { echo "configure: error: source directory already configured; run "make distclean" there first" 1>&2; exit 1; }
+fi
+cat >> confdefs.h <<EOF
+#define PACKAGE "$PACKAGE"
+EOF
+
+cat >> confdefs.h <<EOF
+#define VERSION "$VERSION"
+EOF
+
+
+
+missing_dir=`cd $ac_aux_dir && pwd`
+echo $ac_n "checking for working aclocal""... $ac_c" 1>&6
+echo "configure:712: checking for working aclocal" >&5
+# Run test in a subshell; some versions of sh will print an error if
+# an executable is not found, even if stderr is redirected.
+# Redirect stdin to placate older versions of autoconf.  Sigh.
+if (aclocal --version) < /dev/null > /dev/null 2>&1; then
+   ACLOCAL=aclocal
+   echo "$ac_t""found" 1>&6
+else
+   ACLOCAL="$missing_dir/missing aclocal"
+   echo "$ac_t""missing" 1>&6
+fi
+
+echo $ac_n "checking for working autoconf""... $ac_c" 1>&6
+echo "configure:725: checking for working autoconf" >&5
+# Run test in a subshell; some versions of sh will print an error if
+# an executable is not found, even if stderr is redirected.
+# Redirect stdin to placate older versions of autoconf.  Sigh.
+if (autoconf --version) < /dev/null > /dev/null 2>&1; then
+   AUTOCONF=autoconf
+   echo "$ac_t""found" 1>&6
+else
+   AUTOCONF="$missing_dir/missing autoconf"
+   echo "$ac_t""missing" 1>&6
+fi
+
+echo $ac_n "checking for working automake""... $ac_c" 1>&6
+echo "configure:738: checking for working automake" >&5
+# Run test in a subshell; some versions of sh will print an error if
+# an executable is not found, even if stderr is redirected.
+# Redirect stdin to placate older versions of autoconf.  Sigh.
+if (automake --version) < /dev/null > /dev/null 2>&1; then
+   AUTOMAKE=automake
+   echo "$ac_t""found" 1>&6
+else
+   AUTOMAKE="$missing_dir/missing automake"
+   echo "$ac_t""missing" 1>&6
+fi
+
+echo $ac_n "checking for working autoheader""... $ac_c" 1>&6
+echo "configure:751: checking for working autoheader" >&5
+# Run test in a subshell; some versions of sh will print an error if
+# an executable is not found, even if stderr is redirected.
+# Redirect stdin to placate older versions of autoconf.  Sigh.
+if (autoheader --version) < /dev/null > /dev/null 2>&1; then
+   AUTOHEADER=autoheader
+   echo "$ac_t""found" 1>&6
+else
+   AUTOHEADER="$missing_dir/missing autoheader"
+   echo "$ac_t""missing" 1>&6
+fi
+
+echo $ac_n "checking for working makeinfo""... $ac_c" 1>&6
+echo "configure:764: checking for working makeinfo" >&5
+# Run test in a subshell; some versions of sh will print an error if
+# an executable is not found, even if stderr is redirected.
+# Redirect stdin to placate older versions of autoconf.  Sigh.
+if (makeinfo --version) < /dev/null > /dev/null 2>&1; then
+   MAKEINFO=makeinfo
+   echo "$ac_t""found" 1>&6
+else
+   MAKEINFO="$missing_dir/missing makeinfo"
+   echo "$ac_t""missing" 1>&6
+fi
+
+
+# Extract the first word of "gcc", so it can be a program name with args.
+set dummy gcc; ac_word=$2
+echo $ac_n "checking for $ac_word""... $ac_c" 1>&6
+echo "configure:780: checking for $ac_word" >&5
+if eval "test \"`echo '$''{'ac_cv_prog_CC'+set}'`\" = set"; then
+  echo $ac_n "(cached) $ac_c" 1>&6
+else
+  if test -n "$CC"; then
+  ac_cv_prog_CC="$CC" # Let the user override the test.
+else
+  IFS="${IFS= 	}"; ac_save_ifs="$IFS"; IFS=":"
+  ac_dummy="$PATH"
+  for ac_dir in $ac_dummy; do
+    test -z "$ac_dir" && ac_dir=.
+    if test -f $ac_dir/$ac_word; then
+      ac_cv_prog_CC="gcc"
+      break
+    fi
+  done
+  IFS="$ac_save_ifs"
+fi
+fi
+CC="$ac_cv_prog_CC"
+if test -n "$CC"; then
+  echo "$ac_t""$CC" 1>&6
+else
+  echo "$ac_t""no" 1>&6
+fi
+
+if test -z "$CC"; then
+  # Extract the first word of "cc", so it can be a program name with args.
+set dummy cc; ac_word=$2
+echo $ac_n "checking for $ac_word""... $ac_c" 1>&6
+echo "configure:810: checking for $ac_word" >&5
+if eval "test \"`echo '$''{'ac_cv_prog_CC'+set}'`\" = set"; then
+  echo $ac_n "(cached) $ac_c" 1>&6
+else
+  if test -n "$CC"; then
+  ac_cv_prog_CC="$CC" # Let the user override the test.
+else
+  IFS="${IFS= 	}"; ac_save_ifs="$IFS"; IFS=":"
+  ac_prog_rejected=no
+  ac_dummy="$PATH"
+  for ac_dir in $ac_dummy; do
+    test -z "$ac_dir" && ac_dir=.
+    if test -f $ac_dir/$ac_word; then
+      if test "$ac_dir/$ac_word" = "/usr/ucb/cc"; then
+        ac_prog_rejected=yes
+	continue
+      fi
+      ac_cv_prog_CC="cc"
+      break
+    fi
+  done
+  IFS="$ac_save_ifs"
+if test $ac_prog_rejected = yes; then
+  # We found a bogon in the path, so make sure we never use it.
+  set dummy $ac_cv_prog_CC
+  shift
+  if test $# -gt 0; then
+    # We chose a different compiler from the bogus one.
+    # However, it has the same basename, so the bogon will be chosen
+    # first if we set CC to just the basename; use the full file name.
+    shift
+    set dummy "$ac_dir/$ac_word" "$@"
+    shift
+    ac_cv_prog_CC="$@"
+  fi
+fi
+fi
+fi
+CC="$ac_cv_prog_CC"
+if test -n "$CC"; then
+  echo "$ac_t""$CC" 1>&6
+else
+  echo "$ac_t""no" 1>&6
+fi
+
+  if test -z "$CC"; then
+    case "`uname -s`" in
+    *win32* | *WIN32*)
+      # Extract the first word of "cl", so it can be a program name with args.
+set dummy cl; ac_word=$2
+echo $ac_n "checking for $ac_word""... $ac_c" 1>&6
+echo "configure:861: checking for $ac_word" >&5
+if eval "test \"`echo '$''{'ac_cv_prog_CC'+set}'`\" = set"; then
+  echo $ac_n "(cached) $ac_c" 1>&6
+else
+  if test -n "$CC"; then
+  ac_cv_prog_CC="$CC" # Let the user override the test.
+else
+  IFS="${IFS= 	}"; ac_save_ifs="$IFS"; IFS=":"
+  ac_dummy="$PATH"
+  for ac_dir in $ac_dummy; do
+    test -z "$ac_dir" && ac_dir=.
+    if test -f $ac_dir/$ac_word; then
+      ac_cv_prog_CC="cl"
+      break
+    fi
+  done
+  IFS="$ac_save_ifs"
+fi
+fi
+CC="$ac_cv_prog_CC"
+if test -n "$CC"; then
+  echo "$ac_t""$CC" 1>&6
+else
+  echo "$ac_t""no" 1>&6
+fi
+ ;;
+    esac
+  fi
+  test -z "$CC" && { echo "configure: error: no acceptable cc found in \$PATH" 1>&2; exit 1; }
+fi
+
+echo $ac_n "checking whether the C compiler ($CC $CFLAGS $LDFLAGS) works""... $ac_c" 1>&6
+echo "configure:893: checking whether the C compiler ($CC $CFLAGS $LDFLAGS) works" >&5
+
+ac_ext=c
+# CFLAGS is not in ac_cpp because -g, -O, etc. are not valid cpp options.
+ac_cpp='$CPP $CPPFLAGS'
+ac_compile='${CC-cc} -c $CFLAGS $CPPFLAGS conftest.$ac_ext 1>&5'
+ac_link='${CC-cc} -o conftest${ac_exeext} $CFLAGS $CPPFLAGS $LDFLAGS conftest.$ac_ext $LIBS 1>&5'
+cross_compiling=$ac_cv_prog_cc_cross
+
+cat > conftest.$ac_ext << EOF
+
+#line 904 "configure"
+#include "confdefs.h"
+
+main(){return(0);}
+EOF
+if { (eval echo configure:909: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext}; then
+  ac_cv_prog_cc_works=yes
+  # If we can't run a trivial program, we are probably using a cross compiler.
+  if (./conftest; exit) 2>/dev/null; then
+    ac_cv_prog_cc_cross=no
+  else
+    ac_cv_prog_cc_cross=yes
+  fi
+else
+  echo "configure: failed program was:" >&5
+  cat conftest.$ac_ext >&5
+  ac_cv_prog_cc_works=no
+fi
+rm -fr conftest*
+ac_ext=c
+# CFLAGS is not in ac_cpp because -g, -O, etc. are not valid cpp options.
+ac_cpp='$CPP $CPPFLAGS'
+ac_compile='${CC-cc} -c $CFLAGS $CPPFLAGS conftest.$ac_ext 1>&5'
+ac_link='${CC-cc} -o conftest${ac_exeext} $CFLAGS $CPPFLAGS $LDFLAGS conftest.$ac_ext $LIBS 1>&5'
+cross_compiling=$ac_cv_prog_cc_cross
+
+echo "$ac_t""$ac_cv_prog_cc_works" 1>&6
+if test $ac_cv_prog_cc_works = no; then
+  { echo "configure: error: installation or configuration problem: C compiler cannot create executables." 1>&2; exit 1; }
+fi
+echo $ac_n "checking whether the C compiler ($CC $CFLAGS $LDFLAGS) is a cross-compiler""... $ac_c" 1>&6
+echo "configure:935: checking whether the C compiler ($CC $CFLAGS $LDFLAGS) is a cross-compiler" >&5
+echo "$ac_t""$ac_cv_prog_cc_cross" 1>&6
+cross_compiling=$ac_cv_prog_cc_cross
+
+echo $ac_n "checking whether we are using GNU C""... $ac_c" 1>&6
+echo "configure:940: checking whether we are using GNU C" >&5
+if eval "test \"`echo '$''{'ac_cv_prog_gcc'+set}'`\" = set"; then
+  echo $ac_n "(cached) $ac_c" 1>&6
+else
+  cat > conftest.c <<EOF
+#ifdef __GNUC__
+  yes;
+#endif
+EOF
+if { ac_try='${CC-cc} -E conftest.c'; { (eval echo configure:949: \"$ac_try\") 1>&5; (eval $ac_try) 2>&5; }; } | egrep yes >/dev/null 2>&1; then
+  ac_cv_prog_gcc=yes
+else
+  ac_cv_prog_gcc=no
+fi
+fi
+
+echo "$ac_t""$ac_cv_prog_gcc" 1>&6
+
+if test $ac_cv_prog_gcc = yes; then
+  GCC=yes
+else
+  GCC=
+fi
+
+ac_test_CFLAGS="${CFLAGS+set}"
+ac_save_CFLAGS="$CFLAGS"
+CFLAGS=
+echo $ac_n "checking whether ${CC-cc} accepts -g""... $ac_c" 1>&6
+echo "configure:968: checking whether ${CC-cc} accepts -g" >&5
+if eval "test \"`echo '$''{'ac_cv_prog_cc_g'+set}'`\" = set"; then
+  echo $ac_n "(cached) $ac_c" 1>&6
+else
+  echo 'void f(){}' > conftest.c
+if test -z "`${CC-cc} -g -c conftest.c 2>&1`"; then
+  ac_cv_prog_cc_g=yes
+else
+  ac_cv_prog_cc_g=no
+fi
+rm -f conftest*
+
+fi
+
+echo "$ac_t""$ac_cv_prog_cc_g" 1>&6
+if test "$ac_test_CFLAGS" = set; then
+  CFLAGS="$ac_save_CFLAGS"
+elif test $ac_cv_prog_cc_g = yes; then
+  if test "$GCC" = yes; then
+    CFLAGS="-g -O2"
+  else
+    CFLAGS="-g"
+  fi
+else
+  if test "$GCC" = yes; then
+    CFLAGS="-O2"
+  else
+    CFLAGS=
+  fi
+fi
+
+# Extract the first word of "ranlib", so it can be a program name with args.
+set dummy ranlib; ac_word=$2
+echo $ac_n "checking for $ac_word""... $ac_c" 1>&6
+echo "configure:1002: checking for $ac_word" >&5
+if eval "test \"`echo '$''{'ac_cv_prog_RANLIB'+set}'`\" = set"; then
+  echo $ac_n "(cached) $ac_c" 1>&6
+else
+  if test -n "$RANLIB"; then
+  ac_cv_prog_RANLIB="$RANLIB" # Let the user override the test.
+else
+  IFS="${IFS= 	}"; ac_save_ifs="$IFS"; IFS=":"
+  ac_dummy="$PATH"
+  for ac_dir in $ac_dummy; do
+    test -z "$ac_dir" && ac_dir=.
+    if test -f $ac_dir/$ac_word; then
+      ac_cv_prog_RANLIB="ranlib"
+      break
+    fi
+  done
+  IFS="$ac_save_ifs"
+  test -z "$ac_cv_prog_RANLIB" && ac_cv_prog_RANLIB=":"
+fi
+fi
+RANLIB="$ac_cv_prog_RANLIB"
+if test -n "$RANLIB"; then
+  echo "$ac_t""$RANLIB" 1>&6
+else
+  echo "$ac_t""no" 1>&6
+fi
+
+trap '' 1 2 15
+cat > confcache <<\EOF
+# This file is a shell script that caches the results of configure
+# tests run on this system so they can be shared between configure
+# scripts and configure runs.  It is not useful on other systems.
+# If it contains results you don't want to keep, you may remove or edit it.
+#
+# By default, configure uses ./config.cache as the cache file,
+# creating it if it does not exist already.  You can give configure
+# the --cache-file=FILE option to use a different cache file; that is
+# what configure does when it calls configure scripts in
+# subdirectories, so they share the cache.
+# Giving --cache-file=/dev/null disables caching, for debugging configure.
+# config.status only pays attention to the cache file if you give it the
+# --recheck option to rerun configure.
+#
+EOF
+# The following way of writing the cache mishandles newlines in values,
+# but we know of no workaround that is simple, portable, and efficient.
+# So, don't put newlines in cache variables' values.
+# Ultrix sh set writes to stderr and can't be redirected directly,
+# and sets the high bit in the cache file unless we assign to the vars.
+(set) 2>&1 |
+  case `(ac_space=' '; set | grep ac_space) 2>&1` in
+  *ac_space=\ *)
+    # `set' does not quote correctly, so add quotes (double-quote substitution
+    # turns \\\\ into \\, and sed turns \\ into \).
+    sed -n \
+      -e "s/'/'\\\\''/g" \
+      -e "s/^\\([a-zA-Z0-9_]*_cv_[a-zA-Z0-9_]*\\)=\\(.*\\)/\\1=\${\\1='\\2'}/p"
+    ;;
+  *)
+    # `set' quotes correctly as required by POSIX, so do not add quotes.
+    sed -n -e 's/^\([a-zA-Z0-9_]*_cv_[a-zA-Z0-9_]*\)=\(.*\)/\1=${\1=\2}/p'
+    ;;
+  esac >> confcache
+if cmp -s $cache_file confcache; then
+  :
+else
+  if test -w $cache_file; then
+    echo "updating cache $cache_file"
+    cat confcache > $cache_file
+  else
+    echo "not updating unwritable cache $cache_file"
+  fi
+fi
+rm -f confcache
+
+trap 'rm -fr conftest* confdefs* core core.* *.core $ac_clean_files; exit 1' 1 2 15
+
+test "x$prefix" = xNONE && prefix=$ac_default_prefix
+# Let make expand exec_prefix.
+test "x$exec_prefix" = xNONE && exec_prefix='${prefix}'
+
+# Any assignment to VPATH causes Sun make to only execute
+# the first set of double-colon rules, so remove it if not needed.
+# If there is a colon in the path, we need to keep it.
+if test "x$srcdir" = x.; then
+  ac_vpsub='/^[ 	]*VPATH[ 	]*=[^:]*$/d'
+fi
+
+trap 'rm -f $CONFIG_STATUS conftest*; exit 1' 1 2 15
+
+# Transform confdefs.h into DEFS.
+# Protect against shell expansion while executing Makefile rules.
+# Protect against Makefile macro expansion.
+cat > conftest.defs <<\EOF
+s%#define \([A-Za-z_][A-Za-z0-9_]*\) *\(.*\)%-D\1=\2%g
+s%[ 	`~#$^&*(){}\\|;'"<>?]%\\&%g
+s%\[%\\&%g
+s%\]%\\&%g
+s%\$%$$%g
+EOF
+DEFS=`sed -f conftest.defs confdefs.h | tr '\012' ' '`
+rm -f conftest.defs
+
+
+# Without the "./", some shells look in PATH for config.status.
+: ${CONFIG_STATUS=./config.status}
+
+echo creating $CONFIG_STATUS
+rm -f $CONFIG_STATUS
+cat > $CONFIG_STATUS <<EOF
+#! /bin/sh
+# Generated automatically by configure.
+# Run this file to recreate the current configuration.
+# This directory was configured as follows,
+# on host `(hostname || uname -n) 2>/dev/null | sed 1q`:
+#
+# $0 $ac_configure_args
+#
+# Compiler output produced by configure, useful for debugging
+# configure, is in ./config.log if it exists.
+
+ac_cs_usage="Usage: $CONFIG_STATUS [--recheck] [--version] [--help]"
+for ac_option
+do
+  case "\$ac_option" in
+  -recheck | --recheck | --rechec | --reche | --rech | --rec | --re | --r)
+    echo "running \${CONFIG_SHELL-/bin/sh} $0 $ac_configure_args --no-create --no-recursion"
+    exec \${CONFIG_SHELL-/bin/sh} $0 $ac_configure_args --no-create --no-recursion ;;
+  -version | --version | --versio | --versi | --vers | --ver | --ve | --v)
+    echo "$CONFIG_STATUS generated by autoconf version 2.13"
+    exit 0 ;;
+  -help | --help | --hel | --he | --h)
+    echo "\$ac_cs_usage"; exit 0 ;;
+  *) echo "\$ac_cs_usage"; exit 1 ;;
+  esac
+done
+
+ac_given_srcdir=$srcdir
+ac_given_INSTALL="$INSTALL"
+
+trap 'rm -fr `echo "Makefile" | sed "s/:[^ ]*//g"` conftest*; exit 1' 1 2 15
+EOF
+cat >> $CONFIG_STATUS <<EOF
+
+# Protect against being on the right side of a sed subst in config.status.
+sed 's/%@/@@/; s/@%/@@/; s/%g\$/@g/; /@g\$/s/[\\\\&%]/\\\\&/g;
+ s/@@/%@/; s/@@/@%/; s/@g\$/%g/' > conftest.subs <<\\CEOF
+$ac_vpsub
+$extrasub
+s%@SHELL@%$SHELL%g
+s%@CFLAGS@%$CFLAGS%g
+s%@CPPFLAGS@%$CPPFLAGS%g
+s%@CXXFLAGS@%$CXXFLAGS%g
+s%@FFLAGS@%$FFLAGS%g
+s%@DEFS@%$DEFS%g
+s%@LDFLAGS@%$LDFLAGS%g
+s%@LIBS@%$LIBS%g
+s%@exec_prefix@%$exec_prefix%g
+s%@prefix@%$prefix%g
+s%@program_transform_name@%$program_transform_name%g
+s%@bindir@%$bindir%g
+s%@sbindir@%$sbindir%g
+s%@libexecdir@%$libexecdir%g
+s%@datadir@%$datadir%g
+s%@sysconfdir@%$sysconfdir%g
+s%@sharedstatedir@%$sharedstatedir%g
+s%@localstatedir@%$localstatedir%g
+s%@libdir@%$libdir%g
+s%@includedir@%$includedir%g
+s%@oldincludedir@%$oldincludedir%g
+s%@infodir@%$infodir%g
+s%@mandir@%$mandir%g
+s%@INSTALL_PROGRAM@%$INSTALL_PROGRAM%g
+s%@INSTALL_SCRIPT@%$INSTALL_SCRIPT%g
+s%@INSTALL_DATA@%$INSTALL_DATA%g
+s%@PACKAGE@%$PACKAGE%g
+s%@VERSION@%$VERSION%g
+s%@ACLOCAL@%$ACLOCAL%g
+s%@AUTOCONF@%$AUTOCONF%g
+s%@AUTOMAKE@%$AUTOMAKE%g
+s%@AUTOHEADER@%$AUTOHEADER%g
+s%@MAKEINFO@%$MAKEINFO%g
+s%@SET_MAKE@%$SET_MAKE%g
+s%@CC@%$CC%g
+s%@RANLIB@%$RANLIB%g
+
+CEOF
+EOF
+
+cat >> $CONFIG_STATUS <<\EOF
+
+# Split the substitutions into bite-sized pieces for seds with
+# small command number limits, like on Digital OSF/1 and HP-UX.
+ac_max_sed_cmds=90 # Maximum number of lines to put in a sed script.
+ac_file=1 # Number of current file.
+ac_beg=1 # First line for current file.
+ac_end=$ac_max_sed_cmds # Line after last line for current file.
+ac_more_lines=:
+ac_sed_cmds=""
+while $ac_more_lines; do
+  if test $ac_beg -gt 1; then
+    sed "1,${ac_beg}d; ${ac_end}q" conftest.subs > conftest.s$ac_file
+  else
+    sed "${ac_end}q" conftest.subs > conftest.s$ac_file
+  fi
+  if test ! -s conftest.s$ac_file; then
+    ac_more_lines=false
+    rm -f conftest.s$ac_file
+  else
+    if test -z "$ac_sed_cmds"; then
+      ac_sed_cmds="sed -f conftest.s$ac_file"
+    else
+      ac_sed_cmds="$ac_sed_cmds | sed -f conftest.s$ac_file"
+    fi
+    ac_file=`expr $ac_file + 1`
+    ac_beg=$ac_end
+    ac_end=`expr $ac_end + $ac_max_sed_cmds`
+  fi
+done
+if test -z "$ac_sed_cmds"; then
+  ac_sed_cmds=cat
+fi
+EOF
+
+cat >> $CONFIG_STATUS <<EOF
+
+CONFIG_FILES=\${CONFIG_FILES-"Makefile"}
+EOF
+cat >> $CONFIG_STATUS <<\EOF
+for ac_file in .. $CONFIG_FILES; do if test "x$ac_file" != x..; then
+  # Support "outfile[:infile[:infile...]]", defaulting infile="outfile.in".
+  case "$ac_file" in
+  *:*) ac_file_in=`echo "$ac_file"|sed 's%[^:]*:%%'`
+       ac_file=`echo "$ac_file"|sed 's%:.*%%'` ;;
+  *) ac_file_in="${ac_file}.in" ;;
+  esac
+
+  # Adjust a relative srcdir, top_srcdir, and INSTALL for subdirectories.
+
+  # Remove last slash and all that follows it.  Not all systems have dirname.
+  ac_dir=`echo $ac_file|sed 's%/[^/][^/]*$%%'`
+  if test "$ac_dir" != "$ac_file" && test "$ac_dir" != .; then
+    # The file is in a subdirectory.
+    test ! -d "$ac_dir" && mkdir "$ac_dir"
+    ac_dir_suffix="/`echo $ac_dir|sed 's%^\./%%'`"
+    # A "../" for each directory in $ac_dir_suffix.
+    ac_dots=`echo $ac_dir_suffix|sed 's%/[^/]*%../%g'`
+  else
+    ac_dir_suffix= ac_dots=
+  fi
+
+  case "$ac_given_srcdir" in
+  .)  srcdir=.
+      if test -z "$ac_dots"; then top_srcdir=.
+      else top_srcdir=`echo $ac_dots|sed 's%/$%%'`; fi ;;
+  /*) srcdir="$ac_given_srcdir$ac_dir_suffix"; top_srcdir="$ac_given_srcdir" ;;
+  *) # Relative path.
+    srcdir="$ac_dots$ac_given_srcdir$ac_dir_suffix"
+    top_srcdir="$ac_dots$ac_given_srcdir" ;;
+  esac
+
+  case "$ac_given_INSTALL" in
+  [/$]*) INSTALL="$ac_given_INSTALL" ;;
+  *) INSTALL="$ac_dots$ac_given_INSTALL" ;;
+  esac
+
+  echo creating "$ac_file"
+  rm -f "$ac_file"
+  configure_input="Generated automatically from `echo $ac_file_in|sed 's%.*/%%'` by configure."
+  case "$ac_file" in
+  *Makefile*) ac_comsub="1i\\
+# $configure_input" ;;
+  *) ac_comsub= ;;
+  esac
+
+  ac_file_inputs=`echo $ac_file_in|sed -e "s%^%$ac_given_srcdir/%" -e "s%:% $ac_given_srcdir/%g"`
+  sed -e "$ac_comsub
+s%@configure_input@%$configure_input%g
+s%@srcdir@%$srcdir%g
+s%@top_srcdir@%$top_srcdir%g
+s%@INSTALL@%$INSTALL%g
+" $ac_file_inputs | (eval "$ac_sed_cmds") > $ac_file
+fi; done
+rm -f conftest.s*
+
+EOF
+cat >> $CONFIG_STATUS <<EOF
+
+EOF
+cat >> $CONFIG_STATUS <<\EOF
+
+exit 0
+EOF
+chmod +x $CONFIG_STATUS
+rm -fr confdefs* $ac_clean_files
+test "$no_create" = yes || ${CONFIG_SHELL-/bin/sh} $CONFIG_STATUS || exit 1
+
diff --git a/avl-1.4.0/thread-test.c b/avl-1.4.0/thread-test.c
new file mode 100644
index 0000000..20eead4
--- /dev/null
+++ b/avl-1.4.0/thread-test.c
@@ -0,0 +1,142 @@
+/* libavl - manipulates AVL trees.
+   Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License as
+   published by the Free Software Foundation; either version 2 of the
+   License, or (at your option) any later version.
+
+   This program 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 General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+   02111-1307, USA.
+
+   The author may be contacted at <pfaffben@pilot.msu.edu> on the
+   Internet, or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA
+   through more mundane means. */
+
+/* This is file thread-test.c in libavl. */
+
+#if HAVE_CONFIG_H
+#include <config.h>
+#endif
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+#include "avl.h"
+#include "avlt.h"
+#include "avltr.h"
+
+#if __GNUC__ >= 2
+#define unused __attribute__ ((unused))
+#else
+#define unused
+#endif
+
+/* Compare two integers A and B and return a strcmp()-type result. */
+int
+compare_ints (const void *a, const void *b, void unused *param)
+{
+  return ((int) a) - ((int) b);
+}
+
+/* Arrange the N elements of ARRAY in random order. */
+void
+shuffle (int *array, int n)
+{
+  int i;
+  
+  for (i = 0; i < n; i++)
+    {
+      int j = i + rand () % (n - i);
+      int t = array[j];
+      array[j] = array[i];
+      array[i] = t;
+    }
+}
+
+
+/* Simple stress test procedure for the AVL tree threading/unthreading
+   routines. */
+#define TREE_SIZE 1024
+#define N_ITERATIONS 16
+int
+main (int argc, char **argv)
+{
+  int array[TREE_SIZE];
+  int seed;
+  int iteration;
+  
+  if (argc == 2)
+    seed = atoi (argv[1]);
+  else
+    seed = time (0) * 257 % 32768;
+
+  fputs ("Testing threading and unthreading...\n", stdout);
+  for (iteration = 1; iteration <= N_ITERATIONS; iteration++)
+    {
+      avl_tree *tree;
+      avl_traverser trav = AVL_TRAVERSER_INIT;
+      void **nodep = NULL;
+      void *node;
+      int i;
+      
+      printf ("Iteration %4d/%4d: seed=%5d", iteration, N_ITERATIONS, seed);
+      fflush (stdout);
+      
+      srand (seed++);
+      
+      for (i = 0; i < TREE_SIZE; i++)
+	array[i] = i + 1;
+      shuffle (array, TREE_SIZE);
+      
+      tree = avl_create (compare_ints, NULL);
+      for (i = 0; i < TREE_SIZE; i++)
+	avl_force_insert (tree, (void *) (array[i]));
+
+      shuffle (array, TREE_SIZE);
+      for (i = 0; i < TREE_SIZE; i++)
+	{
+	  avlt_tree *t;
+	  avltr_tree *tr;
+
+	  avl_delete (tree, (void *) (array[i]));
+      
+	  while ((node = avl_traverse (tree, &trav)) != NULL);
+      
+	  t = avlt_thread (tree);
+	  while ((nodep = avlt_next (t, nodep)) != NULL);
+	  while ((nodep = avlt_prev (t, nodep)) != NULL);
+	  avlt_unthread (t);
+
+	  tr = avltr_thread (tree);
+	  while ((nodep = avltr_next (tr, nodep)) != NULL);
+	  avltr_unthread (tr);
+	  
+	  while ((node = avl_traverse (tree, &trav)) != NULL);
+
+	  if (i % 128 == 0)
+	    {
+	      putchar ('.');
+	      fflush (stdout);
+	    }
+	}
+      fputs (" good.\n", stdout);
+      
+      avl_destroy (tree, NULL);
+    }
+  
+  return 0;
+}
+
+/*
+  Local variables:
+  compile-command: "gcc -W -Wall -I. -o ./thread-test thread-test.c avl.c avlt.c avltr.c"
+  End:
+*/