Line data Source code
1 : // SPDX-License-Identifier: BSD-2-Clause 2 : // Copyright (C) 2015 Andrea Mazzoleni 3 : 4 : /** \file 5 : * AVL tree. 6 : * 7 : * This tree is a standard AVL tree implementation that stores elements in the 8 : * order defined by the comparison function. 9 : * 10 : * As a difference from other tommy containers, duplicate elements cannot be inserted. 11 : * 12 : * To initialize a tree you have to call tommy_tree_init() specifying a comparison 13 : * function that will define the order in the tree. 14 : * 15 : * \code 16 : * tommy_tree tree; 17 : * 18 : * tommy_tree_init(&tree, cmp); 19 : * \endcode 20 : * 21 : * To insert elements in the tree you have to call tommy_tree_insert() for 22 : * each element. 23 : * In the insertion call you have to specify the address of the node and the 24 : * address of the object. 25 : * The address of the object is used to initialize the tommy_node::data field 26 : * of the node. 27 : * 28 : * \code 29 : * struct object { 30 : * int value; 31 : * // other fields 32 : * tommy_tree_node node; 33 : * }; 34 : * 35 : * struct object* obj = malloc(sizeof(struct object)); // creates the object 36 : * 37 : * obj->value = ...; // initializes the object 38 : * 39 : * tommy_tree_insert(&tree, &obj->node, obj); // inserts the object 40 : * \endcode 41 : * 42 : * To find an element in the tree you have to call tommy_tree_search() providing 43 : * the key to search. 44 : * 45 : * \code 46 : * struct object value_to_find = { 1 }; 47 : * struct object* obj = tommy_tree_search(&tree, &value_to_find); 48 : * if (!obj) { 49 : * // not found 50 : * } else { 51 : * // found 52 : * } 53 : * \endcode 54 : * 55 : * To remove an element from the tree you have to call tommy_tree_remove() 56 : * providing the key to search and remove. 57 : * 58 : * \code 59 : * struct object value_to_remove = { 1 }; 60 : * struct object* obj = tommy_tree_remove(&tree, &value_to_remove); 61 : * if (obj) { 62 : * free(obj); // frees the object allocated memory 63 : * } 64 : * \endcode 65 : * 66 : * To destroy the tree you have to remove or destroy all the contained elements. 67 : * The tree itself doesn't have or need a deallocation function. 68 : * 69 : * If you need to iterate over all the elements in the tree, you can use 70 : * tommy_tree_foreach() or tommy_tree_foreach_arg(). 71 : * If you need a more precise control with a real iteration, you have to insert 72 : * all the elements also in a ::tommy_list, and use the list to iterate. 73 : * See the \ref multiindex example for more detail. 74 : */ 75 : 76 : #ifndef __TOMMYTREE_H 77 : #define __TOMMYTREE_H 78 : 79 : #include "tommytypes.h" 80 : 81 : /******************************************************************************/ 82 : /* tree */ 83 : 84 : /** 85 : * Tree node. 86 : * This is the node that you have to include inside your objects. 87 : */ 88 : typedef tommy_node tommy_tree_node; 89 : 90 : /** 91 : * Tree container type. 92 : * \note Don't use internal fields directly, but access the container only using functions. 93 : */ 94 : typedef struct tommy_tree_struct { 95 : tommy_tree_node* root; /**< Root node. */ 96 : tommy_compare_func* cmp; /**< Comparison function. */ 97 : tommy_size_t count; /**< Number of elements. */ 98 : } tommy_tree; 99 : 100 : /** 101 : * Initializes the tree. 102 : * \param cmp The comparison function that defines the order in the tree. 103 : */ 104 : TOMMY_API void tommy_tree_init(tommy_tree* tree, tommy_compare_func* cmp); 105 : 106 : /** 107 : * Inserts an element in the tree. 108 : * If the element is already present, it's not inserted again. 109 : * Check the return value to identify if the element was already present or not. 110 : * You have to provide the pointer of the node embedded into the object and 111 : * the pointer to the object. 112 : * \param node Pointer to the node embedded into the object to insert. 113 : * \param data Pointer to the object to insert. 114 : * \return The element in the tree. Either the already existing one, or the one just inserted. 115 : */ 116 : TOMMY_API void* tommy_tree_insert(tommy_tree* tree, tommy_tree_node* node, void* data); 117 : 118 : /** 119 : * Searches and removes an element. 120 : * If the element is not found, 0 is returned. 121 : * \param data Element used for comparison. 122 : * \return The removed element, or 0 if not found. 123 : */ 124 : TOMMY_API void* tommy_tree_remove(tommy_tree* tree, void* data); 125 : 126 : /** 127 : * Searches an element in the tree. 128 : * If the element is not found, 0 is returned. 129 : * \param data Element used for comparison. 130 : * \return The first element found, or 0 if none. 131 : */ 132 : TOMMY_API void* tommy_tree_search(tommy_tree* tree, void* data); 133 : 134 : /** 135 : * Searches an element in the tree with a specific comparison function. 136 : * 137 : * Like tommy_tree_search() but you can specify a different comparison function. 138 : * Note that this function must define a suborder of the original one. 139 : * 140 : * The ::data argument will be the first argument of the comparison function, 141 : * and it can be of a different type than the objects in the tree. 142 : */ 143 : TOMMY_API void* tommy_tree_search_compare(tommy_tree* tree, tommy_compare_func* cmp, void* cmp_arg); 144 : 145 : /** 146 : * Removes an element from the tree. 147 : * You must already have the address of the element to remove. 148 : * \return The tommy_node::data field of the node removed. 149 : */ 150 : TOMMY_API void* tommy_tree_remove_existing(tommy_tree* tree, tommy_tree_node* node); 151 : 152 : /** 153 : * Calls the specified function for each element in the tree. 154 : * 155 : * The elements are processed in order. 156 : * 157 : * You cannot add or remove elements from the inside of the callback, 158 : * but can use it to deallocate them. 159 : * 160 : * \code 161 : * tommy_tree tree; 162 : * 163 : * // initializes the tree 164 : * tommy_tree_init(&tree, cmp); 165 : * 166 : * ... 167 : * 168 : * // creates an object 169 : * struct object* obj = malloc(sizeof(struct object)); 170 : * 171 : * ... 172 : * 173 : * // insert it in the tree 174 : * tommy_tree_insert(&tree, &obj->node, obj); 175 : * 176 : * ... 177 : * 178 : * // deallocates all the objects iterating the tree 179 : * tommy_tree_foreach(&tree, free); 180 : * \endcode 181 : */ 182 : TOMMY_API void tommy_tree_foreach(tommy_tree* tree, tommy_foreach_func* func); 183 : 184 : /** 185 : * Calls the specified function with an argument for each element in the tree. 186 : */ 187 : TOMMY_API void tommy_tree_foreach_arg(tommy_tree* tree, tommy_foreach_arg_func* func, void* arg); 188 : 189 : /** 190 : * Gets the number of elements. 191 : */ 192 3 : tommy_inline tommy_size_t tommy_tree_count(tommy_tree* tree) 193 : { 194 3 : return tree->count; 195 : } 196 : 197 : /** 198 : * Gets the size of allocated memory. 199 : * It includes the size of the ::tommy_tree_node of the stored elements. 200 : */ 201 : TOMMY_API tommy_size_t tommy_tree_memory_usage(tommy_tree* tree); 202 : 203 : #endif
