mdds
Loading...
Searching...
No Matches
node.hpp
1// SPDX-FileCopyrightText: 2008 - 2025 Kohei Yoshida
2//
3// SPDX-License-Identifier: MIT
4
5#pragma once
6
7#include "mdds/global.hpp"
8
9#include <iostream>
10#include <vector>
11#include <cassert>
12#include <sstream>
13
14#include <boost/intrusive_ptr.hpp>
15
16namespace mdds { namespace st { namespace detail {
17
18#ifdef MDDS_DEBUG_NODE_BASE
19
20inline std::size_t node_instance_count = 0;
21
22#endif
23
24struct node_base
25{
26 node_base* parent;
27 bool is_leaf;
28
29 node_base(bool _is_leaf) noexcept : parent(nullptr), is_leaf(_is_leaf)
30 {}
31 node_base(const node_base& r) noexcept : parent(nullptr), is_leaf(r.is_leaf)
32 {}
33};
34
38template<typename KeyT, typename ValueT>
39struct nonleaf_node : public node_base
40{
41 using key_type = KeyT;
42 using nonleaf_value_type = ValueT;
43
44 nonleaf_value_type value_nonleaf;
45
46 key_type low = {};
47 key_type high = {};
48
49 node_base* left = nullptr;
50 node_base* right = nullptr;
51
52 static constexpr bool nothrow_default_constructible_v = std::is_nothrow_default_constructible_v<key_type> &&
53 std::is_nothrow_default_constructible_v<nonleaf_value_type>;
54
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>());
58
59public:
60 nonleaf_node() noexcept(nothrow_default_constructible_v) : node_base(false), value_nonleaf()
61 {}
62
67 nonleaf_node(const nonleaf_node& r) : node_base(r), value_nonleaf(r.value_nonleaf), low(r.low), high(r.high)
68 {}
69
73 nonleaf_node& operator=(const nonleaf_node& r)
74 {
75 if (this == &r)
76 // assignment to self.
77 return *this;
78
79 value_nonleaf = r.value_nonleaf;
80 return *this;
81 }
82
83 bool operator==(const nonleaf_node& r) const noexcept(nothrow_eq_comparable_v)
84 {
85 return low == r.low && high == r.high && value_nonleaf == r.value_nonleaf;
86 }
87
88 std::string to_string() const
89 {
90 std::ostringstream os;
91 os << "[" << low << "-" << high << ")";
92 return os.str();
93 }
94};
95
99template<typename KeyT, typename ValueT>
100struct node : node_base
101{
102 using key_type = KeyT;
103 using leaf_value_type = ValueT;
104 using node_ptr = boost::intrusive_ptr<node>;
105
106 static size_t get_instance_count()
107 {
108#ifdef MDDS_DEBUG_NODE_BASE
109 return node_instance_count;
110#else
111 return 0;
112#endif
113 }
114
115 leaf_value_type value_leaf;
116
117 key_type key = {};
118
119 node_ptr prev;
120 node_ptr next;
121
122 std::size_t refcount = 0;
123
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>;
127
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>());
131
132public:
133 node() noexcept(nothrow_default_constructible_v) : node_base(true)
134 {
135#ifdef MDDS_DEBUG_NODE_BASE
136 ++node_instance_count;
137#endif
138 }
139
144 node(const node& r) : node_base(r), key(r.key)
145 {
146#ifdef MDDS_DEBUG_NODE_BASE
147 ++node_instance_count;
148#endif
149 value_leaf = r.value_leaf;
150 }
151
155 node& operator=(const node& r)
156 {
157 if (this == &r)
158 // assignment to self.
159 return *this;
160
161 value_leaf = r.value_leaf;
162 return *this;
163 }
164
165 ~node()
166 {
167#ifdef MDDS_DEBUG_NODE_BASE
168 --node_instance_count;
169#endif
170 }
171
172 bool operator==(const node& r) const noexcept(nothrow_eq_comparable_v)
173 {
174 return key == r.key && value_leaf == r.value_leaf;
175 }
176
177 std::string to_string() const
178 {
179 std::ostringstream os;
180 os << "[" << key << "]";
181 return os.str();
182 }
183};
184
185template<typename KeyT, typename ValueT>
186inline void intrusive_ptr_add_ref(node<KeyT, ValueT>* p)
187{
188 ++p->refcount;
189}
190
191template<typename KeyT, typename ValueT>
192inline void intrusive_ptr_release(node<KeyT, ValueT>* p)
193{
194 --p->refcount;
195 if (!p->refcount)
196 delete p;
197}
198
199template<typename NodePtrT>
200void link_nodes(NodePtrT& left, NodePtrT& right)
201{
202 left->next = right;
203 right->prev = left;
204}
205
206template<typename T>
207class tree_builder
208{
209public:
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;
214
215 tree_builder(nonleaf_node_pool_type& pool) : m_pool(pool), m_pool_pos(pool.begin()), m_pool_pos_end(pool.end())
216 {}
217
218 nonleaf_node* build(const leaf_node_ptr& left_leaf_node)
219 {
220 if (!left_leaf_node)
221 // The left leaf node is empty. Nothing to build.
222 return nullptr;
223
224 leaf_node_ptr node1 = left_leaf_node;
225
226 std::vector<nonleaf_node*> node_list;
227 while (true)
228 {
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);
232
233 if (!node2 || !node2->next)
234 // no more nodes. Break out of the loop.
235 break;
236
237 node1 = node2->next;
238 }
239
240 return build_tree_non_leaf(node_list);
241 }
242
243private:
244 nonleaf_node* make_parent_node(node_base* node1, node_base* node2)
245 {
246 assert(m_pool_pos != m_pool_pos_end);
247
248 nonleaf_node* parent_node = &(*m_pool_pos);
249 ++m_pool_pos;
250 node1->parent = parent_node;
251 parent_node->left = node1;
252 if (node2)
253 {
254 node2->parent = parent_node;
255 parent_node->right = node2;
256 }
257
258 fill_nonleaf_parent_node(parent_node, node1, node2);
259 return parent_node;
260 }
261
262 void fill_nonleaf_parent_node(nonleaf_node* parent_node, const node_base* left_node, const node_base* right_node)
263 {
264 // Parent node should carry the range of all of its child nodes.
265 if (left_node)
266 {
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;
269 }
270 else
271 {
272 // Having a left node is prerequisite.
273 throw general_error("fill_nonleaf_parent_node: Having a left node is prerequisite.");
274 }
275
276 if (right_node)
277 {
278 if (right_node->is_leaf)
279 {
280 // When the child nodes are leaf nodes, the upper bound
281 // must be the value of the node that comes after the
282 // right leaf node (if such node exists).
283
284 const auto* p = static_cast<const leaf_node*>(right_node);
285 if (p->next)
286 parent_node->high = p->next->key;
287 else
288 parent_node->high = p->key;
289 }
290 else
291 {
292 parent_node->high = static_cast<const nonleaf_node*>(right_node)->high;
293 }
294 }
295 else
296 {
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;
299 }
300 }
301
302 nonleaf_node* build_tree_non_leaf(const std::vector<nonleaf_node*>& node_list)
303 {
304 size_t node_count = node_list.size();
305 if (node_count == 1)
306 {
307 return node_list.front();
308 }
309 else if (node_count == 0)
310 return nullptr;
311
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)
317 {
318 if (even_itr)
319 {
320 nonleaf_node* node2 = *it;
321 nonleaf_node* parent_node = make_parent_node(node1, node2);
322 new_node_list.push_back(parent_node);
323 node1 = nullptr;
324 node2 = nullptr;
325 }
326 else
327 node1 = *it;
328 }
329
330 if (node1)
331 {
332 // Un-paired node still needs a parent...
333 nonleaf_node* parent_node = make_parent_node(node1, nullptr);
334 new_node_list.push_back(parent_node);
335 }
336
337 // Move up one level, and do the same procedure until the root node is reached.
338 return build_tree_non_leaf(new_node_list);
339 }
340
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;
344};
345
346template<typename KeyT, typename ValueT>
347void disconnect_all_nodes(node<KeyT, ValueT>* p)
348{
349 if (!p)
350 return;
351
352 p->prev.reset();
353 p->next.reset();
354 p->parent = nullptr;
355}
356
357template<typename KeyT, typename ValueT>
358void disconnect_leaf_nodes(node<KeyT, ValueT>* left_node, node<KeyT, ValueT>* right_node)
359{
360 if (!left_node || !right_node)
361 return;
362
363 // Go through all leaf nodes, and disconnect their links.
364 auto* cur_node = left_node;
365 do
366 {
367 auto* next_node = cur_node->next.get();
368 disconnect_all_nodes(cur_node);
369 cur_node = next_node;
370 } while (cur_node != right_node);
371
372 disconnect_all_nodes(right_node);
373}
374
375template<typename SizeT, typename KeyT, typename ValueT>
376SizeT count_leaf_nodes(const node<KeyT, ValueT>* left_end, const node<KeyT, ValueT>* right_end) noexcept(
377 noexcept(++std::declval<SizeT&>()))
378{
379 SizeT leaf_count = 1;
380 const auto* p = left_end;
381 const auto* p_end = right_end;
382 for (; p != p_end; p = p->next.get(), ++leaf_count)
383 ;
384
385 return leaf_count;
386}
387
388inline size_t count_needed_nonleaf_nodes(size_t leaf_count)
389{
390 size_t nonleaf_count = 0;
391 while (true)
392 {
393 if (leaf_count == 1)
394 break;
395
396 if ((leaf_count % 2) == 1)
397 // Add one to make it an even number.
398 ++leaf_count;
399
400 leaf_count /= 2;
401 nonleaf_count += leaf_count;
402 }
403
404 return nonleaf_count;
405}
406
407template<typename TraitsT>
409{
410 using node_list_type = std::vector<const node_base*>;
411 using tree_type = typename TraitsT::tree_type;
412
413public:
414 static size_t dump(std::ostream& os, const tree_type& tree, const node_base* root_node)
415 {
416 if (!root_node)
417 return 0;
418
419 node_list_type node_list;
420 node_list.push_back(root_node);
421 return dump_layer(os, tree, node_list, 0);
422 }
423
424private:
425 static size_t dump_layer(
426 std::ostream& os, const tree_type& tree, const node_list_type& node_list, unsigned int level)
427 {
428 using leaf_type = typename TraitsT::leaf_type;
429 using nonleaf_type = typename TraitsT::nonleaf_type;
430 using to_string = typename TraitsT::to_string;
431
432 if (node_list.empty())
433 return 0;
434
435 size_t node_count = node_list.size();
436
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;
441
442 node_list_type new_list;
443
444 for (const node_base* p : node_list)
445 {
446 os << " - '";
447
448 if (!p)
449 {
450 os << "*'" << std::endl;
451 continue;
452 }
453
454 if (p->is_leaf)
455 {
456 const auto* pl = static_cast<const leaf_type*>(p);
457 os << to_string{tree}(*pl) << "'" << std::endl;
458 continue;
459 }
460
461 const auto* pnl = static_cast<const nonleaf_type*>(p);
462 os << to_string{tree}(*pnl) << "'" << std::endl;
463
464 if (pnl->left)
465 {
466 new_list.push_back(pnl->left);
467 if (pnl->right)
468 new_list.push_back(pnl->right);
469 }
470 }
471
472 if (!new_list.empty())
473 node_count += dump_layer(os, tree, new_list, level + 1);
474
475 return node_count;
476 }
477};
478
479}}} // namespace mdds::st::detail
Definition global.hpp:54
Definition node.hpp:409
Definition node.hpp:25
bool is_leaf
parent nonleaf_node
Definition node.hpp:27
Definition node.hpp:101
node & operator=(const node &r)
Definition node.hpp:155
node(const node &r)
Definition node.hpp:144
std::size_t refcount
Definition node.hpp:122
Definition node.hpp:40
nonleaf_node & operator=(const nonleaf_node &r)
Definition node.hpp:73
static constexpr bool nothrow_default_constructible_v
Definition node.hpp:52
nonleaf_node(const nonleaf_node &r)
Definition node.hpp:67