hh::halloc::RBTreeDriver< T > Class Template Reference

Template wrapper for managing a Red-Black tree. More...

#include <RBTreeDriver.hpp>

Public Member Functions
	RBTreeDriver ()
	Default constructor - creates an empty tree.
	RBTreeDriver (T *node)
	Constructor with existing root node.
	RBTreeDriver (const RBTreeDriver &)=delete
	Copy constructor - deleted (move-only semantics).
RBTreeDriver &	operator= (const RBTreeDriver &)=delete
	Copy assignment - deleted (move-only semantics).
	RBTreeDriver (RBTreeDriver &&other)
	Move constructor - transfers ownership of tree.
RBTreeDriver &	operator= (RBTreeDriver &&other)
	Move assignment - transfers ownership of tree.
void	insert (T *node)
	Inserts a node into the RB-tree.
void	remove (T *node)
	Removes a node from the RB-tree.
T *	lower_bound (std::size_t key, bool(*cmp)(std::size_t, std::size_t))
	Finds the smallest node with value >= key using custom comparison.

Detailed Description

template<typename T>
class hh::halloc::RBTreeDriver< T >

Template wrapper for managing a Red-Black tree.

This class provides a convenient interface for RB-tree operations while maintaining ownership of the root pointer. It enforces move-only semantics to prevent accidental tree duplication.

Template Parameters

T	Node type (must have fields: value, left, right, parent)

Note

This class is move-only (no copy constructor/assignment)

The node type T must be compatible with hh::rb_tree functions

Constructor & Destructor Documentation

RBTreeDriver() [1/4]

template<typename T >

hh::halloc::RBTreeDriver< T >::RBTreeDriver ( )

inlineexplicit

Default constructor - creates an empty tree.

Postcondition

root == nullptr

RBTreeDriver() [2/4]

template<typename T >

hh::halloc::RBTreeDriver< T >::RBTreeDriver ( T *  node )

inlineexplicit

Constructor with existing root node.

Parameters

node	Pointer to existing RB-tree root

Postcondition

root == node

Note

Caller transfers ownership of the tree to this driver

RBTreeDriver() [3/4]

template<typename T >

hh::halloc::RBTreeDriver< T >::RBTreeDriver ( const RBTreeDriver< T > &  )

delete

Copy constructor - deleted (move-only semantics).

RBTreeDriver() [4/4]

template<typename T >

hh::halloc::RBTreeDriver< T >::RBTreeDriver ( RBTreeDriver< T > &&  other )

inline

Move constructor - transfers ownership of tree.

Parameters

other

Source driver (will be left with nullptr root)

Postcondition

this->root == other.root (original value)

other.root == nullptr

Member Function Documentation

insert()

template<typename T >

void hh::halloc::RBTreeDriver< T >::insert ( T *  node )

inline

Inserts a node into the RB-tree.

Delegates to hh::rb_tree::insert, which handles:

• Binary search tree insertion
• Red-Black tree property restoration
• Root updates

Parameters

node	Node to insert (must not already be in tree)

Precondition

node != nullptr

node is not already in the tree

Postcondition

Tree contains node

RB-tree properties are maintained

Note

Time complexity: O(log n)

lower_bound()

template<typename T >

T * hh::halloc::RBTreeDriver< T >::lower_bound ( std::size_t  key, bool(*)(std::size_t, std::size_t)  cmp  )

inline

Finds the smallest node with value >= key using custom comparison.

Delegates to hh::rb_tree::lower_bound for efficient search.

Parameters

key	Search key
cmp	Comparison function: returns true if first >= second

Returns

Pointer to node with smallest value >= key, or nullptr if no such node

Precondition

cmp != nullptr

Postcondition

Return value is nullptr or points to node in tree

Note

Time complexity: O(log n)

Used for best-fit allocation (find smallest free block >= requested size)

operator=() [1/2]

template<typename T >

RBTreeDriver & hh::halloc::RBTreeDriver< T >::operator= ( const RBTreeDriver< T > &  )

delete

Copy assignment - deleted (move-only semantics).

operator=() [2/2]

template<typename T >

RBTreeDriver & hh::halloc::RBTreeDriver< T >::operator= ( RBTreeDriver< T > &&  other )

inline

Move assignment - transfers ownership of tree.

Parameters

other

Source driver (will be left with nullptr root)

Returns

Reference to this driver

Postcondition

this->root == other.root (original value)

other.root == nullptr

remove()

template<typename T >

void hh::halloc::RBTreeDriver< T >::remove ( T *  node )

inline

Removes a node from the RB-tree.

Delegates to hh::rb_tree::remove, which handles:

• Binary search tree deletion
• Red-Black tree property restoration
• Root updates

Parameters

node	Node to remove (must be in tree)

Precondition

node != nullptr

node is in the tree

Postcondition

Tree does not contain node

RB-tree properties are maintained

Note

Time complexity: O(log n)

Warning

Do not call this after modifying node->value (tree uses value for comparisons)

---

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

• halloc/includes/RBTreeDriver.hpp