rb-tree.hpp File Reference

Red-Black Tree implementation for memory allocator. More...

#include <cstddef>

Include dependency graph for rb-tree.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces
namespace	hh
namespace	hh::rb_tree

Functions
template<typename RbNode >
void	hh::rb_tree::insert (RbNode *&root, RbNode *new_node)
	Inserts a new node into the Red-Black tree.
template<typename RbNode >
void	hh::rb_tree::remove (RbNode *&root, RbNode *node)
	Removes a node from the Red-Black tree.
template<typename RbNode >
RbNode *	hh::rb_tree::lower_bound (RbNode *root, std::size_t key, bool(*cmp)(std::size_t, std::size_t))
	Finds the smallest node with value >= key.
void	hh::rb_tree::set_color_red (std::size_t &value)
	Sets the color of a node to RED.
void	hh::rb_tree::set_color_black (std::size_t &value)
	Sets the color of a node to BLACK.
bool	hh::rb_tree::is_red (const std::size_t &value)
	Checks if a node is RED.
bool	hh::rb_tree::is_black (const std::size_t &value)
	Checks if a node is BLACK.
std::size_t	hh::rb_tree::get_value (const std::size_t &value)
	Extracts the actual value without the color bit.
bool	hh::rb_tree::get_color (const std::size_t &value)
	Gets the color bit value.
template<typename RbNode >
void	hh::rb_tree::left_rotate (RbNode *&root, RbNode *node)
	Performs a left rotation around a node.
template<typename RbNode >
void	hh::rb_tree::right_rotate (RbNode *&root, RbNode *node)
	Performs a right rotation around a node.
template<typename RbNode >
void	hh::rb_tree::fix_insert (RbNode *&root, RbNode *z)
	Fixes Red-Black tree properties after insertion.
template<typename RbNode >
void	hh::rb_tree::transplant (RbNode *&root, RbNode *u, RbNode *v)
	Replaces one subtree with another.
template<typename RbNode >
void	hh::rb_tree::fix_remove (RbNode *&root, RbNode *x, RbNode *x_parent)
	Fixes Red-Black tree properties after deletion.

Detailed Description

Red-Black Tree implementation for memory allocator.

This is a specialized Red-Black Tree implementation designed specifically for memory allocation purposes. It is NOT a general-purpose RB-tree.

Note

Users are responsible for node allocation and deallocation.

Warning

Bit 63 of the value field is RESERVED for Red-Black coloring.

Required Node Structure:

struct your_node {
    your_node *left, *right, *parent;
    std::size_t value;  // Bit 63 reserved for color
    // Your additional data members...
};