1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file constructors_destructor_fn_imps.hpp 44169691Skan * Contains an implementation class for ov_tree_. 45169691Skan */ 46169691Skan 47169691SkanPB_DS_CLASS_T_DEC 48169691Skantypename PB_DS_CLASS_C_DEC::value_allocator 49169691SkanPB_DS_CLASS_C_DEC::s_value_alloc; 50169691Skan 51169691SkanPB_DS_CLASS_T_DEC 52169691Skantypename PB_DS_CLASS_C_DEC::metadata_allocator 53169691SkanPB_DS_CLASS_C_DEC::s_metadata_alloc; 54169691Skan 55169691SkanPB_DS_CLASS_T_DEC 56169691SkanPB_DS_CLASS_C_DEC:: 57169691SkanPB_DS_OV_TREE_CLASS_NAME() : 58169691Skan m_a_values(NULL), 59169691Skan m_a_metadata(NULL), 60169691Skan m_end_it(NULL), 61169691Skan m_size(0) 62169691Skan{ _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) } 63169691Skan 64169691SkanPB_DS_CLASS_T_DEC 65169691SkanPB_DS_CLASS_C_DEC:: 66169691SkanPB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn) : 67169691Skan cmp_fn_base(r_cmp_fn), 68169691Skan m_a_values(NULL), 69169691Skan m_a_metadata(NULL), 70169691Skan m_end_it(NULL), 71169691Skan m_size(0) 72169691Skan{ _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) } 73169691Skan 74169691SkanPB_DS_CLASS_T_DEC 75169691SkanPB_DS_CLASS_C_DEC:: 76169691SkanPB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update) : 77169691Skan cmp_fn_base(r_cmp_fn), 78169691Skan node_update(r_node_update), 79169691Skan m_a_values(NULL), 80169691Skan m_a_metadata(NULL), 81169691Skan m_end_it(NULL), 82169691Skan m_size(0) 83169691Skan{ _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) } 84169691Skan 85169691SkanPB_DS_CLASS_T_DEC 86169691SkanPB_DS_CLASS_C_DEC:: 87169691SkanPB_DS_OV_TREE_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) : 88169691Skan#ifdef _GLIBCXX_DEBUG 89169691Skan map_debug_base(other), 90169691Skan#endif 91169691Skan#ifdef PB_DS_TREE_TRACE 92169691Skan PB_DS_TREE_TRACE_BASE_C_DEC(other), 93169691Skan#endif 94169691Skan cmp_fn_base(other), 95169691Skan node_update(other), 96169691Skan m_a_values(NULL), 97169691Skan m_a_metadata(NULL), 98169691Skan m_end_it(NULL), 99169691Skan m_size(0) 100169691Skan{ 101169691Skan copy_from_ordered_range(other.begin(), other.end()); 102169691Skan _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) 103169691Skan} 104169691Skan 105169691SkanPB_DS_CLASS_T_DEC 106169691Skantemplate<typename It> 107169691Skaninline void 108169691SkanPB_DS_CLASS_C_DEC:: 109169691Skancopy_from_range(It first_it, It last_it) 110169691Skan{ 111169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 112169691Skan typedef 113169691Skan std::map< 114169691Skan key_type, 115169691Skan mapped_type, 116169691Skan Cmp_Fn, 117169691Skan typename Allocator::template rebind< 118169691Skan value_type>::other> 119169691Skan map_type; 120169691Skan#else 121169691Skan typedef 122169691Skan std::set< 123169691Skan key_type, 124169691Skan Cmp_Fn, 125169691Skan typename Allocator::template rebind< 126169691Skan Key>::other> 127169691Skan map_type; 128169691Skan#endif 129169691Skan 130169691Skan map_type m(first_it, last_it); 131169691Skan copy_from_ordered_range(m.begin(), m.end()); 132169691Skan} 133169691Skan 134169691SkanPB_DS_CLASS_T_DEC 135169691Skantemplate<typename It> 136169691Skanvoid 137169691SkanPB_DS_CLASS_C_DEC:: 138169691Skancopy_from_ordered_range(It first_it, It last_it) 139169691Skan{ 140169691Skan const size_type len = std::distance(first_it, last_it); 141169691Skan if (len == 0) 142169691Skan return; 143169691Skan 144169691Skan value_vector a_values = s_value_alloc.allocate(len); 145169691Skan iterator target_it = a_values; 146169691Skan It source_it = first_it; 147169691Skan It source_end_it = last_it; 148169691Skan 149169691Skan cond_dtor<size_type> cd(a_values, target_it, len); 150169691Skan while (source_it != source_end_it) 151169691Skan { 152169691Skan new (const_cast<void* >(static_cast<const void* >(target_it))) 153169691Skan value_type(*source_it++); 154169691Skan 155169691Skan ++target_it; 156169691Skan } 157169691Skan 158169691Skan reallocate_metadata((node_update* )this, len); 159169691Skan cd.set_no_action(); 160169691Skan m_a_values = a_values; 161169691Skan m_size = len; 162169691Skan m_end_it = m_a_values + m_size; 163169691Skan update(PB_DS_node_begin_imp(), (node_update* )this); 164169691Skan 165169691Skan#ifdef _GLIBCXX_DEBUG 166169691Skan const_iterator dbg_it = m_a_values; 167169691Skan while (dbg_it != m_end_it) 168169691Skan { 169169691Skan map_debug_base::insert_new(PB_DS_V2F(*dbg_it)); 170169691Skan dbg_it++; 171169691Skan } 172169691Skan PB_DS_CLASS_C_DEC::assert_valid(); 173169691Skan#endif 174169691Skan} 175169691Skan 176169691SkanPB_DS_CLASS_T_DEC 177169691Skantemplate<typename It> 178169691Skanvoid 179169691SkanPB_DS_CLASS_C_DEC:: 180169691Skancopy_from_ordered_range(It first_it, It last_it, It other_first_it, 181169691Skan It other_last_it) 182169691Skan{ 183169691Skan clear(); 184169691Skan const size_type len = std::distance(first_it, last_it) 185169691Skan + std::distance(other_first_it, other_last_it); 186169691Skan 187169691Skan value_vector a_values = s_value_alloc.allocate(len); 188169691Skan 189169691Skan iterator target_it = a_values; 190169691Skan It source_it = first_it; 191169691Skan It source_end_it = last_it; 192169691Skan 193169691Skan cond_dtor<size_type> cd(a_values, target_it, len); 194169691Skan while (source_it != source_end_it) 195169691Skan { 196169691Skan new (const_cast<void* >(static_cast<const void* >(target_it))) 197169691Skan value_type(*source_it++); 198169691Skan ++target_it; 199169691Skan } 200169691Skan 201169691Skan source_it = other_first_it; 202169691Skan source_end_it = other_last_it; 203169691Skan 204169691Skan while (source_it != source_end_it) 205169691Skan { 206169691Skan new (const_cast<void* >(static_cast<const void* >(target_it))) 207169691Skan value_type(*source_it++); 208169691Skan ++target_it; 209169691Skan } 210169691Skan 211169691Skan reallocate_metadata((node_update* )this, len); 212169691Skan cd.set_no_action(); 213169691Skan m_a_values = a_values; 214169691Skan m_size = len; 215169691Skan m_end_it = m_a_values + m_size; 216169691Skan update(PB_DS_node_begin_imp(), (node_update* )this); 217169691Skan 218169691Skan#ifdef _GLIBCXX_DEBUG 219169691Skan const_iterator dbg_it = m_a_values; 220169691Skan while (dbg_it != m_end_it) 221169691Skan { 222169691Skan map_debug_base::insert_new(PB_DS_V2F(*dbg_it)); 223169691Skan dbg_it++; 224169691Skan } 225169691Skan PB_DS_CLASS_C_DEC::assert_valid(); 226169691Skan#endif 227169691Skan} 228169691Skan 229169691SkanPB_DS_CLASS_T_DEC 230169691Skanvoid 231169691SkanPB_DS_CLASS_C_DEC:: 232169691Skanswap(PB_DS_CLASS_C_DEC& other) 233169691Skan{ 234169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 235169691Skan value_swap(other); 236169691Skan std::swap((Cmp_Fn& )(*this), (Cmp_Fn& )other); 237169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 238169691Skan} 239169691Skan 240169691SkanPB_DS_CLASS_T_DEC 241169691Skanvoid 242169691SkanPB_DS_CLASS_C_DEC:: 243169691Skanvalue_swap(PB_DS_CLASS_C_DEC& other) 244169691Skan{ 245169691Skan std::swap(m_a_values, other.m_a_values); 246169691Skan std::swap(m_a_metadata, other.m_a_metadata); 247169691Skan std::swap(m_size, other.m_size); 248169691Skan std::swap(m_end_it, other.m_end_it); 249169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::swap(other);) 250169691Skan} 251169691Skan 252169691SkanPB_DS_CLASS_T_DEC 253169691SkanPB_DS_CLASS_C_DEC:: 254169691Skan~PB_DS_OV_TREE_CLASS_NAME() 255169691Skan{ 256169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 257169691Skan cond_dtor<size_type> cd(m_a_values, m_end_it, m_size); 258169691Skan reallocate_metadata((node_update* )this, 0); 259169691Skan} 260169691Skan 261169691SkanPB_DS_CLASS_T_DEC 262169691Skaninline void 263169691SkanPB_DS_CLASS_C_DEC:: 264169691Skanupdate(node_iterator /*it*/, null_node_update_pointer) 265169691Skan{ } 266169691Skan 267169691SkanPB_DS_CLASS_T_DEC 268169691Skantemplate<typename Node_Update> 269169691Skanvoid 270169691SkanPB_DS_CLASS_C_DEC:: 271169691Skanupdate(node_iterator nd_it, Node_Update* p_update) 272169691Skan{ 273169691Skan const_node_iterator end_it = PB_DS_node_end_imp(); 274169691Skan if (nd_it == end_it) 275169691Skan return; 276169691Skan update(nd_it.get_l_child(), p_update); 277169691Skan update(nd_it.get_r_child(), p_update); 278169691Skan node_update::operator()(nd_it, end_it); 279169691Skan} 280