0

I defined a red-black tree node (with template):

struct rb_node {
    rb_node   *left;
    rb_node   *right;
    rb_node   *parent;
    value_type val;
    enum _Node_color { Black, Red } color;
};

Obviously, I can't create a sentinel node for the Test class, for example:

class Test {
private:
    int v;

public:
    explicit Test(int x) : v(x) {}
    bool operator<(const Test & t) const noexcept { return t.V() > v; }
    int V() const noexcept { return v; }
};

// ... In rb_node<Test>:
static const rb_node sentinel_node; // Wrong!

How to fix this problem without changing Test? --- I found that MSVC STL also uses sentinel nodes, but they solved this problem. How did they do it?

// In <xtree>
    
template <class _Value_type, class _Voidptr>
struct _Tree_node {
    using _Nodeptr   = _Rebind_pointer_t<_Voidptr, _Tree_node>;
    using value_type = _Value_type;
    _Nodeptr _Left; // left subtree, or smallest element if head
    _Nodeptr _Parent; // parent, or root of tree if head
    _Nodeptr _Right; // right subtree, or largest element if head
    char _Color; // _Red or _Black, _Black if head
    char _Isnil; // true only if head (also nil) node; TRANSITION, should be bool
    value_type _Myval = // the stored value, unused if head
        _Returns_exactly<value_type>(); // fake a viable constructor to workaround GH-2749
}
// ...
    void _Alloc_sentinel_and_proxy() {
        const auto _Scary = _Get_scary();
        auto&& _Alproxy   = _GET_PROXY_ALLOCATOR(_Alnode, _Getal());
        _Container_proxy_ptr<_Alnode> _Proxy(_Alproxy, *_Scary);
        _Scary->_Myhead = _Node::_Buyheadnode(_Getal());
        _Proxy._Release();
    }
273K
  • 29,503
  • 10
  • 41
  • 64
himu
  • 41
  • 2
  • 4
    `_Node_color` - Don't use such names, it's prohibited. See https://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier – 273K May 07 '23 at 07:08
  • `Wrong!` - please explain what is wrong there. `In rb_node:` - what is it? `rb_node` is not a class template. – 273K May 07 '23 at 07:11
  • Unfortunately the question is unclear. Maybe your defintion of `rb_node` is supposed to be a template? That's rather an important detail to miss out. – john May 07 '23 at 08:09
  • Maybe `static const rb_node sentinel_node;`. But that's rather obvious, so maybe something else. – john May 07 '23 at 08:10
  • You don't have to allocate, as @john says you just need to be able to refer to an instance of a node that you call guard node, using a (static) member variable in your tree class should do it. And yes that also means you should hide the node type as a internal/private data type of your tree class. The node type should never leak into client code. – Pepijn Kramer May 07 '23 at 08:17
  • 1
    One way to do that is to create a `Node_base` class that does *not* have user data, and a `Node` that inherits from `Node_base` that does have user data. The sentinel is the only node that is allocated as `Node_base`, all the real nodes are allocated as `Node`. The links have to be of type `Node_base*` and you need to cast them before obtaining a `Node` (use an inline accessor function to simplify this). Use a `static_cast` here. (This is against the core guidelines but those are not designed to apply to low-level code, just obtain an exception if needed). – n. m. could be an AI May 07 '23 at 08:48
  • 1
    MSVC seems to do this differently, they apparently allocate the sentinel as raw memory (not calling the constructor) and then construct all fields *except* `_Myval` in place within this raw memory. This may or may not be UB but this is OK, the standard library implementation is not user code, it may rely on UB or use something that is not C++ at all, as long as it works. – n. m. could be an AI May 07 '23 at 09:10
  • @n.m. That's what I mean. I have roughly understood the idea. Thank you for your help. :) – himu May 08 '23 at 03:14
  • @PepijnKramer @john I'm sorry about this. Yes, This is a struct defined inside the template class Tree (with template value_type) so it is actually In `Tree`. I am trying to implement some features of the STL, so I used some irregular name and omitted many details，which makes the problem unclear. – himu May 08 '23 at 03:25

0 Answers0