39struct nonleaf_node :
public node_base
41 using key_type = KeyT;
42 using nonleaf_value_type = ValueT;
44 nonleaf_value_type value_nonleaf;
53 std::is_nothrow_default_constructible_v<nonleaf_value_type>;
55 static constexpr bool nothrow_eq_comparable_v =
56 noexcept(std::declval<key_type>() == std::declval<key_type>()) &&
57 noexcept(std::declval<nonleaf_value_type>() == std::declval<nonleaf_value_type>());
67 nonleaf_node(
const nonleaf_node& r) : node_base(r), value_nonleaf(r.value_nonleaf), low(r.low),
high(r.
high)
79 value_nonleaf = r.value_nonleaf;
83 bool operator==(
const nonleaf_node& r)
const noexcept(nothrow_eq_comparable_v)
85 return low == r.low &&
high == r.high && value_nonleaf == r.value_nonleaf;
88 std::string to_string()
const
90 std::ostringstream os;
91 os <<
"[" << low <<
"-" <<
high <<
")";
100struct node : node_base
102 using key_type = KeyT;
103 using leaf_value_type = ValueT;
104 using node_ptr = boost::intrusive_ptr<node>;
106 static size_t get_instance_count()
108#ifdef MDDS_DEBUG_NODE_BASE
109 return node_instance_count;
115 leaf_value_type value_leaf;
124 static constexpr bool nothrow_default_constructible_v = std::is_nothrow_default_constructible_v<key_type> &&
125 std::is_nothrow_default_constructible_v<leaf_value_type> &&
126 std::is_nothrow_default_constructible_v<node_ptr>;
128 static constexpr bool nothrow_eq_comparable_v =
129 noexcept(std::declval<key_type>() == std::declval<key_type>()) &&
130 noexcept(std::declval<leaf_value_type>() == std::declval<leaf_value_type>());
133 node() noexcept(nothrow_default_constructible_v) : node_base(true)
135#ifdef MDDS_DEBUG_NODE_BASE
136 ++node_instance_count;
144 node(
const node& r) : node_base(r), key(r.key)
146#ifdef MDDS_DEBUG_NODE_BASE
147 ++node_instance_count;
149 value_leaf = r.value_leaf;
161 value_leaf = r.value_leaf;
167#ifdef MDDS_DEBUG_NODE_BASE
168 --node_instance_count;
172 bool operator==(
const node& r)
const noexcept(nothrow_eq_comparable_v)
174 return key == r.key && value_leaf == r.value_leaf;
177 std::string to_string()
const
179 std::ostringstream os;
180 os <<
"[" << key <<
"]";
210 typedef typename T::node leaf_node;
211 typedef typename leaf_node::node_ptr leaf_node_ptr;
212 typedef typename T::nonleaf_node nonleaf_node;
213 typedef std::vector<nonleaf_node> nonleaf_node_pool_type;
215 tree_builder(nonleaf_node_pool_type& pool) : m_pool(pool), m_pool_pos(pool.begin()), m_pool_pos_end(pool.end())
218 nonleaf_node* build(
const leaf_node_ptr& left_leaf_node)
224 leaf_node_ptr node1 = left_leaf_node;
226 std::vector<nonleaf_node*> node_list;
229 leaf_node_ptr node2 = node1->next;
230 nonleaf_node* parent_node = make_parent_node(node1.get(), node2.get());
231 node_list.push_back(parent_node);
233 if (!node2 || !node2->next)
240 return build_tree_non_leaf(node_list);
246 assert(m_pool_pos != m_pool_pos_end);
248 nonleaf_node* parent_node = &(*m_pool_pos);
250 node1->parent = parent_node;
251 parent_node->left = node1;
254 node2->parent = parent_node;
255 parent_node->right = node2;
258 fill_nonleaf_parent_node(parent_node, node1, node2);
262 void fill_nonleaf_parent_node(nonleaf_node* parent_node,
const node_base* left_node,
const node_base* right_node)
267 parent_node->low = left_node->
is_leaf ?
static_cast<const leaf_node*
>(left_node)->key
268 :
static_cast<const nonleaf_node*
>(left_node)->low;
273 throw general_error(
"fill_nonleaf_parent_node: Having a left node is prerequisite.");
284 const auto* p =
static_cast<const leaf_node*
>(right_node);
286 parent_node->high = p->next->key;
288 parent_node->high = p->key;
292 parent_node->high =
static_cast<const nonleaf_node*
>(right_node)->high;
297 parent_node->high = left_node->
is_leaf ?
static_cast<const leaf_node*
>(left_node)->key
298 :
static_cast<const nonleaf_node*
>(left_node)->high;
302 nonleaf_node* build_tree_non_leaf(
const std::vector<nonleaf_node*>& node_list)
304 size_t node_count = node_list.size();
307 return node_list.front();
309 else if (node_count == 0)
312 std::vector<nonleaf_node*> new_node_list;
313 nonleaf_node* node1 =
nullptr;
314 typename std::vector<nonleaf_node*>::const_iterator it = node_list.begin();
315 typename std::vector<nonleaf_node*>::const_iterator it_end = node_list.end();
316 for (
bool even_itr =
false; it != it_end; ++it, even_itr = !even_itr)
320 nonleaf_node* node2 = *it;
321 nonleaf_node* parent_node = make_parent_node(node1, node2);
322 new_node_list.push_back(parent_node);
333 nonleaf_node* parent_node = make_parent_node(node1,
nullptr);
334 new_node_list.push_back(parent_node);
338 return build_tree_non_leaf(new_node_list);
341 nonleaf_node_pool_type& m_pool;
342 typename nonleaf_node_pool_type::iterator m_pool_pos;
343 typename nonleaf_node_pool_type::iterator m_pool_pos_end;
376SizeT count_leaf_nodes(
const node<KeyT, ValueT>* left_end,
const node<KeyT, ValueT>* right_end)
noexcept(
410 using node_list_type = std::vector<const node_base*>;
411 using tree_type =
typename TraitsT::tree_type;
414 static size_t dump(std::ostream& os,
const tree_type& tree,
const node_base* root_node)
419 node_list_type node_list;
420 node_list.push_back(root_node);
421 return dump_layer(os, tree, node_list, 0);
425 static size_t dump_layer(
426 std::ostream& os,
const tree_type& tree,
const node_list_type& node_list,
unsigned int level)
428 using leaf_type =
typename TraitsT::leaf_type;
429 using nonleaf_type =
typename TraitsT::nonleaf_type;
430 using to_string =
typename TraitsT::to_string;
432 if (node_list.empty())
435 size_t node_count = node_list.size();
437 bool is_leaf = node_list.front()->is_leaf;
438 os <<
"level " << level <<
':' << std::endl;
439 os <<
" type: " << (is_leaf ?
"leaf" :
"non-leaf") << std::endl;
440 os <<
" nodes:" << std::endl;
442 node_list_type new_list;
450 os <<
"*'" << std::endl;
456 const auto* pl =
static_cast<const leaf_type*
>(p);
457 os << to_string{tree}(*pl) <<
"'" << std::endl;
461 const auto* pnl =
static_cast<const nonleaf_type*
>(p);
462 os << to_string{tree}(*pnl) <<
"'" << std::endl;
466 new_list.push_back(pnl->left);
468 new_list.push_back(pnl->right);
472 if (!new_list.empty())
473 node_count += dump_layer(os, tree, new_list, level + 1);