universe@192: /* universe@192: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. universe@192: * universe@192: * Copyright 2015 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@192: * removal of elements. 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@193: #include "ucx.h" universe@194: #include "allocator.h" universe@194: #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@194: * ucx_strcmp() 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@196: * Destroys an UcxAVLTree. universe@196: * @param tree the tree to destroy universe@196: */ universe@196: void ucx_avl_free(UcxAVLTree *tree); universe@196: universe@196: /** universe@194: * Macro for initializing a new UcxAVLTree with the default allocator and a universe@194: * ucx_ptrcmp() compare function. universe@194: * universe@194: * @return a new default UcxAVLTree object universe@194: */ universe@194: #define ucx_avl_default_new() ucx_avl_new_a(ucx_ptrcmp, ucx_default_allocator()) universe@194: universe@194: /** 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@193: * Puts a key/value pair into the tree. universe@193: * @param tree the UcxAVLTree universe@193: * @param key the key universe@193: * @param value the new value universe@193: * @return the replaced value (or NULL, if the key is new to the universe@193: * tree) universe@193: */ universe@194: void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value); universe@193: universe@193: /** universe@193: * Removes an element from the AVL tree. universe@193: * @param tree the UcxAVLTree universe@193: * @param key the key universe@193: * @return the removed value (or NULL, if the key was not present) universe@193: */ universe@194: void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key); 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@192: #ifdef __cplusplus universe@192: } universe@192: #endif universe@192: universe@192: #endif /* UCX_AVL_H */ universe@192: