Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // -*- C++ -*-
  2.  
  3. // Copyright (C) 2005-2015 Free Software Foundation, Inc.
  4. //
  5. // This file is part of the GNU ISO C++ Library.  This library is free
  6. // software; you can redistribute it and/or modify it under the terms
  7. // of the GNU General Public License as published by the Free Software
  8. // Foundation; either version 3, or (at your option) any later
  9. // version.
  10.  
  11. // This library is distributed in the hope that it will be useful, but
  12. // WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14. // General Public License for more details.
  15.  
  16. // Under Section 7 of GPL version 3, you are granted additional
  17. // permissions described in the GCC Runtime Library Exception, version
  18. // 3.1, as published by the Free Software Foundation.
  19.  
  20. // You should have received a copy of the GNU General Public License and
  21. // a copy of the GCC Runtime Library Exception along with this program;
  22. // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23. // <http://www.gnu.org/licenses/>.
  24.  
  25. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26.  
  27. // Permission to use, copy, modify, sell, and distribute this software
  28. // is hereby granted without fee, provided that the above copyright
  29. // notice appears in all copies, and that both that copyright notice
  30. // and this permission notice appear in supporting documentation. None
  31. // of the above authors, nor IBM Haifa Research Laboratories, make any
  32. // representation about the suitability of this software for any
  33. // purpose. It is provided "as is" without express or implied
  34. // warranty.
  35.  
  36. /**
  37.  * @file ov_tree_map_/constructors_destructor_fn_imps.hpp
  38.  * Contains an implementation class for ov_tree_.
  39.  */
  40.  
  41. PB_DS_CLASS_T_DEC
  42. typename PB_DS_CLASS_C_DEC::value_allocator
  43. PB_DS_CLASS_C_DEC::s_value_alloc;
  44.  
  45. PB_DS_CLASS_T_DEC
  46. typename PB_DS_CLASS_C_DEC::metadata_allocator
  47. PB_DS_CLASS_C_DEC::s_metadata_alloc;
  48.  
  49. PB_DS_CLASS_T_DEC
  50. PB_DS_CLASS_C_DEC::
  51. PB_DS_OV_TREE_NAME() :
  52.   m_a_values(0),
  53.   m_a_metadata(0),
  54.   m_end_it(0),
  55.   m_size(0)
  56. { PB_DS_ASSERT_VALID((*this)) }
  57.  
  58. PB_DS_CLASS_T_DEC
  59. PB_DS_CLASS_C_DEC::
  60. PB_DS_OV_TREE_NAME(const Cmp_Fn& r_cmp_fn) :
  61.   cmp_fn(r_cmp_fn),
  62.   m_a_values(0),
  63.   m_a_metadata(0),
  64.   m_end_it(0),
  65.   m_size(0)
  66. { PB_DS_ASSERT_VALID((*this)) }
  67.  
  68. PB_DS_CLASS_T_DEC
  69. PB_DS_CLASS_C_DEC::
  70. PB_DS_OV_TREE_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_nodeu) :
  71.   cmp_fn(r_cmp_fn),
  72.   node_update(r_nodeu),
  73.   m_a_values(0),
  74.   m_a_metadata(0),
  75.   m_end_it(0),
  76.   m_size(0)
  77. { PB_DS_ASSERT_VALID((*this)) }
  78.  
  79. PB_DS_CLASS_T_DEC
  80. PB_DS_CLASS_C_DEC::
  81. PB_DS_OV_TREE_NAME(const PB_DS_CLASS_C_DEC& other) :
  82. #ifdef PB_DS_TREE_TRACE
  83.   trace_base(other),
  84. #endif
  85.   cmp_fn(other),
  86.   node_update(other),
  87.   m_a_values(0),
  88.   m_a_metadata(0),
  89.   m_end_it(0),
  90.   m_size(0)
  91. {
  92.   copy_from_ordered_range(other.begin(), other.end());
  93.   PB_DS_ASSERT_VALID((*this))
  94. }
  95.  
  96. PB_DS_CLASS_T_DEC
  97. template<typename It>
  98. inline void
  99. PB_DS_CLASS_C_DEC::
  100. copy_from_range(It first_it, It last_it)
  101. {
  102. #ifdef PB_DS_DATA_TRUE_INDICATOR
  103.   typedef std::map<key_type, mapped_type, Cmp_Fn,
  104.                    typename _Alloc::template rebind<value_type>::other>
  105.     map_type;
  106. #else
  107.   typedef std::set<key_type, Cmp_Fn,
  108.                    typename _Alloc::template rebind<Key>::other>
  109.     map_type;
  110. #endif
  111.  
  112.   map_type m(first_it, last_it);
  113.   copy_from_ordered_range(m.begin(), m.end());
  114.   PB_DS_ASSERT_VALID((*this))
  115. }
  116.  
  117. PB_DS_CLASS_T_DEC
  118. template<typename It>
  119. void
  120. PB_DS_CLASS_C_DEC::
  121. copy_from_ordered_range(It first_it, It last_it)
  122. {
  123.   const size_type len = std::distance(first_it, last_it);
  124.   if (len == 0)
  125.     return;
  126.  
  127.   value_vector a_values = s_value_alloc.allocate(len);
  128.   iterator target_it = a_values;
  129.   It source_it = first_it;
  130.   It source_end_it = last_it;
  131.  
  132.   cond_dtor<size_type> cd(a_values, target_it, len);
  133.   while (source_it != source_end_it)
  134.     {
  135.       void* __v = const_cast<void*>(static_cast<const void*>(target_it));
  136.       new (__v) value_type(*source_it++);
  137.       ++target_it;
  138.     }
  139.  
  140.   reallocate_metadata((node_update*)this, len);
  141.   cd.set_no_action();
  142.   m_a_values = a_values;
  143.   m_size = len;
  144.   m_end_it = m_a_values + m_size;
  145.   update(PB_DS_node_begin_imp(), (node_update*)this);
  146.  
  147. #ifdef _GLIBCXX_DEBUG
  148.   for (const_iterator dbg_it = m_a_values; dbg_it != m_end_it; ++dbg_it)
  149.     debug_base::insert_new(PB_DS_V2F(*dbg_it));
  150. #endif
  151. }
  152.  
  153. PB_DS_CLASS_T_DEC
  154. template<typename It>
  155. void
  156. PB_DS_CLASS_C_DEC::
  157. copy_from_ordered_range(It first_it, It last_it, It other_first_it,
  158.                         It other_last_it)
  159. {
  160.   clear();
  161.   const size_type len = std::distance(first_it, last_it)
  162.                          + std::distance(other_first_it, other_last_it);
  163.  
  164.   value_vector a_values = s_value_alloc.allocate(len);
  165.  
  166.   iterator target_it = a_values;
  167.   It source_it = first_it;
  168.   It source_end_it = last_it;
  169.  
  170.   cond_dtor<size_type> cd(a_values, target_it, len);
  171.   while (source_it != source_end_it)
  172.     {
  173.       new (const_cast<void* >(static_cast<const void* >(target_it)))
  174.         value_type(*source_it++);
  175.       ++target_it;
  176.     }
  177.  
  178.   source_it = other_first_it;
  179.   source_end_it = other_last_it;
  180.  
  181.   while (source_it != source_end_it)
  182.     {
  183.       new (const_cast<void* >(static_cast<const void* >(target_it)))
  184.         value_type(*source_it++);
  185.       ++target_it;
  186.     }
  187.  
  188.   reallocate_metadata((node_update* )this, len);
  189.   cd.set_no_action();
  190.   m_a_values = a_values;
  191.   m_size = len;
  192.   m_end_it = m_a_values + m_size;
  193.   update(PB_DS_node_begin_imp(), (node_update* )this);
  194.  
  195. #ifdef _GLIBCXX_DEBUG
  196.   for (const_iterator dbg_it = m_a_values; dbg_it != m_end_it; ++dbg_it)
  197.     debug_base::insert_new(PB_DS_V2F(*dbg_it));
  198. #endif
  199. }
  200.  
  201. PB_DS_CLASS_T_DEC
  202. void
  203. PB_DS_CLASS_C_DEC::
  204. swap(PB_DS_CLASS_C_DEC& other)
  205. {
  206.   PB_DS_ASSERT_VALID((*this))
  207.   PB_DS_ASSERT_VALID(other)
  208.   value_swap(other);
  209.   std::swap(static_cast<cmp_fn&>(*this),
  210.             static_cast<cmp_fn&>(other));
  211.   std::swap(static_cast<traits_base&>(*this),
  212.             static_cast<traits_base&>(other));
  213.   PB_DS_ASSERT_VALID(other)
  214.   PB_DS_ASSERT_VALID((*this))
  215. }
  216.  
  217. PB_DS_CLASS_T_DEC
  218. void
  219. PB_DS_CLASS_C_DEC::
  220. value_swap(PB_DS_CLASS_C_DEC& other)
  221. {
  222.   _GLIBCXX_DEBUG_ONLY(debug_base::swap(other);)
  223.   std::swap(m_a_values, other.m_a_values);
  224.   std::swap(m_a_metadata, other.m_a_metadata);
  225.   std::swap(m_size, other.m_size);
  226.   std::swap(m_end_it, other.m_end_it);
  227. }
  228.  
  229. PB_DS_CLASS_T_DEC
  230. PB_DS_CLASS_C_DEC::
  231. ~PB_DS_OV_TREE_NAME()
  232. {
  233.   PB_DS_ASSERT_VALID((*this))
  234.   cond_dtor<size_type> cd(m_a_values, m_end_it, m_size);
  235.   reallocate_metadata((node_update*)this, 0);
  236. }
  237.  
  238. PB_DS_CLASS_T_DEC
  239. inline void
  240. PB_DS_CLASS_C_DEC::
  241. update(node_iterator, null_node_update_pointer)
  242. { }
  243.  
  244. PB_DS_CLASS_T_DEC
  245. template<typename Node_Update>
  246. void
  247. PB_DS_CLASS_C_DEC::
  248. update(node_iterator nd_it, Node_Update* p_update)
  249. {
  250.   node_const_iterator end_it = PB_DS_node_end_imp();
  251.   if (nd_it != end_it)
  252.     {
  253.       update(nd_it.get_l_child(), p_update);
  254.       update(nd_it.get_r_child(), p_update);
  255.       node_update::operator()(nd_it, end_it);
  256.     }
  257. }
  258.