avl.h

Go to the documentation of this file.

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */
 
#ifndef _ACF_UTILS_AVL_H_
#define _ACF_UTILS_AVL_H_
 
#ifdef  __cplusplus
extern "C" {
#endif
 
#include <sys/types.h>
#include "types.h"
 
#define _AVL_IMPL_INCLUDED_FROM_AVL_H
#include "avl_impl.h"
 
typedef struct avl_tree avl_tree_t;
 
typedef struct avl_node avl_node_t;
 
typedef uintptr_t avl_index_t;
 
 
#define AVL_BEFORE  (0)
#define AVL_AFTER   (1)
 
 
/*
 * Prototypes
 *
 * Where not otherwise mentioned, "void *" arguments are a pointer to the
 * user data structure which must contain a field of type avl_node_t.
 *
 * Also assume the user data structures looks like:
 *  stuct my_type {
 *      ...
 *      avl_node_t  my_link;
 *      ...
 *  };
 */
 
API_EXPORT extern void avl_create(avl_tree_t *tree,
    int (*compar) (const void *, const void *), size_t size, size_t offset);
 
 
API_EXPORT extern void *avl_find(const avl_tree_t *tree, const void *node,
    avl_index_t *where);
 
API_EXPORT extern void avl_insert(avl_tree_t *tree, void *node,
    avl_index_t where);
 
API_EXPORT extern void avl_insert_here(avl_tree_t *tree, void *new_data,
    void *here, int direction);
 
 
API_EXPORT extern void *avl_first(const avl_tree_t *tree);
API_EXPORT extern void *avl_last(const avl_tree_t *tree);
 
#define AVL_NEXT(tree, node)    avl_walk(tree, node, AVL_AFTER)
#define AVL_PREV(tree, node)    avl_walk(tree, node, AVL_BEFORE)
 
API_EXPORT extern void *avl_nearest(const avl_tree_t *tree, avl_index_t where,
    int direction);
 
 
API_EXPORT extern void avl_add(avl_tree_t *tree, void *node);
 
 
API_EXPORT extern void avl_remove(avl_tree_t *tree, void *node);
 
API_EXPORT extern bool_t avl_update(avl_tree_t *, void *);
API_EXPORT extern bool_t avl_update_lt(avl_tree_t *, void *);
API_EXPORT extern bool_t avl_update_gt(avl_tree_t *, void *);
 
API_EXPORT extern unsigned long avl_numnodes(const avl_tree_t *tree);
 
API_EXPORT extern bool_t avl_is_empty(avl_tree_t *tree);
 
API_EXPORT extern void *avl_destroy_nodes(avl_tree_t *tree, void **cookie);
 
 
API_EXPORT extern void avl_destroy(avl_tree_t *tree);
 
 
 
#ifdef  __cplusplus
}
#endif
 
#endif  /* _ACF_UTILS_AVL_H_ */