bst.c

00001 /**
00002  *  @file
00003  *  Contains the implementation of a generic binary search tree.  The
00004  *  tree is implemented as a red-black tree, as inspired by Julienne
00005  *  Walker (http://eternallyconfuzzled.com/tuts/redblack.html).
00006  *
00007  *  @author Jeremy A. Mowery jmowery@tresys.com
00008  *  @author Jason Tang jtang@tresys.com
00009  *
00010  *  Copyright (C) 2006-2007 Tresys Technology, LLC
00011  *
00012  *  This library is free software; you can redistribute it and/or
00013  *  modify it under the terms of the GNU Lesser General Public
00014  *  License as published by the Free Software Foundation; either
00015  *  version 2.1 of the License, or (at your option) any later version.
00016  *
00017  *  This library is distributed in the hope that it will be useful,
00018  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00019  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00020  *  Lesser General Public License for more details.
00021  *
00022  *  You should have received a copy of the GNU Lesser General Public
00023  *  License along with this library; if not, write to the Free Software
00024  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00025  */
00026 
00027 #include <apol/bst.h>
00028 #include <apol/vector.h>
00029 #include <assert.h>
00030 #include <errno.h>
00031 #include <stdlib.h>
00032 #include <string.h>
00033 
00034 #include "vector-internal.h"
00035 
00036 typedef struct bst_node
00037 {
00038         void *elem;
00039         int is_red;
00040         struct bst_node *child[2];
00041 } bst_node_t;
00042 
00043 /**
00044  *  Generic binary search tree structure.  Stores elements as void*.
00045  */
00046 struct apol_bst
00047 {
00048         /** Comparison function for nodes. */
00049         apol_bst_comp_func *cmp;
00050         /** Destroy function for the nodes, or NULL to not free each node. */
00051         apol_bst_free_func *fr;
00052         /** The number of elements currently stored in the bst. */
00053         size_t size;
00054         /** Pointer to top of the tree. */
00055         bst_node_t *head;
00056 };
00057 
00058 apol_bst_t *apol_bst_create(apol_bst_comp_func * cmp, apol_bst_free_func * fr)
00059 {
00060         apol_bst_t *b = NULL;
00061         if ((b = calloc(1, sizeof(*b))) == NULL) {
00062                 return NULL;
00063         }
00064         b->cmp = cmp;
00065         b->fr = fr;
00066         return b;
00067 }
00068 
00069 /**
00070  * Free the data stored within a bst node, recurse through the node's
00071  * children, and then the node itself.
00072  *
00073  * @param node Node to free.  If NULL then do stop recursing.
00074  * @param fr Callback to free a node's data.  If NULL then do not free
00075  * the data.
00076  */
00077 static void bst_node_free(bst_node_t * node, apol_bst_free_func * fr)
00078 {
00079         if (node != NULL) {
00080                 if (fr != NULL) {
00081                         fr(node->elem);
00082                 }
00083                 bst_node_free(node->child[0], fr);
00084                 bst_node_free(node->child[1], fr);
00085                 free(node);
00086         }
00087 }
00088 
00089 void apol_bst_destroy(apol_bst_t ** b)
00090 {
00091         if (!b || !(*b))
00092                 return;
00093         bst_node_free((*b)->head, (*b)->fr);
00094         (*b)->head = NULL;
00095         free(*b);
00096         *b = NULL;
00097 }
00098 
00099 /**
00100  * Given a BST node, traverse the node infix, appending the node's
00101  * element to vector v.
00102  *
00103  * @param node BST node to recurse.
00104  * @param v Vector to which append.
00105  *
00106  * @return 0 on success, < 0 on error.
00107  */
00108 static int bst_node_to_vector(bst_node_t * node, apol_vector_t * v)
00109 {
00110         int retval;
00111         if (node == NULL) {
00112                 return 0;
00113         }
00114         if ((retval = bst_node_to_vector(node->child[0], v)) < 0) {
00115                 return retval;
00116         }
00117         if ((retval = apol_vector_append(v, node->elem)) < 0) {
00118                 return retval;
00119         }
00120         return bst_node_to_vector(node->child[1], v);
00121 }
00122 
00123 apol_vector_t *apol_bst_get_vector(apol_bst_t * b, int change_owner)
00124 {
00125         apol_vector_t *v = NULL;
00126         if (!b) {
00127                 errno = EINVAL;
00128                 return NULL;
00129         }
00130         if ((v = apol_vector_create_with_capacity(b->size, NULL)) == NULL) {
00131                 return NULL;
00132         }
00133         if (bst_node_to_vector(b->head, v) < 0) {
00134                 int error = errno;
00135                 apol_vector_destroy(&v);
00136                 errno = error;
00137                 return NULL;
00138         }
00139         if (change_owner) {
00140                 vector_set_free_func(v, b->fr);
00141                 b->fr = NULL;
00142         }
00143         return v;
00144 }
00145 
00146 size_t apol_bst_get_size(const apol_bst_t * b)
00147 {
00148         if (!b) {
00149                 errno = EINVAL;
00150                 return 0;
00151         } else {
00152                 return b->size;
00153         }
00154 }
00155 
00156 int apol_bst_get_element(const apol_bst_t * b, const void *elem, void *data, void **result)
00157 {
00158         bst_node_t *node;
00159         int compval;
00160         if (!b || !result) {
00161                 errno = EINVAL;
00162                 return -1;
00163         }
00164         node = b->head;
00165         while (node != NULL) {
00166                 if (b->cmp != NULL) {
00167                         compval = b->cmp(node->elem, elem, data);
00168                 } else {
00169                         char *p1 = (char *)node->elem;
00170                         char *p2 = (char *)elem;
00171                         if (p1 < p2) {
00172                                 compval = -1;
00173                         } else if (p1 > p2) {
00174                                 compval = 1;
00175                         } else {
00176                                 compval = 0;
00177                         }
00178                 }
00179                 if (compval == 0) {
00180                         *result = node->elem;
00181                         return 0;
00182                 } else if (compval > 0) {
00183                         node = node->child[0];
00184                 } else {
00185                         node = node->child[1];
00186                 }
00187         }
00188         return -1;
00189 }
00190 
00191 /**
00192  * Allocate and return a new BST node, with data set to elem and color
00193  * to red.  Also increment the tree's size.
00194  *
00195  * @param b BST size to increment.
00196  * @param elem Value for the node.
00197  *
00198  * @return Allocated BST node, which the caller must insert, or NULL
00199  * on error.
00200  */
00201 static bst_node_t *bst_node_make(apol_bst_t * b, void *elem)
00202 {
00203         bst_node_t *new_node;
00204         if ((new_node = calloc(1, sizeof(*new_node))) == NULL) {
00205                 return NULL;
00206         }
00207         new_node->elem = elem;
00208         new_node->is_red = 1;
00209         b->size++;
00210         return new_node;
00211 }
00212 
00213 /**
00214  * Determines if a node is red or not.
00215  *
00216  * @param node Node to check.  If NULL then treat the node as black.
00217  *
00218  * @return 0 if the node is black, 1 if red.
00219  */
00220 static int bst_node_is_red(bst_node_t * node)
00221 {
00222         return node != NULL && node->is_red;
00223 }
00224 
00225 static bst_node_t *bst_rotate_single(bst_node_t * root, int dir)
00226 {
00227         bst_node_t *save = root->child[!dir];
00228         root->child[!dir] = save->child[dir];
00229         save->child[dir] = root;
00230         root->is_red = 1;
00231         save->is_red = 0;
00232         return save;
00233 }
00234 
00235 static bst_node_t *bst_rotate_double(bst_node_t * root, int dir)
00236 {
00237         root->child[!dir] = bst_rotate_single(root->child[!dir], !dir);
00238         return bst_rotate_single(root, dir);
00239 }
00240 
00241 static bst_node_t *bst_insert_recursive(apol_bst_t * b, bst_node_t * root, void **elem, void *data, apol_bst_free_func * fr,
00242                                         int *not_uniq)
00243 {
00244         int compval, dir;
00245         if (root == NULL) {
00246                 if ((root = bst_node_make(b, *elem)) == NULL) {
00247                         *not_uniq = -1;
00248                         return NULL;
00249                 }
00250                 *not_uniq = 0;
00251         } else {
00252                 if (b->cmp != NULL) {
00253                         compval = b->cmp(root->elem, *elem, data);
00254                 } else {
00255                         char *p1 = (char *)root->elem;
00256                         char *p2 = (char *)(*elem);
00257                         if (p1 < p2) {
00258                                 compval = -1;
00259                         } else if (p1 > p2) {
00260                                 compval = 1;
00261                         } else {
00262                                 compval = 0;
00263                         }
00264                 }
00265                 if (compval == 0) {
00266                         /* already exists */
00267                         if (fr != NULL) {
00268                                 fr(*elem);
00269                         }
00270                         *elem = root->elem;
00271                         *not_uniq = 1;
00272                         return root;
00273                 } else if (compval > 0) {
00274                         dir = 0;
00275                 } else {
00276                         dir = 1;
00277                 }
00278                 root->child[dir] = bst_insert_recursive(b, root->child[dir], elem, data, fr, not_uniq);
00279                 if (*not_uniq != 0) {
00280                         return root;
00281                 }
00282 
00283                 /* rebalance tree */
00284                 if (bst_node_is_red(root->child[dir])) {
00285                         if (bst_node_is_red(root->child[!dir])) {
00286                                 /* recolor myself and children.  note
00287                                  * that this can't be reached if a
00288                                  * child is NULL */
00289                                 root->is_red = 1;
00290                                 root->child[0]->is_red = 0;
00291                                 root->child[1]->is_red = 0;
00292                         } else {
00293                                 if (bst_node_is_red(root->child[dir]->child[dir])) {
00294                                         root = bst_rotate_single(root, !dir);
00295                                 } else if (bst_node_is_red(root->child[dir]->child[!dir])) {
00296                                         root = bst_rotate_double(root, !dir);
00297                                 }
00298                         }
00299                 }
00300         }
00301         return root;
00302 }
00303 
00304 int apol_bst_insert(apol_bst_t * b, void *elem, void *data)
00305 {
00306         int retval = -1;
00307         if (!b || !elem) {
00308                 errno = EINVAL;
00309                 return -1;
00310         }
00311         b->head = bst_insert_recursive(b, b->head, &elem, data, NULL, &retval);
00312         if (retval >= 0) {
00313                 b->head->is_red = 0;
00314         }
00315         return retval;
00316 }
00317 
00318 int apol_bst_insert_and_get(apol_bst_t * b, void **elem, void *data)
00319 {
00320         int retval = -1;
00321         if (!b || !elem) {
00322                 errno = EINVAL;
00323                 return -1;
00324         }
00325         b->head = bst_insert_recursive(b, b->head, elem, data, b->fr, &retval);
00326         if (retval >= 0) {
00327                 b->head->is_red = 0;
00328         }
00329         return retval;
00330 }
00331 
00332 static int bst_inorder_map(const bst_node_t * node, int (*fn) (void *, void *), void *data)
00333 {
00334         int retval;
00335         if (node == NULL) {
00336                 return 0;
00337         }
00338         if ((retval = bst_inorder_map(node->child[0], fn, data)) < 0) {
00339                 return retval;
00340         }
00341         if ((retval = fn(node->elem, data)) < 0) {
00342                 return retval;
00343         }
00344         return bst_inorder_map(node->child[1], fn, data);
00345 }
00346 
00347 int apol_bst_inorder_map(const apol_bst_t * b, int (*fn) (void *, void *), void *data)
00348 {
00349         if (b == NULL || fn == NULL)
00350                 return -1;
00351         return bst_inorder_map(b->head, fn, data);
00352 }