src/include/eina_rbtree.h

   1 /* EINA - EFL data type library
   2  * Copyright (C) 2008 Cedric Bail
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2.1 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library;
  16  * if not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19 #ifndef EINA_RBTREE_H__
  20 #define EINA_RBTREE_H__
  21
  22 #include <stdlib.h>
  23
  24 #include "eina_types.h"
  25 #include "eina_error.h"
  26 #include "eina_iterator.h"
  27
  28 /**
  29  * @addtogroup Eina_Rbtree_Group Red-Black tree
  30  *
  31  * @brief These functions provide Red-Black trees management.
  32  *
  33  * For a brief description look at http://en.wikipedia.org/wiki/Red-black_tree .
  34  * This code is largely inspired from a tutorial written by Julienne Walker at :
  35  * http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx . The
  36  * main difference is that this set of function never allocate any data, making
  37  * them particularly useful for memory management.
  38  */
  39
  40 /**
  41  * @addtogroup Eina_Data_Types_Group Data Types
  42  *
  43  * @{
  44  */
  45
  46 /**
  47  * @addtogroup Eina_Containers_Group Containers
  48  *
  49  * @{
  50  */
  51
  52 /**
  53  * @defgroup Eina_Rbtree_Group Red-Black tree
  54  *
  55  * @{
  56  */
  57
  58 /**
  59  * @typedef Eina_Rbtree_Color
  60  * node color.
  61  */
  62 typedef enum {
  63    EINA_RBTREE_RED,
  64    EINA_RBTREE_BLACK
  65 } Eina_Rbtree_Color;
  66
  67 /**
  68  * @typedef Eina_Rbtree_Direction
  69  * walk direction.
  70  */
  71 typedef enum {
  72    EINA_RBTREE_LEFT = 0,
  73    EINA_RBTREE_RIGHT = 1
  74 } Eina_Rbtree_Direction;
  75
  76 /**
  77  * @typedef Eina_Rbtree
  78  * Type for a Red-Black tree node. It should be inlined into user's type.
  79  */
  80 typedef struct _Eina_Rbtree Eina_Rbtree;
  81 struct _Eina_Rbtree
  82 {
  83    Eina_Rbtree      *son[2];
  84
  85    Eina_Rbtree_Color color : 1;
  86 };
  87
  88 /**
  89  * @def EINA_RBTREE
  90  * recommended way to declare the inlined Eina_Rbtree in your type.
  91  *
  92  * @code
  93  * struct my_type {
  94  *    EINA_RBTREE;
  95  *    int my_value;
  96  *    char *my_name;
  97  * };
  98  * @endcode
  99  *
 100  * @see EINA_RBTREE_GET()
 101  */
 102 #define EINA_RBTREE Eina_Rbtree __rbtree
 103
 104 /**
 105  * @def EINA_RBTREE_GET
 106  * access the inlined node if it was created with #EINA_RBTREE.
 107  */
 108 #define EINA_RBTREE_GET(Rbtree) (&((Rbtree)->__rbtree))
 109
 110 /**
 111  * @def EINA_RBTREE_CONTAINER_GET
 112  * find back the container of an red black tree.
 113  */
 114 #define EINA_RBTREE_CONTAINER_GET(Ptr, Type) ((Type *)((char *)Ptr - offsetof(Type, __rbtree)))
 115
 116 /**
 117  * @typedef Eina_Rbtree_Cmp_Node_Cb
 118  * Function used compare two nodes and see which direction to navigate.
 119  */
 120 typedef Eina_Rbtree_Direction (*Eina_Rbtree_Cmp_Node_Cb)(const Eina_Rbtree *left, const Eina_Rbtree *right, void *data);
 121
 122 /**
 123  * @def EINA_RBTREE_CMP_NODE_CB
 124  * Cast using #Eina_Rbtree_Cmp_Node_Cb
 125  */
 126 #define EINA_RBTREE_CMP_NODE_CB(Function) ((Eina_Rbtree_Cmp_Node_Cb)Function)
 127
 128 /**
 129  * @typedef Eina_Rbtree_Cmp_Key_Cb
 130  * Function used compare node with a given key of specified length.
 131  */
 132 typedef int (*Eina_Rbtree_Cmp_Key_Cb)(const Eina_Rbtree *node, const void *key, int length, void *data);
 133 /**
 134  * @def EINA_RBTREE_CMP_KEY_CB
 135  * Cast using #Eina_Rbtree_Cmp_Key_Cb
 136  */
 137 #define EINA_RBTREE_CMP_KEY_CB(Function) ((Eina_Rbtree_Cmp_Key_Cb)Function)
 138
 139 /**
 140  * @typedef Eina_Rbtree_Free_Cb
 141  * Function used free a node.
 142  */
 143 typedef void (*Eina_Rbtree_Free_Cb)(Eina_Rbtree *node, void *data);
 144 /**
 145  * @def EINA_RBTREE_FREE_CB
 146  * Cast using #Eina_Rbtree_Free_Cb
 147  */
 148 #define EINA_RBTREE_FREE_CB(Function) ((Eina_Rbtree_Free_Cb)Function)
 149
 150
 151 /**
 152  * @brief Insert a new node inside an existing red black tree.
 153  *
 154  * @param root The root of an exisiting valid red black tree.
 155  * @param node The new node to insert.
 156  * @param cmp The callback that is able to compare two nodes.
 157  * @param data Private data to help the compare function.
 158  * @return The new root of the red black tree.
 159  *
 160  * This function insert a new node in a valid red black tree. @c NULL is
 161  * an empty valid red black tree. The resulting new tree is a valid red
 162  * black tree. This function doesn't allocate any data.
 163  */
 164 EAPI Eina_Rbtree          *eina_rbtree_inline_insert(Eina_Rbtree *root, Eina_Rbtree *node, Eina_Rbtree_Cmp_Node_Cb cmp, const void *data) EINA_ARG_NONNULL(2, 3) EINA_WARN_UNUSED_RESULT;
 165
 166 /**
 167  * @brief Remove a node from an existing red black tree.
 168  *
 169  * @param root The root of a valid red black tree.
 170  * @param node The node to remove from the tree.
 171  * @param cmp The callback that is able to compare two nodes.
 172  * @param data Private data to help the compare function.
 173  * @return The new root of the red black tree.
 174  *
 175  * This function remove a new node in a valid red black tree that should
 176  * contain the node that you are removing. This function will return @c NULL
 177  * when the red black tree got empty. This function doesn't free any data.
 178  */
 179 EAPI Eina_Rbtree          *eina_rbtree_inline_remove(Eina_Rbtree *root, Eina_Rbtree *node, Eina_Rbtree_Cmp_Node_Cb cmp, const void *data) EINA_ARG_NONNULL(2, 3) EINA_WARN_UNUSED_RESULT;
 180
 181 /**
 182  * @brief Delete all nodes from a valid red black tree.
 183  *
 184  * @param root The root of a valid red black tree.
 185  * @param func The callback that will free each node.
 186  * @param data Private data to help the compare function.
 187  *
 188  */
 189 EAPI void                  eina_rbtree_delete(Eina_Rbtree *root, Eina_Rbtree_Free_Cb func, void *data) EINA_ARG_NONNULL(2);
 190
 191 static inline Eina_Rbtree *eina_rbtree_inline_lookup(const Eina_Rbtree *root, const void *key, int length, Eina_Rbtree_Cmp_Key_Cb cmp, const void *data) EINA_PURE EINA_ARG_NONNULL(2, 4) EINA_WARN_UNUSED_RESULT;
 192
 193
 194 /**
 195  * @brief Returned a new prefix iterator associated to a rbtree.
 196  *
 197  * @param root The root of rbtree.
 198  * @return A new iterator.
 199  *
 200  * This function returns a newly allocated iterator associated to @p
 201  * root. It will iterate the tree using prefix walk. If @p root is @c
 202  * NULL, this function still returns a valid iterator that will always
 203  * return false on eina_iterator_next(), thus keeping API sane.
 204  *
 205  * If the memory can not be allocated, @c NULL is returned
 206  * and #EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is
 207  * returned.
 208  *
 209  * @warning if the rbtree structure changes then the iterator becomes
 210  *    invalid! That is, if you add or remove nodes this iterator
 211  *    behavior is undefined and your program may crash!
 212  */
 213 EAPI Eina_Iterator        *eina_rbtree_iterator_prefix(const Eina_Rbtree *root) EINA_MALLOC EINA_WARN_UNUSED_RESULT;
 214
 215 /**
 216  * @brief Returned a new prefix iterator associated to a rbtree.
 217  *
 218  * @param root The root of rbtree.
 219  * @return A new iterator.
 220  *
 221  * This function returns a newly allocated iterator associated to @p
 222  * root. It will iterate the tree using infix walk. If @p root is @c
 223  * NULL, this function still returns a valid iterator that will always
 224  * return false on eina_iterator_next(), thus keeping API sane.
 225  *
 226  * If the memory can not be allocated, @c NULL is returned
 227  * and #EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is
 228  * returned.
 229  *
 230  * @warning if the rbtree structure changes then the iterator becomes
 231  *    invalid! That is, if you add or remove nodes this iterator
 232  *    behavior is undefined and your program may crash!
 233  */
 234 EAPI Eina_Iterator        *eina_rbtree_iterator_infix(const Eina_Rbtree *root) EINA_MALLOC EINA_WARN_UNUSED_RESULT;
 235
 236 /**
 237  * @brief Returned a new prefix iterator associated to a rbtree.
 238  *
 239  * @param root The root of rbtree.
 240  * @return A new iterator.
 241  *
 242  * This function returns a newly allocated iterator associated to @p
 243  * root. It will iterate the tree using postfix walk. If @p root is @c
 244  * NULL, this function still returns a valid iterator that will always
 245  * return false on eina_iterator_next(), thus keeping API sane.
 246  *
 247  * If the memory can not be allocated, @c NULL is returned
 248  * and #EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is
 249  * returned.
 250  *
 251  * @warning if the rbtree structure changes then the iterator becomes
 252  *    invalid! That is, if you add or remove nodes this iterator
 253  *    behavior is undefined and your program may crash!
 254  */
 255 EAPI Eina_Iterator        *eina_rbtree_iterator_postfix(const Eina_Rbtree *root) EINA_MALLOC EINA_WARN_UNUSED_RESULT;
 256
 257 #include "eina_inline_rbtree.x"
 258
 259 /**
 260  * @}
 261  */
 262
 263 /**
 264  * @}
 265  */
 266
 267 /**
 268  * @}
 269  */
 270
 271 #endif