/***************************************************************************** avl.h - Extra functions for the AVL-tree library. Copyright (C) 1998 Michael H. Buselli <cosine@cosine.org> Copyright (C) 2000-2005 Wessel Dankers <wsl@nl.linux.org> This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This library 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 Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Augmented AVL-tree. Original by Michael H. Buselli <cosine@cosine.org>. Modified by Wessel Dankers <wsl@nl.linux.org> to add a bunch of bloat to the sourcecode, change the interface and squash a few bugs. Mail him if you find new bugs. *****************************************************************************/ #include <avl.h> #ifndef _FAIR_AVL_H #define _FAIR_AVL_H /* Insert an item into the tree and return the new node. * If a nodes with equal items are already in the tree, this item will * be inserted to the left of all those. Returns NULL and sets errno if * memory for the new node could not be allocated. * O(lg n) */ extern avl_node_t *avl_item_insert_left(avl_tree_t *, void *); /* Insert an item into the tree and return the new node. * If a nodes with equal items are already in the tree, this item will * be inserted to the right of all those. Returns NULL and sets errno if * memory for the new node could not be allocated. * O(lg n) */ extern avl_node_t *avl_item_insert_right(avl_tree_t *, void *); /* Insert an item into the tree and return the new node. * If a nodes with equal items are already in the tree, this item will * be inserted somewhere among those. Returns NULL and sets errno if * memory for the new node could not be allocated. * O(lg n) */ extern avl_node_t *avl_item_insert_somewhere(avl_tree_t *, void *item); /* Insert a node into the tree and return it. * If a nodes with equal items are already in the tree, this node will * be inserted to the left of all those. * O(lg n) */ extern avl_node_t *avl_insert_left(avl_tree_t *, avl_node_t *); /* Insert a node into the tree and return it. * If a nodes with equal items are already in the tree, this node will * be inserted to the right of all those. * O(lg n) */ extern avl_node_t *avl_insert_right(avl_tree_t *, avl_node_t *); /* Insert a node into the tree and return it. * If a nodes with equal items are already in the tree, this node will * be inserted somewhere among those. * O(lg n) */ extern avl_node_t *avl_insert_somewhere(avl_tree_t *, avl_node_t *); /* Searches for an item, returning either the first (leftmost) exact * match, or (if no exact match could be found) the first (leftmost) * of the nodes that have an item greater than the search item. * If exact is not NULL, *exact will be set to: * 0 if the returned node is inequal or NULL * 1 if the returned node is equal * Returns NULL if no equal or greater element could be found. * O(lg n) */ extern avl_node_t *avl_search_left(const avl_tree_t *, const void *item, int *exact); /* Searches for an item, returning either the last (rightmost) exact * match, or (if no exact match could be found) the last (rightmost) * of the nodes that have an item smaller than the search item. * If exact is not NULL, *exact will be set to: * 0 if the returned node is inequal or NULL * 1 if the returned node is equal * Returns NULL if no equal or smaller element could be found. * O(lg n) */ extern avl_node_t *avl_search_right(const avl_tree_t *, const void *item, int *exact); /* Searches for an item, returning either some exact * match, or (if no exact match could be found) the last (rightmost) * of the nodes that have an item smaller than the search item. * If exact is not NULL, *exact will be set to: * 0 if the returned node is inequal or NULL * 1 if the returned node is equal * Returns NULL if no equal or smaller element could be found. * O(lg n) */ extern avl_node_t *avl_search_rightish(const avl_tree_t *, const void *item, int *exact); #endif

Generated by Doxygen 1.6.0 Back to index