bst.c File Reference

Detailed Description

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
Jason Tang jtang@tresys.com

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

Definition in file bst.c.

#include <apol/bst.h>
#include <apol/vector.h>
#include <assert.h>
#include <errno.h>
#include <stdlib.h>
#include <string.h>
#include "vector-internal.h"

Go to the source code of this file.


Classes
struct	bst_node
struct	apol_bst
	Generic binary search tree structure. More...
Typedefs
typedef bst_node	bst_node_t
Functions
apol_bst_t *	apol_bst_create (apol_bst_comp_func cmp, apol_bst_free_func fr)
	Allocate and initialize an empty binary search tree.
void	bst_node_free (bst_node_t node, apol_bst_free_func fr)
	Free the data stored within a bst node, recurse through the node's children, and then the node itself.
void	apol_bst_destroy (apol_bst_t **b)
	Free a BST and any memory used by it.
int	bst_node_to_vector (bst_node_t node, apol_vector_t v)
	Given a BST node, traverse the node infix, appending the node's element to vector v.
apol_vector_t *	apol_bst_get_vector (apol_bst_t *b, int change_owner)
	Allocate and return a vector that has been initialized with the contents of a binary search tree.
size_t	apol_bst_get_size (const apol_bst_t *b)
	Get the number of elements stored in the BST.
int	apol_bst_get_element (const apol_bst_t b, const void elem, void data, void *result)
	Find an element within a BST and return it.
bst_node_t *	bst_node_make (apol_bst_t b, void elem)
	Allocate and return a new BST node, with data set to elem and color to red.
int	bst_node_is_red (bst_node_t *node)
	Determines if a node is red or not.
bst_node_t *	bst_rotate_single (bst_node_t *root, int dir)
bst_node_t *	bst_rotate_double (bst_node_t *root, int dir)
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	apol_bst_insert (apol_bst_t b, void elem, void *data)
	Insert an element to the BST.
int	apol_bst_insert_and_get (apol_bst_t b, void elem, void data)
	Insert an element into the BST, and then get the element back out.
int	bst_inorder_map (const bst_node_t node, int(fn)(void , void ), void *data)
int	apol_bst_inorder_map (const apol_bst_t b, int(fn)(void , void ), void *data)
	Map a function across all the elements of the BST.

Typedef Documentation

typedef struct bst_node bst_node_t

Referenced by apol_bst_get_element(), bst_inorder_map(), bst_insert_recursive(), bst_node_free(), bst_node_is_red(), bst_node_make(), bst_node_to_vector(), bst_rotate_double(), and bst_rotate_single().

Function Documentation

apol_bst_t* apol_bst_create	(	apol_bst_comp_func *	cmp,
		apol_bst_free_func *	fr
	)

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.

Parameters:

	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.
	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.

Returns:: 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.

Definition at line 58 of file bst.c.

References apol_bst_t, apol_bst::cmp, and apol_bst::fr.

Referenced by apol_avrule_list_to_syn_avrules(), apol_domain_trans_table_new(), apol_infoflow_graph_create(), apol_infoflow_graph_create_required_types(), apol_terule_list_to_syn_terules(), avrule_get_items(), db_convert::db_convert(), dom_node_create(), ep_node_create(), poldiff_build_bsts(), role_allow_get_items(), seaudit_log_clear(), seaudit_log_create(), seaudit_model_create(), sefs_fclist::sefs_fclist(), and terule_get_items().

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 }

void bst_node_free	(	bst_node_t *	node,
		apol_bst_free_func *	fr
	)	`[static]`

Free the data stored within a bst node, recurse through the node's children, and then the node itself.

Parameters:

	node	Node to free. If NULL then do stop recursing.
	fr	Callback to free a node's data. If NULL then do not free the data.

Definition at line 77 of file bst.c.

References bst_node_t, bst_node::child, and bst_node::elem.

Referenced by apol_bst_destroy().

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 }

void apol_bst_destroy

(

apol_bst_t **

)

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.

Parameters:

Pointer to the BST to free. The pointer will be set to NULL afterwards. If already NULL then this function does nothing.

Definition at line 89 of file bst.c.

References apol_bst_t, bst_node_free(), and apol_bst::head.

Referenced by apol_avrule_list_to_syn_avrules(), apol_infoflow_graph_create(), apol_infoflow_graph_create_required_types(), apol_infoflow_graph_destroy(), apol_terule_list_to_syn_terules(), avrule_get_items(), db_convert::db_convert(), dom_node_create(), dom_node_free(), domain_trans_table_destroy(), ep_node_create(), ep_node_free(), poldiff_destroy(), role_allow_get_items(), seaudit_log_clear(), seaudit_log_destroy(), seaudit_model_destroy(), sefs_fclist::sefs_fclist(), terule_get_items(), db_convert::~db_convert(), and sefs_fclist::~sefs_fclist().

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 }

int bst_node_to_vector	(	bst_node_t *	node,
		apol_vector_t *	v
	)	`[static]`

Given a BST node, traverse the node infix, appending the node's element to vector v.

Parameters:

	node	BST node to recurse.
	v	Vector to which append.

Returns:: 0 on success, < 0 on error.

Definition at line 108 of file bst.c.

References apol_vector_append(), apol_vector_t, bst_node_t, bst_node::child, and bst_node::elem.

Referenced by apol_bst_get_vector().

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 }

apol_vector_t* apol_bst_get_vector	(	apol_bst_t *	b,
		int	change_owner
	)

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 shallow copy of the BST's contents; the BST will still own 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.)

Parameters:

	b	Binary search tree from which to copy.
	change_owner	If zero then do a shallow copy, else change item ownership.

Returns:: 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.

Definition at line 123 of file bst.c.

References apol_bst_t, apol_vector_create_with_capacity(), apol_vector_destroy(), apol_vector_t, bst_node_to_vector(), apol_bst::fr, apol_bst::head, apol_bst::size, and vector_set_free_func().

Referenced by apol_avrule_list_to_syn_avrules(), apol_infoflow_graph_create(), apol_terule_list_to_syn_terules(), avrule_get_items(), domain_trans_table_find_orphan_type_transitions(), domain_trans_table_get_all_forward_trans(), domain_trans_table_get_all_reverse_trans(), role_allow_get_items(), seaudit_log_get_classes(), seaudit_log_get_roles(), seaudit_log_get_types(), seaudit_log_get_users(), and terule_get_items().

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 }

size_t apol_bst_get_size

(

const apol_bst_t *

)

Get the number of elements stored in the BST.

Parameters:

The BST from which to get the number of elements. Must be non-NULL.

Returns:: The number of elements in the BST; if b is NULL, return 0 and set errno.

Definition at line 146 of file bst.c.

References apol_bst_t, and apol_bst::size.

00147 {
00148         if (!b) {
00149                 errno = EINVAL;
00150                 return 0;
00151         } else {
00152                 return b->size;
00153         }
00154 }

int apol_bst_get_element	(	const apol_bst_t *	b,
		const void *	elem,
		void *	data,
		void **	result
	)

Find an element within a BST and return it.

Parameters:

	b	The BST from which to get the element.
	elem	The element to find. (This will be the second parameter to the comparison function given in apol_bst_create().)
	data	Arbitrary data to pass as the comparison function's third paramater (the function given in apol_bst_create()).
	elem	Location to write the found element. This value is undefined if the key did not match any elements.

Returns:: 0 if element was found, or < 0 if not found.

Definition at line 156 of file bst.c.

References apol_bst_t, bst_node_t, bst_node::child, apol_bst::cmp, bst_node::elem, and apol_bst::head.

Referenced by apol_domain_trans_table_verify_trans(), apol_infoflow_graph_check_types(), apol_infoflow_graph_create_node(), apol_infoflow_graph_create_nodes(), avrule_add_to_bst(), avrule_build_cond(), domain_trans_table_find_orphan_type_transitions(), domain_trans_table_get_all_forward_trans(), domain_trans_table_get_all_reverse_trans(), sefs_fclist::getContext(), db_convert::getID(), model_refresh(), table_add_avrule(), table_add_terule(), terule_add_to_bst(), and terule_build_cond().

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 }

bst_node_t* bst_node_make	(	apol_bst_t *	b,
		void *	elem
	)	`[static]`

Allocate and return a new BST node, with data set to elem and color to red.

Also increment the tree's size.

Parameters:

	b	BST size to increment.
	elem	Value for the node.

Returns:: Allocated BST node, which the caller must insert, or NULL on error.

Definition at line 201 of file bst.c.

References apol_bst_t, bst_node_t, bst_node::elem, bst_node::is_red, and apol_bst::size.

Referenced by bst_insert_recursive().

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 }

int bst_node_is_red ( bst_node_t * node ) [static]

Determines if a node is red or not.

Parameters:

node

Node to check. If NULL then treat the node as black.

Returns:: 0 if the node is black, 1 if red.

Definition at line 220 of file bst.c.

References bst_node_t, and bst_node::is_red.

Referenced by bst_insert_recursive().

00221 {
00222         return node != NULL && node->is_red;
00223 }

bst_node_t* bst_rotate_single	(	bst_node_t *	root,
		int	dir
	)	`[static]`

Definition at line 225 of file bst.c.

References bst_node_t, bst_node::child, and bst_node::is_red.

Referenced by bst_insert_recursive(), and bst_rotate_double().

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 }

bst_node_t* bst_rotate_double	(	bst_node_t *	root,
		int	dir
	)	`[static]`

Definition at line 235 of file bst.c.

References bst_node_t, bst_rotate_single(), and bst_node::child.

Referenced by bst_insert_recursive().

00236 {
00237         root->child[!dir] = bst_rotate_single(root->child[!dir], !dir);
00238         return bst_rotate_single(root, dir);
00239 }

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
	)	`[static]`

Definition at line 241 of file bst.c.

References apol_bst_t, bst_node_is_red(), bst_node_make(), bst_node_t, bst_rotate_double(), bst_rotate_single(), bst_node::child, apol_bst::cmp, bst_node::elem, and bst_node::is_red.

Referenced by apol_bst_insert(), and apol_bst_insert_and_get().

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 }

int apol_bst_insert	(	apol_bst_t *	b,
		void *	elem,
		void *	data
	)

Insert an element to the BST.

If the element already exists then do not insert it again.

Parameters:

	b	The BST to which to add the element.
	elem	The element to add.
	data	Arbitrary data to pass as the comparison function's third paramater (the function given in apol_bst_create()).

Returns:: 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.

Definition at line 304 of file bst.c.

References apol_bst_t, bst_insert_recursive(), apol_bst::head, and bst_node::is_red.

Referenced by apol_avrule_list_to_syn_avrules(), apol_infoflow_graph_create_node(), apol_infoflow_graph_create_required_types(), apol_terule_list_to_syn_terules(), sefs_fclist::getContext(), db_convert::getID(), seaudit_model_hide_message(), table_add_avrule(), and table_add_terule().

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 }

int apol_bst_insert_and_get	(	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.

Parameters:

	b	The BST to which to add the element.
	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.
	data	Arbitrary data to pass as the comparison function's third paramater (the function given in apol_bst_create()).

Returns:: 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.

Definition at line 318 of file bst.c.

References apol_bst_t, bst_insert_recursive(), apol_bst::fr, apol_bst::head, and bst_node::is_red.

Referenced by avc_msg_insert_perms(), avc_msg_insert_tclass(), avrule_add_to_bst(), bool_change_append(), sefs_filesystem::buildDevMap(), sefs_fclist::getContext(), sefs_filesystem::getEntry(), sefs_db::getEntry(), insert_hostname(), insert_manager(), parse_context(), sefs_fcfile::parse_line(), poldiff_build_bsts(), role_allow_get_items(), table_add_avrule(), table_add_terule(), and terule_add_to_bst().

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 }

int bst_inorder_map	(	const bst_node_t *	node,
		int()(void , void *)	fn,
		void *	data
	)	`[static]`

Definition at line 332 of file bst.c.

References bst_node_t, bst_node::child, and bst_node::elem.

Referenced by apol_bst_inorder_map().

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 }

int apol_bst_inorder_map	(	const apol_bst_t *	b,
		int()(void , void *)	fn,
		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.

Parameters:

	node	BST upon which to map against.
	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.

Returns:: Result of the last call to fn() (i.e., >= 0 on success < 0 on failure). If the tree is empty then return 0.

Definition at line 347 of file bst.c.

References apol_bst_t, bst_inorder_map(), and apol_bst::head.

Referenced by apol_policy_reset_domain_trans_table(), sefs_fclist::associatePolicy(), dom_node_reset(), ep_node_reset(), find_avrules_in_node(), and find_terules_in_node().

00348 {
00349         if (b == NULL || fn == NULL)
00350                 return -1;
00351         return bst_inorder_map(b->head, fn, data);
00352 }

bst.c File Reference

Detailed Description

Classes

Typedefs

Functions

Typedef Documentation

Function Documentation