Useful add-on libraries

4 files changed, 460 insertions, 0 deletions

diff --git a/avl-1.4.0/THANKS b/avl-1.4.0/THANKS
new file mode 100644
index 0000000..cd9319a
--- /dev/null
+++ b/avl-1.4.0/THANKS
@@ -0,0 +1,15 @@
+Thanks to...
+                                       
+* Donald Knuth for _The Art of Computer Programming_.
+
+* Thomas Cormen, Charles Leiserson, and Ron Rivest for _Introduction
+  to Algorithms_.
+
+* David MacKenzie for writing Autoconf, the automatic configuration
+  tool.
+
+* David MacKenzie and Tom Tromey for writing Automake, the tool for
+  generating `Makefile's.
+
+* All those who have contributed bug reports and enhancements.  You
+  can find them listed individually in the NEWS and the ChangeLog.
diff --git a/avl-1.4.0/avl.h b/avl-1.4.0/avl.h
new file mode 100644
index 0000000..436a461
--- /dev/null
+++ b/avl-1.4.0/avl.h
@@ -0,0 +1,148 @@
+/* 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.h in libavl. */
+
+#if !avl_h
+#define avl_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 an AVL tree. */
+typedef struct avl_node
+  {
+    void *data;			/* Pointer to data. */
+    struct avl_node *link[2];	/* Subtrees. */
+    signed char bal;		/* Balance factor. */
+    char cache;			/* Used during insertion. */
+    signed char pad[2];		/* Unused.  Reserved for threaded trees. */
+  }
+avl_node;
+
+/* Used for traversing an AVL tree. */
+typedef struct avl_traverser
+  {
+    int init;			/* Initialized? */
+    int nstack;			/* Top of stack. */
+    const avl_node *p;		/* Used for traversal. */
+    const avl_node *stack[AVL_MAX_HEIGHT];/* Descended trees. */
+  }
+avl_traverser;
+
+/* Initializer for avl_traverser. */
+#define AVL_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 an AVL tree. */
+typedef struct avl_tree
+  {
+#if PSPP
+    struct arena **owner;	/* Arena to store nodes. */
+#endif
+    avl_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. */
+  }
+avl_tree;
+
+#if PSPP
+#define MAYBE_ARENA struct arena **owner,
+#else
+#define MAYBE_ARENA /* nothing */
+#endif
+
+/* General functions. */
+avl_tree *avl_create (MAYBE_ARENA avl_comparison_func, void *param);
+void avl_destroy (avl_tree *, avl_node_func);
+void avl_free (avl_tree *);
+int avl_count (const avl_tree *);
+avl_tree *avl_copy (MAYBE_ARENA const avl_tree *, avl_copy_func);
+
+/* Walk the tree. */
+void avl_walk (const avl_tree *, avl_node_func, void *param);
+void *avl_traverse (const avl_tree *, avl_traverser *);
+#define avl_init_traverser(TRAVERSER) ((TRAVERSER)->init = 0)
+
+/* Search for a given item. */
+void **avl_probe (avl_tree *, void *);
+void *avl_delete (avl_tree *, const void *);
+void *avl_find (const avl_tree *, const void *);
+void *avl_find_close (const avl_tree *, const void *);
+
+#if __GCC__ >= 2
+extern inline void *
+avl_insert (avl_tree *tree, void *item)
+{
+  void **p = avl_probe (tree, item);
+  return (*p == item) ? NULL : *p;
+}
+
+extern inline void *
+avl_replace (avl_tree *tree, void *item)
+{
+  void **p = avl_probe (tree, item);
+  if (*p == item)
+    return NULL;
+  else
+    {
+      void *r = *p;
+      *p = item;
+      return r;
+    }
+}
+#else /* not gcc */
+void *avl_insert (avl_tree *tree, void *item);
+void *avl_replace (avl_tree *tree, void *item);
+#endif /* not gcc */
+
+/* Easy assertions on insertion & deletion. */
+#ifndef NDEBUG
+#define avl_force_insert(A, B)			\
+	do					\
+	  {					\
+            void *r = avl_insert (A, B);	\
+	    assert (r == NULL);			\
+	  }					\
+	while (0)
+void *avl_force_delete (avl_tree *, void *);
+#else
+#define avl_force_insert(A, B)			\
+	avl_insert (A, B)
+#define avl_force_delete(A, B)			\
+	avl_delete (A, B)
+#endif
+
+#endif /* avl_h */
diff --git a/avl-1.4.0/avltr.h b/avl-1.4.0/avltr.h
new file mode 100644
index 0000000..27465ef
--- /dev/null
+++ b/avl-1.4.0/avltr.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 avltr.h in libavl. */
+
+#if !avltr_h
+#define avltr_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 right-threaded AVL tree. */
+typedef struct avltr_node
+  {
+    void *data;			/* Pointer to data. */
+    struct avltr_node *link[2];	/* Subtrees or threads. */
+    signed char bal;		/* Balance factor. */
+    char cache;			/* Used during insertion. */
+    char pad;			/* Reserved for fully threaded trees. */
+    signed char rtag;		/* Right thread tag. */
+  }
+avltr_node;
+
+/* Used for traversing a right-threaded AVL tree. */
+typedef struct avltr_traverser
+  {
+    int init;				/* Initialized? */
+    const avltr_node *p;		/* Last node returned. */
+  }
+avltr_traverser;
+
+/* Initializer for avltr_traverser. */
+#define AVLTR_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 avltr_tree
+  {
+    avltr_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. */
+  }
+avltr_tree;
+
+/* General functions. */
+avltr_tree *avltr_create (avl_comparison_func, void *param);
+void avltr_destroy (avltr_tree *, avl_node_func);
+void avltr_free (avltr_tree *);
+int avltr_count (const avltr_tree *);
+avltr_tree *avltr_copy (const avltr_tree *, avl_copy_func);
+struct avl_tree;
+avltr_tree *avltr_thread (struct avl_tree *);
+struct avl_tree *avltr_unthread (avltr_tree *);
+
+/* Walk the tree. */
+void avltr_walk (const avltr_tree *, avl_node_func, void *param);
+void *avltr_traverse (const avltr_tree *, avltr_traverser *);
+#define avlt_init_traverser(TRAVERSER) ((TRAVERSER)->init = 0)
+void **avltr_next (const avltr_tree *tree, void **item);
+
+/* Search for a given item. */
+void **avltr_probe (avltr_tree *, void *);
+void *avltr_delete (avltr_tree *, const void *);
+void **avltr_find (const avltr_tree *, const void *);
+void **avltr_find_close (const avltr_tree *, const void *);
+
+#if __GCC__ >= 2
+extern inline void *
+avltr_insert (avltr_tree *tree, void *item)
+{
+  void **p = avltr_probe (tree, item);
+  return (*p == item) ? NULL : *p;
+}
+
+extern inline void *
+avltr_replace (avltr_tree *tree, void *item)
+{
+  void **p = avltr_probe (tree, item);
+  if (*p == item)
+    return NULL;
+  else
+    {
+      void *r = *p;
+      *p = item;
+      return r;
+    }
+}
+#else /* not gcc */
+void *avltr_insert (avltr_tree *tree, void *item);
+void *avltr_replace (avltr_tree *tree, void *item);
+#endif /* not gcc */
+
+/* Easy assertions on insertion & deletion. */
+#ifndef NDEBUG
+#define avltr_force_insert(A, B)		\
+	do					\
+	  {					\
+            void *r = avltr_insert (A, B);	\
+	    assert (r == NULL);			\
+	  }					\
+	while (0)
+void *avltr_force_delete (avltr_tree *, void *);
+#else
+#define avltr_force_insert(A, B)		\
+	avltr_insert (A, B)
+#define avltr_force_delete(A, B)		\
+	avltr_delete (A, B)
+#endif
+
+#endif /* avltr_h */
diff --git a/avl-1.4.0/rb.h b/avl-1.4.0/rb.h
new file mode 100644
index 0000000..26a9f49
--- /dev/null
+++ b/avl-1.4.0/rb.h
@@ -0,0 +1,155 @@
+/* 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 rb.h in libavl. */
+
+#if !rb_h
+#define rb_h 1
+
+/* The default maximum height of 32 allows for red-black trees having
+   between 65,535 and 4,294,967,295 nodes, depending on order of
+   insertion.  You may change this compile-time constant as you
+   wish. */
+#ifndef RB_MAX_HEIGHT
+#define RB_MAX_HEIGHT	32
+#endif
+
+/* Node colors. */
+enum
+  {
+    RB_BLACK,
+    RB_RED,
+  };
+
+/* Structure for a node in a red-black tree. */
+typedef struct rb_node
+  {
+    void *data;			/* Pointer to data. */
+    struct rb_node *link[2];	/* Subtrees. */
+    signed char color;		/* Color. */
+    char cache;			/* Used during insertion. */
+    signed char pad[2];		/* Unused.  Reserved for threaded trees. */
+  }
+rb_node;
+
+/* Used for traversing a red-black tree. */
+typedef struct rb_traverser
+  {
+    int init;			/* Initialized? */
+    int nstack;			/* Top of stack. */
+    const rb_node *p;		/* Used for traversal. */
+    const rb_node *stack[RB_MAX_HEIGHT];/* Descended trees. */
+  }
+rb_traverser;
+
+/* Initializer for rb_traverser. */
+#define RB_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 red-black tree. */
+typedef struct rb_tree
+  {
+#if PSPP
+    struct arena **owner;	/* Arena to store nodes. */
+#endif
+    rb_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. */
+  }
+rb_tree;
+
+#if PSPP
+#define MAYBE_ARENA struct arena **owner,
+#else
+#define MAYBE_ARENA /* nothing */
+#endif
+
+/* General functions. */
+rb_tree *rb_create (MAYBE_ARENA avl_comparison_func, void *param);
+void rb_destroy (rb_tree *, avl_node_func);
+void rb_free (rb_tree *);
+int rb_count (const rb_tree *);
+rb_tree *rb_copy (MAYBE_ARENA const rb_tree *, avl_copy_func);
+
+/* Walk the tree. */
+void rb_walk (const rb_tree *, avl_node_func, void *param);
+void *rb_traverse (const rb_tree *, rb_traverser *);
+#define rb_init_traverser(TRAVERSER) ((TRAVERSER)->init = 0)
+
+/* Search for a given item. */
+void **rb_probe (rb_tree *, void *);
+void *rb_delete (rb_tree *, const void *);
+void *rb_find (const rb_tree *, const void *);
+void *rb_find_close (const rb_tree *, const void *);
+
+#if __GCC__ >= 2
+extern inline void *
+rb_insert (rb_tree *tree, void *item)
+{
+  void **p = rb_probe (tree, item);
+  return (*p == item) ? NULL : *p;
+}
+
+extern inline void *
+rb_replace (rb_tree *tree, void *item)
+{
+  void **p = rb_probe (tree, item);
+  if (*p == item)
+    return NULL;
+  else
+    {
+      void *r = *p;
+      *p = item;
+      return r;
+    }
+}
+#else /* not gcc */
+void *rb_insert (rb_tree *tree, void *item);
+void *rb_replace (rb_tree *tree, void *item);
+#endif /* not gcc */
+
+/* Easy assertions on insertion & deletion. */
+#ifndef NDEBUG
+#define rb_force_insert(A, B)			\
+	do					\
+	  {					\
+            void *r = rb_insert (A, B);		\
+	    assert (r == NULL);			\
+	  }					\
+	while (0)
+void *rb_force_delete (rb_tree *, void *);
+#else
+#define rb_force_insert(A, B)			\
+	rb_insert (A, B)
+#define rb_force_delete(A, B)			\
+	rb_delete (A, B)
+#endif
+
+#endif /* rb_h */