红黑树实现，支持泛型键和值，并提供线程安全操作 Red-Black Tree implementation supporting generic keys and values with thread-safe operations. More...

#include <rbt.hpp>

Classes
class	BaseNode
	红黑树的基本节点结构 / Base node structure of the Red-Black Tree. More...

class	Node
	红黑树的泛型数据节点，继承自 `BaseNode` Generic data node for Red-Black Tree, inheriting from `BaseNode`. More...

Public Types
enum class	RbtColor : uint8_t { RED , BLACK }
	定义红黑树节点的颜色 / Enumeration for node colors in Red-Black Tree. More...

Public Member Functions
	RBTree (int(*compare_fun)(const Key &, const Key &))
	构造函数，初始化红黑树 / Constructor initializing the Red-Black Tree.

template<typename Data , SizeLimitMode LimitMode = SizeLimitMode::MORE>
Node< Data > *	Search (const Key &key)
	搜索红黑树中的节点 / Search for a node in the Red-Black Tree.

void	Delete (BaseNode &node)
	从树中删除指定节点 / Delete a specified node from the tree.

template<typename KeyType >
void	Insert (BaseNode &node, KeyType &&key)
	在树中插入新节点 / Insert a new node into the tree.

uint32_t	GetNum ()
	获取树中的节点数量 / Get the number of nodes in the tree.

template<typename Data , typename Func , SizeLimitMode LimitMode = SizeLimitMode::MORE>
ErrorCode	Foreach (Func func)
	遍历红黑树并执行用户提供的操作 (Traverse the Red-Black Tree and apply a user-defined function).

template<typename Data >
Node< Data > *	ForeachDisc (Node< Data > *node)
	获取红黑树的下一个中序遍历节点 Get the next node in in-order traversal.

Detailed Description

template<typename Key>
class LibXR::RBTree< Key >

红黑树实现，支持泛型键和值，并提供线程安全操作 Red-Black Tree implementation supporting generic keys and values with thread-safe operations.

该类实现了自平衡二叉查找树（红黑树），以提供高效的插入、删除和查找操作。 This class implements a self-balancing binary search tree (Red-Black Tree) to provide efficient insert, delete, and search operations.

Template Parameters

Key	用作节点键的类型 / Type used as node key.

Definition at line 22 of file rbt.hpp.

Member Enumeration Documentation

◆ RbtColor

template<typename Key >

enum class LibXR::RBTree::RbtColor : uint8_t

strong

定义红黑树节点的颜色 / Enumeration for node colors in Red-Black Tree.

Enumerator
RED	红色节点 / Red node.
BLACK	黑色节点 / Black node.

Definition at line 28 of file rbt.hpp.

  {
    RED,   
    BLACK  
  };

Constructor & Destructor Documentation

◆ RBTree()

template<typename Key >

LibXR::RBTree< Key >::RBTree ( int(* compare_fun )(const Key &, const Key &) )

inlineexplicit

构造函数，初始化红黑树 / Constructor initializing the Red-Black Tree.

Parameters

compare_fun 比较函数指针，用于键值比较 / Comparison function pointer for key comparison.

Definition at line 106 of file rbt.hpp.

                                                              : compare_fun_(compare_fun)
  {
    ASSERT(compare_fun_);
  }

Member Function Documentation

◆ Delete()

template<typename Key >

void LibXR::RBTree< Key >::Delete ( BaseNode & node )

inline

从树中删除指定节点 / Delete a specified node from the tree.

Parameters

node	要删除的节点 / Node to be deleted.

Definition at line 139 of file rbt.hpp.

  {
    mutex_.Lock();
 
    BaseNode *child = nullptr, *parent = nullptr;
    RbtColor color = RbtColor::BLACK;
 
    if (node.left && node.right)
    {
      BaseNode* replace = node.right;
      while (replace->left)
      {
        replace = replace->left;
      }
 
      if (node.parent)
      {
        (node.parent->left == &node ? node.parent->left : node.parent->right) = replace;
      }
      else
      {
        root_ = replace;
      }
 
      child = replace->right;
      parent = replace->parent;
      color = replace->color;
 
      if (parent == &node)
      {
        parent = replace;
      }
      else
      {
        if (child)
        {
          child->parent = parent;
        }
 
        if (parent)
        {
          parent->left = child;
        }
 
        if (node.right)
        {
          replace->right = node.right;
          node.right->parent = replace;
        }
      }
 
      replace->parent = node.parent;
      replace->color = node.color;
      replace->left = node.left;
      node.left->parent = replace;
 
      if (color == RbtColor::BLACK)
      {
        RbtreeDeleteFixup(child, parent);
      }
      mutex_.Unlock();
      return;
    }
 
    child = node.left ? node.left : node.right;
    parent = node.parent;
    color = node.color;
 
    if (child)
    {
      child->parent = parent;
    }
 
    if (parent)
    {
      (parent->left == &node ? parent->left : parent->right) = child;
    }
    else
    {
      root_ = child;
    }
 
    if (color == RbtColor::BLACK)
    {
      RbtreeDeleteFixup(child, parent);
    }
    mutex_.Unlock();
  }

◆ Foreach()

template<typename Key >

template<typename Data , typename Func , SizeLimitMode LimitMode = SizeLimitMode::MORE>

ErrorCode LibXR::RBTree< Key >::Foreach ( Func func )

inline

遍历红黑树并执行用户提供的操作 (Traverse the Red-Black Tree and apply a user-defined function).

Template Parameters

Data	存储的数据类型 / Type of data stored in the node.
Func	用户定义的操作函数 / User-defined function to apply.
LimitMode	结构大小检查模式 / Size limit check mode.

Parameters

func	作用于每个节点的函数 / Function applied to each node.

Returns: 操作结果，成功返回 ErrorCode::OK Operation result: ErrorCode::OK on success.

Definition at line 271 of file rbt.hpp.

  {
    mutex_.Lock();
    ErrorCode result = RbtreeForeachStart<Data>(root_, func);
    mutex_.Unlock();
    return result;
  }

◆ ForeachDisc()

template<typename Key >

template<typename Data >

Node< Data > * LibXR::RBTree< Key >::ForeachDisc ( Node< Data > * node )

inline

获取红黑树的下一个中序遍历节点 Get the next node in in-order traversal.

Template Parameters

Data	存储的数据类型 / Type of data stored in the node.

Parameters

node	当前节点 / Current node.

Returns: 指向下一个节点的指针 / Pointer to the next node.

Definition at line 287 of file rbt.hpp.

  {
    mutex_.Lock();
    Node<Data>* result = nullptr;
    if (!node)
    {
      result = static_cast<Node<Data>*>(root_);
      while (result && result->left)
      {
        result = static_cast<Node<Data>*>(result->left);
      }
    }
    else if (node->right)
    {
      result = static_cast<Node<Data>*>(node->right);
      while (result && result->left)
      {
        result = static_cast<Node<Data>*>(result->left);
      }
    }
    else if (node->parent)
    {
      if (node == node->parent->left)
      {
        result = static_cast<Node<Data>*>(node->parent);
      }
      else
      {
        while (node->parent && node == node->parent->right)
        {
          node = static_cast<Node<Data>*>(node->parent);
        }
        result = static_cast<Node<Data>*>(node->parent);
      }
    }
    mutex_.Unlock();
    return result;
  }

◆ GetNum()

template<typename Key >

uint32_t LibXR::RBTree< Key >::GetNum ( )

inline

获取树中的节点数量 / Get the number of nodes in the tree.

Returns: 树中节点的数量 / Number of nodes in the tree.

Definition at line 251 of file rbt.hpp.

  {
    mutex_.Lock();
    uint32_t count = 0;
    RbtreeGetNum(root_, &count);
    mutex_.Unlock();
    return count;
  }

◆ Insert()

template<typename Key >

template<typename KeyType >

void LibXR::RBTree< Key >::Insert	(	BaseNode &	node,
		KeyType &&	key )

inline

在树中插入新节点 / Insert a new node into the tree.

Template Parameters

KeyType 插入键的类型 / Type of the key to insert.

Parameters

node	要插入的节点 / Node to insert.
key	节点键 / Key of the node.

Definition at line 235 of file rbt.hpp.

  {
    mutex_.Lock();
    node.left = nullptr;
    node.right = nullptr;
    node.parent = nullptr;
    node.color = RbtColor::RED;
    node.key = std::forward<KeyType>(key);
    RbtreeInsert(node);
    mutex_.Unlock();
  }

◆ Search()

template<typename Key >

template<typename Data , SizeLimitMode LimitMode = SizeLimitMode::MORE>

Node< Data > * LibXR::RBTree< Key >::Search ( const Key & key )

inline

搜索红黑树中的节点 / Search for a node in the Red-Black Tree.

Template Parameters

Data	存储的数据类型 / Type of data stored in the node.
LimitMode	结构大小检查模式 / Size limit check mode.

Parameters

key	要搜索的键 / Key to search for.

Returns: 指向找到的节点的指针，如果未找到返回 nullptr Pointer to the found node, or nullptr if not found.

Definition at line 120 of file rbt.hpp.

  {
    mutex_.Lock();
    Node<Data>* result = nullptr;
    if (root_)
    {
      if (BaseNode* found = Search(root_, key))
      {
        result = ToDerivedType<Data, LimitMode>(found);
      }
    }
    mutex_.Unlock();
    return result;
  }

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

src/structure/rbt.hpp

Classes

Public Types

Public Member Functions

Detailed Description

Member Enumeration Documentation

◆ RbtColor

Constructor & Destructor Documentation

◆ RBTree()

Member Function Documentation

◆ Delete()

◆ Foreach()

◆ ForeachDisc()

◆ GetNum()

◆ Insert()

◆ Search()