mdds
Loading...
Searching...
No Matches
node.hpp
1/*************************************************************************
2 *
3 * Copyright (c) 2008-2014 Kohei Yoshida
4 *
5 * Permission is hereby granted, free of charge, to any person
6 * obtaining a copy of this software and associated documentation
7 * files (the "Software"), to deal in the Software without
8 * restriction, including without limitation the rights to use,
9 * copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following
12 * conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 * OTHER DEALINGS IN THE SOFTWARE.
25 *
26 ************************************************************************/
27
28#ifndef __MDDS_NODE_HXX__
29#define __MDDS_NODE_HXX__
30
31#include "mdds/global.hpp"
32
33#include <iostream>
34#include <vector>
35#include <cassert>
36#include <sstream>
37
38#include <boost/intrusive_ptr.hpp>
39
40namespace mdds { namespace st { namespace detail {
41
42#ifdef MDDS_DEBUG_NODE_BASE
43
44inline std::size_t node_instance_count = 0;
45
46#endif
47
49{
50 node_base* parent;
51 bool is_leaf;
52
53 node_base(bool _is_leaf) : parent(nullptr), is_leaf(_is_leaf)
54 {}
55 node_base(const node_base& r) : parent(nullptr), is_leaf(r.is_leaf)
56 {}
57};
58
62template<typename KeyT, typename ValueT>
63struct nonleaf_node : public node_base
64{
65 using key_type = KeyT;
66 using nonleaf_value_type = ValueT;
67
68 nonleaf_value_type value_nonleaf;
69
70 key_type low = {};
71 key_type high = {};
72
73 node_base* left = nullptr;
74 node_base* right = nullptr;
75
76public:
77 nonleaf_node() : node_base(false), value_nonleaf()
78 {}
79
84 nonleaf_node(const nonleaf_node& r) : node_base(r), value_nonleaf(r.value_nonleaf), low(r.low), high(r.high)
85 {}
86
91 {
92 if (this == &r)
93 // assignment to self.
94 return *this;
95
96 value_nonleaf = r.value_nonleaf;
97 return *this;
98 }
99
100 bool operator==(const nonleaf_node& r) const
101 {
102 return low == r.low && high == r.high && value_nonleaf == r.value_nonleaf;
103 }
104
105 bool operator!=(const nonleaf_node& r) const
106 {
107 return !operator==(r);
108 }
109
110 std::string to_string() const
111 {
112 std::ostringstream os;
113 os << "[" << low << "-" << high << ")";
114 return os.str();
115 }
116};
117
121template<typename KeyT, typename ValueT>
123{
124 using key_type = KeyT;
125 using leaf_value_type = ValueT;
126 using node_ptr = boost::intrusive_ptr<node>;
127
128 static size_t get_instance_count()
129 {
130#ifdef MDDS_DEBUG_NODE_BASE
131 return node_instance_count;
132#else
133 return 0;
134#endif
135 }
136
137 leaf_value_type value_leaf;
138
139 key_type key = {};
140
141 node_ptr prev;
142 node_ptr next;
143
144 std::size_t refcount = 0;
145
146public:
147 node() : node_base(true)
148 {
149#ifdef MDDS_DEBUG_NODE_BASE
150 ++node_instance_count;
151#endif
152 }
153
158 node(const node& r) : node_base(r), key(r.key)
159 {
160#ifdef MDDS_DEBUG_NODE_BASE
161 ++node_instance_count;
162#endif
163 value_leaf = r.value_leaf;
164 }
165
169 node& operator=(const node& r)
170 {
171 if (this == &r)
172 // assignment to self.
173 return *this;
174
175 value_leaf = r.value_leaf;
176 return *this;
177 }
178
179 ~node()
180 {
181#ifdef MDDS_DEBUG_NODE_BASE
182 --node_instance_count;
183#endif
184 }
185
186 bool operator==(const node& r) const
187 {
188 return key == r.key && value_leaf == r.value_leaf;
189 }
190
191 bool operator!=(const node& r) const
192 {
193 return !operator==(r);
194 }
195
196 std::string to_string() const
197 {
198 std::ostringstream os;
199 os << "[" << key << "]";
200 return os.str();
201 }
202};
203
204template<typename KeyT, typename ValueT>
205inline void intrusive_ptr_add_ref(node<KeyT, ValueT>* p)
206{
207 ++p->refcount;
208}
209
210template<typename KeyT, typename ValueT>
211inline void intrusive_ptr_release(node<KeyT, ValueT>* p)
212{
213 --p->refcount;
214 if (!p->refcount)
215 delete p;
216}
217
218template<typename NodePtrT>
219void link_nodes(NodePtrT& left, NodePtrT& right)
220{
221 left->next = right;
222 right->prev = left;
223}
224
225template<typename T>
227{
228public:
229 typedef typename T::node leaf_node;
230 typedef typename leaf_node::node_ptr leaf_node_ptr;
231 typedef typename T::nonleaf_node nonleaf_node;
232 typedef std::vector<nonleaf_node> nonleaf_node_pool_type;
233
234 tree_builder(nonleaf_node_pool_type& pool) : m_pool(pool), m_pool_pos(pool.begin()), m_pool_pos_end(pool.end())
235 {}
236
237 nonleaf_node* build(const leaf_node_ptr& left_leaf_node)
238 {
239 if (!left_leaf_node)
240 // The left leaf node is empty. Nothing to build.
241 return nullptr;
242
243 leaf_node_ptr node1 = left_leaf_node;
244
245 std::vector<nonleaf_node*> node_list;
246 while (true)
247 {
248 leaf_node_ptr node2 = node1->next;
249 nonleaf_node* parent_node = make_parent_node(node1.get(), node2.get());
250 node_list.push_back(parent_node);
251
252 if (!node2 || !node2->next)
253 // no more nodes. Break out of the loop.
254 break;
255
256 node1 = node2->next;
257 }
258
259 return build_tree_non_leaf(node_list);
260 }
261
262private:
263 nonleaf_node* make_parent_node(node_base* node1, node_base* node2)
264 {
265 assert(m_pool_pos != m_pool_pos_end);
266
267 nonleaf_node* parent_node = &(*m_pool_pos);
268 ++m_pool_pos;
269 node1->parent = parent_node;
270 parent_node->left = node1;
271 if (node2)
272 {
273 node2->parent = parent_node;
274 parent_node->right = node2;
275 }
276
277 fill_nonleaf_parent_node(parent_node, node1, node2);
278 return parent_node;
279 }
280
281 void fill_nonleaf_parent_node(nonleaf_node* parent_node, const node_base* left_node, const node_base* right_node)
282 {
283 // Parent node should carry the range of all of its child nodes.
284 if (left_node)
285 {
286 parent_node->low = left_node->is_leaf ? static_cast<const leaf_node*>(left_node)->key
287 : static_cast<const nonleaf_node*>(left_node)->low;
288 }
289 else
290 {
291 // Having a left node is prerequisite.
292 throw general_error("fill_nonleaf_parent_node: Having a left node is prerequisite.");
293 }
294
295 if (right_node)
296 {
297 if (right_node->is_leaf)
298 {
299 // When the child nodes are leaf nodes, the upper bound
300 // must be the value of the node that comes after the
301 // right leaf node (if such node exists).
302
303 const auto* p = static_cast<const leaf_node*>(right_node);
304 if (p->next)
305 parent_node->high = p->next->key;
306 else
307 parent_node->high = p->key;
308 }
309 else
310 {
311 parent_node->high = static_cast<const nonleaf_node*>(right_node)->high;
312 }
313 }
314 else
315 {
316 parent_node->high = left_node->is_leaf ? static_cast<const leaf_node*>(left_node)->key
317 : static_cast<const nonleaf_node*>(left_node)->high;
318 }
319 }
320
321 nonleaf_node* build_tree_non_leaf(const std::vector<nonleaf_node*>& node_list)
322 {
323 size_t node_count = node_list.size();
324 if (node_count == 1)
325 {
326 return node_list.front();
327 }
328 else if (node_count == 0)
329 return nullptr;
330
331 std::vector<nonleaf_node*> new_node_list;
332 nonleaf_node* node1 = nullptr;
333 typename std::vector<nonleaf_node*>::const_iterator it = node_list.begin();
334 typename std::vector<nonleaf_node*>::const_iterator it_end = node_list.end();
335 for (bool even_itr = false; it != it_end; ++it, even_itr = !even_itr)
336 {
337 if (even_itr)
338 {
339 nonleaf_node* node2 = *it;
340 nonleaf_node* parent_node = make_parent_node(node1, node2);
341 new_node_list.push_back(parent_node);
342 node1 = nullptr;
343 node2 = nullptr;
344 }
345 else
346 node1 = *it;
347 }
348
349 if (node1)
350 {
351 // Un-paired node still needs a parent...
352 nonleaf_node* parent_node = make_parent_node(node1, nullptr);
353 new_node_list.push_back(parent_node);
354 }
355
356 // Move up one level, and do the same procedure until the root node is reached.
357 return build_tree_non_leaf(new_node_list);
358 }
359
360 nonleaf_node_pool_type& m_pool;
361 typename nonleaf_node_pool_type::iterator m_pool_pos;
362 typename nonleaf_node_pool_type::iterator m_pool_pos_end;
363};
364
365template<typename KeyT, typename ValueT>
366void disconnect_all_nodes(node<KeyT, ValueT>* p)
367{
368 if (!p)
369 return;
370
371 p->prev.reset();
372 p->next.reset();
373 p->parent = nullptr;
374}
375
376template<typename KeyT, typename ValueT>
377void disconnect_leaf_nodes(node<KeyT, ValueT>* left_node, node<KeyT, ValueT>* right_node)
378{
379 if (!left_node || !right_node)
380 return;
381
382 // Go through all leaf nodes, and disconnect their links.
383 auto* cur_node = left_node;
384 do
385 {
386 auto* next_node = cur_node->next.get();
387 disconnect_all_nodes(cur_node);
388 cur_node = next_node;
389 } while (cur_node != right_node);
390
391 disconnect_all_nodes(right_node);
392}
393
394template<typename KeyT, typename ValueT>
395size_t count_leaf_nodes(const node<KeyT, ValueT>* left_end, const node<KeyT, ValueT>* right_end)
396{
397 size_t leaf_count = 1;
398 const auto* p = left_end;
399 const auto* p_end = right_end;
400 for (; p != p_end; p = p->next.get(), ++leaf_count)
401 ;
402
403 return leaf_count;
404}
405
406inline size_t count_needed_nonleaf_nodes(size_t leaf_count)
407{
408 size_t nonleaf_count = 0;
409 while (true)
410 {
411 if (leaf_count == 1)
412 break;
413
414 if ((leaf_count % 2) == 1)
415 // Add one to make it an even number.
416 ++leaf_count;
417
418 leaf_count /= 2;
419 nonleaf_count += leaf_count;
420 }
421
422 return nonleaf_count;
423}
424
425template<typename TraitsT>
427{
428 using node_list_type = std::vector<const node_base*>;
429 using tree_type = typename TraitsT::tree_type;
430
431public:
432 static size_t dump(std::ostream& os, const tree_type& tree, const node_base* root_node)
433 {
434 if (!root_node)
435 return 0;
436
437 node_list_type node_list;
438 node_list.push_back(root_node);
439 return dump_layer(os, tree, node_list, 0);
440 }
441
442private:
443 static size_t dump_layer(
444 std::ostream& os, const tree_type& tree, const node_list_type& node_list, unsigned int level)
445 {
446 using leaf_type = typename TraitsT::leaf_type;
447 using nonleaf_type = typename TraitsT::nonleaf_type;
448 using to_string = typename TraitsT::to_string;
449
450 if (node_list.empty())
451 return 0;
452
453 size_t node_count = node_list.size();
454
455 bool is_leaf = node_list.front()->is_leaf;
456 os << "level " << level << ':' << std::endl;
457 os << " type: " << (is_leaf ? "leaf" : "non-leaf") << std::endl;
458 os << " nodes:" << std::endl;
459
460 node_list_type new_list;
461
462 for (const node_base* p : node_list)
463 {
464 os << " - '";
465
466 if (!p)
467 {
468 os << "*'" << std::endl;
469 continue;
470 }
471
472 if (p->is_leaf)
473 {
474 const auto* pl = static_cast<const leaf_type*>(p);
475 os << to_string{tree}(*pl) << "'" << std::endl;
476 continue;
477 }
478
479 const auto* pnl = static_cast<const nonleaf_type*>(p);
480 os << to_string{tree}(*pnl) << "'" << std::endl;
481
482 if (pnl->left)
483 {
484 new_list.push_back(pnl->left);
485 if (pnl->right)
486 new_list.push_back(pnl->right);
487 }
488 }
489
490 if (!new_list.empty())
491 node_count += dump_layer(os, tree, new_list, level + 1);
492
493 return node_count;
494 }
495};
496
497}}} // namespace mdds::st::detail
498
499#endif
Definition global.hpp:84
Definition node.hpp:227
Definition node.hpp:427
Definition node.hpp:49
bool is_leaf
parent nonleaf_node
Definition node.hpp:51
Definition node.hpp:123
node & operator=(const node &r)
Definition node.hpp:169
node(const node &r)
Definition node.hpp:158
std::size_t refcount
next sibling leaf node.
Definition node.hpp:144
node_ptr next
previous sibling leaf node.
Definition node.hpp:142
Definition node.hpp:64
nonleaf_node & operator=(const nonleaf_node &r)
Definition node.hpp:90
nonleaf_node(const nonleaf_node &r)
Definition node.hpp:84
node_base * right
left child nonleaf_node
Definition node.hpp:74
node_base * left
high range value (non-inclusive)
Definition node.hpp:73
nonleaf_node()
right child nonleaf_node
Definition node.hpp:77
key_type high
low range value (inclusive)
Definition node.hpp:71