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 
37 namespace mdds { namespace __st {
38 
39 #ifdef MDDS_DEBUG_NODE_BASE
40 size_t node_instance_count = 0;
41 #endif
42 
43 struct node_base
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 
54 template<typename T>
55 struct 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 
69 private:
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 
77 public:
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 
105  ~nonleaf_node()
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 
138 template<typename T>
139 struct 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 
166 private:
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 
173 public:
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 
238 template<typename T>
239 inline void intrusive_ptr_add_ref(node<T>* p)
240 {
241  ++p->refcount;
242 }
243 
244 template<typename T>
245 inline void intrusive_ptr_release(node<T>* p)
246 {
247  --p->refcount;
248  if (!p->refcount)
249  delete p;
250 }
251 
252 template<typename T>
253 void 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 
259 template<typename T>
261 {
262 public:
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 
296 private:
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 
359 template<typename T>
360 void 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 
370 template<typename T>
371 void 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 
388 template<typename T>
389 size_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 
400 inline 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 
421 template<typename _Leaf, typename _NonLeaf>
422 class tree_dumper
423 {
424  typedef std::vector<const node_base*> node_list_type;
425 
426 public:
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 
437 private:
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:260
node_base * right
left child nonleaf_node
Definition: node.hpp:67
bool is_leaf
parent nonleaf_node
Definition: node.hpp:46
nonleaf_node & operator=(const nonleaf_node &r)
Definition: node.hpp:95
Definition: node.hpp:43
nonleaf_node(const nonleaf_node &r)
Definition: node.hpp:87
Definition: node.hpp:55
Definition: flat_segment_tree.hpp:46
node & operator=(const node &r)
Definition: node.hpp:197
Definition: node.hpp:139
size_t refcount
next sibling leaf node.
Definition: node.hpp:164
node_ptr next
previous sibling leaf node.
Definition: node.hpp:162
node(const node &r)
Definition: node.hpp:186