#include <RBTree.h>

Inheritance diagram for swoc::detail::RBNode:

Collaboration diagram for swoc::detail::RBNode:

Classes
struct	Linkage
	Support for `IntrusiveDList`. More...

Public Types
enum class	Color { RED , BLACK }
	Node colors. More...

enum class	Direction { NONE , LEFT , RIGHT }
	Directional constants. More...

using	self_type = RBNode
	self reference type

Public Member Functions
	RBNode ()=default
	Default constructor.

virtual	~RBNode ()
	Force virtual destructor.

self_type *	child_at (Direction d) const

Direction	direction_of (self_type *const &n) const

Color	color () const

self_type *	left_most_descendant () const

Direction	flip (Direction d)

int	validate ()

self_type *	rotate (Direction dir)

self_type *	set_child (self_type *child, Direction dir)

self_type *	remove ()

void	clear_child (Direction dir)

Subclass hook methods
Color	_color {Color::RED}
	node color

self_type *	_parent {nullptr}
	parent node (needed for rotations)

self_type *	_left {nullptr}
	left child

self_type *	_right {nullptr}
	right child

self_type *	_next {nullptr}
	Next node.

self_type *	_prev {nullptr}
	Previous node.

virtual void	structure_fixup ()

virtual bool	structure_validate ()

void	replace_with (self_type *n)

self_type *	rebalance_after_insert ()
	Rebalance the tree starting at this node.

self_type *	rebalance_after_remove (Color c, Direction dir)

self_type *	ripple_structure_fixup ()

static self_type *	buildTree (self_type *&head, int n)
	Recursively build a balanced RB tree from a sorted linked list.

static self_type *	buildTree (self_type *&head, int n, bool isBlack)
	Called by buildTree above.

static void	printTree (self_type *root, std::string indent="", bool last=true)
	Recursively print the tree in a human-readable format.

Detailed Description

A node in a red/black tree.

This class provides only the basic tree operations. The container must provide the search and decision logic. This enables this class to be a base class for templated nodes with much less code duplication.

Definition at line 26 of file RBTree.h.

Member Typedef Documentation

◆ self_type

using swoc::detail::RBNode::self_type = RBNode

self reference type

Definition at line 27 of file RBTree.h.

Member Enumeration Documentation

◆ Color

enum class swoc::detail::RBNode::Color

strong

Node colors.

Definition at line 30 of file RBTree.h.

◆ Direction

enum class swoc::detail::RBNode::Direction

strong

Directional constants.

Definition at line 36 of file RBTree.h.

Constructor & Destructor Documentation

◆ ~RBNode()

virtual swoc::detail::RBNode::~RBNode ( )

inlinevirtual

Force virtual destructor.

Definition at line 46 of file RBTree.h.

Member Function Documentation

◆ buildTree() [1/2]

RBNode * swoc::detail::RBNode::buildTree	(	self_type *&	head,
		int	n )

static

Recursively build a balanced RB tree from a sorted linked list.

Constraints:

The list is sorted in ascending order.
A copy (not reference) of the head pointer is passed in.

Parameters

head	Copy of the head pointer of the list.
n	Number of nodes being processed at the current level.

Returns: self_type* The root node of the tree.

Definition at line 299 of file RBTree.cc.

◆ buildTree() [2/2]

RBNode * swoc::detail::RBNode::buildTree	(	self_type *&	head,
		int	n,
		bool	isBlack )

static

Called by buildTree above.

Definition at line 314 of file RBTree.cc.

◆ child_at()

RBNode * swoc::detail::RBNode::child_at ( Direction d ) const

Get the child in direction dir.

Parameters

d	Child direction.

Returns: A pointer to the child node, or nullptr if no child in that direction.

Definition at line 32 of file RBTree.cc.

◆ clear_child()

void swoc::detail::RBNode::clear_child ( RBNode::Direction dir )

inline

Remove the dir child.

Parameters

dir	Direction of child to remove.

The pointers in this and the child are updated as needed. It is not an error if there is no child in the direction dir.

Definition at line 245 of file RBTree.h.

◆ color()

RBNode::Color swoc::detail::RBNode::color ( ) const

inline

Returns: The color of the node.

Definition at line 235 of file RBTree.h.

◆ direction_of()

auto swoc::detail::RBNode::direction_of ( self_type *const & n ) const

inline

Get the direction of a child node n.

Parameters

n	Child node.

Returns: Direction of the child if n is a child, Direction::NONE if not.

Definition at line 230 of file RBTree.h.

◆ flip()

RBNode::Direction swoc::detail::RBNode::flip ( RBNode::Direction d )

inline

Reverse a direction

Returns: LEFT if d is RIGHT, RIGHT if d is LEFT, NONE otherwise.

Definition at line 240 of file RBTree.h.

◆ left_most_descendant()

auto swoc::detail::RBNode::left_most_descendant ( ) const

Returns: The left most descendant of this, or null ptr if no left child.

Definition at line 439 of file RBTree.cc.

◆ printTree()

void swoc::detail::RBNode::printTree	(	self_type *	root,
		std::string	indent = "",
		bool	last = true )

static

Recursively print the tree in a human-readable format.

Parameters

root	Root node of the tree.
indent	Indentation string.
last	Flag to indicate if the node is the last node.

Definition at line 371 of file RBTree.cc.

◆ rebalance_after_insert()

RBNode * swoc::detail::RBNode::rebalance_after_insert ( )

Rebalance the tree starting at this node.

The tree is rebalanced so that all of the invariants are true. The (potentially new) root of the tree is returned.

Returns: The root node of the tree after the rebalance.

Definition at line 110 of file RBTree.cc.

◆ rebalance_after_remove()

RBNode * swoc::detail::RBNode::rebalance_after_remove	(	Color	c,
		Direction	d )

Rebalance the tree after a deletion. Called on the lowest modified node.

Returns: The new root of the tree. Rebalance the tree root at this node after a removal.

Parameters

c	The color of the removed node.
d	The direction of the removed node from this.

Returns: The new root node.

Invariant: this is the parent of the removed node.

Rebalance tree after a deletion Called on the spliced in node or its parent, whichever is not NIL. This modifies the tree structure only if c is BLACK.

Parameters

c	The color of the removed node
d	Direction of removed node from its parent

Definition at line 231 of file RBTree.cc.

◆ remove()

RBNode * swoc::detail::RBNode::remove ( )

Remove this node from the tree. The tree is rebalanced after removal.

Returns: The new root node.

Definition at line 152 of file RBTree.cc.

◆ replace_with()

void swoc::detail::RBNode::replace_with ( self_type * n )

Replace this node with n.

Parameters

n	Replacement node.

Invariant: this is a non-order modifying replacement.

Definition at line 87 of file RBTree.cc.

◆ ripple_structure_fixup()

RBNode * swoc::detail::RBNode::ripple_structure_fixup ( )

Invoke structure_fixup on this node and its parents to the root.

Returns: The root node.

Note: This is used by the base class to inform subclasses of structure changes, starting from a leaf node up to the root node.

Definition at line 75 of file RBTree.cc.

◆ rotate()

RBNode * swoc::detail::RBNode::rotate ( Direction dir )

Rotate the subtree rooted at this node in the direction dir.

Parameters

dir	Direction of rotatoin.

Returns: The root node after rotation.

this node is rotated in to the position of its dir child and the child in the other direction becomes the new root node for the subtree. This operation is a no-op if there is no other child.

If this node has a parent then that parent's child pointer is updated as needed.

Definition at line 37 of file RBTree.cc.

◆ set_child()

RBNode * swoc::detail::RBNode::set_child	(	self_type *	child,
		Direction	dir )

Set the dir child of this node to child.

Parameters

child	Node to set as the child.
dir	Direction of the child location.

Returns: child

The internal pointers in both this and child are updated as needed. It is an error to call this if the specified child is already set.

Definition at line 62 of file RBTree.cc.

◆ structure_fixup()

virtual void swoc::detail::RBNode::structure_fixup ( )

inlinevirtual

Structural change notification.

This method is called if the structure of the subtree rooted at this node was changed. This makes it possible to keep subtree information nodes synchronized with the state of the tree efficiently.

This is intended a hook. The base method is empty so that subclasses are not required to override.

Reimplemented in swoc::DiscreteSpace< METRIC, PAYLOAD >::Node.

Definition at line 132 of file RBTree.h.

◆ structure_validate()

bool swoc::detail::RBNode::structure_validate ( )

inlinevirtual

Called from validate to perform any additional validation checks. Clients should chain this if they wish to perform additional checks.

Returns: true if the validation is successful, false otherwise.

Definition at line 253 of file RBTree.h.

◆ validate()

int swoc::detail::RBNode::validate ( )

Perform internal validation checks.

Returns: 0 on failure, black height of the tree on success.

Ensure that the local information associated with each node is correct globally This should only be called on debug builds as it breaks any efficiencies we have gained from our tree structure.

Definition at line 398 of file RBTree.cc.

Member Data Documentation

◆ _color

Color swoc::detail::RBNode::_color {Color::RED}

node color

Definition at line 205 of file RBTree.h.

◆ _left

self_type* swoc::detail::RBNode::_left {nullptr}

left child

Definition at line 207 of file RBTree.h.

◆ _next

self_type* swoc::detail::RBNode::_next {nullptr}

Next node.

Definition at line 209 of file RBTree.h.

◆ _parent

self_type* swoc::detail::RBNode::_parent {nullptr}

parent node (needed for rotations)

Definition at line 206 of file RBTree.h.

◆ _prev

self_type* swoc::detail::RBNode::_prev {nullptr}

Previous node.

Definition at line 210 of file RBTree.h.

◆ _right

self_type* swoc::detail::RBNode::_right {nullptr}

right child

Definition at line 208 of file RBTree.h.

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

Classes

Public Types

Public Member Functions

Subclass hook methods

Detailed Description

Member Typedef Documentation

◆ self_type

Member Enumeration Documentation

◆ Color

◆ Direction

Constructor & Destructor Documentation

◆ ~RBNode()

Member Function Documentation

◆ buildTree() [1/2]

◆ buildTree() [2/2]

◆ child_at()

◆ clear_child()

◆ color()

◆ direction_of()

◆ flip()

◆ left_most_descendant()

◆ printTree()

◆ rebalance_after_insert()

◆ rebalance_after_remove()

◆ remove()

◆ replace_with()

◆ ripple_structure_fixup()

◆ rotate()

◆ set_child()

◆ structure_fixup()

◆ structure_validate()

◆ validate()

Member Data Documentation

◆ _color

◆ _left

◆ _next

◆ _parent

◆ _prev

◆ _right