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

#include <rbt.hpp>

Collaboration diagram for LibXR::RBTree< Key >:

[legend]

Data Structures
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).

Private Member Functions
void	RbtreeInsert (BaseNode &node)

void	RbtreeInsertFixup (BaseNode *node)

void	RbtreeLeftRotate (BaseNode *x)

void	RbtreeRightRotate (BaseNode *y)

void	RbtreeDeleteFixup (BaseNode node, BaseNode parent)

template<typename Data , typename Func >
ErrorCode	RbtreeForeachStart (BaseNode *node, Func func)

template<typename Data , typename Func >
ErrorCode	RbtreeForeach (BaseNode *node, Func func)

void	RbtreeGetNum (BaseNode node, uint32_t count)

BaseNode *	Search (BaseNode *x, const Key &key)

Static Private Member Functions
template<typename Data , SizeLimitMode LimitMode>
static Node< Data > *	ToDerivedType (BaseNode *node)

Private Attributes
BaseNode *	root_ = nullptr
	红黑树的根节点 (Root node of the Red-Black Tree).

LibXR::Mutex	mutex_
	互斥锁，确保线程安全 (Mutex for thread-safety).

int(*	compare_fun_ )(const Key &, const Key &)
	键值比较函数 (Function for key comparison).

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();
  }

◆ RbtreeDeleteFixup()

template<typename Key >

void LibXR::RBTree< Key >::RbtreeDeleteFixup	(	BaseNode *	node,
		BaseNode *	parent )

inlineprivate

Definition at line 481 of file rbt.hpp.

  {
    BaseNode* other = nullptr;
 
    while ((!node || node->color == RbtColor::BLACK) && node != root_)
    {
      if (parent->left == node)
      {
        other = parent->right;
        if (other->color == RbtColor::RED)
        {
          other->color = RbtColor::BLACK;
          parent->color = RbtColor::RED;
          RbtreeLeftRotate(parent);
          other = parent->right;
        }
        if ((!other->left || other->left->color == RbtColor::BLACK) &&
            (!other->right || other->right->color == RbtColor::BLACK))
        {
          other->color = RbtColor::RED;
          node = parent;
          parent = node->parent;
        }
        else
        {
          if (!other->right || other->right->color == RbtColor::BLACK)
          {
            other->left->color = RbtColor::BLACK;
            other->color = RbtColor::RED;
            RbtreeRightRotate(other);
            other = parent->right;
          }
          other->color = parent->color;
          parent->color = RbtColor::BLACK;
          other->right->color = RbtColor::BLACK;
          RbtreeLeftRotate(parent);
          node = root_;
          break;
        }
      }
      else
      {
        other = parent->left;
        if (other->color == RbtColor::RED)
        {
          other->color = RbtColor::BLACK;
          parent->color = RbtColor::RED;
          RbtreeRightRotate(parent);
          other = parent->left;
        }
        if ((!other->left || other->left->color == RbtColor::BLACK) &&
            (!other->right || other->right->color == RbtColor::BLACK))
        {
          other->color = RbtColor::RED;
          node = parent;
          parent = node->parent;
        }
        else
        {
          if (!other->left || other->left->color == RbtColor::BLACK)
          {
            other->right->color = RbtColor::BLACK;
            other->color = RbtColor::RED;
            RbtreeLeftRotate(other);
            other = parent->left;
          }
          other->color = parent->color;
          parent->color = RbtColor::BLACK;
          other->left->color = RbtColor::BLACK;
          RbtreeRightRotate(parent);
          node = root_;
          break;
        }
      }
    }
    if (node)
    {
      node->color = RbtColor::BLACK;
    }
  }

◆ RbtreeForeach()

template<typename Key >

template<typename Data , typename Func >

ErrorCode LibXR::RBTree< Key >::RbtreeForeach	(	BaseNode *	node,
		Func	func )

inlineprivate

Definition at line 587 of file rbt.hpp.

  {
    if (!node)
    {
      return ErrorCode::OK;
    }
 
    if (ErrorCode code =
            RbtreeForeach<Data, Func>(reinterpret_cast<Node<Data>*>(node->left), func);
        code != ErrorCode::OK)
    {
      return code;
    }
 
    if (ErrorCode code = func(*reinterpret_cast<Node<Data>*>(node));
        code != ErrorCode::OK)
    {
      return code;
    }
 
    return RbtreeForeach<Data, Func>(reinterpret_cast<Node<Data>*>(node->right), func);
  }

◆ RbtreeForeachStart()

template<typename Key >

template<typename Data , typename Func >

ErrorCode LibXR::RBTree< Key >::RbtreeForeachStart	(	BaseNode *	node,
		Func	func )

inlineprivate

Definition at line 563 of file rbt.hpp.

  {
    if (!node)
    {
      return ErrorCode::OK;
    }
 
    if (ErrorCode code =
            RbtreeForeach<Data, Func>(reinterpret_cast<Node<Data>*>(node->left), func);
        code != ErrorCode::OK)
    {
      return code;
    }
 
    if (ErrorCode code = func(*reinterpret_cast<Node<Data>*>(node));
        code != ErrorCode::OK)
    {
      return code;
    }
 
    return RbtreeForeach<Data, Func>(reinterpret_cast<Node<Data>*>(node->right), func);
  }

◆ RbtreeGetNum()

template<typename Key >

void LibXR::RBTree< Key >::RbtreeGetNum	(	BaseNode *	node,
		uint32_t *	count )

inlineprivate

Definition at line 610 of file rbt.hpp.

  {
    if (!node)
    {
      return;
    }
    ++(*count);
    RbtreeGetNum(node->left, count);
    RbtreeGetNum(node->right, count);
  }

◆ RbtreeInsert()

template<typename Key >

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

inlineprivate

Definition at line 332 of file rbt.hpp.

  {
    BaseNode* parent = nullptr;
    BaseNode** current = &root_;
    while (*current)
    {
      parent = *current;
      current =
          (compare_fun_(node.key, parent->key) < 0) ? &parent->left : &parent->right;
    }
    node.parent = parent;
    *current = &node;
    RbtreeInsertFixup(&node);
  }

◆ RbtreeInsertFixup()

template<typename Key >

void LibXR::RBTree< Key >::RbtreeInsertFixup ( BaseNode * node )

inlineprivate

Definition at line 347 of file rbt.hpp.

  {
    BaseNode *parent = nullptr, *gparent = nullptr;
 
    while ((parent = node->parent) && parent->color == RbtColor::RED)
    {
      gparent = parent->parent;
 
      if (parent == gparent->left)
      {
        BaseNode* uncle = gparent->right;
        if (uncle && uncle->color == RbtColor::RED)
        {
          uncle->color = RbtColor::BLACK;
          parent->color = RbtColor::BLACK;
          gparent->color = RbtColor::RED;
          node = gparent;
          continue;
        }
 
        if (node == parent->right)
        {
          BaseNode* tmp = nullptr;
          RbtreeLeftRotate(parent);
          tmp = parent;
          parent = node;
          node = tmp;
        }
 
        parent->color = RbtColor::BLACK;
        gparent->color = RbtColor::RED;
        RbtreeRightRotate(gparent);
      }
      else
      {
        BaseNode* uncle = gparent->left;
        if (uncle && uncle->color == RbtColor::RED)
        {
          uncle->color = RbtColor::BLACK;
          parent->color = RbtColor::BLACK;
          gparent->color = RbtColor::RED;
          node = gparent;
          continue;
        }
 
        if (node == parent->left)
        {
          BaseNode* tmp = nullptr;
          RbtreeRightRotate(parent);
          tmp = parent;
          parent = node;
          node = tmp;
        }
 
        parent->color = RbtColor::BLACK;
        gparent->color = RbtColor::RED;
        RbtreeLeftRotate(gparent);
      }
    }
    root_->color = RbtColor::BLACK;
  }

◆ RbtreeLeftRotate()

template<typename Key >

void LibXR::RBTree< Key >::RbtreeLeftRotate ( BaseNode * x )

inlineprivate

Definition at line 409 of file rbt.hpp.

  {
    if (!x || !x->right)
    {
      return;
    }
 
    BaseNode* y = x->right;
    x->right = y->left;
    if (y->left)
    {
      y->left->parent = x;
    }
 
    y->parent = x->parent;
 
    if (!x->parent)
    {
      root_ = y;
    }
    else
    {
      if (x == x->parent->left)
      {
        x->parent->left = y;
      }
      else
      {
        x->parent->right = y;
      }
    }
 
    y->left = x;
    x->parent = y;
  }

◆ RbtreeRightRotate()

template<typename Key >

void LibXR::RBTree< Key >::RbtreeRightRotate ( BaseNode * y )

inlineprivate

Definition at line 445 of file rbt.hpp.

  {
    if (!y || !y->left)
    {
      return;
    }
 
    BaseNode* x = y->left;
    y->left = x->right;
    if (x->right)
    {
      x->right->parent = y;
    }
 
    x->parent = y->parent;
 
    if (!y->parent)
    {
      root_ = x;
    }
    else
    {
      if (y == y->parent->right)
      {
        y->parent->right = x;
      }
      else
      {
        y->parent->left = x;
      }
    }
 
    x->right = y;
    y->parent = x;
  }

◆ Search() [1/2]

template<typename Key >

BaseNode * LibXR::RBTree< Key >::Search	(	BaseNode *	x,
		const Key &	key )

inlineprivate

Definition at line 621 of file rbt.hpp.

  {
    while (x)
    {
      int cmp = compare_fun_(key, x->key);
      if (cmp == 0)
      {
        break;
      }
      x = cmp < 0 ? x->left : x->right;
    }
    return x;
  }

◆ Search() [2/2]

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;
  }

◆ ToDerivedType()

template<typename Key >

template<typename Data , SizeLimitMode LimitMode>

static Node< Data > * LibXR::RBTree< Key >::ToDerivedType ( BaseNode * node )

inlinestaticprivate

Definition at line 636 of file rbt.hpp.

  {
    if (node)
    {
      ASSERT(LibXR::SizeLimitCheck(LimitMode, sizeof(Data), node->size));
    }
    return static_cast<Node<Data>*>(node);
  }

Field Documentation

◆ compare_fun_

template<typename Key >

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

private

键值比较函数 (Function for key comparison).

Definition at line 329 of file rbt.hpp.

◆ mutex_

template<typename Key >

LibXR::Mutex LibXR::RBTree< Key >::mutex_

private

互斥锁，确保线程安全 (Mutex for thread-safety).

Definition at line 328 of file rbt.hpp.

◆ root_

template<typename Key >

BaseNode* LibXR::RBTree< Key >::root_ = nullptr

private

红黑树的根节点 (Root node of the Red-Black Tree).

Definition at line 327 of file rbt.hpp.

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

src/structure/rbt.hpp

Data Structures

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

◆ RbtColor

Constructor & Destructor Documentation

◆ RBTree()

Member Function Documentation

◆ Delete()

◆ Foreach()

◆ ForeachDisc()

◆ GetNum()

◆ Insert()

◆ RbtreeDeleteFixup()

◆ RbtreeForeach()

◆ RbtreeForeachStart()

◆ RbtreeGetNum()

◆ RbtreeInsert()

◆ RbtreeInsertFixup()

◆ RbtreeLeftRotate()

◆ RbtreeRightRotate()

◆ Search() [1/2]

◆ Search() [2/2]

◆ ToDerivedType()

Field Documentation

◆ compare_fun_

◆ mutex_

◆ root_