Loading...
Searching...
No Matches
node.hpp
// SPDX-FileCopyrightText: 2008 - 2025 Kohei Yoshida
//
// SPDX-License-Identifier: MIT
#pragma once
#include "mdds/global.hpp"
#include <iostream>
#include <vector>
#include <cassert>
#include <sstream>
#include <boost/intrusive_ptr.hpp>
namespace mdds { namespace st { namespace detail {
#ifdef MDDS_DEBUG_NODE_BASE
inline std::size_t node_instance_count = 0;
#endif
struct node_base
{
node_base* parent;
bool is_leaf;
node_base(bool _is_leaf) noexcept : parent(nullptr), is_leaf(_is_leaf)
{}
node_base(const node_base& r) noexcept : parent(nullptr), is_leaf(r.is_leaf)
{}
};
template<typename KeyT, typename ValueT>
struct nonleaf_node : public node_base
{
using key_type = KeyT;
using nonleaf_value_type = ValueT;
nonleaf_value_type value_nonleaf;
key_type low = {};
key_type high = {};
node_base* left = nullptr;
node_base* right = nullptr;
static constexpr bool nothrow_default_constructible_v = std::is_nothrow_default_constructible_v<key_type> &&
std::is_nothrow_default_constructible_v<nonleaf_value_type>;
static constexpr bool nothrow_eq_comparable_v =
noexcept(std::declval<key_type>() == std::declval<key_type>()) &&
noexcept(std::declval<nonleaf_value_type>() == std::declval<nonleaf_value_type>());
public:
nonleaf_node() noexcept(nothrow_default_constructible_v) : node_base(false), value_nonleaf()
{}
nonleaf_node(const nonleaf_node& r) : node_base(r), value_nonleaf(r.value_nonleaf), low(r.low), high(r.high)
{}
nonleaf_node& operator=(const nonleaf_node& r)
{
if (this == &r)
// assignment to self.
return *this;
value_nonleaf = r.value_nonleaf;
return *this;
}
bool operator==(const nonleaf_node& r) const noexcept(nothrow_eq_comparable_v)
{
return low == r.low && high == r.high && value_nonleaf == r.value_nonleaf;
}
bool operator!=(const nonleaf_node& r) const noexcept(nothrow_eq_comparable_v)
{
return !operator==(r);
}
std::string to_string() const
{
std::ostringstream os;
os << "[" << low << "-" << high << ")";
return os.str();
}
};
template<typename KeyT, typename ValueT>
struct node : node_base
{
using key_type = KeyT;
using leaf_value_type = ValueT;
using node_ptr = boost::intrusive_ptr<node>;
static size_t get_instance_count()
{
#ifdef MDDS_DEBUG_NODE_BASE
return node_instance_count;
#else
return 0;
#endif
}
leaf_value_type value_leaf;
key_type key = {};
node_ptr prev;
node_ptr next;
std::size_t refcount = 0;
static constexpr bool nothrow_default_constructible_v = std::is_nothrow_default_constructible_v<key_type> &&
std::is_nothrow_default_constructible_v<leaf_value_type> &&
std::is_nothrow_default_constructible_v<node_ptr>;
static constexpr bool nothrow_eq_comparable_v =
noexcept(std::declval<key_type>() == std::declval<key_type>()) &&
noexcept(std::declval<leaf_value_type>() == std::declval<leaf_value_type>());
public:
node() noexcept(nothrow_default_constructible_v) : node_base(true)
{
#ifdef MDDS_DEBUG_NODE_BASE
++node_instance_count;
#endif
}
node(const node& r) : node_base(r), key(r.key)
{
#ifdef MDDS_DEBUG_NODE_BASE
++node_instance_count;
#endif
value_leaf = r.value_leaf;
}
node& operator=(const node& r)
{
if (this == &r)
// assignment to self.
return *this;
value_leaf = r.value_leaf;
return *this;
}
~node()
{
#ifdef MDDS_DEBUG_NODE_BASE
--node_instance_count;
#endif
}
bool operator==(const node& r) const noexcept(nothrow_eq_comparable_v)
{
return key == r.key && value_leaf == r.value_leaf;
}
bool operator!=(const node& r) const noexcept(nothrow_eq_comparable_v)
{
return !operator==(r);
}
std::string to_string() const
{
std::ostringstream os;
os << "[" << key << "]";
return os.str();
}
};
template<typename KeyT, typename ValueT>
inline void intrusive_ptr_add_ref(node<KeyT, ValueT>* p)
{
++p->refcount;
}
template<typename KeyT, typename ValueT>
inline void intrusive_ptr_release(node<KeyT, ValueT>* p)
{
--p->refcount;
if (!p->refcount)
delete p;
}
template<typename NodePtrT>
void link_nodes(NodePtrT& left, NodePtrT& right)
{
left->next = right;
right->prev = left;
}
template<typename T>
class tree_builder
{
public:
typedef typename T::node leaf_node;
typedef typename leaf_node::node_ptr leaf_node_ptr;
typedef typename T::nonleaf_node nonleaf_node;
typedef std::vector<nonleaf_node> nonleaf_node_pool_type;
tree_builder(nonleaf_node_pool_type& pool) : m_pool(pool), m_pool_pos(pool.begin()), m_pool_pos_end(pool.end())
{}
nonleaf_node* build(const leaf_node_ptr& left_leaf_node)
{
if (!left_leaf_node)
// The left leaf node is empty. Nothing to build.
return nullptr;
leaf_node_ptr node1 = left_leaf_node;
std::vector<nonleaf_node*> node_list;
while (true)
{
leaf_node_ptr node2 = node1->next;
nonleaf_node* parent_node = make_parent_node(node1.get(), node2.get());
node_list.push_back(parent_node);
if (!node2 || !node2->next)
// no more nodes. Break out of the loop.
break;
node1 = node2->next;
}
return build_tree_non_leaf(node_list);
}
private:
nonleaf_node* make_parent_node(node_base* node1, node_base* node2)
{
assert(m_pool_pos != m_pool_pos_end);
nonleaf_node* parent_node = &(*m_pool_pos);
++m_pool_pos;
node1->parent = parent_node;
parent_node->left = node1;
if (node2)
{
node2->parent = parent_node;
parent_node->right = node2;
}
fill_nonleaf_parent_node(parent_node, node1, node2);
return parent_node;
}
void fill_nonleaf_parent_node(nonleaf_node* parent_node, const node_base* left_node, const node_base* right_node)
{
// Parent node should carry the range of all of its child nodes.
if (left_node)
{
parent_node->low = left_node->is_leaf ? static_cast<const leaf_node*>(left_node)->key
: static_cast<const nonleaf_node*>(left_node)->low;
}
else
{
// Having a left node is prerequisite.
throw general_error("fill_nonleaf_parent_node: Having a left node is prerequisite.");
}
if (right_node)
{
if (right_node->is_leaf)
{
// When the child nodes are leaf nodes, the upper bound
// must be the value of the node that comes after the
// right leaf node (if such node exists).
const auto* p = static_cast<const leaf_node*>(right_node);
if (p->next)
parent_node->high = p->next->key;
else
parent_node->high = p->key;
}
else
{
parent_node->high = static_cast<const nonleaf_node*>(right_node)->high;
}
}
else
{
parent_node->high = left_node->is_leaf ? static_cast<const leaf_node*>(left_node)->key
: static_cast<const nonleaf_node*>(left_node)->high;
}
}
nonleaf_node* build_tree_non_leaf(const std::vector<nonleaf_node*>& node_list)
{
size_t node_count = node_list.size();
if (node_count == 1)
{
return node_list.front();
}
else if (node_count == 0)
return nullptr;
std::vector<nonleaf_node*> new_node_list;
nonleaf_node* node1 = nullptr;
typename std::vector<nonleaf_node*>::const_iterator it = node_list.begin();
typename std::vector<nonleaf_node*>::const_iterator it_end = node_list.end();
for (bool even_itr = false; it != it_end; ++it, even_itr = !even_itr)
{
if (even_itr)
{
nonleaf_node* node2 = *it;
nonleaf_node* parent_node = make_parent_node(node1, node2);
new_node_list.push_back(parent_node);
node1 = nullptr;
node2 = nullptr;
}
else
node1 = *it;
}
if (node1)
{
// Un-paired node still needs a parent...
nonleaf_node* parent_node = make_parent_node(node1, nullptr);
new_node_list.push_back(parent_node);
}
// Move up one level, and do the same procedure until the root node is reached.
return build_tree_non_leaf(new_node_list);
}
nonleaf_node_pool_type& m_pool;
typename nonleaf_node_pool_type::iterator m_pool_pos;
typename nonleaf_node_pool_type::iterator m_pool_pos_end;
};
template<typename KeyT, typename ValueT>
void disconnect_all_nodes(node<KeyT, ValueT>* p)
{
if (!p)
return;
p->prev.reset();
p->next.reset();
p->parent = nullptr;
}
template<typename KeyT, typename ValueT>
void disconnect_leaf_nodes(node<KeyT, ValueT>* left_node, node<KeyT, ValueT>* right_node)
{
if (!left_node || !right_node)
return;
// Go through all leaf nodes, and disconnect their links.
auto* cur_node = left_node;
do
{
auto* next_node = cur_node->next.get();
disconnect_all_nodes(cur_node);
cur_node = next_node;
} while (cur_node != right_node);
disconnect_all_nodes(right_node);
}
template<typename SizeT, typename KeyT, typename ValueT>
SizeT count_leaf_nodes(const node<KeyT, ValueT>* left_end, const node<KeyT, ValueT>* right_end) noexcept(
noexcept(++std::declval<SizeT&>()))
{
SizeT leaf_count = 1;
const auto* p = left_end;
const auto* p_end = right_end;
for (; p != p_end; p = p->next.get(), ++leaf_count)
;
return leaf_count;
}
inline size_t count_needed_nonleaf_nodes(size_t leaf_count)
{
size_t nonleaf_count = 0;
while (true)
{
if (leaf_count == 1)
break;
if ((leaf_count % 2) == 1)
// Add one to make it an even number.
++leaf_count;
leaf_count /= 2;
nonleaf_count += leaf_count;
}
return nonleaf_count;
}
template<typename TraitsT>
class tree_dumper
{
using node_list_type = std::vector<const node_base*>;
using tree_type = typename TraitsT::tree_type;
public:
static size_t dump(std::ostream& os, const tree_type& tree, const node_base* root_node)
{
if (!root_node)
return 0;
node_list_type node_list;
node_list.push_back(root_node);
return dump_layer(os, tree, node_list, 0);
}
private:
static size_t dump_layer(
std::ostream& os, const tree_type& tree, const node_list_type& node_list, unsigned int level)
{
using leaf_type = typename TraitsT::leaf_type;
using nonleaf_type = typename TraitsT::nonleaf_type;
using to_string = typename TraitsT::to_string;
if (node_list.empty())
return 0;
size_t node_count = node_list.size();
bool is_leaf = node_list.front()->is_leaf;
os << "level " << level << ':' << std::endl;
os << " type: " << (is_leaf ? "leaf" : "non-leaf") << std::endl;
os << " nodes:" << std::endl;
node_list_type new_list;
for (const node_base* p : node_list)
{
os << " - '";
if (!p)
{
os << "*'" << std::endl;
continue;
}
if (p->is_leaf)
{
const auto* pl = static_cast<const leaf_type*>(p);
os << to_string{tree}(*pl) << "'" << std::endl;
continue;
}
const auto* pnl = static_cast<const nonleaf_type*>(p);
os << to_string{tree}(*pnl) << "'" << std::endl;
if (pnl->left)
{
new_list.push_back(pnl->left);
if (pnl->right)
new_list.push_back(pnl->right);
}
}
if (!new_list.empty())
node_count += dump_layer(os, tree, new_list, level + 1);
return node_count;
}
};
}}} // namespace mdds::st::detail
mdds::general_error
Definition global.hpp:60
mdds::st::detail::tree_dumper
Definition node.hpp:419
mdds::st::detail::node_base
Definition node.hpp:25
mdds::st::detail::node_base::is_leaf
bool is_leaf
parent nonleaf_node
Definition node.hpp:27
mdds::st::detail::node
Definition node.hpp:106
mdds::st::detail::node::operator=
node & operator=(const node &r)
Definition node.hpp:160
mdds::st::detail::node::node
node(const node &r)
Definition node.hpp:149
mdds::st::detail::node< key_type, leaf_value_type >::refcount
std::size_t refcount
Definition node.hpp:127
mdds::st::detail::node< key_type, leaf_value_type >::next
node_ptr next
Definition node.hpp:125
mdds::st::detail::nonleaf_node
Definition node.hpp:40
mdds::st::detail::nonleaf_node::operator=
nonleaf_node & operator=(const nonleaf_node &r)
Definition node.hpp:73
mdds::st::detail::nonleaf_node< key_type, nonleaf_value_type >::nothrow_default_constructible_v
static constexpr bool nothrow_default_constructible_v
Definition node.hpp:52
mdds::st::detail::nonleaf_node::nonleaf_node
nonleaf_node(const nonleaf_node &r)
Definition node.hpp:67
mdds::st::detail::nonleaf_node< key_type, nonleaf_value_type >::right
node_base * right
Definition node.hpp:50
mdds::st::detail::nonleaf_node< key_type, nonleaf_value_type >::left
node_base * left
Definition node.hpp:49
mdds::st::detail::nonleaf_node< key_type, nonleaf_value_type >::high
key_type high
Definition node.hpp:47