Line data Source code
1 : /*
2 : * Copyright (c) 2015, Andrea Mazzoleni. All rights reserved.
3 : *
4 : * Redistribution and use in source and binary forms, with or without
5 : * modification, are permitted provided that the following conditions
6 : * are met:
7 : *
8 : * 1. Redistributions of source code must retain the above copyright
9 : * notice, this list of conditions and the following disclaimer.
10 : *
11 : * 2. Redistributions in binary form must reproduce the above copyright
12 : * notice, this list of conditions and the following disclaimer in the
13 : * documentation and/or other materials provided with the distribution.
14 : *
15 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
19 : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
20 : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
21 : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
22 : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23 : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
24 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
25 : * POSSIBILITY OF SUCH DAMAGE.
26 : */
27 :
28 : /** \file
29 : * AVL tree.
30 : *
31 : * This tree is a standard AVL tree implementation that stores elements in the
32 : * order defined by the comparison function.
33 : *
34 : * As difference than other tommy containers, duplicate elements cannot be inserted.
35 : *
36 : * To initialize a tree you have to call tommy_tree_init() specifing a comparison
37 : * function that will define the order in the tree.
38 : *
39 : * \code
40 : * tommy_tree tree;
41 : *
42 : * tommy_tree_init(&tree, cmp);
43 : * \endcode
44 : *
45 : * To insert elements in the tree you have to call tommy_tree_insert() for
46 : * each element.
47 : * In the insertion call you have to specify the address of the node and the
48 : * address of the object.
49 : * The address of the object is used to initialize the tommy_node::data field
50 : * of the node.
51 : *
52 : * \code
53 : * struct object {
54 : * int value;
55 : * // other fields
56 : * tommy_tree_node node;
57 : * };
58 : *
59 : * struct object* obj = malloc(sizeof(struct object)); // creates the object
60 : *
61 : * obj->value = ...; // initializes the object
62 : *
63 : * tommy_tree_insert(&tree, &obj->node, obj); // inserts the object
64 : * \endcode
65 : *
66 : * To find and element in the tree you have to call tommy_tree_search() providing
67 : * the key to search.
68 : *
69 : * \code
70 : * struct object value_to_find = { 1 };
71 : * struct object* obj = tommy_tree_search(&tree, &value_to_find);
72 : * if (!obj) {
73 : * // not found
74 : * } else {
75 : * // found
76 : * }
77 : * \endcode
78 : *
79 : * To remove an element from the tree you have to call tommy_tree_remove()
80 : * providing the key to search and remove.
81 : *
82 : * \code
83 : * struct object value_to_remove = { 1 };
84 : * struct object* obj = tommy_tree_remove(&tree, &value_to_remove);
85 : * if (obj) {
86 : * free(obj); // frees the object allocated memory
87 : * }
88 : * \endcode
89 : *
90 : * To destroy the tree you have to remove or destroy all the contained elements.
91 : * The tree itself doesn't have or need a deallocation function.
92 : *
93 : * If you need to iterate over all the elements in the tree, you can use
94 : * tommy_tree_foreach() or tommy_tree_foreach_arg().
95 : * If you need a more precise control with a real iteration, you have to insert
96 : * all the elements also in a ::tommy_list, and use the list to iterate.
97 : * See the \ref multiindex example for more detail.
98 : */
99 :
100 : #ifndef __TOMMYTREE_H
101 : #define __TOMMYTREE_H
102 :
103 : #include "tommytypes.h"
104 :
105 : /******************************************************************************/
106 : /* tree */
107 :
108 : /**
109 : * Tree node.
110 : * This is the node that you have to include inside your objects.
111 : */
112 : typedef tommy_node tommy_tree_node;
113 :
114 : /**
115 : * Tree container type.
116 : * \note Don't use internal fields directly, but access the container only using functions.
117 : */
118 : typedef struct tommy_tree_struct {
119 : tommy_tree_node* root; /**< Root node. */
120 : tommy_count_t count; /**< Number of elements. */
121 : tommy_compare_func* cmp; /**< Comparison function. */
122 : } tommy_tree;
123 :
124 : /**
125 : * Initializes the tree.
126 : * \param cmp The comparison function that defines the orderin the tree.
127 : */
128 : void tommy_tree_init(tommy_tree* tree, tommy_compare_func* cmp);
129 :
130 : /**
131 : * Inserts an element in the tree.
132 : * If the element is already present, it's not inserted again.
133 : * Check the return value to identify if the element was already present or not.
134 : * You have to provide the pointer of the node embedded into the object and
135 : * the pointer to the object.
136 : * \param node Pointer to the node embedded into the object to insert.
137 : * \param data Pointer to the object to insert.
138 : * \return The element in the tree. Either the already existing one, or the one just inserted.
139 : */
140 : void* tommy_tree_insert(tommy_tree* tree, tommy_tree_node* node, void* data);
141 :
142 : /**
143 : * Searches and removes an element.
144 : * If the element is not found, 0 is returned.
145 : * \param data Element used for comparison.
146 : * \return The removed element, or 0 if not found.
147 : */
148 : void* tommy_tree_remove(tommy_tree* tree, void* data);
149 :
150 : /**
151 : * Searches an element in the tree.
152 : * If the element is not found, 0 is returned.
153 : * \param data Element used for comparison.
154 : * \return The first element found, or 0 if none.
155 : */
156 : void* tommy_tree_search(tommy_tree* tree, void* data);
157 :
158 : /**
159 : * Searches an element in the tree with a specific comparison function.
160 : *
161 : * Like tommy_tree_search() but you can specify a different comparison function.
162 : * Note that this function must define a suborder of the original one.
163 : *
164 : * The ::data argument will be the first argument of the comparison function,
165 : * and it can be of a different type of the objects in the tree.
166 : */
167 : void* tommy_tree_search_compare(tommy_tree* tree, tommy_compare_func* cmp, void* cmp_arg);
168 :
169 : /**
170 : * Removes an element from the tree.
171 : * You must already have the address of the element to remove.
172 : * \return The tommy_node::data field of the node removed.
173 : */
174 : void* tommy_tree_remove_existing(tommy_tree* tree, tommy_tree_node* node);
175 :
176 : /**
177 : * Calls the specified function for each element in the tree.
178 : *
179 : * The elements are processed in order.
180 : *
181 : * You cannot add or remove elements from the inside of the callback,
182 : * but can use it to deallocate them.
183 : *
184 : * \code
185 : * tommy_tree tree;
186 : *
187 : * // initializes the tree
188 : * tommy_tree_init(&tree, cmp);
189 : *
190 : * ...
191 : *
192 : * // creates an object
193 : * struct object* obj = malloc(sizeof(struct object));
194 : *
195 : * ...
196 : *
197 : * // insert it in the tree
198 : * tommy_tree_insert(&tree, &obj->node, obj);
199 : *
200 : * ...
201 : *
202 : * // deallocates all the objects iterating the tree
203 : * tommy_tree_foreach(&tree, free);
204 : * \endcode
205 : */
206 : void tommy_tree_foreach(tommy_tree* tree, tommy_foreach_func* func);
207 :
208 : /**
209 : * Calls the specified function with an argument for each element in the tree.
210 : */
211 : void tommy_tree_foreach_arg(tommy_tree* tree, tommy_foreach_arg_func* func, void* arg);
212 :
213 : /**
214 : * Gets the number of elements.
215 : */
216 3 : tommy_inline tommy_count_t tommy_tree_count(tommy_tree* tree)
217 : {
218 3 : return tree->count;
219 : }
220 :
221 : /**
222 : * Gets the size of allocated memory.
223 : * It includes the size of the ::tommy_tree_node of the stored elements.
224 : */
225 : tommy_size_t tommy_tree_memory_usage(tommy_tree* tree);
226 :
227 : #endif
228 :
|