1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
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 */
|
