1// -*- C++ -*- 2 3// Copyright (C) 2005-2020 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 bin_search_tree_/constructors_destructor_fn_imps.hpp 38 * Contains an implementation class for bin_search_tree_. 39 */ 40 41#ifdef PB_DS_CLASS_C_DEC 42 43PB_DS_CLASS_T_DEC 44typename PB_DS_CLASS_C_DEC::node_allocator 45PB_DS_CLASS_C_DEC::s_node_allocator; 46 47PB_DS_CLASS_T_DEC 48PB_DS_CLASS_C_DEC:: 49PB_DS_BIN_TREE_NAME() : m_p_head(s_node_allocator.allocate(1)), m_size(0) 50{ 51 initialize(); 52 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 53} 54 55PB_DS_CLASS_T_DEC 56PB_DS_CLASS_C_DEC:: 57PB_DS_BIN_TREE_NAME(const Cmp_Fn& r_cmp_fn) : 58 Cmp_Fn(r_cmp_fn), m_p_head(s_node_allocator.allocate(1)), m_size(0) 59{ 60 initialize(); 61 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 62} 63 64PB_DS_CLASS_T_DEC 65PB_DS_CLASS_C_DEC:: 66PB_DS_BIN_TREE_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update) : 67 Cmp_Fn(r_cmp_fn), 68 node_update(r_node_update), 69 m_p_head(s_node_allocator.allocate(1)), 70 m_size(0) 71{ 72 initialize(); 73 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 74} 75 76PB_DS_CLASS_T_DEC 77PB_DS_CLASS_C_DEC:: 78PB_DS_BIN_TREE_NAME(const PB_DS_CLASS_C_DEC& other) : 79#ifdef _GLIBCXX_DEBUG 80 debug_base(other), 81#endif 82#ifdef PB_DS_TREE_TRACE 83 PB_DS_TREE_TRACE_BASE_C_DEC(other), 84#endif 85 Cmp_Fn(other), 86 node_update(other), 87 m_p_head(s_node_allocator.allocate(1)), 88 m_size(0) 89{ 90 initialize(); 91 m_size = other.m_size; 92 PB_DS_STRUCT_ONLY_ASSERT_VALID(other) 93 94 __try 95 { 96 m_p_head->m_p_parent = recursive_copy_node(other.m_p_head->m_p_parent); 97 if (m_p_head->m_p_parent != 0) 98 m_p_head->m_p_parent->m_p_parent = m_p_head; 99 m_size = other.m_size; 100 initialize_min_max(); 101 } 102 __catch(...) 103 { 104 _GLIBCXX_DEBUG_ONLY(debug_base::clear();) 105 s_node_allocator.deallocate(m_p_head, 1); 106 __throw_exception_again; 107 } 108 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 109} 110 111PB_DS_CLASS_T_DEC 112void 113PB_DS_CLASS_C_DEC:: 114swap(PB_DS_CLASS_C_DEC& other) 115{ 116 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 117 PB_DS_STRUCT_ONLY_ASSERT_VALID(other) 118 value_swap(other); 119 std::swap((Cmp_Fn& )(*this), (Cmp_Fn& )other); 120 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 121 PB_DS_STRUCT_ONLY_ASSERT_VALID(other) 122} 123 124PB_DS_CLASS_T_DEC 125void 126PB_DS_CLASS_C_DEC:: 127value_swap(PB_DS_CLASS_C_DEC& other) 128{ 129 _GLIBCXX_DEBUG_ONLY(debug_base::swap(other);) 130 std::swap(m_p_head, other.m_p_head); 131 std::swap(m_size, other.m_size); 132} 133 134PB_DS_CLASS_T_DEC 135PB_DS_CLASS_C_DEC:: 136~PB_DS_BIN_TREE_NAME() 137{ 138 clear(); 139 s_node_allocator.deallocate(m_p_head, 1); 140} 141 142PB_DS_CLASS_T_DEC 143void 144PB_DS_CLASS_C_DEC:: 145initialize() 146{ 147 m_p_head->m_p_parent = 0; 148 m_p_head->m_p_left = m_p_head; 149 m_p_head->m_p_right = m_p_head; 150 m_size = 0; 151} 152 153PB_DS_CLASS_T_DEC 154typename PB_DS_CLASS_C_DEC::node_pointer 155PB_DS_CLASS_C_DEC:: 156recursive_copy_node(const node_pointer p_nd) 157{ 158 if (p_nd == 0) 159 return (0); 160 161 node_pointer p_ret = s_node_allocator.allocate(1); 162 __try 163 { 164 new (p_ret) node(*p_nd); 165 } 166 __catch(...) 167 { 168 s_node_allocator.deallocate(p_ret, 1); 169 __throw_exception_again; 170 } 171 172 p_ret->m_p_left = p_ret->m_p_right = 0; 173 174 __try 175 { 176 p_ret->m_p_left = recursive_copy_node(p_nd->m_p_left); 177 p_ret->m_p_right = recursive_copy_node(p_nd->m_p_right); 178 } 179 __catch(...) 180 { 181 clear_imp(p_ret); 182 __throw_exception_again; 183 } 184 185 if (p_ret->m_p_left != 0) 186 p_ret->m_p_left->m_p_parent = p_ret; 187 188 if (p_ret->m_p_right != 0) 189 p_ret->m_p_right->m_p_parent = p_ret; 190 191 PB_DS_ASSERT_NODE_CONSISTENT(p_ret) 192 return p_ret; 193} 194 195PB_DS_CLASS_T_DEC 196void 197PB_DS_CLASS_C_DEC:: 198initialize_min_max() 199{ 200 if (m_p_head->m_p_parent == 0) 201 { 202 m_p_head->m_p_left = m_p_head->m_p_right = m_p_head; 203 return; 204 } 205 206 { 207 node_pointer p_min = m_p_head->m_p_parent; 208 while (p_min->m_p_left != 0) 209 p_min = p_min->m_p_left; 210 m_p_head->m_p_left = p_min; 211 } 212 213 { 214 node_pointer p_max = m_p_head->m_p_parent; 215 while (p_max->m_p_right != 0) 216 p_max = p_max->m_p_right; 217 m_p_head->m_p_right = p_max; 218 } 219} 220#endif 221