mdds
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 <iostream>
32#include <vector>
33#include <cassert>
34
35#include <boost/intrusive_ptr.hpp>
36
37namespace mdds { namespace __st {
38
39#ifdef MDDS_DEBUG_NODE_BASE
40size_t node_instance_count = 0;
41#endif
42
44{
45 node_base* parent;
46 bool is_leaf;
47
48 node_base(bool _is_leaf) : parent(nullptr), is_leaf(_is_leaf)
49 {}
50 node_base(const node_base& r) : parent(nullptr), is_leaf(r.is_leaf)
51 {}
52};
53
54template<typename T>
55struct nonleaf_node : public node_base
56{
57 typedef typename T::nonleaf_value_type nonleaf_value_type;
58 typedef typename T::fill_nonleaf_value_handler fill_nonleaf_value_handler;
59 typedef typename T::init_handler init_handler;
60 typedef typename T::dispose_handler dispose_handler;
61#ifdef MDDS_UNIT_TEST
62 typedef typename T::to_string_handler to_string_handler;
63#endif
64 nonleaf_value_type value_nonleaf;
65
66 node_base* left;
68
69private:
70 fill_nonleaf_value_handler _hdl_fill_nonleaf;
71 init_handler _hdl_init;
72 dispose_handler _hdl_dispose;
73#ifdef MDDS_UNIT_TEST
74 to_string_handler _hdl_to_string;
75#endif
76
77public:
78 nonleaf_node() : node_base(false), left(nullptr), right(nullptr)
79 {
80 _hdl_init(*this);
81 }
82
87 nonleaf_node(const nonleaf_node& r) : node_base(r), left(nullptr), right(nullptr)
88 {
89 value_nonleaf = r.value_nonleaf;
90 }
91
96 {
97 if (this == &r)
98 // assignment to self.
99 return *this;
100
101 value_nonleaf = r.value_nonleaf;
102 return *this;
103 }
104
106 {
107 dispose();
108 }
109
110 void dispose()
111 {
112 _hdl_dispose(*this);
113 }
114
115 bool equals(const nonleaf_node& r) const
116 {
117 return value_nonleaf == r.value_nonleaf;
118 }
119
120 void fill_nonleaf_value(const node_base* left_node, const node_base* right_node)
121 {
122 _hdl_fill_nonleaf(*this, left_node, right_node);
123 }
124
125#ifdef MDDS_UNIT_TEST
126 void dump_value() const
127 {
128 ::std::cout << _hdl_to_string(*this);
129 }
130
131 ::std::string to_string() const
132 {
133 return _hdl_to_string(*this);
134 }
135#endif
136};
137
138template<typename T>
139struct node : public node_base
140{
141 typedef ::boost::intrusive_ptr<node> node_ptr;
142
143 typedef typename T::leaf_value_type leaf_value_type;
144 typedef typename T::init_handler init_handler;
145 typedef typename T::dispose_handler dispose_handler;
146#ifdef MDDS_UNIT_TEST
147 typedef typename T::to_string_handler to_string_handler;
148#endif
149
150 static size_t get_instance_count()
151 {
152#ifdef MDDS_DEBUG_NODE_BASE
153 return node_instance_count;
154#else
155 return 0;
156#endif
157 }
158
159 leaf_value_type value_leaf;
160
161 node_ptr prev;
162 node_ptr next;
163
164 size_t refcount;
165
166private:
167 init_handler _hdl_init;
168 dispose_handler _hdl_dispose;
169#ifdef MDDS_UNIT_TEST
170 to_string_handler _hdl_to_string;
171#endif
172
173public:
174 node() : node_base(true), refcount(0)
175 {
176#ifdef MDDS_DEBUG_NODE_BASE
177 ++node_instance_count;
178#endif
179 _hdl_init(*this);
180 }
181
186 node(const node& r) : node_base(r), refcount(0)
187 {
188#ifdef MDDS_DEBUG_NODE_BASE
189 ++node_instance_count;
190#endif
191 value_leaf = r.value_leaf;
192 }
193
197 node& operator=(const node& r)
198 {
199 if (this == &r)
200 // assignment to self.
201 return *this;
202
203 value_leaf = r.value_leaf;
204 return *this;
205 }
206
207 ~node()
208 {
209#ifdef MDDS_DEBUG_NODE_BASE
210 --node_instance_count;
211#endif
212 dispose();
213 }
214
215 void dispose()
216 {
217 _hdl_dispose(*this);
218 }
219
220 bool equals(const node& r) const
221 {
222 return value_leaf == r.value_leaf;
223 }
224
225#ifdef MDDS_UNIT_TEST
226 void dump_value() const
227 {
228 ::std::cout << _hdl_to_string(*this);
229 }
230
231 ::std::string to_string() const
232 {
233 return _hdl_to_string(*this);
234 }
235#endif
236};
237
238template<typename T>
239inline void intrusive_ptr_add_ref(node<T>* p)
240{
241 ++p->refcount;
242}
243
244template<typename T>
245inline void intrusive_ptr_release(node<T>* p)
246{
247 --p->refcount;
248 if (!p->refcount)
249 delete p;
250}
251
252template<typename T>
253void link_nodes(typename node<T>::node_ptr& left, typename node<T>::node_ptr& right)
254{
255 left->next = right;
256 right->prev = left;
257}
258
259template<typename T>
261{
262public:
264 typedef typename mdds::__st::node<T>::node_ptr leaf_node_ptr;
266 typedef std::vector<nonleaf_node> nonleaf_node_pool_type;
267
268 tree_builder(nonleaf_node_pool_type& pool) : m_pool(pool), m_pool_pos(pool.begin()), m_pool_pos_end(pool.end())
269 {}
270
271 nonleaf_node* build(const leaf_node_ptr& left_leaf_node)
272 {
273 if (!left_leaf_node)
274 // The left leaf node is empty. Nothing to build.
275 return nullptr;
276
277 leaf_node_ptr node1 = left_leaf_node;
278
279 std::vector<nonleaf_node*> node_list;
280 while (true)
281 {
282 leaf_node_ptr node2 = node1->next;
283 nonleaf_node* parent_node = make_parent_node(node1.get(), node2.get());
284 node_list.push_back(parent_node);
285
286 if (!node2 || !node2->next)
287 // no more nodes. Break out of the loop.
288 break;
289
290 node1 = node2->next;
291 }
292
293 return build_tree_non_leaf(node_list);
294 }
295
296private:
297 nonleaf_node* make_parent_node(node_base* node1, node_base* node2)
298 {
299 assert(m_pool_pos != m_pool_pos_end);
300
301 nonleaf_node* parent_node = &(*m_pool_pos);
302 ++m_pool_pos;
303 node1->parent = parent_node;
304 parent_node->left = node1;
305 if (node2)
306 {
307 node2->parent = parent_node;
308 parent_node->right = node2;
309 }
310
311 parent_node->fill_nonleaf_value(node1, node2);
312 return parent_node;
313 }
314
315 nonleaf_node* build_tree_non_leaf(const std::vector<nonleaf_node*>& node_list)
316 {
317 size_t node_count = node_list.size();
318 if (node_count == 1)
319 {
320 return node_list.front();
321 }
322 else if (node_count == 0)
323 return nullptr;
324
325 std::vector<nonleaf_node*> new_node_list;
326 nonleaf_node* node1 = nullptr;
327 typename std::vector<nonleaf_node*>::const_iterator it = node_list.begin();
328 typename std::vector<nonleaf_node*>::const_iterator it_end = node_list.end();
329 for (bool even_itr = false; it != it_end; ++it, even_itr = !even_itr)
330 {
331 if (even_itr)
332 {
333 nonleaf_node* node2 = *it;
334 nonleaf_node* parent_node = make_parent_node(node1, node2);
335 new_node_list.push_back(parent_node);
336 node1 = nullptr;
337 node2 = nullptr;
338 }
339 else
340 node1 = *it;
341 }
342
343 if (node1)
344 {
345 // Un-paired node still needs a parent...
346 nonleaf_node* parent_node = make_parent_node(node1, nullptr);
347 new_node_list.push_back(parent_node);
348 }
349
350 // Move up one level, and do the same procedure until the root node is reached.
351 return build_tree_non_leaf(new_node_list);
352 }
353
354 nonleaf_node_pool_type& m_pool;
355 typename nonleaf_node_pool_type::iterator m_pool_pos;
356 typename nonleaf_node_pool_type::iterator m_pool_pos_end;
357};
358
359template<typename T>
360void disconnect_all_nodes(node<T>* p)
361{
362 if (!p)
363 return;
364
365 p->prev.reset();
366 p->next.reset();
367 p->parent = nullptr;
368}
369
370template<typename T>
371void disconnect_leaf_nodes(node<T>* left_node, node<T>* right_node)
372{
373 if (!left_node || !right_node)
374 return;
375
376 // Go through all leaf nodes, and disconnect their links.
377 node<T>* cur_node = left_node;
378 do
379 {
380 node<T>* next_node = cur_node->next.get();
381 disconnect_all_nodes(cur_node);
382 cur_node = next_node;
383 } while (cur_node != right_node);
384
385 disconnect_all_nodes(right_node);
386}
387
388template<typename T>
389size_t count_leaf_nodes(const node<T>* left_end, const node<T>* right_end)
390{
391 size_t leaf_count = 1;
392 const node<T>* p = left_end;
393 const node<T>* p_end = right_end;
394 for (; p != p_end; p = p->next.get(), ++leaf_count)
395 ;
396
397 return leaf_count;
398}
399
400inline size_t count_needed_nonleaf_nodes(size_t leaf_count)
401{
402 size_t nonleaf_count = 0;
403 while (true)
404 {
405 if (leaf_count == 1)
406 break;
407
408 if ((leaf_count % 2) == 1)
409 // Add one to make it an even number.
410 ++leaf_count;
411
412 leaf_count /= 2;
413 nonleaf_count += leaf_count;
414 }
415
416 return nonleaf_count;
417}
418
419#ifdef MDDS_UNIT_TEST
420
421template<typename _Leaf, typename _NonLeaf>
422class tree_dumper
423{
424 typedef std::vector<const node_base*> node_list_type;
425
426public:
427 static size_t dump(const node_base* root_node)
428 {
429 if (!root_node)
430 return 0;
431
432 node_list_type node_list;
433 node_list.push_back(root_node);
434 return dump_layer(node_list, 0);
435 }
436
437private:
438 static size_t dump_layer(const node_list_type& node_list, unsigned int level)
439 {
440 using ::std::cout;
441 using ::std::endl;
442
443 if (node_list.empty())
444 return 0;
445
446 size_t node_count = node_list.size();
447
448 bool is_leaf = node_list.front()->is_leaf;
449 cout << "level " << level << " (" << (is_leaf ? "leaf" : "non-leaf") << ")" << endl;
450
451 node_list_type new_list;
452 typename node_list_type::const_iterator it = node_list.begin(), it_end = node_list.end();
453 for (; it != it_end; ++it)
454 {
455 const node_base* p = *it;
456 if (!p)
457 {
458 cout << "(x) ";
459 continue;
460 }
461
462 if (p->is_leaf)
463 static_cast<const _Leaf*>(p)->dump_value();
464 else
465 static_cast<const _NonLeaf*>(p)->dump_value();
466
467 if (p->is_leaf)
468 continue;
469
470 if (static_cast<const _NonLeaf*>(p)->left)
471 {
472 new_list.push_back(static_cast<const _NonLeaf*>(p)->left);
473 if (static_cast<const _NonLeaf*>(p)->right)
474 new_list.push_back(static_cast<const _NonLeaf*>(p)->right);
475 }
476 }
477 cout << endl;
478
479 if (!new_list.empty())
480 node_count += dump_layer(new_list, level + 1);
481
482 return node_count;
483 }
484};
485
486#endif
487
488}} // namespace mdds::__st
489
490#endif
Definition: node.hpp:261
Definition: node.hpp:44
bool is_leaf
parent nonleaf_node
Definition: node.hpp:46
Definition: node.hpp:140
size_t refcount
next sibling leaf node.
Definition: node.hpp:164
node_ptr next
previous sibling leaf node.
Definition: node.hpp:162
node & operator=(const node &r)
Definition: node.hpp:197
node(const node &r)
Definition: node.hpp:186
Definition: node.hpp:56
node_base * right
left child nonleaf_node
Definition: node.hpp:67
nonleaf_node & operator=(const nonleaf_node &r)
Definition: node.hpp:95
nonleaf_node(const nonleaf_node &r)
Definition: node.hpp:87