#include <sys/types.h>
#include "types.h"
#include "avl_impl.h"

Include dependency graph for avl.h:

Macros
#define	_AVL_IMPL_INCLUDED_FROM_AVL_H

#define	AVL_BEFORE (0)

#define	AVL_AFTER (1)

#define	AVL_NEXT(tree, node) avl_walk(tree, node, AVL_AFTER)

#define	AVL_PREV(tree, node) avl_walk(tree, node, AVL_BEFORE)

Typedefs
typedef uintptr_t	avl_index_t

Functions
void	avl_create (avl_tree_t tree, int(compar)(const void , const void ), size_t size, size_t offset)

void *	avl_find (const avl_tree_t tree, const void node, avl_index_t *where)

void	avl_insert (avl_tree_t tree, void node, avl_index_t where)

void	avl_insert_here (avl_tree_t tree, void new_data, void *here, int direction)

void *	avl_first (const avl_tree_t *tree)

void *	avl_last (const avl_tree_t *tree)

void *	avl_nearest (const avl_tree_t *tree, avl_index_t where, int direction)

void	avl_add (avl_tree_t tree, void node)

void	avl_remove (avl_tree_t tree, void node)

bool_t	avl_update (avl_tree_t , void )

bool_t	avl_update_lt (avl_tree_t , void )

bool_t	avl_update_gt (avl_tree_t , void )

unsigned long	avl_numnodes (const avl_tree_t *tree)

bool_t	avl_is_empty (avl_tree_t *tree)

void *	avl_destroy_nodes (avl_tree_t tree, void *cookie)

void	avl_destroy (avl_tree_t *tree)

Detailed Description

This is a generic implemenatation of AVL trees for use in the Solaris kernel. The interfaces provide an efficient way of implementing an ordered set of data structures.

AVL trees provide an alternative to using an ordered linked list. Using AVL trees will usually be faster, however they requires more storage. An ordered linked list in general requires 2 pointers in each data structure. The AVL tree implementation uses 3 pointers. The following chart gives the approximate performance of operations with the different approaches:

Operation Link List AVL tree

lookup O(n) O(log(n))

insert 1 node constant constant

delete 1 node constant between constant and O(log(n))

delete all nodes O(n) O(n)

visit the next or prev node constant between constant and O(log(n))

The data structure nodes are anchored at an avl_tree_t (the equivalent of a list header) and the individual nodes will have a field of type "avl_node_t" (corresponding to list pointers).

The type avl_index_t is used to indicate a position in the list for certain calls.

The usage scenario is generally:

Create the list/tree with: avl_create()

followed by any mixture of:

2a. Insert nodes with: avl_add(), or avl_find() and avl_insert()

2b. Visited elements with: avl_first() - returns the lowest valued node avl_last() - returns the highest valued node AVL_NEXT() - given a node go to next higher one AVL_PREV() - given a node go to previous lower one

2c. Find the node with the closest value either less than or greater than a given value with avl_nearest().

2d. Remove individual nodes from the list/tree with avl_remove().

and finally when the list is being destroyed

Use avl_destroy_nodes() to quickly process/free up any remaining nodes. Note that once you use avl_destroy_nodes(), you can no longer use any routine except avl_destroy_nodes() and avl_destoy().
Use avl_destroy() to destroy the AVL tree itself.

Any locking for multiple thread access is up to the user to provide, just as is needed for any linked list implementation.

Definition in file avl.h.

Macro Definition Documentation

◆ _AVL_IMPL_INCLUDED_FROM_AVL_H

#define _AVL_IMPL_INCLUDED_FROM_AVL_H

Definition at line 36 of file avl.h.

◆ AVL_AFTER

#define AVL_AFTER (1)

Direction constants used for avl_nearest().

Definition at line 129 of file avl.h.

◆ AVL_BEFORE

#define AVL_BEFORE (0)

Direction constants used for avl_nearest().

Definition at line 125 of file avl.h.

◆ AVL_NEXT

#define AVL_NEXT	(	tree,
		node
	)	avl_walk(tree, node, AVL_AFTER)

Returns: the next or previous valued node in the tree. Will return NULL if at the last node.

Parameters

node	the node from which the next or previous node is found

Definition at line 212 of file avl.h.

◆ AVL_PREV

#define AVL_PREV	(	tree,
		node
	)	avl_walk(tree, node, AVL_BEFORE)

Returns: the previous valued node in the tree. Will return NULL if at the first node.

Parameters

node	the node from which the next or previous node is found

Definition at line 218 of file avl.h.

Typedef Documentation

◆ avl_index_t

typedef uintptr_t avl_index_t

An opaque type used to locate a position in the tree where a node would be inserted.

Definition at line 119 of file avl.h.

Function Documentation

◆ avl_add()

void avl_add	(	avl_tree_t *	tree,
		void *	node
	)

extern

Add a single node to the tree.

The node must not be in the tree, and it must not compare equal to any other node already in the tree.

Parameters

node	the node to add

Definition at line 621 of file avl.c.

◆ avl_create()

void avl_create	(	avl_tree_t *	tree,
		int()(const void , const void *)	compar,
		size_t	size,
		size_t	offset
	)

extern

Initialize an AVL tree.

Parameters

tree	the tree to be initialized
compar	function to compare two nodes, it must return exactly: -1, 0, or +1. -1 for <, 0 for ==, and +1 for >
size	the value of sizeof(struct my_type)
offset	the value of OFFSETOF(struct my_type, my_link)

Definition at line 867 of file avl.c.

◆ avl_destroy()

void avl_destroy ( avl_tree_t * tree )

extern

Final destroy of an AVL tree.

Parameters

tree	the empty tree to destroy

Definition at line 890 of file avl.c.

◆ avl_destroy_nodes()

void * avl_destroy_nodes	(	avl_tree_t *	tree,
		void **	cookie
	)

extern

Used to destroy any remaining nodes in a tree. The cookie argument should be initialized to NULL before the first call. Returns a node that has been removed from the tree and may be free()'d. Returns NULL when the tree is empty.

Once you call avl_destroy_nodes(), you can only continuing calling it and finally avl_destroy(). No other AVL routines will be valid.

Parameters

cookie a "void *" used to save state between calls to avl_destroy_nodes()

Example:

avl_tree_t *tree;
struct my_data *node;
void *cookie;
 
cookie = NULL;
while ((node = avl_destroy_nodes(tree, &cookie)) != NULL)
    free(node);
avl_destroy(tree);

Definition at line 938 of file avl.c.

◆ avl_find()

void * avl_find	(	const avl_tree_t *	tree,
		const void *	node,
		avl_index_t *	where
	)

extern

Find a node with a matching value in the tree.

Parameters

node	node that has the value being looked for
where	position for use with avl_nearest() or avl_insert(), may be NULL

Returns: The matching node found. If not found, it returns NULL and then if "where" is not NULL it sets "where" for use with avl_insert() or avl_nearest().

Definition at line 244 of file avl.c.

◆ avl_first()

void * avl_first ( const avl_tree_t * tree )

extern

Returns: The first valued node in the tree. Will return NULL if the tree is empty.

Definition at line 172 of file avl.c.

◆ avl_insert()

void avl_insert	(	avl_tree_t *	tree,
		void *	node,
		avl_index_t	where
	)

extern

Insert a node into the tree.

Parameters

node	the node to insert
where	position as returned from avl_find()

Definition at line 471 of file avl.c.

◆ avl_insert_here()

void avl_insert_here	(	avl_tree_t *	tree,
		void *	new_data,
		void *	here,
		int	direction
	)

extern

Insert "new_data" in "tree" in the given "direction" either after or before the data "here".

This might be useful for avl clients caching recently accessed data to avoid doing avl_find() again for insertion.

Parameters

new_data	new data to insert
here	existing node in "tree"
direction	either AVL_AFTER or AVL_BEFORE the data "here".

Definition at line 561 of file avl.c.

◆ avl_is_empty()

bool_t avl_is_empty ( avl_tree_t * tree )

extern

Returns: B_TRUE if there are zero nodes in the tree, B_FALSE otherwise.

Definition at line 910 of file avl.c.

◆ avl_last()

void * avl_last ( const avl_tree_t * tree )

extern

Returns: The last valued node in the tree. Will return NULL if the tree is empty.

Definition at line 191 of file avl.c.

◆ avl_nearest()

void * avl_nearest	(	const avl_tree_t *	tree,
		avl_index_t	where,
		int	direction
	)

extern

Find the node with the nearest value either greater or less than the value from a previous avl_find().

Parameters

where	position as returned from avl_find()
direction	either AVL_BEFORE or AVL_AFTER

Returns: the node or NULL if there isn't a matching one.

Example: get the greatest node that is less than a given value:

avl_tree_t *tree;
struct my_data look_for_value = {....};
struct my_data *node;
struct my_data *less;
avl_index_t where;
 
node = avl_find(tree, &look_for_value, &where);
if (node != NULL)
    less = AVL_PREV(tree, node);
else
    less = avl_nearest(tree, where, AVL_BEFORE);

Definition at line 215 of file avl.c.

◆ avl_numnodes()

unsigned long avl_numnodes ( const avl_tree_t * tree )

extern

Returns: the number of nodes in the tree

Definition at line 903 of file avl.c.

◆ avl_remove()

void avl_remove	(	avl_tree_t *	tree,
		void *	node
	)

extern

Remove a single node from the tree. The node must be in the tree.

Parameters

node	the node to remove

Definition at line 660 of file avl.c.

◆ avl_update()

bool_t avl_update	(	avl_tree_t *	t,
		void *	obj
	)

extern

Reinsert a node only if its order has changed relative to its nearest neighbors. To optimize performance avl_update_lt() checks only the previous node and avl_update_gt() checks only the next node. Use avl_update_lt() and avl_update_gt() only if you know the direction in which the order of the node may change.

Definition at line 844 of file avl.c.

◆ avl_update_gt()

bool_t avl_update_gt	(	avl_tree_t *	t,
		void *	obj
	)

extern

See also: avl_update()

Definition at line 827 of file avl.c.

◆ avl_update_lt()

bool_t avl_update_lt	(	avl_tree_t *	t,
		void *	obj
	)

extern

See also: avl_update()

Definition at line 810 of file avl.c.

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

◆ _AVL_IMPL_INCLUDED_FROM_AVL_H

◆ AVL_AFTER

◆ AVL_BEFORE

◆ AVL_NEXT

◆ AVL_PREV

Typedef Documentation

◆ avl_index_t

Function Documentation

◆ avl_add()

◆ avl_create()

◆ avl_destroy()

◆ avl_destroy_nodes()

◆ avl_find()

◆ avl_first()

◆ avl_insert()

◆ avl_insert_here()

◆ avl_is_empty()

◆ avl_last()

◆ avl_nearest()

◆ avl_numnodes()

◆ avl_remove()

◆ avl_update()

◆ avl_update_gt()

◆ avl_update_lt()