Detailed Description

The realtime ordered map offers strict O(log(N)) searching, inserting, and deleting operations with the Weak AVL Tree Rank Balance framework. The number of rotations after an operation are kept to a maximum of two, which neither the Red-Black Tree or AVL tree are able to achieve. However, there may be O(log(N)) rank changes, but these are efficient bit flip ops.

This makes the Weak AVL tree the leader in terms of minimal rotations and a hybrid of the search strengths of an AVL tree with the favorable fix-up maintenance of a Red-Black Tree. In fact, under a workload that is strictly insertions, the WAVL tree is identical to an AVL tree in terms of balance and shape, making it fast for searching while performing fewer rotations than the AVL tree. The implementation is also simpler than either of the other trees.

Data Fields
struct CCC_Tree_map_node *	root

size_t	count

size_t	key_offset

size_t	type_intruder_offset

size_t	sizeof_type

CCC_Key_comparator *	compare

CCC_Allocator *	allocate

void *	context

Field Documentation

◆ allocate

CCC_Allocator* CCC_Tree_map::allocate

An allocation function, if any.

◆ compare

CCC_Key_comparator* CCC_Tree_map::compare

The comparison function for three way comparison.

◆ context

void* CCC_Tree_map::context

Auxiliary data, if any.

◆ count

size_t CCC_Tree_map::count

The count of stored nodes in the tree.

◆ key_offset

size_t CCC_Tree_map::key_offset

The byte offset of the key in the user struct.

◆ root

struct CCC_Tree_map_node* CCC_Tree_map::root

The root of the tree or the sentinel end if empty.

◆ sizeof_type

size_t CCC_Tree_map::sizeof_type

The size of the user struct holding the intruder.

◆ type_intruder_offset

size_t CCC_Tree_map::type_intruder_offset

The byte offset of the intrusive element in the user struct.

The documentation for this struct was generated from the following file:

ccc/private/private_tree_map.h