ucx/ucx/avl.h

   1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
   3  *
   4  * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are met:
   8  *
   9  *   1. Redistributions of source code must retain the above copyright
  10  *      notice, this list of conditions and the following disclaimer.
  11  *
  12  *   2. Redistributions in binary form must reproduce the above copyright
  13  *      notice, this list of conditions and the following disclaimer in the
  14  *      documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  26  * POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29
  30 /**
  31  * @file avl.h
  32  *
  33  * AVL tree implementation.
  34  *
  35  * This binary search tree implementation allows average O(1) insertion and
  36  * removal of elements (excluding binary search time).
  37  *
  38  * @author Mike Becker
  39  * @author Olaf Wintermann
  40  */
  41
  42 #ifndef UCX_AVL_H
  43 #define UCX_AVL_H
  44
  45 #include "ucx.h"
  46 #include "allocator.h"
  47 #include <inttypes.h>
  48
  49 #ifdef  __cplusplus
  50 extern "C" {
  51 #endif
  52
  53 /**
  54  * UCX AVL Node type.
  55  *
  56  * @see UcxAVLNode
  57  */
  58 typedef struct UcxAVLNode UcxAVLNode;
  59
  60 /**
  61  * UCX AVL Node.
  62  */
  63 struct UcxAVLNode {
  64     /**
  65      * The key for this node.
  66      */
  67     intptr_t key;
  68     /**
  69      * Data contained by this node.
  70      */
  71     void *value;
  72     /**
  73      * The height of this (sub)-tree.
  74      */
  75     size_t height;
  76     /**
  77      * Parent node.
  78      */
  79     UcxAVLNode *parent;
  80     /**
  81      * Root node of left subtree.
  82      */
  83     UcxAVLNode *left;
  84     /**
  85      * Root node of right subtree.
  86      */
  87     UcxAVLNode *right;
  88 };
  89
  90 /**
  91  * UCX AVL Tree.
  92  */
  93 typedef struct {
  94     /**
  95      * The UcxAllocator that shall be used to manage the memory for node data.
  96      */
  97     UcxAllocator *allocator;
  98     /**
  99      * Root node of the tree.
 100      */
 101     UcxAVLNode *root;
 102     /**
 103      * Compare function that shall be used to compare the UcxAVLNode keys.
 104      * @see UcxAVLNode.key
 105      */
 106     cmp_func cmpfunc;
 107     /**
 108      * Custom user data.
 109      * This data will also be provided to the cmpfunc.
 110      */
 111     void *userdata;
 112 } UcxAVLTree;
 113
 114 /**
 115  * Initializes a new UcxAVLTree with a default allocator.
 116  *
 117  * @param cmpfunc the compare function that shall be used
 118  * @return a new UcxAVLTree object
 119  * @see ucx_avl_new_a()
 120  */
 121 UcxAVLTree *ucx_avl_new(cmp_func cmpfunc);
 122
 123 /**
 124  * Initializes a new UcxAVLTree with the specified allocator.
 125  *
 126  * The cmpfunc should be capable of comparing two keys within this AVL tree.
 127  * So if you want to use null terminated strings as keys, you could use the
 128  * ucx_cmp_str() function here.
 129  *
 130  * @param cmpfunc the compare function that shall be used
 131  * @param allocator the UcxAllocator that shall be used
 132  * @return a new UcxAVLTree object
 133  */
 134 UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator);
 135
 136 /**
 137  * Destroys a UcxAVLTree.
 138  *
 139  * Note, that the contents are not automatically freed.
 140  * Use may use #ucx_avl_free_content() before calling this function.
 141  *
 142  * @param tree the tree to destroy
 143  * @see ucx_avl_free_content()
 144  */
 145 void ucx_avl_free(UcxAVLTree *tree);
 146
 147 /**
 148  * Frees the contents of a UcxAVLTree.
 149  *
 150  * This is a convenience function that iterates over the tree and passes all
 151  * values to the specified destructor function.
 152  *
 153  * If no destructor is specified (<code>NULL</code>), the free() function of
 154  * the tree's own allocator is used.
 155  *
 156  * You must ensure, that it is valid to pass each value in the map to the same
 157  * destructor function.
 158  *
 159  * You should free the entire tree afterwards, as the contents will be invalid.
 160  *
 161  * @param tree for which the contents shall be freed
 162  * @param destr optional pointer to a destructor function
 163  * @see ucx_avl_free()
 164  */
 165 void ucx_avl_free_content(UcxAVLTree *tree, ucx_destructor destr);
 166
 167 /**
 168  * Macro for initializing a new UcxAVLTree with the default allocator and a
 169  * ucx_cmp_ptr() compare function.
 170  *
 171  * @return a new default UcxAVLTree object
 172  */
 173 #define ucx_avl_default_new() \
 174     ucx_avl_new_a(ucx_cmp_ptr, ucx_default_allocator())
 175
 176 /**
 177  * Gets the node from the tree, that is associated with the specified key.
 178  * @param tree the UcxAVLTree
 179  * @param key the key
 180  * @return the node (or <code>NULL</code>, if the key is not present)
 181  */
 182 UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key);
 183
 184 /**
 185  * Gets the value from the tree, that is associated with the specified key.
 186  * @param tree the UcxAVLTree
 187  * @param key the key
 188  * @return the value (or <code>NULL</code>, if the key is not present)
 189  */
 190 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key);
 191
 192 /**
 193  * A mode for #ucx_avl_find_node() with the same behavior as
 194  * #ucx_avl_get_node().
 195  */
 196 #define UCX_AVL_FIND_EXACT         0
 197 /**
 198  * A mode for #ucx_avl_find_node() finding the node whose key is at least
 199  * as large as the specified key.
 200  */
 201 #define UCX_AVL_FIND_LOWER_BOUNDED 1
 202 /**
 203  * A mode for #ucx_avl_find_node() finding the node whose key is at most
 204  * as large as the specified key.
 205  */
 206 #define UCX_AVL_FIND_UPPER_BOUNDED 2
 207 /**
 208  * A mode for #ucx_avl_find_node() finding the node with a key that is as close
 209  * to the specified key as possible. If the key is present, the behavior is
 210  * like #ucx_avl_get_node(). This mode only returns <code>NULL</code> on
 211  * empty trees.
 212  */
 213 #define UCX_AVL_FIND_CLOSEST       3
 214
 215 /**
 216  * Finds a node within the tree. The following modes are supported:
 217  * <ul>
 218  * <li>#UCX_AVL_FIND_EXACT: the same behavior as #ucx_avl_get_node()</li>
 219  * <li>#UCX_AVL_FIND_LOWER_BOUNDED: finds the node whose key is at least
 220  * as large as the specified key</li>
 221  * <li>#UCX_AVL_FIND_UPPER_BOUNDED: finds the node whose key is at most
 222  * as large as the specified key</li>
 223  * <li>#UCX_AVL_FIND_CLOSEST: finds the node with a key that is as close to
 224  * the specified key as possible. If the key is present, the behavior is
 225  * like #ucx_avl_get_node(). This mode only returns <code>NULL</code> on
 226  * empty trees.</li>
 227  * </ul>
 228  *
 229  * The distance function provided MUST agree with the compare function of
 230  * the AVL tree.
 231  *
 232  * @param tree the UcxAVLTree
 233  * @param key the key
 234  * @param dfnc the distance function
 235  * @param mode the find mode
 236  * @return the node (or <code>NULL</code>, if no node can be found)
 237  */
 238 UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key,
 239         distance_func dfnc, int mode);
 240
 241 /**
 242  * Finds a value within the tree.
 243  * See #ucx_avl_find_node() for details.
 244  *
 245  * @param tree the UcxAVLTree
 246  * @param key the key
 247  * @param dfnc the distance function
 248  * @param mode the find mode
 249  * @return the value (or <code>NULL</code>, if no value can be found)
 250  */
 251 void *ucx_avl_find(UcxAVLTree *tree, intptr_t key,
 252         distance_func dfnc, int mode);
 253
 254 /**
 255  * Puts a key/value pair into the tree.
 256  *
 257  * Attention: use this function only, if a possible old value does not need
 258  * to be preserved.
 259  *
 260  * @param tree the UcxAVLTree
 261  * @param key the key
 262  * @param value the new value
 263  * @return zero, if and only if the operation succeeded
 264  */
 265 int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value);
 266
 267 /**
 268  * Puts a key/value pair into the tree.
 269  *
 270  * This is a secure function which saves the old value to the variable pointed
 271  * at by oldvalue.
 272  *
 273  * @param tree the UcxAVLTree
 274  * @param key the key
 275  * @param value the new value
 276  * @param oldvalue optional: a pointer to the location where a possible old
 277  * value shall be stored
 278  * @return zero, if and only if the operation succeeded
 279  */
 280 int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, void **oldvalue);
 281
 282 /**
 283  * Removes a node from the AVL tree.
 284  *
 285  * Note: the specified node is logically removed. The tree implementation
 286  * decides which memory area is freed. In most cases the here provided node
 287  * is freed, so its further use is generally undefined.
 288  *
 289  * @param tree the UcxAVLTree
 290  * @param node the node to remove
 291  * @return zero, if and only if an element has been removed
 292  */
 293 int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node);
 294
 295 /**
 296  * Removes an element from the AVL tree.
 297  *
 298  * @param tree the UcxAVLTree
 299  * @param key the key
 300  * @return zero, if and only if an element has been removed
 301  */
 302 int ucx_avl_remove(UcxAVLTree *tree, intptr_t key);
 303
 304 /**
 305  * Removes an element from the AVL tree.
 306  *
 307  * This is a secure function which saves the old key and value data from node
 308  * to the variables at the location of oldkey and oldvalue (if specified), so
 309  * they can be freed afterwards (if necessary).
 310  *
 311  * Note: the returned key in oldkey is possibly not the same as the provided
 312  * key for the lookup (in terms of memory location).
 313  *
 314  * @param tree the UcxAVLTree
 315  * @param key the key of the element to remove
 316  * @param oldkey optional: a pointer to the location where the old key shall be
 317  * stored
 318  * @param oldvalue optional: a pointer to the location where the old value
 319  * shall be stored
 320  * @return zero, if and only if an element has been removed
 321  */
 322 int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key,
 323         intptr_t *oldkey, void **oldvalue);
 324
 325 /**
 326  * Counts the nodes in the specified UcxAVLTree.
 327  * @param tree the AVL tree
 328  * @return the node count
 329  */
 330 size_t ucx_avl_count(UcxAVLTree *tree);
 331
 332 /**
 333  * Finds the in-order predecessor of the given node.
 334  * @param node an AVL node
 335  * @return the in-order predecessor of the given node, or <code>NULL</code> if
 336  * the given node is the in-order minimum
 337  */
 338 UcxAVLNode* ucx_avl_pred(UcxAVLNode* node);
 339
 340 /**
 341  * Finds the in-order successor of the given node.
 342  * @param node an AVL node
 343  * @return the in-order successor of the given node, or <code>NULL</code> if
 344  * the given node is the in-order maximum
 345  */
 346 UcxAVLNode* ucx_avl_succ(UcxAVLNode* node);
 347
 348 #ifdef  __cplusplus
 349 }
 350 #endif
 351
 352 #endif  /* UCX_AVL_H */
 353