Detailed Description

Author: hacatu

Version: 0.3.0 A featureful generic avl tree implementation. Useful for storing ordered mappings.

This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

Definition in file avl.h.

Go to the source code of this file.

Data Structures
struct	cr8r_avl_node
	An avl tree node, also used to store an entire tree by synecdoche. More...

struct	cr8r_avl_ft
	Function table for avl tree. More...

Macros
#define	CR8R_AVL_DATA(T, n) CR8R_FLA_CAST(T, (char)((cr8r_avl_node)(n))->data)
	Get a pointer to the data field of an avl node and cast to a given type.

Enumerations
enum	cr8r_map_insert_result { CR8R_AVL_FAILED = 0 , CR8R_AVL_INSERTED = 1 , CR8R_AVL_UPDATED = 2 }
	Constants to test map like data structure insertion against where applicable.

Functions
bool	cr8r_avl_ft_init (cr8r_avl_ft , void data, uint64_t size, int(cmp)(const cr8r_base_ft , const void , const void ), int(add)(cr8r_base_ft , void , void ), void (alloc)(cr8r_base_ft ), void(free)(cr8r_base_ft , void ))
	Convenience function to initialize a cr8r_avl_ft. More...

bool	cr8r_avl_ft_initsla (cr8r_avl_ft , cr8r_sla sla, uint64_t size, uint64_t reserve, int(cmp)(const cr8r_base_ft , const void , const void ), int(add)(cr8r_base_ft , void , void ))
	Convenience function to initialize a cr8r_avl_ft and associated slab allocator. More...

cr8r_avl_node *	cr8r_avl_new (void key, cr8r_avl_node left, cr8r_avl_node right, cr8r_avl_node parent, char balance, cr8r_avl_ft *)
	Allocate a new avl node and initialize it with given data. More...

int	cr8r_avl_insert (cr8r_avl_node *r, void key, cr8r_avl_ft *)
	Create a new node in an avl tree with a given value. More...

int	cr8r_avl_remove (cr8r_avl_node *r, void key, cr8r_avl_ft *)
	Remove the node in an avl tree with a given value. More...

int	cr8r_avl_insert_update (cr8r_avl_node *r, void key, cr8r_avl_ft *)
	Create a new node in an avl tree or modify an existing one with a given value. More...

cr8r_avl_node *	cr8r_avl_remove_node (cr8r_avl_node n, cr8r_avl_ft )
	Remove a given node from the tree containing it. More...

cr8r_avl_node *	cr8r_avl_attach (cr8r_avl_node r, cr8r_avl_node n, cr8r_avl_ft , int is_duplicate)
	Add a given node to an existing tree. More...

cr8r_avl_node *	cr8r_avl_attach_exclusive (cr8r_avl_node r, cr8r_avl_node n, cr8r_avl_ft *)
	Add a given node to an existing tree. More...

cr8r_avl_node *	cr8r_avl_detach (cr8r_avl_node n, cr8r_avl_ft )
	Remove a given node from the tree containing it but do not free it. More...

cr8r_avl_node *	cr8r_avl_get (cr8r_avl_node r, void key, cr8r_avl_ft *)
	Find the node matching a given element in a tree. More...

cr8r_avl_node *	cr8r_avl_search (cr8r_avl_node r, void key, cr8r_avl_ft *)
	Find the deepest node on the search path for a given key If there is a node in the tree with the given key, returns a pointer to that node. More...

cr8r_avl_node *	cr8r_avl_root (cr8r_avl_node *n)
	Find the root of the tree containing a given node. More...

cr8r_avl_node *	cr8r_avl_first (cr8r_avl_node *r)
	Find the node in the tree with the lowest key. More...

cr8r_avl_node *	cr8r_avl_next (cr8r_avl_node *n)
	Find the inorder successor of a node. More...

cr8r_avl_node *	cr8r_avl_last (cr8r_avl_node *n)
	Find the node in the tree with the greatest key. More...

cr8r_avl_node *	cr8r_avl_prev (cr8r_avl_node *n)
	Find the inorder predecessor of a node. More...

cr8r_avl_node *	cr8r_avl_lower_bound (cr8r_avl_node r, void key, cr8r_avl_ft *)
	Find the greatest element l in the tree so that l <= key. More...

cr8r_avl_node *	cr8r_avl_upper_bound (cr8r_avl_node r, void key, cr8r_avl_ft *)
	Find the lowest element u in the tree so that key < u. More...

void	cr8r_avl_delete (cr8r_avl_node r, cr8r_avl_ft )
	Delete an entire avl tree, freeing all nodes in the process. More...

cr8r_avl_node *	cr8r_avl_decrease (cr8r_avl_node n, cr8r_avl_ft , int *is_duplicate)
	Restore the binary search tree invariant after decreasing the key for a single node. More...

cr8r_avl_node *	cr8r_avl_increase (cr8r_avl_node n, cr8r_avl_ft , int *is_duplicate)
	Restore the binary search tree invariant after increasing the key for a single node. More...

cr8r_avl_node *	cr8r_avl_first_post (cr8r_avl_node *r)
	Find the first node in a postorder traversal of the tree. More...

cr8r_avl_node *	cr8r_avl_next_post (cr8r_avl_node *n)
	Find the postorder successor of a given node. More...

void	cr8r_avl_sift_down (cr8r_avl_node r, cr8r_avl_ft )
	Treat the avl tree as a max heap and sift down a given node. More...

void	cr8r_avl_heapify (cr8r_avl_node r, cr8r_avl_ft )
	Convert the avl tree into a max heap in place. More...

cr8r_avl_node *	cr8r_avl_heappop_node (cr8r_avl_node *r, cr8r_avl_ft )
	Treat the avl tree as a max heap and remove the top element. More...

void	cr8r_avl_reorder (cr8r_avl_node r, cr8r_avl_ft )
	Reorder the tree so that it is sorted according to a new ordering function. More...

Function Documentation

◆ cr8r_avl_ft_init()

bool cr8r_avl_ft_init	(	cr8r_avl_ft *	,
		void *	data,
		uint64_t	size,
		int()(const cr8r_base_ft , const void , const void )	cmp,
		int()(cr8r_base_ft , void , void )	add,
		void ()(cr8r_base_ft *)	alloc,
		void()(cr8r_base_ft , void *)	free
	)

Convenience function to initialize a cr8r_avl_ft.

Using standard structure initializer syntax with designated initializers may be simpler. However, this function provides basic checking (it checks the required functions aren't NULL).

Parameters

[in]	data	pointer to user defined data to associate with the function table. generally NULL is sufficient. see cr8r_base_ft for a more in-depth explaination
[in]	size	size of a single element in bytes. Note that the size of a node will be offsetof(cr8r_avl_node, data) + size
[in]	cmp	comparison function. should not be NULL. some functions do not require it, but it is required to do anything useful with avl trees. See cr8r_default_cmp for a basic generic implementation.
[in]	add	element composition function. can be NULL for all functions besides cr8r_avl_insert_update. called to combine an existing and new element when this function is called and the element to insert is already in the tree.
[in]	alloc	allocate a single node. Using a slab allocator ( cr8r_sla ) is a good choice.
[in]	free	free a single node.

Returns: 1 on success, 0 on failure (if cmp, alloc, or free is NULL)

◆ cr8r_avl_ft_initsla()

bool cr8r_avl_ft_initsla	(	cr8r_avl_ft *	,
		cr8r_sla *	sla,
		uint64_t	size,
		uint64_t	reserve,
		int()(const cr8r_base_ft , const void , const void )	cmp,
		int()(cr8r_base_ft , void , void )	add
	)

Convenience function to initialize a cr8r_avl_ft and associated slab allocator.

Automatically initializes sla, points ft->base.data at sla, and sets ft->alloc and ft->free to cr8r_default_alloc_sla and cr8r_default_free_sla respectively. WARNING sla is always initialized, an initialized sla should not be passed and in particular to make multiple tables with the same slab allocator, call this once and then call cr8r_avl_ft_init or use a literal for subsequent function tables.

Parameters

[out]	sla	slab allocator to initialize and point ft->base.data at. must be uninitialized. it is possible to have more information in ft->base.data by placing sla in a structure and additional information before or after it.
[in]	size	size of a single element (of the avl tree) in bytes. the size of a node (or slab allocator element) is offsetof(cr8r_avl_node, data) + size.
[in]	reserve	how many nodes to reserve space for in the slab allocator initially. must not be 0.
[in]	cmp	comparison function. should not be NULL. some functions do not require it, but it is required to do anything useful with avl trees. See cr8r_default_cmp for a basic generic implementation.
[in]	add	element composition function. can be NULL for all functions besides cr8r_avl_insert_update. called to combine an existing and new element when this function is called and the element to insert is already in the tree.

Returns: 1 on success, 0 on failure (if cmp, sla, or reserve is NULL/0 or the slab allocator cannot reserve enough memory)

◆ cr8r_avl_new()

cr8r_avl_node* cr8r_avl_new	(	void *	key,
		cr8r_avl_node *	left,
		cr8r_avl_node *	right,
		cr8r_avl_node *	parent,
		char	balance,
		cr8r_avl_ft *
	)

Allocate a new avl node and initialize it with given data.

Remember that ft->alloc(ft->base.data) will be called to allocate the node

Parameters

[in]	key	element to put into the node. This is generally a structure with conceptual "key" and "value" parts.
[in]	left,right,parent	initial values for node pointers. This function does NOT adjust the links in these pointers. Generally left and right will be NULL and changed later.
[in]	balance	avl balance value, generally 0.

Returns: a pointer to the new, initialized node, or NULL if ft->alloc fails

◆ cr8r_avl_insert()

int cr8r_avl_insert	(	cr8r_avl_node **	r,
		void *	key,
		cr8r_avl_ft *
	)

Create a new node in an avl tree with a given value.

Parameters

[in,out]	r	root node. This is a pointer to a pointer, so that if the root node changes, the change can be indicated to the caller. *r can be NULL to indicate an empty tree.
[in]	key	element to insert. If no node with an element comparing equal to this element exists in the tree, a new node is created in the tree to hold it.

Returns: 0 if allocation fails or a node with the given element is already present in the tree, 1 if the element is not present and insertion suceeds.

◆ cr8r_avl_remove()

int cr8r_avl_remove	(	cr8r_avl_node **	r,
		void *	key,
		cr8r_avl_ft *
	)

Remove the node in an avl tree with a given value.

If multiple nodes with the same value exist in the tree, their order is unspecified and an unspecified one will be removed. Notice that cr8r_avl_insert will never create a tree with duplicate nodes. The removed node is freed using ft->free.

Parameters

[in,out]	r	root node. This is a pointer to a pointer, so that if the root node changes, the change can be indicated to the caller. *r can be NULL to indicate an empty tree.
[in]	key	element to remove.

Returns: 0 if no node with the given element exists in the tree, 1 if successful

◆ cr8r_avl_insert_update()

int cr8r_avl_insert_update	(	cr8r_avl_node **	r,
		void *	key,
		cr8r_avl_ft *
	)

Create a new node in an avl tree or modify an existing one with a given value.

Parameters

[in,out]	r	root node. This is a pointer to a pointer, so that if the root node changes, the change can be indicated to the caller. *r can be NULL to indicate an empty tree.
[in]	key	element to insert. If no node with an element comparing equal to this element exists in the tree, a new node is created in the tree to hold it.

Returns: 0 if allocation fails, 1 (AVL_INSERTED) if the element is not present and insertion suceeds, 2 (AVL_UPDATED) if an existing node was updated.

◆ cr8r_avl_remove_node()

cr8r_avl_node* cr8r_avl_remove_node	(	cr8r_avl_node *	n,
		cr8r_avl_ft *
	)

Remove a given node from the tree containing it.

This modifies the containing tree and frees the removed node.

Parameters

[in] n node to remove. n->left, n->right, and n->parent are used to find the rest of the tree and rebuild it without this node. This node is freed.

Returns: a pointer to the new root node of the tree that contained n, in case it changed. Can be NULL.

◆ cr8r_avl_attach()

cr8r_avl_node* cr8r_avl_attach	(	cr8r_avl_node *	r,
		cr8r_avl_node *	n,
		cr8r_avl_ft *	,
		int *	is_duplicate
	)

Add a given node to an existing tree.

The existing tree may contain a node with the same element (see cr8r_avl_attach_exclusive for a version that disallows this).

Parameters

[in]	r	the root of the existing tree. Notice this is a pointer, not a pointer to a pointer as many other functions have. Can be NULL.
[in]	n	the node to insert. Should not have links.
[out]	is_duplicate	if this is not null, 0 is written if the node's key is not equal to any existing node, and 1 is written if it is.

Returns: a pointer to the new root, in case it changed.

◆ cr8r_avl_attach_exclusive()

cr8r_avl_node* cr8r_avl_attach_exclusive	(	cr8r_avl_node *	r,
		cr8r_avl_node *	n,
		cr8r_avl_ft *
	)

Add a given node to an existing tree.

The existing tree should not already contain a node with the same element.

Parameters

[in]	r	the root of the existing tree. Notice this is a pointer, not a pointer to a pointer as many other functions have. Can be NULL.
[in]	n	the node to insert. Should not have links.

Returns: a pointer to the new root, in case it changed, or NULL if n has the same key as an existing node

◆ cr8r_avl_detach()

cr8r_avl_node* cr8r_avl_detach	(	cr8r_avl_node *	n,
		cr8r_avl_ft *
	)

Remove a given node from the tree containing it but do not free it.

This modifies the containing tree and clears the pointers in the node, but allows further use of the node.

Parameters

[in,out] n n->left, n->right, and n->parent are used to find the rest of the tree and rebuild it without this node, then cleared so this node is a singleton.

Returns: a pointer to the new root of the tree that contained the node, in case its root changed. Can be NULL if the last node was removed.

◆ cr8r_avl_get()

cr8r_avl_node* cr8r_avl_get	(	cr8r_avl_node *	r,
		void *	key,
		cr8r_avl_ft *
	)

Find the node matching a given element in a tree.

Parameters

[in]	r	the root of the tree to search
[in]	key	element to find in the tree

Returns: a pointer to the node matching the given key, or NULL if no match exists.

◆ cr8r_avl_search()

cr8r_avl_node* cr8r_avl_search	(	cr8r_avl_node *	r,
		void *	key,
		cr8r_avl_ft *
	)

Find the deepest node on the search path for a given key If there is a node in the tree with the given key, returns a pointer to that node.

Otherwise, returns a pointer leaf node which is either the lower bound or upper bound of the given key. In both cases, the node returned is the deepest node that would be an ancestor of the key if it were inserted into the tree without rebalancing.

Parameters

[in]	r	the root of the tree to search
[in]	key	element to search for in the tree

Returns: a pointer to the last node in the tree on the search path for the given key, which could compare equal to the key, be its lower bound or upper bound, or, if the given root is null, be null

◆ cr8r_avl_root()

cr8r_avl_node* cr8r_avl_root ( cr8r_avl_node * n )

Find the root of the tree containing a given node.

Simply climbs the parent links repeatedly.

Parameters

[in] n node in tree to find root of.

Returns: a pointer to the root of the tree containing n.

◆ cr8r_avl_first()

cr8r_avl_node* cr8r_avl_first ( cr8r_avl_node * r )

Find the node in the tree with the lowest key.

Simply follows the left links repeatedly.

Parameters

[in] r the root of the tree

Returns: a pointer to the node with the lowest key in the tree

◆ cr8r_avl_next()

cr8r_avl_node* cr8r_avl_next ( cr8r_avl_node * n )

Find the inorder successor of a node.

Parameters

[in] n node to find the successor of

Returns: a pointer to the inorder successor of n

◆ cr8r_avl_last()

cr8r_avl_node* cr8r_avl_last ( cr8r_avl_node * n )

Find the node in the tree with the greatest key.

Simply follows the right links repeatedly.

Parameters

[in] n the root of the tree

Returns: a pointer to the node with the greatest key in the tree

◆ cr8r_avl_prev()

cr8r_avl_node* cr8r_avl_prev ( cr8r_avl_node * n )

Find the inorder predecessor of a node.

Parameters

[in] n node to find the predecessor of

Returns: a pointer to the inorder predecessor of n

◆ cr8r_avl_lower_bound()

cr8r_avl_node* cr8r_avl_lower_bound	(	cr8r_avl_node *	r,
		void *	key,
		cr8r_avl_ft *
	)

Find the greatest element l in the tree so that l <= key.

This is useful along with cr8r_avl_upper_bound for partitioning the tree into ranges, and partitions the inorder traversal in a nice way. In particular, if the tree has no duplicate keys, then cr8r_avl_upper_bound is the inorder successor of cr8r_avl_lower_bound, so if we start at cr8r_avl_first or some node known to have a key less than the key given to cr8r_avl_lower_bound, then we can do an inorder traversal with cr8r_avl_next from the starting point to the lower bound (inclusive).

Parameters

[in]	r	root of the tree to search
[in]	key	element to find a maximal inclusive lower bound of in the tree

Returns: a pointer to a node whose key is a maximal inclusive lower bound

◆ cr8r_avl_upper_bound()

cr8r_avl_node* cr8r_avl_upper_bound	(	cr8r_avl_node *	r,
		void *	key,
		cr8r_avl_ft *
	)

Find the lowest element u in the tree so that key < u.

See cr8r_avl_lower_bound

Parameters

[in]	r	root of the tree to search
[in]	key	element to find a minimal exclusive upper bound of in the tree

Returns: a pointer to a node whose key is a minimal exclusive upper bound

◆ cr8r_avl_delete()

void cr8r_avl_delete	(	cr8r_avl_node *	r,
		cr8r_avl_ft *
	)

Delete an entire avl tree, freeing all nodes in the process.

Parameters

[in] r the root of the tree, which is invalidated (unless ft->free doesn't invalidate nodes for some reason)

◆ cr8r_avl_decrease()

cr8r_avl_node* cr8r_avl_decrease	(	cr8r_avl_node *	n,
		cr8r_avl_ft *	,
		int *	is_duplicate
	)

Restore the binary search tree invariant after decreasing the key for a single node.

After decreasing the key in a node, this function should be called, which then moves the node if necessary to ensure the tree is a BST. Only the given node should violate the BST condition.

Parameters

[in]	n	the node that has had its key decreased and may need to be moved
[out]	is_duplicate	if this is not null, 0 is written if the decreased key is unique within the tree, and 1 is written if it is equal to some existing key

Returns: a pointer to the root of the tree, in case it changes

◆ cr8r_avl_increase()

cr8r_avl_node* cr8r_avl_increase	(	cr8r_avl_node *	n,
		cr8r_avl_ft *	,
		int *	is_duplicate
	)

Restore the binary search tree invariant after increasing the key for a single node.

After increasing the key in a node, this function should be called, which then moves the node if necessary to ensure the tree is a BST. Only the given node should violate the BST condition.

Parameters

[in]	n	the node that has had its key increased and may need to be moved
[out]	is_duplicate	if this is not null, 0 is written if the increased key is unique within the tree, and 1 is written if it is equal to some existing key

Returns: a pointer to the root of the tree, in case it changes, or NULL if a duplicate key is encountered

◆ cr8r_avl_first_post()

cr8r_avl_node* cr8r_avl_first_post ( cr8r_avl_node * r )

Find the first node in a postorder traversal of the tree.

A postorder traversal visits the children of a node before the node, useful for evaluating expression trees and so on.

Parameters

[in] r pointer to the root

Returns: a pointer to the first node in a postorder traversal

◆ cr8r_avl_next_post()

cr8r_avl_node* cr8r_avl_next_post ( cr8r_avl_node * n )

Find the postorder successor of a given node.

Parameters

[in] n current node

Returns: a pointer to the next node in a postorder traversal

◆ cr8r_avl_sift_down()

void cr8r_avl_sift_down	(	cr8r_avl_node *	r,
		cr8r_avl_ft *
	)

Treat the avl tree as a max heap and sift down a given node.

If this node has had its key decreased but the avl tree is otherwise a max heap, this will restore the max heap invariant.

Parameters

[in] r the node to sift down

◆ cr8r_avl_heapify()

void cr8r_avl_heapify	(	cr8r_avl_node *	r,
		cr8r_avl_ft *
	)

Convert the avl tree into a max heap in place.

This takes linear time. The shape of the tree is not changed. To change the ordering function of the heap, this function can just be called again on a formed heap with ft->cmp changed appropriately.

Parameters

[in,out] r root of the tree to heapify

◆ cr8r_avl_heappop_node()

cr8r_avl_node* cr8r_avl_heappop_node	(	cr8r_avl_node **	r,
		cr8r_avl_ft *
	)

Treat the avl tree as a max heap and remove the top element.

Restores heap invariant afterwards

Parameters

[in,out] r pointer to pointer to root node, updated to point to new root node afterwards

Returns: pointer to removed node, or NULL if *r was NULL

◆ cr8r_avl_reorder()

void cr8r_avl_reorder	(	cr8r_avl_node *	r,
		cr8r_avl_ft *
	)

Reorder the tree so that it is sorted according to a new ordering function.

Currently this works by heapifying the tree in place and then placing the nodes in order one by one, which takes n*log(n) time.

Parameters

[in,out] r root of the tree to reorder, reordering is in place and does not change the root

Detailed Description

Data Structures

Macros

Enumerations

Functions

Function Documentation

◆ cr8r_avl_ft_init()

◆ cr8r_avl_ft_initsla()

◆ cr8r_avl_new()

◆ cr8r_avl_insert()

◆ cr8r_avl_remove()

◆ cr8r_avl_insert_update()

◆ cr8r_avl_remove_node()

◆ cr8r_avl_attach()

◆ cr8r_avl_attach_exclusive()

◆ cr8r_avl_detach()

◆ cr8r_avl_get()

◆ cr8r_avl_search()

◆ cr8r_avl_root()

◆ cr8r_avl_first()

◆ cr8r_avl_next()

◆ cr8r_avl_last()

◆ cr8r_avl_prev()

◆ cr8r_avl_lower_bound()

◆ cr8r_avl_upper_bound()

◆ cr8r_avl_delete()

◆ cr8r_avl_decrease()

◆ cr8r_avl_increase()

◆ cr8r_avl_first_post()

◆ cr8r_avl_next_post()

◆ cr8r_avl_sift_down()

◆ cr8r_avl_heapify()

◆ cr8r_avl_heappop_node()

◆ cr8r_avl_reorder()