LibXR::RBTree< Key > Class Template Reference

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

#include <rbt.hpp>

Collaboration diagram for LibXR::RBTree< Key >:

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 23 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 29 of file rbt.hpp.

  {
    RED,   
    BLACK  
  };

Constructor & Destructor Documentation

RBTree()

template<typename Key >

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

inlineexplicit

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

Parameters

compare_fun

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

Definition at line 107 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 141 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 275 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 291 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 255 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 237 of file rbt.hpp.

  {
    mutex_.Lock();
    node.left = nullptr;
    node.right = nullptr;
    node.parent = nullptr;
    node.color = RbtColor::RED;
    node.key = key;
    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 485 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 591 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 567 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 614 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 336 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 351 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 413 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 449 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 625 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 122 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 640 of file rbt.hpp.

  {
    if (node)
    {
      Assert::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 333 of file rbt.hpp.

mutex_

template<typename Key >

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

private

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

Definition at line 332 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 331 of file rbt.hpp.

---

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

• src/structure/rbt.hpp