libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005-2015 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file bin_search_tree_/constructors_destructor_fn_imps.hpp 00038 * Contains an implementation class for bin_search_tree_. 00039 */ 00040 00041 PB_DS_CLASS_T_DEC 00042 typename PB_DS_CLASS_C_DEC::node_allocator 00043 PB_DS_CLASS_C_DEC::s_node_allocator; 00044 00045 PB_DS_CLASS_T_DEC 00046 PB_DS_CLASS_C_DEC:: 00047 PB_DS_BIN_TREE_NAME() : m_p_head(s_node_allocator.allocate(1)), m_size(0) 00048 { 00049 initialize(); 00050 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 00051 } 00052 00053 PB_DS_CLASS_T_DEC 00054 PB_DS_CLASS_C_DEC:: 00055 PB_DS_BIN_TREE_NAME(const Cmp_Fn& r_cmp_fn) : 00056 Cmp_Fn(r_cmp_fn), m_p_head(s_node_allocator.allocate(1)), m_size(0) 00057 { 00058 initialize(); 00059 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 00060 } 00061 00062 PB_DS_CLASS_T_DEC 00063 PB_DS_CLASS_C_DEC:: 00064 PB_DS_BIN_TREE_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update) : 00065 Cmp_Fn(r_cmp_fn), 00066 node_update(r_node_update), 00067 m_p_head(s_node_allocator.allocate(1)), 00068 m_size(0) 00069 { 00070 initialize(); 00071 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 00072 } 00073 00074 PB_DS_CLASS_T_DEC 00075 PB_DS_CLASS_C_DEC:: 00076 PB_DS_BIN_TREE_NAME(const PB_DS_CLASS_C_DEC& other) : 00077 #ifdef _GLIBCXX_DEBUG 00078 debug_base(other), 00079 #endif 00080 #ifdef PB_DS_TREE_TRACE 00081 PB_DS_TREE_TRACE_BASE_C_DEC(other), 00082 #endif 00083 Cmp_Fn(other), 00084 node_update(other), 00085 m_p_head(s_node_allocator.allocate(1)), 00086 m_size(0) 00087 { 00088 initialize(); 00089 m_size = other.m_size; 00090 PB_DS_STRUCT_ONLY_ASSERT_VALID(other) 00091 00092 __try 00093 { 00094 m_p_head->m_p_parent = recursive_copy_node(other.m_p_head->m_p_parent); 00095 if (m_p_head->m_p_parent != 0) 00096 m_p_head->m_p_parent->m_p_parent = m_p_head; 00097 m_size = other.m_size; 00098 initialize_min_max(); 00099 } 00100 __catch(...) 00101 { 00102 _GLIBCXX_DEBUG_ONLY(debug_base::clear();) 00103 s_node_allocator.deallocate(m_p_head, 1); 00104 __throw_exception_again; 00105 } 00106 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 00107 } 00108 00109 PB_DS_CLASS_T_DEC 00110 void 00111 PB_DS_CLASS_C_DEC:: 00112 swap(PB_DS_CLASS_C_DEC& other) 00113 { 00114 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 00115 PB_DS_STRUCT_ONLY_ASSERT_VALID(other) 00116 value_swap(other); 00117 std::swap((Cmp_Fn& )(*this), (Cmp_Fn& )other); 00118 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 00119 PB_DS_STRUCT_ONLY_ASSERT_VALID(other) 00120 } 00121 00122 PB_DS_CLASS_T_DEC 00123 void 00124 PB_DS_CLASS_C_DEC:: 00125 value_swap(PB_DS_CLASS_C_DEC& other) 00126 { 00127 _GLIBCXX_DEBUG_ONLY(debug_base::swap(other);) 00128 std::swap(m_p_head, other.m_p_head); 00129 std::swap(m_size, other.m_size); 00130 } 00131 00132 PB_DS_CLASS_T_DEC 00133 PB_DS_CLASS_C_DEC:: 00134 ~PB_DS_BIN_TREE_NAME() 00135 { 00136 clear(); 00137 s_node_allocator.deallocate(m_p_head, 1); 00138 } 00139 00140 PB_DS_CLASS_T_DEC 00141 void 00142 PB_DS_CLASS_C_DEC:: 00143 initialize() 00144 { 00145 m_p_head->m_p_parent = 0; 00146 m_p_head->m_p_left = m_p_head; 00147 m_p_head->m_p_right = m_p_head; 00148 m_size = 0; 00149 } 00150 00151 PB_DS_CLASS_T_DEC 00152 typename PB_DS_CLASS_C_DEC::node_pointer 00153 PB_DS_CLASS_C_DEC:: 00154 recursive_copy_node(const node_pointer p_nd) 00155 { 00156 if (p_nd == 0) 00157 return (0); 00158 00159 node_pointer p_ret = s_node_allocator.allocate(1); 00160 __try 00161 { 00162 new (p_ret) node(*p_nd); 00163 } 00164 __catch(...) 00165 { 00166 s_node_allocator.deallocate(p_ret, 1); 00167 __throw_exception_again; 00168 } 00169 00170 p_ret->m_p_left = p_ret->m_p_right = 0; 00171 00172 __try 00173 { 00174 p_ret->m_p_left = recursive_copy_node(p_nd->m_p_left); 00175 p_ret->m_p_right = recursive_copy_node(p_nd->m_p_right); 00176 } 00177 __catch(...) 00178 { 00179 clear_imp(p_ret); 00180 __throw_exception_again; 00181 } 00182 00183 if (p_ret->m_p_left != 0) 00184 p_ret->m_p_left->m_p_parent = p_ret; 00185 00186 if (p_ret->m_p_right != 0) 00187 p_ret->m_p_right->m_p_parent = p_ret; 00188 00189 PB_DS_ASSERT_NODE_CONSISTENT(p_ret) 00190 return p_ret; 00191 } 00192 00193 PB_DS_CLASS_T_DEC 00194 void 00195 PB_DS_CLASS_C_DEC:: 00196 initialize_min_max() 00197 { 00198 if (m_p_head->m_p_parent == 0) 00199 { 00200 m_p_head->m_p_left = m_p_head->m_p_right = m_p_head; 00201 return; 00202 } 00203 00204 { 00205 node_pointer p_min = m_p_head->m_p_parent; 00206 while (p_min->m_p_left != 0) 00207 p_min = p_min->m_p_left; 00208 m_p_head->m_p_left = p_min; 00209 } 00210 00211 { 00212 node_pointer p_max = m_p_head->m_p_parent; 00213 while (p_max->m_p_right != 0) 00214 p_max = p_max->m_p_right; 00215 m_p_head->m_p_right = p_max; 00216 } 00217 } 00218