diff options
Diffstat (limited to 'libapol/src/bst.c')
| -rw-r--r-- | libapol/src/bst.c | 352 |
1 files changed, 352 insertions, 0 deletions
diff --git a/libapol/src/bst.c b/libapol/src/bst.c new file mode 100644 index 0000000..df0beb6 --- /dev/null +++ b/libapol/src/bst.c @@ -0,0 +1,352 @@ +/** + * @file + * Contains the implementation of a generic binary search tree. The + * tree is implemented as a red-black tree, as inspired by Julienne + * Walker (http://eternallyconfuzzled.com/tuts/redblack.html). + * + * @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 + */ + +#include <apol/bst.h> +#include <apol/vector.h> +#include <assert.h> +#include <errno.h> +#include <stdlib.h> +#include <string.h> + +#include "vector-internal.h" + +typedef struct bst_node +{ + void *elem; + int is_red; + struct bst_node *child[2]; +} bst_node_t; + +/** + * Generic binary search tree structure. Stores elements as void*. + */ +struct apol_bst +{ + /** Comparison function for nodes. */ + apol_bst_comp_func *cmp; + /** Destroy function for the nodes, or NULL to not free each node. */ + apol_bst_free_func *fr; + /** The number of elements currently stored in the bst. */ + size_t size; + /** Pointer to top of the tree. */ + bst_node_t *head; +}; + +apol_bst_t *apol_bst_create(apol_bst_comp_func * cmp, apol_bst_free_func * fr) +{ + apol_bst_t *b = NULL; + if ((b = calloc(1, sizeof(*b))) == NULL) { + return NULL; + } + b->cmp = cmp; + b->fr = fr; + return b; +} + +/** + * Free the data stored within a bst node, recurse through the node's + * children, and then the node itself. + * + * @param node Node to free. If NULL then do stop recursing. + * @param fr Callback to free a node's data. If NULL then do not free + * the data. + */ +static void bst_node_free(bst_node_t * node, apol_bst_free_func * fr) +{ + if (node != NULL) { + if (fr != NULL) { + fr(node->elem); + } + bst_node_free(node->child[0], fr); + bst_node_free(node->child[1], fr); + free(node); + } +} + +void apol_bst_destroy(apol_bst_t ** b) +{ + if (!b || !(*b)) + return; + bst_node_free((*b)->head, (*b)->fr); + (*b)->head = NULL; + free(*b); + *b = NULL; +} + +/** + * Given a BST node, traverse the node infix, appending the node's + * element to vector v. + * + * @param node BST node to recurse. + * @param v Vector to which append. + * + * @return 0 on success, < 0 on error. + */ +static int bst_node_to_vector(bst_node_t * node, apol_vector_t * v) +{ + int retval; + if (node == NULL) { + return 0; + } + if ((retval = bst_node_to_vector(node->child[0], v)) < 0) { + return retval; + } + if ((retval = apol_vector_append(v, node->elem)) < 0) { + return retval; + } + return bst_node_to_vector(node->child[1], v); +} + +apol_vector_t *apol_bst_get_vector(apol_bst_t * b, int change_owner) +{ + apol_vector_t *v = NULL; + if (!b) { + errno = EINVAL; + return NULL; + } + if ((v = apol_vector_create_with_capacity(b->size, NULL)) == NULL) { + return NULL; + } + if (bst_node_to_vector(b->head, v) < 0) { + int error = errno; + apol_vector_destroy(&v); + errno = error; + return NULL; + } + if (change_owner) { + vector_set_free_func(v, b->fr); + b->fr = NULL; + } + return v; +} + +size_t apol_bst_get_size(const apol_bst_t * b) +{ + if (!b) { + errno = EINVAL; + return 0; + } else { + return b->size; + } +} + +int apol_bst_get_element(const apol_bst_t * b, const void *elem, void *data, void **result) +{ + bst_node_t *node; + int compval; + if (!b || !result) { + errno = EINVAL; + return -1; + } + node = b->head; + while (node != NULL) { + if (b->cmp != NULL) { + compval = b->cmp(node->elem, elem, data); + } else { + char *p1 = (char *)node->elem; + char *p2 = (char *)elem; + if (p1 < p2) { + compval = -1; + } else if (p1 > p2) { + compval = 1; + } else { + compval = 0; + } + } + if (compval == 0) { + *result = node->elem; + return 0; + } else if (compval > 0) { + node = node->child[0]; + } else { + node = node->child[1]; + } + } + return -1; +} + +/** + * Allocate and return a new BST node, with data set to elem and color + * to red. Also increment the tree's size. + * + * @param b BST size to increment. + * @param elem Value for the node. + * + * @return Allocated BST node, which the caller must insert, or NULL + * on error. + */ +static bst_node_t *bst_node_make(apol_bst_t * b, void *elem) +{ + bst_node_t *new_node; + if ((new_node = calloc(1, sizeof(*new_node))) == NULL) { + return NULL; + } + new_node->elem = elem; + new_node->is_red = 1; + b->size++; + return new_node; +} + +/** + * Determines if a node is red or not. + * + * @param node Node to check. If NULL then treat the node as black. + * + * @return 0 if the node is black, 1 if red. + */ +static int bst_node_is_red(bst_node_t * node) +{ + return node != NULL && node->is_red; +} + +static bst_node_t *bst_rotate_single(bst_node_t * root, int dir) +{ + bst_node_t *save = root->child[!dir]; + root->child[!dir] = save->child[dir]; + save->child[dir] = root; + root->is_red = 1; + save->is_red = 0; + return save; +} + +static bst_node_t *bst_rotate_double(bst_node_t * root, int dir) +{ + root->child[!dir] = bst_rotate_single(root->child[!dir], !dir); + return bst_rotate_single(root, dir); +} + +static bst_node_t *bst_insert_recursive(apol_bst_t * b, bst_node_t * root, void **elem, void *data, apol_bst_free_func * fr, + int *not_uniq) +{ + int compval, dir; + if (root == NULL) { + if ((root = bst_node_make(b, *elem)) == NULL) { + *not_uniq = -1; + return NULL; + } + *not_uniq = 0; + } else { + if (b->cmp != NULL) { + compval = b->cmp(root->elem, *elem, data); + } else { + char *p1 = (char *)root->elem; + char *p2 = (char *)(*elem); + if (p1 < p2) { + compval = -1; + } else if (p1 > p2) { + compval = 1; + } else { + compval = 0; + } + } + if (compval == 0) { + /* already exists */ + if (fr != NULL) { + fr(*elem); + } + *elem = root->elem; + *not_uniq = 1; + return root; + } else if (compval > 0) { + dir = 0; + } else { + dir = 1; + } + root->child[dir] = bst_insert_recursive(b, root->child[dir], elem, data, fr, not_uniq); + if (*not_uniq != 0) { + return root; + } + + /* rebalance tree */ + if (bst_node_is_red(root->child[dir])) { + if (bst_node_is_red(root->child[!dir])) { + /* recolor myself and children. note + * that this can't be reached if a + * child is NULL */ + root->is_red = 1; + root->child[0]->is_red = 0; + root->child[1]->is_red = 0; + } else { + if (bst_node_is_red(root->child[dir]->child[dir])) { + root = bst_rotate_single(root, !dir); + } else if (bst_node_is_red(root->child[dir]->child[!dir])) { + root = bst_rotate_double(root, !dir); + } + } + } + } + return root; +} + +int apol_bst_insert(apol_bst_t * b, void *elem, void *data) +{ + int retval = -1; + if (!b || !elem) { + errno = EINVAL; + return -1; + } + b->head = bst_insert_recursive(b, b->head, &elem, data, NULL, &retval); + if (retval >= 0) { + b->head->is_red = 0; + } + return retval; +} + +int apol_bst_insert_and_get(apol_bst_t * b, void **elem, void *data) +{ + int retval = -1; + if (!b || !elem) { + errno = EINVAL; + return -1; + } + b->head = bst_insert_recursive(b, b->head, elem, data, b->fr, &retval); + if (retval >= 0) { + b->head->is_red = 0; + } + return retval; +} + +static int bst_inorder_map(const bst_node_t * node, int (*fn) (void *, void *), void *data) +{ + int retval; + if (node == NULL) { + return 0; + } + if ((retval = bst_inorder_map(node->child[0], fn, data)) < 0) { + return retval; + } + if ((retval = fn(node->elem, data)) < 0) { + return retval; + } + return bst_inorder_map(node->child[1], fn, data); +} + +int apol_bst_inorder_map(const apol_bst_t * b, int (*fn) (void *, void *), void *data) +{ + if (b == NULL || fn == NULL) + return -1; + return bst_inorder_map(b->head, fn, data); +} |