Logo Search packages:      
Sourcecode: fair version File versions  Download package

avlr.h

/*****************************************************************************

    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