AVLtree is a small, malloc-based, in-memory index package generally

like B-trees and hash tables. The interface resembles that of the BPLUS
(B-tree) index package.

Index creation options are:

  - fixed-length binary keys OR variable-length string keys
  - unique OR duplicate keys
  - with duplicate keys:
      standard (void *) pointers for each key OR
      instance-counting (saves time and memory)

Key insert/search time is O(log N).

Package submitted in PR 9252 by wrstuden@netbsd.org, assembled by
Bill Ross.

7 files changed, 77 insertions, 0 deletions

diff --git a/devel/avltree/Makefile b/devel/avltree/Makefile
new file mode 100644
index 00000000000..b9be5e05823
--- /dev/null
+++ b/devel/avltree/Makefile
@@ -0,0 +1,12 @@
+# $NetBSD: Makefile,v 1.1.1.1 2000/01/20 01:40:10 hubertf Exp $
+
+DISTNAME=	avltree-1.1
+CATEGORIES=	devel
+MASTER_SITES=	ftp://odin.compchem.ucsf.edu/pub/amber/
+
+MAINTAINER=	wrstuden@netbsd.org
+
+MANCOMPRESSED=	yes
+USE_LIBTOOL=	yes
+
+.include "../../mk/bsd.pkg.mk"
diff --git a/devel/avltree/files/md5 b/devel/avltree/files/md5
new file mode 100644
index 00000000000..26be64f05b5
--- /dev/null
+++ b/devel/avltree/files/md5
@@ -0,0 +1,3 @@
+$NetBSD: md5,v 1.1.1.1 2000/01/20 01:40:10 hubertf Exp $
+
+MD5 (avltree-1.1.tar.gz) = 45a5dafb8de20059b450ce3137860c53
diff --git a/devel/avltree/files/patch-sum b/devel/avltree/files/patch-sum
new file mode 100644
index 00000000000..c8fee6ae5d1
--- /dev/null
+++ b/devel/avltree/files/patch-sum
@@ -0,0 +1,3 @@
+$NetBSD: patch-sum,v 1.1.1.1 2000/01/20 01:40:11 hubertf Exp $
+
+MD5 (patch-aa) = 21694b40597410d7ccffa44572b2a875
diff --git a/devel/avltree/patches/patch-aa b/devel/avltree/patches/patch-aa
new file mode 100644
index 00000000000..ae028762dd5
--- /dev/null
+++ b/devel/avltree/patches/patch-aa
@@ -0,0 +1,31 @@
+$NetBSD: patch-aa,v 1.1.1.1 2000/01/20 01:40:11 hubertf Exp $
+
+--- Makefile.orig	Wed Jan 19 15:47:48 2000
++++ Makefile	Wed Jan 19 16:03:35 2000
+@@ -1,21 +1,21 @@
+ # makefile for:		avltree
+ # version:		1.1
+ # Date created:		13 January 2000
+ # Whom:			Bill Ross <bross@nas.nasa.gov> <ross@cgl.ucsf.edu>
+ #
+-CC=	cc
+ 
+ all:		libavltree.a
+ 
+ libavltree.a:	avltree.o
+-		$(AR) r  libavltree.a avltree.o
+-		strip libavltree.a
++		${LIBTOOL} --mode=link cc -o ${.TARGET:.a=.la} \
++			avltree.lo -rpath ${PREFIX}/lib \
++			-version-info 1:0
+ 
+ avltree.o: 	avltree.c avltree.h
+-		$(CC) -c avltree.c
++		${LIBTOOL} --mode=compile ${CC} -c avltree.c
+ 
+ install:	libavltree.a
+-		install -c libavltree.a $(PREFIX)/lib
++		${LIBTOOL} --mode=install install -c libavltree.la ${PREFIX}/lib
+ 		install -c avltree.h $(PREFIX)/include
+ 		gzip -c avltree.3 > $(PREFIX)/man/man3/avltree.3.gz
+ 
diff --git a/devel/avltree/pkg/COMMENT b/devel/avltree/pkg/COMMENT
new file mode 100644
index 00000000000..c0fa9ab6f24
--- /dev/null
+++ b/devel/avltree/pkg/COMMENT
@@ -0,0 +1 @@
+In-memory index w/ binary and string keys and key counts
diff --git a/devel/avltree/pkg/DESCR b/devel/avltree/pkg/DESCR
new file mode 100644
index 00000000000..e5677dfc1d3
--- /dev/null
+++ b/devel/avltree/pkg/DESCR
@@ -0,0 +1,22 @@
+AVLtree is a small, malloc-based, in-memory index package generally 
+like B-trees and hash tables. The interface resembles that of the BPLUS
+(B-tree) index package.
+
+Index creation options are:
+
+  - fixed-length binary keys OR variable-length string keys
+  - unique OR duplicate keys
+  - with duplicate keys: 
+      standard (void *) pointers for each key OR 
+      instance-counting (saves time and memory)
+
+Key insert/search time is O(log N).  References:
+
+Adelson-Velskii, G. M., and E. M. Landis. 
+  "An Algorithm for the Organization of Information." 
+  Soviet Math. Doclady 3, 1962, pp. 1259-1263.
+Knuth, D. E. 
+  The Art of Computer Programming, Volume 3: Sorting and Searching 
+  (2nd printing).  Addison-Wesley, 1975, pp. 451-468.
+
+AVLtree was written by Gregory Tseytin, tseyting@acm.org.
diff --git a/devel/avltree/pkg/PLIST b/devel/avltree/pkg/PLIST
new file mode 100644
index 00000000000..b409e491783
--- /dev/null
+++ b/devel/avltree/pkg/PLIST
@@ -0,0 +1,5 @@
+@comment $NetBSD: PLIST,v 1.1.1.1 2000/01/20 01:40:11 hubertf Exp $
+lib/libavltree.a
+lib/libavltree.so.1.0
+include/avltree.h
+man/man3/avltree.3.gz