snapraid/tommyds/tommytree.h
2020-09-11 13:42:22 +02:00

229 lines
7.1 KiB
C

/*
* Copyright (c) 2015, Andrea Mazzoleni. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
/** \file
* AVL tree.
*
* This tree is a standard AVL tree implementation that stores elements in the
* order defined by the comparison function.
*
* As difference than other tommy containers, duplicate elements cannot be inserted.
*
* To initialize a tree you have to call tommy_tree_init() specifying a comparison
* function that will define the order in the tree.
*
* \code
* tommy_tree tree;
*
* tommy_tree_init(&tree, cmp);
* \endcode
*
* To insert elements in the tree you have to call tommy_tree_insert() for
* each element.
* In the insertion call you have to specify the address of the node and the
* address of the object.
* The address of the object is used to initialize the tommy_node::data field
* of the node.
*
* \code
* struct object {
* int value;
* // other fields
* tommy_tree_node node;
* };
*
* struct object* obj = malloc(sizeof(struct object)); // creates the object
*
* obj->value = ...; // initializes the object
*
* tommy_tree_insert(&tree, &obj->node, obj); // inserts the object
* \endcode
*
* To find and element in the tree you have to call tommy_tree_search() providing
* the key to search.
*
* \code
* struct object value_to_find = { 1 };
* struct object* obj = tommy_tree_search(&tree, &value_to_find);
* if (!obj) {
* // not found
* } else {
* // found
* }
* \endcode
*
* To remove an element from the tree you have to call tommy_tree_remove()
* providing the key to search and remove.
*
* \code
* struct object value_to_remove = { 1 };
* struct object* obj = tommy_tree_remove(&tree, &value_to_remove);
* if (obj) {
* free(obj); // frees the object allocated memory
* }
* \endcode
*
* To destroy the tree you have to remove or destroy all the contained elements.
* The tree itself doesn't have or need a deallocation function.
*
* If you need to iterate over all the elements in the tree, you can use
* tommy_tree_foreach() or tommy_tree_foreach_arg().
* If you need a more precise control with a real iteration, you have to insert
* all the elements also in a ::tommy_list, and use the list to iterate.
* See the \ref multiindex example for more detail.
*/
#ifndef __TOMMYTREE_H
#define __TOMMYTREE_H
#include "tommytypes.h"
/******************************************************************************/
/* tree */
/**
* Tree node.
* This is the node that you have to include inside your objects.
*/
typedef tommy_node tommy_tree_node;
/**
* Tree container type.
* \note Don't use internal fields directly, but access the container only using functions.
*/
typedef struct tommy_tree_struct {
tommy_tree_node* root; /**< Root node. */
tommy_compare_func* cmp; /**< Comparison function. */
tommy_size_t count; /**< Number of elements. */
} tommy_tree;
/**
* Initializes the tree.
* \param cmp The comparison function that defines the order in the tree.
*/
void tommy_tree_init(tommy_tree* tree, tommy_compare_func* cmp);
/**
* Inserts an element in the tree.
* If the element is already present, it's not inserted again.
* Check the return value to identify if the element was already present or not.
* You have to provide the pointer of the node embedded into the object and
* the pointer to the object.
* \param node Pointer to the node embedded into the object to insert.
* \param data Pointer to the object to insert.
* \return The element in the tree. Either the already existing one, or the one just inserted.
*/
void* tommy_tree_insert(tommy_tree* tree, tommy_tree_node* node, void* data);
/**
* Searches and removes an element.
* If the element is not found, 0 is returned.
* \param data Element used for comparison.
* \return The removed element, or 0 if not found.
*/
void* tommy_tree_remove(tommy_tree* tree, void* data);
/**
* Searches an element in the tree.
* If the element is not found, 0 is returned.
* \param data Element used for comparison.
* \return The first element found, or 0 if none.
*/
void* tommy_tree_search(tommy_tree* tree, void* data);
/**
* Searches an element in the tree with a specific comparison function.
*
* Like tommy_tree_search() but you can specify a different comparison function.
* Note that this function must define a suborder of the original one.
*
* The ::data argument will be the first argument of the comparison function,
* and it can be of a different type of the objects in the tree.
*/
void* tommy_tree_search_compare(tommy_tree* tree, tommy_compare_func* cmp, void* cmp_arg);
/**
* Removes an element from the tree.
* You must already have the address of the element to remove.
* \return The tommy_node::data field of the node removed.
*/
void* tommy_tree_remove_existing(tommy_tree* tree, tommy_tree_node* node);
/**
* Calls the specified function for each element in the tree.
*
* The elements are processed in order.
*
* You cannot add or remove elements from the inside of the callback,
* but can use it to deallocate them.
*
* \code
* tommy_tree tree;
*
* // initializes the tree
* tommy_tree_init(&tree, cmp);
*
* ...
*
* // creates an object
* struct object* obj = malloc(sizeof(struct object));
*
* ...
*
* // insert it in the tree
* tommy_tree_insert(&tree, &obj->node, obj);
*
* ...
*
* // deallocates all the objects iterating the tree
* tommy_tree_foreach(&tree, free);
* \endcode
*/
void tommy_tree_foreach(tommy_tree* tree, tommy_foreach_func* func);
/**
* Calls the specified function with an argument for each element in the tree.
*/
void tommy_tree_foreach_arg(tommy_tree* tree, tommy_foreach_arg_func* func, void* arg);
/**
* Gets the number of elements.
*/
tommy_inline tommy_size_t tommy_tree_count(tommy_tree* tree)
{
return tree->count;
}
/**
* Gets the size of allocated memory.
* It includes the size of the ::tommy_tree_node of the stored elements.
*/
tommy_size_t tommy_tree_memory_usage(tommy_tree* tree);
#endif