LCOV - code coverage report
Current view: top level - tommyds/tommyds - tommytree.h (source / functions) Hit Total Coverage
Test: lcov.info Lines: 2 2 100.0 %
Date: 2018-04-02 17:50:51 Functions: 1 1 100.0 %

          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_compare_func* cmp; /**< Comparison function. */
     121             :         tommy_size_t count; /**< Number of elements. */
     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           2 : tommy_inline tommy_size_t tommy_tree_count(tommy_tree* tree)
     217             : {
     218           2 :         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             : 

Generated by: LCOV version 1.13