1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/ucx/avl.h Tue Oct 17 16:15:41 2017 +0200
1.3 @@ -0,0 +1,327 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 + *
1.7 + * Copyright 2017 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/ucx.h>
1.49 +#include <ucx/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_strcmp() 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 + * @param tree the tree to destroy
1.142 + */
1.143 +void ucx_avl_free(UcxAVLTree *tree);
1.144 +
1.145 +/**
1.146 + * Macro for initializing a new UcxAVLTree with the default allocator and a
1.147 + * ucx_ptrcmp() compare function.
1.148 + *
1.149 + * @return a new default UcxAVLTree object
1.150 + */
1.151 +#define ucx_avl_default_new() ucx_avl_new_a(ucx_ptrcmp, ucx_default_allocator())
1.152 +
1.153 +/**
1.154 + * Gets the node from the tree, that is associated with the specified key.
1.155 + * @param tree the UcxAVLTree
1.156 + * @param key the key
1.157 + * @return the node (or <code>NULL</code>, if the key is not present)
1.158 + */
1.159 +UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key);
1.160 +
1.161 +/**
1.162 + * Gets the value from the tree, that is associated with the specified key.
1.163 + * @param tree the UcxAVLTree
1.164 + * @param key the key
1.165 + * @return the value (or <code>NULL</code>, if the key is not present)
1.166 + */
1.167 +void *ucx_avl_get(UcxAVLTree *tree, intptr_t key);
1.168 +
1.169 +/**
1.170 + * A mode for #ucx_avl_find_node() with the same behavior as
1.171 + * #ucx_avl_get_node().
1.172 + */
1.173 +#define UCX_AVL_FIND_EXACT 0
1.174 +/**
1.175 + * A mode for #ucx_avl_find_node() finding the node whose key is at least
1.176 + * as large as the specified key.
1.177 + */
1.178 +#define UCX_AVL_FIND_LOWER_BOUNDED 1
1.179 +/**
1.180 + * A mode for #ucx_avl_find_node() finding the node whose key is at most
1.181 + * as large as the specified key.
1.182 + */
1.183 +#define UCX_AVL_FIND_UPPER_BOUNDED 2
1.184 +/**
1.185 + * A mode for #ucx_avl_find_node() finding the node with a key that is as close
1.186 + * to the specified key as possible. If the key is present, the behavior is
1.187 + * like #ucx_avl_get_node(). This mode only returns <code>NULL</code> on
1.188 + * empty trees.
1.189 + */
1.190 +#define UCX_AVL_FIND_CLOSEST 3
1.191 +
1.192 +/**
1.193 + * Finds a node within the tree. The following modes are supported:
1.194 + * <ul>
1.195 + * <li>#UCX_AVL_FIND_EXACT: the same behavior as #ucx_avl_get_node()</li>
1.196 + * <li>#UCX_AVL_FIND_LOWER_BOUNDED: finds the node whose key is at least
1.197 + * as large as the specified key</li>
1.198 + * <li>#UCX_AVL_FIND_UPPER_BOUNDED: finds the node whose key is at most
1.199 + * as large as the specified key</li>
1.200 + * <li>#UCX_AVL_FIND_CLOSEST: finds the node with a key that is as close to
1.201 + * the specified key as possible. If the key is present, the behavior is
1.202 + * like #ucx_avl_get_node(). This mode only returns <code>NULL</code> on
1.203 + * empty trees.</li>
1.204 + * </ul>
1.205 + *
1.206 + * The distance function provided MUST agree with the compare function of
1.207 + * the AVL tree.
1.208 + *
1.209 + * @param tree the UcxAVLTree
1.210 + * @param key the key
1.211 + * @param dfnc the distance function
1.212 + * @param mode the find mode
1.213 + * @return the node (or <code>NULL</code>, if no node can be found)
1.214 + */
1.215 +UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key,
1.216 + distance_func dfnc, int mode);
1.217 +
1.218 +/**
1.219 + * Finds a value within the tree.
1.220 + * See #ucx_avl_find_node() for details.
1.221 + *
1.222 + * @param tree the UcxAVLTree
1.223 + * @param key the key
1.224 + * @param dfnc the distance function
1.225 + * @param mode the find mode
1.226 + * @return the value (or <code>NULL</code>, if no value can be found)
1.227 + */
1.228 +void *ucx_avl_find(UcxAVLTree *tree, intptr_t key,
1.229 + distance_func dfnc, int mode);
1.230 +
1.231 +/**
1.232 + * Puts a key/value pair into the tree.
1.233 + *
1.234 + * Attention: use this function only, if a possible old value does not need
1.235 + * to be preserved.
1.236 + *
1.237 + * @param tree the UcxAVLTree
1.238 + * @param key the key
1.239 + * @param value the new value
1.240 + * @return zero, if and only if the operation succeeded
1.241 + */
1.242 +int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value);
1.243 +
1.244 +/**
1.245 + * Puts a key/value pair into the tree.
1.246 + *
1.247 + * This is a secure function which saves the old value to the variable pointed
1.248 + * at by oldvalue.
1.249 + *
1.250 + * @param tree the UcxAVLTree
1.251 + * @param key the key
1.252 + * @param value the new value
1.253 + * @param oldvalue optional: a pointer to the location where a possible old
1.254 + * value shall be stored
1.255 + * @return zero, if and only if the operation succeeded
1.256 + */
1.257 +int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, void **oldvalue);
1.258 +
1.259 +/**
1.260 + * Removes a node from the AVL tree.
1.261 + *
1.262 + * Note: the specified node is logically removed. The tree implementation
1.263 + * decides which memory area is freed. In most cases the here provided node
1.264 + * is freed, so its further use is generally undefined.
1.265 + *
1.266 + * @param tree the UcxAVLTree
1.267 + * @param node the node to remove
1.268 + * @return zero, if and only if an element has been removed
1.269 + */
1.270 +int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node);
1.271 +
1.272 +/**
1.273 + * Removes an element from the AVL tree.
1.274 + *
1.275 + * @param tree the UcxAVLTree
1.276 + * @param key the key
1.277 + * @return zero, if and only if an element has been removed
1.278 + */
1.279 +int ucx_avl_remove(UcxAVLTree *tree, intptr_t key);
1.280 +
1.281 +/**
1.282 + * Removes an element from the AVL tree.
1.283 + *
1.284 + * This is a secure function which saves the old key and value data from node
1.285 + * to the variables at the location of oldkey and oldvalue (if specified), so
1.286 + * they can be freed afterwards (if necessary).
1.287 + *
1.288 + * Note: the returned key in oldkey is possibly not the same as the provided
1.289 + * key for the lookup (in terms of memory location).
1.290 + *
1.291 + * @param tree the UcxAVLTree
1.292 + * @param key the key of the element to remove
1.293 + * @param oldkey optional: a pointer to the location where the old key shall be
1.294 + * stored
1.295 + * @param oldvalue optional: a pointer to the location where the old value
1.296 + * shall be stored
1.297 + * @return zero, if and only if an element has been removed
1.298 + */
1.299 +int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key,
1.300 + intptr_t *oldkey, void **oldvalue);
1.301 +
1.302 +/**
1.303 + * Counts the nodes in the specified UcxAVLTree.
1.304 + * @param tree the AVL tree
1.305 + * @return the node count
1.306 + */
1.307 +size_t ucx_avl_count(UcxAVLTree *tree);
1.308 +
1.309 +/**
1.310 + * Finds the in-order predecessor of the given node.
1.311 + * @param node an AVL node
1.312 + * @return the in-order predecessor of the given node, or <code>NULL</code> if
1.313 + * the given node is the in-order minimum
1.314 + */
1.315 +UcxAVLNode* ucx_avl_pred(UcxAVLNode* node);
1.316 +
1.317 +/**
1.318 + * Finds the in-order successor of the given node.
1.319 + * @param node an AVL node
1.320 + * @return the in-order successor of the given node, or <code>NULL</code> if
1.321 + * the given node is the in-order maximum
1.322 + */
1.323 +UcxAVLNode* ucx_avl_succ(UcxAVLNode* node);
1.324 +
1.325 +#ifdef __cplusplus
1.326 +}
1.327 +#endif
1.328 +
1.329 +#endif /* UCX_AVL_H */
1.330 +
