1 files changed, 178 insertions, 0 deletions
diff --git a/libapol/include/apol/bst.h b/libapol/include/apol/bst.h
new file mode 100644
index 0000000..ca21a76
--- /dev/null
+++ b/libapol/include/apol/bst.h
@@ -0,0 +1,178 @@
+/**
+ *  @file
+ *  Contains the API for a binary search tree.  The tree guarantees
+ *  uniqueness of all entries within.  Note that BST functions are not
+ *  thread-safe.  Use this if you need uniqueness in items; use
+ *  vectors otherwise because they are faster.
+ *
+ *  @author Jeremy A. Mowery jmowery@tresys.com
+ *  @author Jason Tang jtang@tresys.com
+ *
+ *  Copyright (C) 2006-2007 Tresys Technology, LLC
+ *
+ *  This library is free software; you can redistribute it and/or
+ *  modify it under the terms of the GNU Lesser General Public
+ *  License as published by the Free Software Foundation; either
+ *  version 2.1 of the License, or (at your option) any later version.
+ *
+ *  This library 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
+ *  Lesser General Public License for more details.
+ *
+ *  You should have received a copy of the GNU Lesser General Public
+ *  License along with this library; if not, write to the Free Software
+ *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+ */
+
+#ifndef APOL_BST_H
+#define APOL_BST_H
+
+#ifdef	__cplusplus
+extern "C"
+{
+#endif
+
+#include <stdlib.h>
+
+	typedef struct apol_bst apol_bst_t;
+
+	typedef int (apol_bst_comp_func) (const void *a, const void *b, void *data);
+	typedef void (apol_bst_free_func) (void *elem);
+
+#include "vector.h"
+
+/**
+ *  Allocate and initialize an empty binary search tree.  The tree
+ *  must have a comparison function, used when comparing nodes so as
+ *  to determine how to sort them.
+ *
+ *  @param cmp A comparison call back for the type of element stored
+ *  in the BST.  The expected return value from this function is less
+ *  than, equal to, or greater than 0 if the first argument is less
+ *  than, equal to, or greater than the second respectively.  If this
+ *  is NULL then do pointer address comparison.
+ *  @param fr Function to call when destroying the tree.  Each
+ *  element of the tree will be passed into this function; it should
+ *  free the memory used by that element.  If this parameter is NULL,
+ *  the elements will not be freed.
+ *
+ *  @return A pointer to a newly created BST on success and NULL on
+ *  failure.  If the call fails, errno will be set.  The caller is
+ *  responsible for calling apol_bst_destroy() to free memory used.
+ */
+	extern apol_bst_t *apol_bst_create(apol_bst_comp_func * cmp, apol_bst_free_func * fr);
+
+/**
+ *  Free a BST and any memory used by it.  This will recursively
+ *  invoke the free function that was stored within the tree when it
+ *  was created.
+ *
+ *  @param b Pointer to the BST to free.  The pointer will be set to
+ *  NULL afterwards.  If already NULL then this function does nothing.
+ */
+	extern void apol_bst_destroy(apol_bst_t ** b);
+
+/**
+ *  Allocate and return a vector that has been initialized with the
+ *  contents of a binary search tree.  If change_owner is zero then
+ *  this function will make a <b>shallow copy of the BST's
+ *  contents</b>; the BST will still <em>own</em> the objects.
+ *  Otherwise the victor will gain ownership of the items; the BST can
+ *  then be destroyed safely without affecting the vector.  (The
+ *  resulting vector will be sorted as per the BST's comparison
+ *  function.)
+ *
+ *  @param b Binary search tree from which to copy.
+ *  @param change_owner If zero then do a shallow copy, else change
+ *  item ownership.
+ *
+ *  @return A pointer to a newly created vector on success and NULL on
+ *  failure.  If the call fails, errno will be set.  The caller is
+ *  responsible for calling apol_vector_destroy() to free memory used
+ *  by the vector.
+ */
+	extern apol_vector_t *apol_bst_get_vector(apol_bst_t * b, int change_owner);
+
+/**
+ *  Get the number of elements stored in the BST.
+ *
+ *  @param b The BST from which to get the number of elements.  Must
+ *  be non-NULL.
+ *
+ *  @return The number of elements in the BST; if b is NULL, return
+ *  0 and set errno.
+ */
+	extern size_t apol_bst_get_size(const apol_bst_t * v);
+
+/**
+ *  Find an element within a BST and return it.
+ *
+ *  @param b The BST from which to get the element.
+ *  @param elem The element to find.  (This will be the second
+ *  parameter to the comparison function given in apol_bst_create().)
+ *  @param data Arbitrary data to pass as the comparison function's
+ *  third paramater (the function given in apol_bst_create()).
+ *  @param elem Location to write the found element.  This value is
+ *  undefined if the key did not match any elements.
+ *
+ *  @return 0 if element was found, or < 0 if not found.
+ */
+	extern int apol_bst_get_element(const apol_bst_t * b, const void *elem, void *data, void **result);
+
+/**
+ *  Insert an element to the BST.  If the element already exists then
+ *  do not insert it again.
+ *
+ *  @param b The BST to which to add the element.
+ *  @param elem The element to add.
+ *  @param data Arbitrary data to pass as the comparison function's
+ *  third paramater (the function given in apol_bst_create()).
+ *
+ *  @return 0 if the item was inserted, 1 if the item already exists
+ *  (and thus not inserted).  On failure return < 0, set errno, and b
+ *  will be unchanged.
+ */
+	extern int apol_bst_insert(apol_bst_t * b, void *elem, void *data);
+
+/**
+ *  Insert an element into the BST, and then get the element back out.
+ *  If the element did not already exist, then this function behaves
+ *  the same as apol_bst_insert().  If however the element did exist,
+ *  then the passed in element is freed (as per the BST's free
+ *  function) and then the existing element is returned.
+ *
+ *  @param b The BST to which to add the element.
+ *  @param elem Reference to an element to add.  If the element is
+ *  new, then the pointer remains unchanged.  Otherwise set the
+ *  reference to the element already within the tree.
+ *  @param data Arbitrary data to pass as the comparison function's
+ *  third paramater (the function given in apol_bst_create()).
+ *
+ *  @return 0 if the item was inserted, 1 if the item already exists
+ *  (and thus not inserted).  On failure return < 0, set errno, and b
+ *  will be unchanged.
+ */
+	extern int apol_bst_insert_and_get(apol_bst_t * b, void **elem, void *data);
+
+/**
+ * Map a function across all the elements of the BST.  Mapping occurs in
+ * the sorted order as defined by the original comparison function.
+ *
+ * @param node BST upon which to map against.
+ * @param fn Function pointer that takes 2 arguments, first is a
+ * pointer to the data in a node of the BST, second is an arbitrary
+ * data element.  The function may change the BST node, but it must
+ * not affect the node's sorting order within the tree.  This function
+ * should return >= 0 on success; a return of < 0 signals error and
+ * ends the mapping over the tree.
+
+ * @return Result of the last call to fn() (i.e., >= 0 on success < 0 on
+ * failure).  If the tree is empty then return 0.
+ */
+	extern int apol_bst_inorder_map(const apol_bst_t * b, int (*fn) (void *, void *), void *data);
+#ifdef	__cplusplus
+}
+#endif
+
+#endif				       /* APOL_BST_H */