/*
 * Copyright 2002 Sun Microsystems, Inc. All rights reserved.
 * Use is subject to license terms.
 */

/*
 * NOTE: In the current implementation, the AVL support is contained
 * in the NFS kernel module, fs/nfs/nfs_avl.c. If a new consumer of
 * these interfaces is required, then this support should be moved from
 * fs/nfs/avl.c to os/avl.c and thus binary support from the NFS kernel
 * module to genunix.
 */

#ifndef	_AVL_H
#define	_AVL_H

#pragma ident	"@(#)avl.h	1.2	00/10/05 SMI"

#ifdef	__cplusplus
extern "C" {
#endif



#include <sys/avl_impl.h>

/*
 * The data nodes in the AVL tree must have a field of this type.
 */
typedef struct avl_node avl_node_t;


/*
 * an opaque type used to locate a position in the tree where a node
 * would be inserted.
 */
typedef uintptr_t avl_index_t;


/*
 * type used to represent a tree
 */
typedef struct avl_tree avl_tree_t;


/*
 * direction constants used for avl_nearest()
 */
#define	AVL_BEFORE	(0)
#define	AVL_AFTER	(1)



/*
 * prototypes
 *
 * NOTE for avl_create: the compar() function must return exactly: -1, 0, or +1
 */
extern void avl_create(avl_tree_t *, int (*) (const void *, const void *),
	size_t, size_t);

extern void avl_destroy(avl_tree_t *);

extern void * avl_find(avl_tree_t *, void *, avl_index_t *);

extern void * avl_nearest(avl_tree_t *, avl_index_t, int);

extern void avl_insert(avl_tree_t *, void *, avl_index_t);

extern void avl_remove(avl_tree_t *, void *);

extern void * avl_first(avl_tree_t *);
extern void * avl_last(avl_tree_t *);

#define	AVL_NEXT(t, d)	avl_walk(t, d, AVL_AFTER)
#define	AVL_PREV(t, d)	avl_walk(t, d, AVL_BEFORE)
extern void * avl_walk(avl_tree_t *, void *, int);

extern ulong_t avl_numnodes(avl_tree_t *);

extern void * avl_deepest(avl_tree_t *);

extern void avl_detach(avl_tree_t *, avl_tree_t *);



#ifdef	__cplusplus
}
#endif

#endif	/* _AVL_H */
