universe@192: /* universe@192: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. universe@192: * universe@259: * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved. universe@192: * universe@192: * Redistribution and use in source and binary forms, with or without universe@192: * modification, are permitted provided that the following conditions are met: universe@192: * universe@192: * 1. Redistributions of source code must retain the above copyright universe@192: * notice, this list of conditions and the following disclaimer. universe@192: * universe@192: * 2. Redistributions in binary form must reproduce the above copyright universe@192: * notice, this list of conditions and the following disclaimer in the universe@192: * documentation and/or other materials provided with the distribution. universe@192: * universe@192: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" universe@192: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE universe@192: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE universe@192: * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE universe@192: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR universe@192: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF universe@192: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS universe@192: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN universe@192: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) universe@192: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE universe@192: * POSSIBILITY OF SUCH DAMAGE. universe@192: */ universe@192: universe@192: universe@192: /** universe@192: * @file avl.h universe@192: * universe@192: * AVL tree implementation. universe@192: * universe@192: * This binary search tree implementation allows average O(1) insertion and universe@204: * removal of elements (excluding binary search time). universe@192: * universe@192: * @author Mike Becker universe@192: * @author Olaf Wintermann universe@192: */ universe@192: universe@192: #ifndef UCX_AVL_H universe@194: #define UCX_AVL_H universe@192: universe@259: #include "ucx.h" universe@259: #include "allocator.h" universe@218: #include universe@193: universe@192: #ifdef __cplusplus universe@192: extern "C" { universe@192: #endif universe@192: universe@193: /** universe@193: * UCX AVL Node type. universe@193: * universe@193: * @see UcxAVLNode universe@193: */ universe@193: typedef struct UcxAVLNode UcxAVLNode; universe@193: universe@193: /** universe@193: * UCX AVL Node. universe@193: */ universe@193: struct UcxAVLNode { universe@193: /** universe@193: * The key for this node. universe@193: */ universe@194: intptr_t key; universe@193: /** universe@193: * Data contained by this node. universe@193: */ universe@193: void *value; universe@193: /** universe@193: * The height of this (sub)-tree. universe@193: */ universe@193: size_t height; universe@193: /** universe@193: * Parent node. universe@193: */ universe@193: UcxAVLNode *parent; universe@193: /** universe@193: * Root node of left subtree. universe@193: */ universe@193: UcxAVLNode *left; universe@193: /** universe@193: * Root node of right subtree. universe@193: */ universe@193: UcxAVLNode *right; universe@193: }; universe@193: universe@193: /** universe@193: * UCX AVL Tree. universe@193: */ universe@193: typedef struct { universe@193: /** universe@194: * The UcxAllocator that shall be used to manage the memory for node data. universe@194: */ universe@194: UcxAllocator *allocator; universe@194: /** universe@193: * Root node of the tree. universe@193: */ universe@193: UcxAVLNode *root; universe@193: /** universe@193: * Compare function that shall be used to compare the UcxAVLNode keys. universe@193: * @see UcxAVLNode.key universe@193: */ universe@193: cmp_func cmpfunc; universe@193: /** universe@193: * Custom user data. universe@193: * This data will also be provided to the cmpfunc. universe@193: */ universe@193: void *userdata; universe@193: } UcxAVLTree; universe@193: universe@193: /** universe@194: * Initializes a new UcxAVLTree with a default allocator. universe@194: * universe@194: * @param cmpfunc the compare function that shall be used universe@194: * @return a new UcxAVLTree object universe@194: * @see ucx_avl_new_a() universe@194: */ universe@194: UcxAVLTree *ucx_avl_new(cmp_func cmpfunc); universe@194: universe@194: /** universe@194: * Initializes a new UcxAVLTree with the specified allocator. universe@194: * universe@194: * The cmpfunc should be capable of comparing two keys within this AVL tree. universe@194: * So if you want to use null terminated strings as keys, you could use the universe@308: * ucx_cmp_str() function here. universe@194: * universe@194: * @param cmpfunc the compare function that shall be used universe@194: * @param allocator the UcxAllocator that shall be used universe@194: * @return a new UcxAVLTree object universe@194: */ universe@194: UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator); universe@194: universe@194: /** universe@225: * Destroys a UcxAVLTree. universe@287: * universe@287: * Note, that the contents are not automatically freed. universe@287: * Use may use #ucx_avl_free_content() before calling this function. universe@287: * universe@196: * @param tree the tree to destroy universe@287: * @see ucx_avl_free_content() universe@196: */ universe@196: void ucx_avl_free(UcxAVLTree *tree); universe@196: universe@196: /** universe@287: * Frees the contents of a UcxAVLTree. universe@287: * universe@287: * This is a convenience function that iterates over the tree and passes all universe@287: * values to the specified destructor function. universe@287: * universe@287: * If no destructor is specified (NULL), the free() function of universe@287: * the tree's own allocator is used. universe@287: * universe@287: * You must ensure, that it is valid to pass each value in the map to the same universe@287: * destructor function. universe@287: * universe@287: * You should free the entire tree afterwards, as the contents will be invalid. universe@287: * universe@287: * @param tree for which the contents shall be freed universe@287: * @param destr optional pointer to a destructor function universe@287: * @see ucx_avl_free() universe@287: */ universe@287: void ucx_avl_free_content(UcxAVLTree *tree, ucx_destructor destr); universe@287: universe@287: /** universe@194: * Macro for initializing a new UcxAVLTree with the default allocator and a universe@312: * ucx_cmp_ptr() compare function. universe@194: * universe@194: * @return a new default UcxAVLTree object universe@194: */ universe@312: #define ucx_avl_default_new() \ universe@312: ucx_avl_new_a(ucx_cmp_ptr, ucx_default_allocator()) universe@194: universe@194: /** universe@204: * Gets the node from the tree, that is associated with the specified key. universe@204: * @param tree the UcxAVLTree universe@204: * @param key the key universe@204: * @return the node (or NULL, if the key is not present) universe@204: */ universe@205: UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key); universe@204: universe@204: /** universe@193: * Gets the value from the tree, that is associated with the specified key. universe@193: * @param tree the UcxAVLTree universe@193: * @param key the key universe@193: * @return the value (or NULL, if the key is not present) universe@193: */ universe@194: void *ucx_avl_get(UcxAVLTree *tree, intptr_t key); universe@193: universe@193: /** universe@243: * A mode for #ucx_avl_find_node() with the same behavior as universe@243: * #ucx_avl_get_node(). universe@243: */ universe@243: #define UCX_AVL_FIND_EXACT 0 universe@243: /** universe@243: * A mode for #ucx_avl_find_node() finding the node whose key is at least universe@243: * as large as the specified key. universe@243: */ universe@243: #define UCX_AVL_FIND_LOWER_BOUNDED 1 universe@243: /** universe@243: * A mode for #ucx_avl_find_node() finding the node whose key is at most universe@243: * as large as the specified key. universe@243: */ universe@243: #define UCX_AVL_FIND_UPPER_BOUNDED 2 universe@243: /** universe@243: * A mode for #ucx_avl_find_node() finding the node with a key that is as close universe@243: * to the specified key as possible. If the key is present, the behavior is universe@243: * like #ucx_avl_get_node(). This mode only returns NULL on universe@243: * empty trees. universe@243: */ universe@243: #define UCX_AVL_FIND_CLOSEST 3 universe@243: universe@243: /** universe@243: * Finds a node within the tree. The following modes are supported: universe@243: * universe@243: * universe@243: * The distance function provided MUST agree with the compare function of universe@243: * the AVL tree. universe@243: * universe@243: * @param tree the UcxAVLTree universe@243: * @param key the key universe@243: * @param dfnc the distance function universe@243: * @param mode the find mode universe@243: * @return the node (or NULL, if no node can be found) universe@243: */ universe@243: UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key, universe@243: distance_func dfnc, int mode); universe@243: universe@243: /** universe@243: * Finds a value within the tree. universe@243: * See #ucx_avl_find_node() for details. universe@243: * universe@243: * @param tree the UcxAVLTree universe@243: * @param key the key universe@243: * @param dfnc the distance function universe@243: * @param mode the find mode universe@243: * @return the value (or NULL, if no value can be found) universe@243: */ universe@243: void *ucx_avl_find(UcxAVLTree *tree, intptr_t key, universe@243: distance_func dfnc, int mode); universe@243: universe@243: /** universe@193: * Puts a key/value pair into the tree. universe@204: * universe@204: * Attention: use this function only, if a possible old value does not need universe@204: * to be preserved. universe@204: * universe@193: * @param tree the UcxAVLTree universe@193: * @param key the key universe@193: * @param value the new value universe@204: * @return zero, if and only if the operation succeeded universe@193: */ universe@204: int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value); universe@204: universe@204: /** universe@204: * Puts a key/value pair into the tree. universe@204: * universe@204: * This is a secure function which saves the old value to the variable pointed universe@204: * at by oldvalue. universe@204: * universe@204: * @param tree the UcxAVLTree universe@204: * @param key the key universe@204: * @param value the new value universe@204: * @param oldvalue optional: a pointer to the location where a possible old universe@204: * value shall be stored universe@204: * @return zero, if and only if the operation succeeded universe@204: */ universe@204: int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, void **oldvalue); universe@204: universe@204: /** universe@204: * Removes a node from the AVL tree. universe@204: * universe@204: * Note: the specified node is logically removed. The tree implementation universe@204: * decides which memory area is freed. In most cases the here provided node universe@243: * is freed, so its further use is generally undefined. universe@204: * universe@204: * @param tree the UcxAVLTree universe@204: * @param node the node to remove universe@204: * @return zero, if and only if an element has been removed universe@204: */ universe@205: int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node); universe@193: universe@193: /** universe@193: * Removes an element from the AVL tree. universe@204: * universe@193: * @param tree the UcxAVLTree universe@193: * @param key the key universe@204: * @return zero, if and only if an element has been removed universe@193: */ universe@204: int ucx_avl_remove(UcxAVLTree *tree, intptr_t key); universe@204: universe@204: /** universe@204: * Removes an element from the AVL tree. universe@204: * universe@204: * This is a secure function which saves the old key and value data from node universe@204: * to the variables at the location of oldkey and oldvalue (if specified), so universe@204: * they can be freed afterwards (if necessary). universe@204: * universe@204: * Note: the returned key in oldkey is possibly not the same as the provided universe@204: * key for the lookup (in terms of memory location). universe@204: * universe@204: * @param tree the UcxAVLTree universe@204: * @param key the key of the element to remove universe@204: * @param oldkey optional: a pointer to the location where the old key shall be universe@204: * stored universe@204: * @param oldvalue optional: a pointer to the location where the old value universe@204: * shall be stored universe@204: * @return zero, if and only if an element has been removed universe@204: */ universe@204: int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key, universe@204: intptr_t *oldkey, void **oldvalue); universe@192: universe@199: /** universe@199: * Counts the nodes in the specified UcxAVLTree. universe@199: * @param tree the AVL tree universe@199: * @return the node count universe@199: */ universe@199: size_t ucx_avl_count(UcxAVLTree *tree); universe@192: universe@245: /** universe@245: * Finds the in-order predecessor of the given node. universe@245: * @param node an AVL node universe@245: * @return the in-order predecessor of the given node, or NULL if universe@245: * the given node is the in-order minimum universe@245: */ universe@245: UcxAVLNode* ucx_avl_pred(UcxAVLNode* node); universe@245: universe@245: /** universe@245: * Finds the in-order successor of the given node. universe@245: * @param node an AVL node universe@245: * @return the in-order successor of the given node, or NULL if universe@245: * the given node is the in-order maximum universe@245: */ universe@245: UcxAVLNode* ucx_avl_succ(UcxAVLNode* node); universe@245: universe@192: #ifdef __cplusplus universe@192: } universe@192: #endif universe@192: universe@192: #endif /* UCX_AVL_H */ universe@192: