1.1 --- a/src/ucx/avl.h Mon Dec 30 09:54:10 2019 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,353 +0,0 @@
1.4 -/*
1.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 - *
1.7 - * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
1.8 - *
1.9 - * Redistribution and use in source and binary forms, with or without
1.10 - * modification, are permitted provided that the following conditions are met:
1.11 - *
1.12 - * 1. Redistributions of source code must retain the above copyright
1.13 - * notice, this list of conditions and the following disclaimer.
1.14 - *
1.15 - * 2. Redistributions in binary form must reproduce the above copyright
1.16 - * notice, this list of conditions and the following disclaimer in the
1.17 - * documentation and/or other materials provided with the distribution.
1.18 - *
1.19 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1.20 - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.21 - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.22 - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
1.23 - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
1.24 - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
1.25 - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
1.26 - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
1.27 - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
1.28 - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1.29 - * POSSIBILITY OF SUCH DAMAGE.
1.30 - */
1.31 -
1.32 -
1.33 -/**
1.34 - * @file avl.h
1.35 - *
1.36 - * AVL tree implementation.
1.37 - *
1.38 - * This binary search tree implementation allows average O(1) insertion and
1.39 - * removal of elements (excluding binary search time).
1.40 - *
1.41 - * @author Mike Becker
1.42 - * @author Olaf Wintermann
1.43 - */
1.44 -
1.45 -#ifndef UCX_AVL_H
1.46 -#define UCX_AVL_H
1.47 -
1.48 -#include "ucx.h"
1.49 -#include "allocator.h"
1.50 -#include <inttypes.h>
1.51 -
1.52 -#ifdef __cplusplus
1.53 -extern "C" {
1.54 -#endif
1.55 -
1.56 -/**
1.57 - * UCX AVL Node type.
1.58 - *
1.59 - * @see UcxAVLNode
1.60 - */
1.61 -typedef struct UcxAVLNode UcxAVLNode;
1.62 -
1.63 -/**
1.64 - * UCX AVL Node.
1.65 - */
1.66 -struct UcxAVLNode {
1.67 - /**
1.68 - * The key for this node.
1.69 - */
1.70 - intptr_t key;
1.71 - /**
1.72 - * Data contained by this node.
1.73 - */
1.74 - void *value;
1.75 - /**
1.76 - * The height of this (sub)-tree.
1.77 - */
1.78 - size_t height;
1.79 - /**
1.80 - * Parent node.
1.81 - */
1.82 - UcxAVLNode *parent;
1.83 - /**
1.84 - * Root node of left subtree.
1.85 - */
1.86 - UcxAVLNode *left;
1.87 - /**
1.88 - * Root node of right subtree.
1.89 - */
1.90 - UcxAVLNode *right;
1.91 -};
1.92 -
1.93 -/**
1.94 - * UCX AVL Tree.
1.95 - */
1.96 -typedef struct {
1.97 - /**
1.98 - * The UcxAllocator that shall be used to manage the memory for node data.
1.99 - */
1.100 - UcxAllocator *allocator;
1.101 - /**
1.102 - * Root node of the tree.
1.103 - */
1.104 - UcxAVLNode *root;
1.105 - /**
1.106 - * Compare function that shall be used to compare the UcxAVLNode keys.
1.107 - * @see UcxAVLNode.key
1.108 - */
1.109 - cmp_func cmpfunc;
1.110 - /**
1.111 - * Custom user data.
1.112 - * This data will also be provided to the cmpfunc.
1.113 - */
1.114 - void *userdata;
1.115 -} UcxAVLTree;
1.116 -
1.117 -/**
1.118 - * Initializes a new UcxAVLTree with a default allocator.
1.119 - *
1.120 - * @param cmpfunc the compare function that shall be used
1.121 - * @return a new UcxAVLTree object
1.122 - * @see ucx_avl_new_a()
1.123 - */
1.124 -UcxAVLTree *ucx_avl_new(cmp_func cmpfunc);
1.125 -
1.126 -/**
1.127 - * Initializes a new UcxAVLTree with the specified allocator.
1.128 - *
1.129 - * The cmpfunc should be capable of comparing two keys within this AVL tree.
1.130 - * So if you want to use null terminated strings as keys, you could use the
1.131 - * ucx_cmp_str() function here.
1.132 - *
1.133 - * @param cmpfunc the compare function that shall be used
1.134 - * @param allocator the UcxAllocator that shall be used
1.135 - * @return a new UcxAVLTree object
1.136 - */
1.137 -UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator);
1.138 -
1.139 -/**
1.140 - * Destroys a UcxAVLTree.
1.141 - *
1.142 - * Note, that the contents are not automatically freed.
1.143 - * Use may use #ucx_avl_free_content() before calling this function.
1.144 - *
1.145 - * @param tree the tree to destroy
1.146 - * @see ucx_avl_free_content()
1.147 - */
1.148 -void ucx_avl_free(UcxAVLTree *tree);
1.149 -
1.150 -/**
1.151 - * Frees the contents of a UcxAVLTree.
1.152 - *
1.153 - * This is a convenience function that iterates over the tree and passes all
1.154 - * values to the specified destructor function.
1.155 - *
1.156 - * If no destructor is specified (<code>NULL</code>), the free() function of
1.157 - * the tree's own allocator is used.
1.158 - *
1.159 - * You must ensure, that it is valid to pass each value in the map to the same
1.160 - * destructor function.
1.161 - *
1.162 - * You should free the entire tree afterwards, as the contents will be invalid.
1.163 - *
1.164 - * @param tree for which the contents shall be freed
1.165 - * @param destr optional pointer to a destructor function
1.166 - * @see ucx_avl_free()
1.167 - */
1.168 -void ucx_avl_free_content(UcxAVLTree *tree, ucx_destructor destr);
1.169 -
1.170 -/**
1.171 - * Macro for initializing a new UcxAVLTree with the default allocator and a
1.172 - * ucx_cmp_ptr() compare function.
1.173 - *
1.174 - * @return a new default UcxAVLTree object
1.175 - */
1.176 -#define ucx_avl_default_new() \
1.177 - ucx_avl_new_a(ucx_cmp_ptr, ucx_default_allocator())
1.178 -
1.179 -/**
1.180 - * Gets the node from the tree, that is associated with the specified key.
1.181 - * @param tree the UcxAVLTree
1.182 - * @param key the key
1.183 - * @return the node (or <code>NULL</code>, if the key is not present)
1.184 - */
1.185 -UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key);
1.186 -
1.187 -/**
1.188 - * Gets the value from the tree, that is associated with the specified key.
1.189 - * @param tree the UcxAVLTree
1.190 - * @param key the key
1.191 - * @return the value (or <code>NULL</code>, if the key is not present)
1.192 - */
1.193 -void *ucx_avl_get(UcxAVLTree *tree, intptr_t key);
1.194 -
1.195 -/**
1.196 - * A mode for #ucx_avl_find_node() with the same behavior as
1.197 - * #ucx_avl_get_node().
1.198 - */
1.199 -#define UCX_AVL_FIND_EXACT 0
1.200 -/**
1.201 - * A mode for #ucx_avl_find_node() finding the node whose key is at least
1.202 - * as large as the specified key.
1.203 - */
1.204 -#define UCX_AVL_FIND_LOWER_BOUNDED 1
1.205 -/**
1.206 - * A mode for #ucx_avl_find_node() finding the node whose key is at most
1.207 - * as large as the specified key.
1.208 - */
1.209 -#define UCX_AVL_FIND_UPPER_BOUNDED 2
1.210 -/**
1.211 - * A mode for #ucx_avl_find_node() finding the node with a key that is as close
1.212 - * to the specified key as possible. If the key is present, the behavior is
1.213 - * like #ucx_avl_get_node(). This mode only returns <code>NULL</code> on
1.214 - * empty trees.
1.215 - */
1.216 -#define UCX_AVL_FIND_CLOSEST 3
1.217 -
1.218 -/**
1.219 - * Finds a node within the tree. The following modes are supported:
1.220 - * <ul>
1.221 - * <li>#UCX_AVL_FIND_EXACT: the same behavior as #ucx_avl_get_node()</li>
1.222 - * <li>#UCX_AVL_FIND_LOWER_BOUNDED: finds the node whose key is at least
1.223 - * as large as the specified key</li>
1.224 - * <li>#UCX_AVL_FIND_UPPER_BOUNDED: finds the node whose key is at most
1.225 - * as large as the specified key</li>
1.226 - * <li>#UCX_AVL_FIND_CLOSEST: finds the node with a key that is as close to
1.227 - * the specified key as possible. If the key is present, the behavior is
1.228 - * like #ucx_avl_get_node(). This mode only returns <code>NULL</code> on
1.229 - * empty trees.</li>
1.230 - * </ul>
1.231 - *
1.232 - * The distance function provided MUST agree with the compare function of
1.233 - * the AVL tree.
1.234 - *
1.235 - * @param tree the UcxAVLTree
1.236 - * @param key the key
1.237 - * @param dfnc the distance function
1.238 - * @param mode the find mode
1.239 - * @return the node (or <code>NULL</code>, if no node can be found)
1.240 - */
1.241 -UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key,
1.242 - distance_func dfnc, int mode);
1.243 -
1.244 -/**
1.245 - * Finds a value within the tree.
1.246 - * See #ucx_avl_find_node() for details.
1.247 - *
1.248 - * @param tree the UcxAVLTree
1.249 - * @param key the key
1.250 - * @param dfnc the distance function
1.251 - * @param mode the find mode
1.252 - * @return the value (or <code>NULL</code>, if no value can be found)
1.253 - */
1.254 -void *ucx_avl_find(UcxAVLTree *tree, intptr_t key,
1.255 - distance_func dfnc, int mode);
1.256 -
1.257 -/**
1.258 - * Puts a key/value pair into the tree.
1.259 - *
1.260 - * Attention: use this function only, if a possible old value does not need
1.261 - * to be preserved.
1.262 - *
1.263 - * @param tree the UcxAVLTree
1.264 - * @param key the key
1.265 - * @param value the new value
1.266 - * @return zero, if and only if the operation succeeded
1.267 - */
1.268 -int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value);
1.269 -
1.270 -/**
1.271 - * Puts a key/value pair into the tree.
1.272 - *
1.273 - * This is a secure function which saves the old value to the variable pointed
1.274 - * at by oldvalue.
1.275 - *
1.276 - * @param tree the UcxAVLTree
1.277 - * @param key the key
1.278 - * @param value the new value
1.279 - * @param oldvalue optional: a pointer to the location where a possible old
1.280 - * value shall be stored
1.281 - * @return zero, if and only if the operation succeeded
1.282 - */
1.283 -int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, void **oldvalue);
1.284 -
1.285 -/**
1.286 - * Removes a node from the AVL tree.
1.287 - *
1.288 - * Note: the specified node is logically removed. The tree implementation
1.289 - * decides which memory area is freed. In most cases the here provided node
1.290 - * is freed, so its further use is generally undefined.
1.291 - *
1.292 - * @param tree the UcxAVLTree
1.293 - * @param node the node to remove
1.294 - * @return zero, if and only if an element has been removed
1.295 - */
1.296 -int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node);
1.297 -
1.298 -/**
1.299 - * Removes an element from the AVL tree.
1.300 - *
1.301 - * @param tree the UcxAVLTree
1.302 - * @param key the key
1.303 - * @return zero, if and only if an element has been removed
1.304 - */
1.305 -int ucx_avl_remove(UcxAVLTree *tree, intptr_t key);
1.306 -
1.307 -/**
1.308 - * Removes an element from the AVL tree.
1.309 - *
1.310 - * This is a secure function which saves the old key and value data from node
1.311 - * to the variables at the location of oldkey and oldvalue (if specified), so
1.312 - * they can be freed afterwards (if necessary).
1.313 - *
1.314 - * Note: the returned key in oldkey is possibly not the same as the provided
1.315 - * key for the lookup (in terms of memory location).
1.316 - *
1.317 - * @param tree the UcxAVLTree
1.318 - * @param key the key of the element to remove
1.319 - * @param oldkey optional: a pointer to the location where the old key shall be
1.320 - * stored
1.321 - * @param oldvalue optional: a pointer to the location where the old value
1.322 - * shall be stored
1.323 - * @return zero, if and only if an element has been removed
1.324 - */
1.325 -int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key,
1.326 - intptr_t *oldkey, void **oldvalue);
1.327 -
1.328 -/**
1.329 - * Counts the nodes in the specified UcxAVLTree.
1.330 - * @param tree the AVL tree
1.331 - * @return the node count
1.332 - */
1.333 -size_t ucx_avl_count(UcxAVLTree *tree);
1.334 -
1.335 -/**
1.336 - * Finds the in-order predecessor of the given node.
1.337 - * @param node an AVL node
1.338 - * @return the in-order predecessor of the given node, or <code>NULL</code> if
1.339 - * the given node is the in-order minimum
1.340 - */
1.341 -UcxAVLNode* ucx_avl_pred(UcxAVLNode* node);
1.342 -
1.343 -/**
1.344 - * Finds the in-order successor of the given node.
1.345 - * @param node an AVL node
1.346 - * @return the in-order successor of the given node, or <code>NULL</code> if
1.347 - * the given node is the in-order maximum
1.348 - */
1.349 -UcxAVLNode* ucx_avl_succ(UcxAVLNode* node);
1.350 -
1.351 -#ifdef __cplusplus
1.352 -}
1.353 -#endif
1.354 -
1.355 -#endif /* UCX_AVL_H */
1.356 -
