/* $Id: cxtree.c,v 1.8 2006/06/12 09:54:44 rpalsa Exp $ * * This file is part of the ESO C Extension Library * Copyright (C) 2001-2006 European Southern Observatory * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ /* * $Author: rpalsa $ * $Date: 2006/06/12 09:54:44 $ * $Revision: 1.8 $ * $Name: $ */ #ifdef HAVE_CONFIG_H # include #endif #include "cxmemory.h" #include "cxmessages.h" #include "cxtree.h" /** * @defgroup cxtree Balanced Binary Trees * * The module implements a balanced binary tree type, i.e. a container * managing key/value pairs as elements. The container is optimized for * lookup operations. * * @par Synopsis: * @code * #include * @endcode */ /**@{*/ /* * Tree node color, tree node and tree opaque data types */ enum _cx_tnode_color_ { CX_TNODE_RED = 0, CX_TNODE_BLACK }; typedef enum _cx_tnode_color_ cx_tnode_color; struct _cx_tnode_ { struct _cx_tnode_ *left; struct _cx_tnode_ *right; struct _cx_tnode_ *parent; cx_tnode_color color; cxptr key; cxptr value; }; typedef struct _cx_tnode_ cx_tnode; struct _cx_tree_ { cx_tnode *header; cxsize node_count; cx_tree_compare_func key_compare; cx_free_func key_destroy; cx_free_func value_destroy; }; /* * Some macros, mostly defined for readability purposes. */ #define _cx_tnode_left(node) ((node)->left) #define _cx_tnode_right(node) ((node)->right) #define _cx_tnode_parent(node) ((node)->parent) #define _cx_tnode_grandpa(node) ((node)->parent->parent) #define _cx_tnode_color(node) ((node)->color) #define _cx_tnode_key(node) ((node)->key) #define _cx_tnode_value(node) ((node)->value) #define _cx_tree_head(tree) ((tree)->header) #define _cx_tree_root(tree) ((tree)->header->parent) #define _cx_tree_leftmost(tree) ((tree)->header->left) #define _cx_tree_rightmost(tree) ((tree)->header->right) #define _cx_tree_node_count(tree) ((tree)->node_count) #define _cx_tree_key_destroy(tree) ((tree)->key_destroy) #define _cx_tree_value_destroy(tree) ((tree)->value_destroy) #define _cx_tree_compare(tree) ((tree)->key_compare) #define _cx_tree_key_compare(tree, a, b) ((tree)->key_compare((a), (b))) /* * Internal, node related methods */ inline static cx_tnode * _cx_tnode_create(cxcptr key, cxcptr value) { cx_tnode *node = cx_malloc(sizeof(cx_tnode)); _cx_tnode_left(node) = NULL; _cx_tnode_right(node) = NULL; _cx_tnode_parent(node) = NULL; _cx_tnode_key(node) = (cxptr)key; _cx_tnode_value(node) = (cxptr)value; return node; } inline static void _cx_tnode_destroy(cx_tnode *node, cx_free_func key_destroy, cx_free_func value_destroy) { if (node) { if (key_destroy) { key_destroy(_cx_tnode_key(node)); _cx_tnode_key(node) = NULL; } if (value_destroy) { value_destroy(_cx_tnode_value(node)); _cx_tnode_value(node) = NULL; } _cx_tnode_left(node) = NULL; _cx_tnode_right(node) = NULL; _cx_tnode_parent(node) = NULL; cx_free(node); } return; } inline static cx_tnode * _cx_tnode_minimum(const cx_tnode *node) { register cx_tnode *n = (cx_tnode *)node; while (_cx_tnode_left(n) != NULL) n = _cx_tnode_left(n); return n; } inline static cx_tnode * _cx_tnode_maximum(const cx_tnode *node) { register cx_tnode *n = (cx_tnode *)node; while (_cx_tnode_right(n) != NULL) n = _cx_tnode_right(n); return n; } inline static cxptr _cx_tnode_get_key(const cx_tnode *node) { return node->key; } inline static void _cx_tnode_set_key(cx_tnode *node, cxcptr key) { node->key = (cxptr)key; return; } inline static cxptr _cx_tnode_get_value(const cx_tnode *node) { return node->value; } inline static void _cx_tnode_set_value(cx_tnode *node, cxcptr value) { node->value = (cxptr)value; return; } inline static cx_tnode * _cx_tnode_next(const cx_tnode *node) { register cx_tnode *n = (cx_tnode *)node; if (_cx_tnode_right(n) != NULL) { n = _cx_tnode_right(n); while (_cx_tnode_left(n) != NULL) n = _cx_tnode_left(n); } else { cx_tnode *m = _cx_tnode_parent(n); while (n == _cx_tnode_right(m)) { n = m; m = _cx_tnode_parent(m); } if (_cx_tnode_right(n) != m) n = m; } return n; } inline static cx_tnode * _cx_tnode_previous(const cx_tnode *node) { register cx_tnode *n = (cx_tnode *)node; if (_cx_tnode_color(n) == CX_TNODE_RED && _cx_tnode_grandpa(n) == n) n = _cx_tnode_right(n); else if (_cx_tnode_left(n) != NULL) { cx_tnode *m = _cx_tnode_left(n); while (_cx_tnode_right(m) != NULL) m = _cx_tnode_right(m); n = m; } else { cx_tnode *m = _cx_tnode_parent(n); while (n == _cx_tnode_left(m)) { n = m; m = _cx_tnode_parent(m); } n = m; } return n; } /* * Internal, tree related methods */ inline static void _cx_tree_rotate_left(cx_tnode *node, cx_tnode **root) { register cx_tnode *y = _cx_tnode_right(node); _cx_tnode_right(node) = _cx_tnode_left(y); if (_cx_tnode_left(y) != NULL) _cx_tnode_parent(_cx_tnode_left(y)) = node; _cx_tnode_parent(y) = _cx_tnode_parent(node); if (node == *root) *root = y; else if (node == _cx_tnode_left(_cx_tnode_parent(node))) _cx_tnode_left(_cx_tnode_parent(node)) = y; else _cx_tnode_right(_cx_tnode_parent(node)) = y; _cx_tnode_left(y) = node; _cx_tnode_parent(node) = y; return; } inline static void _cx_tree_rotate_right(cx_tnode *node, cx_tnode **root) { register cx_tnode *y = _cx_tnode_left(node); _cx_tnode_left(node) = _cx_tnode_right(y); if (_cx_tnode_right(y) != NULL) _cx_tnode_parent(_cx_tnode_right(y)) = node; _cx_tnode_parent(y) = _cx_tnode_parent(node); if (node == *root) *root = y; else if (node == _cx_tnode_right(_cx_tnode_parent(node))) _cx_tnode_right(_cx_tnode_parent(node)) = y; else _cx_tnode_left(_cx_tnode_parent(node)) = y; _cx_tnode_right(y) = node; _cx_tnode_parent(node) = y; return; } inline static void _cx_tree_rebalance(cx_tnode *node, cx_tnode **root) { _cx_tnode_color(node) = CX_TNODE_RED; while (node != *root && _cx_tnode_color(_cx_tnode_parent(node)) == CX_TNODE_RED) { if (_cx_tnode_parent(node) == _cx_tnode_left(_cx_tnode_grandpa(node))) { cx_tnode *y = _cx_tnode_right(_cx_tnode_grandpa(node)); if (y && _cx_tnode_color(y) == CX_TNODE_RED) { _cx_tnode_color(_cx_tnode_parent(node)) = CX_TNODE_BLACK; _cx_tnode_color(_cx_tnode_grandpa(node)) = CX_TNODE_RED; _cx_tnode_color(y) = CX_TNODE_BLACK; node = _cx_tnode_grandpa(node); } else { if (node == _cx_tnode_right(_cx_tnode_parent(node))) { node = _cx_tnode_parent(node); _cx_tree_rotate_left(node, root); } _cx_tnode_color(_cx_tnode_parent(node)) = CX_TNODE_BLACK; _cx_tnode_color(_cx_tnode_grandpa(node)) = CX_TNODE_RED; _cx_tree_rotate_right(_cx_tnode_grandpa(node), root); } } else { cx_tnode *y = _cx_tnode_left(_cx_tnode_grandpa(node)); if (y && _cx_tnode_color(y) == CX_TNODE_RED) { _cx_tnode_color(_cx_tnode_parent(node)) = CX_TNODE_BLACK; _cx_tnode_color(_cx_tnode_grandpa(node)) = CX_TNODE_RED; _cx_tnode_color(y) = CX_TNODE_BLACK; node = _cx_tnode_grandpa(node); } else { if (node == _cx_tnode_left(_cx_tnode_parent(node))) { node = _cx_tnode_parent(node); _cx_tree_rotate_right(node, root); } _cx_tnode_color(_cx_tnode_parent(node)) = CX_TNODE_BLACK; _cx_tnode_color(_cx_tnode_grandpa(node)) = CX_TNODE_RED; _cx_tree_rotate_left(_cx_tnode_grandpa(node), root); } } } _cx_tnode_color((*root)) = CX_TNODE_BLACK; return; } inline static cx_tnode * _cx_tree_rebalance_for_erase(cx_tnode *node, cx_tnode **root, cx_tnode **leftmost, cx_tnode **rightmost) { cx_tnode *y = node; cx_tnode *x = NULL; cx_tnode *x_parent = NULL; if (_cx_tnode_left(y) == NULL) { /* * node has at most one non-null child. y == node. x might be null. */ x = _cx_tnode_right(y); } else { if (_cx_tnode_right(y) == NULL) { /* * node has exactly one non-null child. y == node. x is not null. */ x = _cx_tnode_left(y); } else { /* * node has 2 non-null children. Set y to node's successor. * x might be null. */ y = _cx_tnode_right(y); while (_cx_tnode_left(y) != NULL) y = _cx_tnode_left(y); x = _cx_tnode_right(y); } } if (y != node) { cx_tnode_color tcolor; /* * relink y in place of node. y is node's successor */ _cx_tnode_parent(_cx_tnode_left(node)) = y; _cx_tnode_left(y) = _cx_tnode_left(node); if (y != _cx_tnode_right(node)) { x_parent = _cx_tnode_parent(y); if (x) _cx_tnode_parent(x) = _cx_tnode_parent(y); _cx_tnode_left(_cx_tnode_parent(y)) = x; _cx_tnode_right(y) = _cx_tnode_right(node); _cx_tnode_parent(_cx_tnode_right(node)) = y; } else x_parent = y; if (*root == node) *root = y; else if (_cx_tnode_left(_cx_tnode_parent(node)) == node) _cx_tnode_left(_cx_tnode_parent(node)) = y; else _cx_tnode_right(_cx_tnode_parent(node)) = y; _cx_tnode_parent(y) = _cx_tnode_parent(node); /* * Swap the colors of y an node. */ tcolor = _cx_tnode_color(node); _cx_tnode_color(node) = _cx_tnode_color(y); _cx_tnode_color(y) = tcolor; /* * Make y point to the node to be actually deleted. */ y = node; } else { /* * y == node */ x_parent = _cx_tnode_parent(y); if (x) _cx_tnode_parent(x) = _cx_tnode_parent(y); if (*root == node) *root = x; else if (_cx_tnode_left(_cx_tnode_parent(node)) == node) _cx_tnode_left(_cx_tnode_parent(node)) = x; else _cx_tnode_right(_cx_tnode_parent(node)) = x; if (*leftmost == node) { if (_cx_tnode_right(node) == NULL) { /* * If node == *root, *leftmost will be the header node. */ *leftmost = _cx_tnode_parent(node); } else *leftmost = _cx_tnode_minimum(x); } if (*rightmost == node) { if (_cx_tnode_left(node) == NULL) { /* * If node == *root, *rightmost will be the header node. */ *rightmost = _cx_tnode_parent(node); } else *rightmost = _cx_tnode_maximum(x); } } if (_cx_tnode_color(y) != CX_TNODE_RED) { while (x != *root && (x == NULL || _cx_tnode_color(x) == CX_TNODE_BLACK)) if (x == _cx_tnode_left(x_parent)) { cx_tnode *w = _cx_tnode_right(x_parent); if (_cx_tnode_color(w) == CX_TNODE_RED) { _cx_tnode_color(w) = CX_TNODE_BLACK; _cx_tnode_color(x_parent) = CX_TNODE_RED; _cx_tree_rotate_left(x_parent, root); w = _cx_tnode_right(x_parent); } if ((_cx_tnode_left(w) == NULL || _cx_tnode_color(_cx_tnode_left(w)) == CX_TNODE_BLACK) && (_cx_tnode_right(w) == NULL || _cx_tnode_color(_cx_tnode_right(w)) == CX_TNODE_BLACK)) { _cx_tnode_color(w) = CX_TNODE_RED; x = x_parent; x_parent = _cx_tnode_parent(x_parent); } else { if (_cx_tnode_right(w) == NULL || _cx_tnode_color(_cx_tnode_right(w)) == CX_TNODE_BLACK) { if (_cx_tnode_left(w)) { cx_tnode *v = _cx_tnode_left(w); _cx_tnode_color(v) = CX_TNODE_BLACK; } _cx_tnode_color(w) = CX_TNODE_RED; _cx_tree_rotate_right(w, root); w = _cx_tnode_right(x_parent); } _cx_tnode_color(w) = _cx_tnode_color(x_parent); _cx_tnode_color(x_parent) = CX_TNODE_BLACK; if (_cx_tnode_right(w)) _cx_tnode_color(_cx_tnode_right(w)) = CX_TNODE_BLACK; _cx_tree_rotate_left(x_parent, root); break; } } else { /* * Same as above with left and right exchanged. */ cx_tnode *w = _cx_tnode_left(x_parent); if (_cx_tnode_color(w) == CX_TNODE_RED) { _cx_tnode_color(w) = CX_TNODE_BLACK; _cx_tnode_color(x_parent) = CX_TNODE_RED; _cx_tree_rotate_right(x_parent, root); w = _cx_tnode_left(x_parent); } if ((_cx_tnode_right(w) == NULL || _cx_tnode_color(_cx_tnode_right(w)) == CX_TNODE_BLACK) && (_cx_tnode_left(w) == NULL || _cx_tnode_color(_cx_tnode_left(w)) == CX_TNODE_BLACK)) { _cx_tnode_color(w) = CX_TNODE_RED; x = x_parent; x_parent = _cx_tnode_parent(x_parent); } else { if (_cx_tnode_left(w) == NULL || _cx_tnode_color(_cx_tnode_left(w)) == CX_TNODE_BLACK) { if (_cx_tnode_right(w)) { cx_tnode *v = _cx_tnode_right(w); _cx_tnode_color(v) = CX_TNODE_BLACK; } _cx_tnode_color(w) = CX_TNODE_RED; _cx_tree_rotate_left(w, root); w = _cx_tnode_left(x_parent); } _cx_tnode_color(w) = _cx_tnode_color(x_parent); _cx_tnode_color(x_parent) = CX_TNODE_BLACK; if (_cx_tnode_left(w)) _cx_tnode_color(_cx_tnode_left(w)) = CX_TNODE_BLACK; _cx_tree_rotate_right(x_parent, root); break; } } if (x) _cx_tnode_color(x) = CX_TNODE_BLACK; } return y; } /* * Convenience function used in cx_tree_verify() */ inline static cxsize _cx_tree_black_count(cx_tnode *node, cx_tnode *root) { cxsize sum = 0; if (node == NULL) return 0; do { if (_cx_tnode_color(node) == CX_TNODE_BLACK) ++sum; if (node == root) break; node = _cx_tnode_parent(node); } while (1); return sum; } /* * Initialize a tree to a valid empty tree. */ inline static void _cx_tree_initialize(cx_tree *tree, cx_tree_compare_func compare, cx_free_func key_destroy, cx_free_func value_destroy) { /* * Used to distinguish header from root in the next operator. * Check this!! */ _cx_tnode_color(_cx_tree_head(tree)) = CX_TNODE_RED; _cx_tree_root(tree) = NULL; _cx_tree_leftmost(tree) = _cx_tree_head(tree); _cx_tree_rightmost(tree) = _cx_tree_head(tree); _cx_tree_node_count(tree) = 0; _cx_tree_compare(tree) = compare; _cx_tree_key_destroy(tree) = key_destroy; _cx_tree_value_destroy(tree) = value_destroy; return; } /* * Inserting elements */ inline static cx_tnode * _cx_tree_insert(cx_tree *tree, cx_tnode *x, cx_tnode *y, cxcptr key, cxcptr value) { cx_tnode *z; if (y == _cx_tree_head(tree) || x != NULL || _cx_tree_key_compare(tree, key, _cx_tnode_key(y))) { z = _cx_tnode_create(key, value); /* * This also makes _cx_tree_leftmost(tree) = z, if * y == _cx_tree_head(tree). */ _cx_tnode_left(y) = z; if (y == _cx_tree_head(tree)) { _cx_tree_root(tree) = z; _cx_tree_rightmost(tree) = z; } else { if (y == _cx_tree_leftmost(tree)) { /* * Maintain _cx_tree_leftmost(tree) pointing to the * minimum node. */ _cx_tree_leftmost(tree) = z; } } } else { z = _cx_tnode_create(key, value); _cx_tnode_right(y) = z; if (y == _cx_tree_rightmost(tree)) { /* * Maintain _cx_tree_rightmost(tree) pointing to the * maximum node. */ _cx_tree_rightmost(tree) = z; } } _cx_tnode_parent(z) = y; _cx_tnode_left(z) = NULL; _cx_tnode_right(z) = NULL; _cx_tree_rebalance(z, &_cx_tree_root(tree)); ++_cx_tree_node_count(tree); return z; } inline static cx_tnode * _cx_tree_insert_equal(cx_tree *tree, cxcptr key, cxcptr value) { cx_tnode *x = _cx_tree_root(tree); cx_tnode *y = _cx_tree_head(tree); while (x != NULL) { cxbool result; y = x; result = _cx_tree_key_compare(tree, key, _cx_tnode_key(x)); x = result ? _cx_tnode_left(x) : _cx_tnode_right(x); } return _cx_tree_insert(tree, x, y, key, value); } inline static cx_tnode * _cx_tree_insert_unique(cx_tree *tree, cxcptr key, cxcptr value) { cx_tnode *x = _cx_tree_root(tree); cx_tnode *y = _cx_tree_head(tree); cx_tnode *pos; cxbool result = TRUE; while (x != NULL) { y = x; result = _cx_tree_key_compare(tree, key, _cx_tnode_key(x)); x = result ? _cx_tnode_left(x) : _cx_tnode_right(x); } pos = y; if (result) { if (pos == _cx_tree_leftmost(tree)) return _cx_tree_insert(tree, x, y, key, value); else pos = _cx_tnode_previous(pos); } if (_cx_tree_key_compare(tree, _cx_tnode_key(pos), key)) return _cx_tree_insert(tree, x, y, key, value); return NULL; } /* * Element removal */ /* * Recursive erase without rebalancing */ inline static void _cx_tree_erase_all(cx_tree *tree, cx_tnode *x) { while (x != NULL) { cx_tnode *y; _cx_tree_erase_all(tree, _cx_tnode_right(x)); y = _cx_tnode_left(x); _cx_tnode_destroy(x, _cx_tree_key_destroy(tree), _cx_tree_value_destroy(tree)); --_cx_tree_node_count(tree); x = y; } return; } inline static void _cx_tree_erase(cx_tree *tree, cx_tnode *x) { cx_tnode *y = _cx_tree_rebalance_for_erase(x, &_cx_tree_root(tree), &_cx_tree_leftmost(tree), &_cx_tree_rightmost(tree)); _cx_tnode_destroy(y, _cx_tree_key_destroy(tree), _cx_tree_value_destroy(tree)); --_cx_tree_node_count(tree); return; } inline static void _cx_tree_clear(cx_tree *tree) { cx_assert(tree != NULL); if (_cx_tree_node_count(tree) != 0) { _cx_tree_erase_all(tree, _cx_tree_root(tree)); _cx_tree_root(tree) = NULL; _cx_tree_leftmost(tree) = _cx_tree_head(tree); _cx_tree_rightmost(tree) = _cx_tree_head(tree); cx_assert(_cx_tree_node_count(tree) == 0); } return; } /* * Iteration */ inline static cx_tree_iterator _cx_tree_begin(const cx_tree *tree) { return _cx_tree_leftmost(tree); } inline static cx_tree_iterator _cx_tree_end(const cx_tree *tree) { return _cx_tree_head(tree); } /* * Basic search */ inline static cx_tnode * _cx_tree_lower_bound(const cx_tree *tree, cxcptr key) { cx_tnode *x = _cx_tree_root(tree); /* Last node not less than key */ cx_tnode *y = _cx_tree_head(tree); /* Current node */ while (x != NULL) { if (!_cx_tree_key_compare(tree, _cx_tnode_key(x), key)) { y = x; x = _cx_tnode_left(x); } else x = _cx_tnode_right(x); } return y; } inline static cx_tnode * _cx_tree_upper_bound(const cx_tree *tree, cxcptr key) { cx_tnode *x = _cx_tree_root(tree); /* Last node greater than key */ cx_tnode *y = _cx_tree_head(tree); /* Current node */ while (x != NULL) { if (_cx_tree_key_compare(tree, key, _cx_tnode_key(x))) { y = x; x = _cx_tnode_left(x); } else x = _cx_tnode_right(x); } return y; } inline static cx_tnode * _cx_tree_find(const cx_tree *tree, cxcptr key) { cx_tnode *x = _cx_tree_root(tree); cx_tnode *y = _cx_tree_head(tree); cx_tnode *pos; while (x != NULL) { if (!_cx_tree_key_compare(tree, _cx_tnode_key(x), key)) { y = x; x = _cx_tnode_left(x); } else x = _cx_tnode_right(x); } pos = y; if (pos == _cx_tree_head(tree) || _cx_tree_key_compare(tree, key, _cx_tnode_key(pos))) return _cx_tree_head(tree); return pos; } inline static cxbool _cx_tree_exists(const cx_tree *tree, cx_tnode *x) { cx_tnode *y; cxptr key = _cx_tnode_key(x); y = _cx_tree_lower_bound(tree, key); if (y != x) { cx_tnode *z = _cx_tree_upper_bound(tree, key); y = _cx_tnode_next(y); while (y != x && y != z) y = _cx_tnode_next(y); } return x == y ? TRUE : FALSE; } /* * Public methods */ /** * @brief * Get an iterator to the first pair in the tree. * * @param tree The tree to query. * * @return Iterator for the first pair or @b cx_tree_end() if the tree is * empty. * * The function returns a handle for the first pair in the tree @em tree. * The returned iterator cannot be used directly to access the value field * of the key/value pair, but only through the appropriate methods. */ cx_tree_iterator cx_tree_begin(const cx_tree *tree) { cx_assert(tree != NULL); return _cx_tree_begin(tree); } /** * @brief * Get an iterator for the position after the last pair in the tree. * * @param tree The tree to query. * * @return Iterator for the end of the tree. * * The function returns an iterator for the position one past the last pair * in the tree @em tree. The iteration is done in ascending order according * to the keys. The returned iterator cannot be used directly to access the * value field of the key/value pair, but only through the appropriate * methods. */ cx_tree_iterator cx_tree_end(const cx_tree *tree) { cx_assert(tree != NULL); return _cx_tree_end(tree); } /** * @brief * Get an iterator for the next pair in the tree. * * @param tree A tree. * @param position Current iterator position. * * @return Iterator for the pair immediately following @em position. * * The function returns an iterator for the next pair in the tree @em tree * with respect to the current iterator position @em position. Iteration * is done in ascending order according to the keys. If the tree is empty * or @em position points to the end of the tree the function returns * @b cx_tree_end(). */ cx_tree_iterator cx_tree_next(const cx_tree *tree, cx_tree_const_iterator position) { cx_assert(tree != NULL); cx_assert(position != NULL); cx_assert(position == _cx_tree_end(tree) || _cx_tree_exists(tree, (cx_tree_iterator)position)); if (position == _cx_tree_end(tree)) { return _cx_tree_end(tree); } return _cx_tnode_next(position); } /** * @brief * Get an iterator for the previous pair in the tree. * * @param tree A tree. * @param position Current iterator position. * * @return Iterator for the pair immediately preceding @em position. * * The function returns an iterator for the previous pair in the tree * @em tree with respect to the current iterator position @em position. * Iteration is done in ascending order according to the keys. If the * tree is empty or @em position points to the beginning of the tree the * function returns @b cx_tree_end(). */ cx_tree_iterator cx_tree_previous(const cx_tree *tree, cx_tree_const_iterator position) { cx_assert(tree != NULL); cx_assert(position != NULL); cx_assert(position == _cx_tree_end(tree) || _cx_tree_exists(tree, (cx_tree_iterator)position)); if (position == _cx_tree_begin(tree)) { return _cx_tree_begin(tree); } return _cx_tnode_previous(position); } /** * @brief * Remove all pairs from a tree. * * @param tree Tree to be cleared. * * @return Nothing. * * The tree @em tree is cleared, i.e. all pairs are removed from the tree. * Keys and values are destroyed using the key and value destructors set up * during tree creation. After calling this function the tree is empty. */ void cx_tree_clear(cx_tree *tree) { cx_assert(tree != NULL); _cx_tree_clear(tree); return; } /** * @brief * Check whether a tree is empty. * * @param tree A tree. * * @return The function returns @c TRUE if the tree is empty, and @c FALSE * otherwise. * * The function checks if the tree contains any pairs. Calling this function * is equivalent to the statement: * @code * return (cx_tree_size(tree) == 0); * @endcode */ cxbool cx_tree_empty(const cx_tree *tree) { return (_cx_tree_node_count(tree) == 0); } /** * @brief * Create a new tree without any elements. * * @param compare Function used to compare keys. * @param key_destroy Destructor for the keys. * @param value_destroy Destructor for the value field. * * @return Handle for the newly allocated tree. * * Memory for a new tree is allocated and the tree is initialized to be a * valid empty tree. * * The tree's key comparison function is set to @em compare. It must * return @c TRUE or @c FALSE if the comparison of the first argument * passed to it with the second argument is found to be true or false * respectively. * * The destructors for a tree node's key and value field are set to * @em key_destroy and @em value_destroy. Whenever a tree node is * destroyed these functions are used to deallocate the memory used * by the key and the value. Each of the destructors might be @c NULL, i.e. * keys and values are not deallocated during destroy operations. * * @see cx_tree_compare_func() */ cx_tree * cx_tree_new(cx_tree_compare_func compare, cx_free_func key_destroy, cx_free_func value_destroy) { cx_tree *tree; cx_assert(compare != NULL); tree = cx_malloc(sizeof *tree); _cx_tree_head(tree) = cx_malloc(sizeof(cx_tnode)); _cx_tree_initialize(tree, compare, key_destroy, value_destroy); return tree; } /** * @brief * Destroy a tree and all its elements. * * @param tree The tree to destroy. * * @return Nothing. * * The tree @em tree is deallocated. All data values and keys are * deallocated using the tree's key and value destructor. If no * key and/or value destructor was set when the @em tree was created * the keys and the stored data values are left untouched. In this * case the key and value deallocation is the responsibility of the * user. * * @see cx_tree_new() */ void cx_tree_delete(cx_tree *tree) { if (tree) { _cx_tree_clear(tree); cx_free(_cx_tree_head(tree)); cx_free(tree); } return; } /** * @brief * Get the actual number of pairs in the tree. * * @param tree A tree. * * @return The current number of pairs, or 0 if the tree is empty. * * Retrieves the current number of pairs stored in the tree. */ cxsize cx_tree_size(const cx_tree *tree) { cx_assert(tree != NULL); return _cx_tree_node_count(tree); } /** * @brief * Get the maximum number of pairs possible. * * @param tree A tree. * * @return The maximum number of pairs that can be stored in the tree. * * Retrieves the tree's capacity, i.e. the maximum possible number of * pairs a tree can manage. */ cxsize cx_tree_max_size(const cx_tree *tree) { cx_assert(tree != NULL); return (cxsize)(-1); } /** * @brief * Get the key comparison function. * * @param tree The tree to query. * * @return Handle for the tree's key comparison function. * * The function retrieves the function used by the tree methods * for comparing keys. The key comparison function is set during * tree creation. * * @see cx_tree_new() */ cx_tree_compare_func cx_tree_key_comp(const cx_tree *tree) { cx_assert(tree != NULL); return _cx_tree_compare(tree); } /** * @brief * Swap the contents of two trees. * * @param tree1 First tree. * @param tree2 Second tree. * * @return Nothing. * * All pairs stored in the first tree @em tree1 are moved to the second tree * @em tree2, while the pairs from @em tree2 are moved to @em tree1. Also * the key comparison function, the key and the value destructor are * exchanged. */ void cx_tree_swap(cx_tree *tree1, cx_tree *tree2) { cx_tnode *tmp; cxsize sz; cx_tree_compare_func cmp; cx_free_func destroy; cx_assert(tree1 != NULL); cx_assert(tree2 != NULL); tmp = _cx_tree_head(tree2); _cx_tree_head(tree2) = _cx_tree_head(tree1); _cx_tree_head(tree1) = tmp; sz = _cx_tree_node_count(tree2); _cx_tree_node_count(tree2) = _cx_tree_node_count(tree1); _cx_tree_node_count(tree1) = sz; cmp = _cx_tree_compare(tree2); _cx_tree_compare(tree2) = _cx_tree_compare(tree1); _cx_tree_compare(tree1) = cmp; destroy = _cx_tree_key_destroy(tree2); _cx_tree_key_destroy(tree2) = _cx_tree_key_destroy(tree1); _cx_tree_key_destroy(tree1) = destroy; destroy = _cx_tree_value_destroy(tree2); _cx_tree_value_destroy(tree2) = _cx_tree_value_destroy(tree1); _cx_tree_value_destroy(tree1) = destroy; return; } /** * @brief * Assign data to an iterator position. * * @param tree A tree. * @param position Iterator positions where the data will be stored. * @param data Data to store. * * @return Handle to the previously stored data object. * * The function assigns a data object reference @em data to the iterator * position @em position of the tree @em tree. */ cxptr cx_tree_assign(cx_tree *tree, cx_tree_iterator position, cxcptr data) { cxptr tmp; cx_assert(tree != NULL); cx_assert(position != NULL); cx_assert(_cx_tree_exists(tree, position)); tmp = _cx_tnode_get_value(position); _cx_tnode_set_value(position, data); return tmp; } /** * @brief * Get the key from a given iterator position. * * @param tree A tree. * @param position Iterator position the data is retrieved from. * * @return Reference for the key. * * The function returns a reference to the key associated with the iterator * position @em position in the tree @em tree. * * @note * One must not modify the key of @em position through the returned * reference, since this might corrupt the tree! */ cxptr cx_tree_get_key(const cx_tree *tree, cx_tree_const_iterator position) { cx_assert(tree != NULL); cx_assert(position != NULL); cx_assert(_cx_tree_exists(tree, (cx_tree_iterator)position)); return _cx_tnode_get_key(position); } /** * @brief * Get the data from a given iterator position. * * @param tree A tree. * @param position Iterator position the data is retrieved from. * * @return Handle for the data object. * * The function returns a reference to the data stored at iterator position * @em position in the tree @em tree. */ cxptr cx_tree_get_value(const cx_tree *tree, cx_tree_const_iterator position) { cx_assert(tree != NULL); cx_assert(position != NULL); cx_assert(_cx_tree_exists(tree, (cx_tree_iterator)position)); return _cx_tnode_get_value(position); } /** * @brief * Locate an element in the tree. * * @param tree A tree. * @param key Key of the (key, value) pair to locate. * * @return Iterator pointing to the sought-after element, or @b cx_tree_end() * if it was not found. * * The function searches the tree @em tree for an element with a key * matching @em key. If the search was successful an iterator to the * sought-after pair is returned. If the search did not succeed, i.e. * @em key is not present in the tree, a one past the end iterator is * returned. */ cx_tree_iterator cx_tree_find(const cx_tree *tree, cxcptr key) { cx_assert(tree != NULL); cx_assert(key != NULL); return _cx_tree_find(tree, key); } /** * @brief * Find the beginning of a subsequence. * * @param tree A tree. * @param key Key of the (key, value) pair(s) to locate. * * @return Iterator pointing to the first position where an element with * key @em key would get inserted, i.e. the first element with a key greater * or equal than @em key. * * The function returns the first element of a subsequence of elements in the * tree that match the given key @em key. If @em key is not present in the * tree @em tree an iterator pointing to the first element that has a greater * key than @em key or @b cx_tree_end() if no such element exists. */ cx_tree_iterator cx_tree_lower_bound(const cx_tree *tree, cxcptr key) { cx_assert(tree != NULL); cx_assert(key != NULL); return _cx_tree_lower_bound(tree, key); } /** * @brief * Find the end of a subsequence. * * @param tree A tree. * @param key Key of the (key, value) pair(s) to locate. * * @return Iterator pointing to the last position where an element with * key @em key would get inserted, i.e. the first element with a key * greater than @em key. * * The function returns the last element of a subsequence of elements in the * tree that match the given key @em key. If @em key is not present in the * tree @em tree an iterator pointing to the first element that has a greater * key than @em key or @b cx_tree_end() if no such element exists. */ cx_tree_iterator cx_tree_upper_bound(const cx_tree *tree, cxcptr key) { cx_assert(tree != NULL); cx_assert(key != NULL); return _cx_tree_upper_bound(tree, key); } /** * @brief * Find a subsequence matching a given key. * * @param tree A tree. * @param key The key of the (key, value) pair(s) to be located. * @param begin First element with key @em key. * @param end Last element with key @em key. * * @return Nothing. * * The function returns the beginning and the end of a subsequence of * tree elements with the key @em key through through the @em begin and * @em end arguments. After calling this function @em begin possibly points * to the first element of @em tree matching the key @em key and @em end * possibly points to the last element of the sequence. If key is not * present in the tree @em begin points to the next greater element or, * if no such element exists, to @b cx_tree_end(). */ void cx_tree_equal_range(const cx_tree *tree, cxcptr key, cx_tree_iterator *begin, cx_tree_iterator *end) { cx_assert(tree != NULL); cx_assert(key != NULL); *begin = _cx_tree_lower_bound(tree, key); *end = _cx_tree_upper_bound(tree, key); return; } /** * @brief * Get the number of elements matching a key. * * @param tree A tree. * @param key Key of the (key, value) pair(s) to locate. * * @return The number of elements with the specified key. * * Counts all elements of the tree @em tree matching the key @em key. */ cxsize cx_tree_count(const cx_tree *tree, cxcptr key) { cx_tnode *x, *y; cxsize count = 0; cx_assert(tree != NULL); cx_assert(key != NULL); x = _cx_tree_lower_bound(tree, key); y = _cx_tree_upper_bound(tree, key); /* * Only if key is not present in the tree x and y are identical, * pointing to the element with the next greater key. */ while (x != y) { ++count; x = _cx_tnode_next(x); } return count; } /** * @brief * Attempt to insert data into a tree. * * @param tree A tree. * @param key Key used to store the data. * @param data Data to insert. * * @return An iterator that points to the inserted pair, or @c NULL if the * pair could not be inserted. * * This function attempts to insert a (key, value) pair into the tree * @em tree. The insertion fails if the key already present in the tree, * i.e. if the key is not unique. */ cx_tree_iterator cx_tree_insert_unique(cx_tree *tree, cxcptr key, cxcptr data) { cx_assert(tree != NULL); cx_assert(key != NULL); return _cx_tree_insert_unique(tree, key, data); } /** * @brief * Insert data into a tree. * * @param tree A tree. * @param key Key used to store the data. * @param data Data to insert. * * @return An iterator that points to the inserted pair. * * This function inserts a (key, value) pair into the tree @em tree. * Contrary to @b cx_tree_insert_unique() the key @em key used for inserting * @em data may already be present in the tree. */ cx_tree_iterator cx_tree_insert_equal(cx_tree *tree, cxcptr key, cxcptr data) { cx_assert(tree != NULL); cx_assert(key != NULL); return _cx_tree_insert_equal(tree, key, data); } /** * @brief * Erase an element from a tree. * * @param tree A tree. * @param position Iterator position of the element to be erased. * * @return Nothing. * * This function erases an element, specified by the iterator @em position, * from @em tree. Key and value associated with the erased pair are * deallocated using the tree's key and value destructors, provided * they have been set. */ void cx_tree_erase_position(cx_tree *tree, cx_tree_iterator position) { cx_assert(tree != NULL); if (!position) { return; } cx_assert(_cx_tree_exists(tree, position)); _cx_tree_erase(tree, position); return; } /** * @brief * Erase a range of elements from a tree. * * @param tree A tree. * @param begin Iterator pointing to the start of the range to erase. * @param end Iterator pointing to the end of the range to erase. * * @return Nothing. * * This function erases all elements in the range [begin, end) from * the tree @em tree. Key and value associated with the erased pair(s) are * deallocated using the tree's key and value destructors, provided * they have been set. */ void cx_tree_erase_range(cx_tree *tree, cx_tree_iterator begin, cx_tree_iterator end) { cx_assert(tree != NULL); cx_assert(begin == _cx_tree_head(tree) || _cx_tree_exists(tree, begin)); cx_assert(end == _cx_tree_head(tree) || _cx_tree_exists(tree, end)); while (begin != end) { cx_tnode *pos = begin; begin = _cx_tnode_next(pos); _cx_tree_erase(tree, pos); } return; } /** * @brief * Erase all elements from a tree matching the provided key. * * @param tree A tree. * @param key Key of the element to be erased. * * @return The number of removed elements. * * This function erases all elements with the specified key @em key, * from @em tree. Key and value associated with the erased pairs are * deallocated using the tree's key and value destructors, provided * they have been set. */ cxsize cx_tree_erase(cx_tree *tree, cxcptr key) { cx_tnode *x, *y; cxsize count = 0; cx_assert(tree != NULL); cx_assert(key != NULL); x = _cx_tree_lower_bound(tree, key); y = _cx_tree_upper_bound(tree, key); while (x != y) { cx_tnode *pos = x; x = _cx_tnode_next(x); _cx_tree_erase(tree, pos); ++count; } return count; } /** * @brief * Validate a tree. * * @param tree The tree to verify. * * @return Returns @c TRUE if the tree is valid, or @c FALSE otherwise. * * The function is provided for debugging purposes. It verifies that * the internal tree structure of @em tree is valid. */ cxbool cx_tree_verify(const cx_tree *tree) { cx_tnode *it; cxsize len = 0; cx_assert(tree != NULL); if (_cx_tree_node_count(tree) == 0 || _cx_tree_begin(tree) == _cx_tree_end(tree)) { if (_cx_tree_node_count(tree) == 0 && _cx_tree_begin(tree) == _cx_tree_end(tree) && _cx_tnode_left(_cx_tree_head(tree)) == _cx_tree_head(tree) && _cx_tnode_right(_cx_tree_head(tree)) == _cx_tree_head(tree)) return TRUE; else return FALSE; } len = _cx_tree_black_count(_cx_tree_leftmost(tree), _cx_tree_root(tree)); for (it = _cx_tree_begin(tree); it != _cx_tree_end(tree); it = _cx_tnode_next(it)) { cx_tnode *x = it; cx_tnode *L = _cx_tnode_left(x); cx_tnode *R = _cx_tnode_right(x); if (_cx_tnode_color(x) == CX_TNODE_RED) if ((L && _cx_tnode_color(L) == CX_TNODE_RED) || (R && _cx_tnode_color(R) == CX_TNODE_RED)) return FALSE; if (L && _cx_tree_key_compare(tree, _cx_tnode_key(x), _cx_tnode_key(L))) return FALSE; if (R && _cx_tree_key_compare(tree, _cx_tnode_key(R), _cx_tnode_key(x))) return FALSE; if (!L && !R && _cx_tree_black_count(x, _cx_tree_root(tree)) != len) return FALSE; } if (_cx_tree_leftmost(tree) != _cx_tnode_minimum(_cx_tree_root(tree))) return FALSE; if (_cx_tree_rightmost(tree) != _cx_tnode_maximum(_cx_tree_root(tree))) return FALSE; return TRUE; } /**@}*/