1// -*- C++ -*- 2 3// Copyright (C) 2005 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 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 2, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 31 32// Permission to use, copy, modify, sell, and distribute this software 33// is hereby granted without fee, provided that the above copyright 34// notice appears in all copies, and that both that copyright notice and 35// this permission notice appear in supporting documentation. None of 36// the above authors, nor IBM Haifa Research Laboratories, make any 37// representation about the suitability of this software for any 38// purpose. It is provided "as is" without express or implied warranty. 39 40/** 41 * @file constructors_destructor_fn_imps.hpp 42 * Contains an implementation class for bin_search_tree_. 43 */ 44 45PB_ASSOC_CLASS_T_DEC 46typename PB_ASSOC_CLASS_C_DEC::node_allocator 47PB_ASSOC_CLASS_C_DEC::s_node_allocator; 48 49PB_ASSOC_CLASS_T_DEC 50PB_ASSOC_CLASS_C_DEC:: 51PB_ASSOC_CLASS_NAME() : 52 m_p_head(s_node_allocator.allocate(1)), 53 m_end_it(m_p_head), 54 m_rend_it(m_p_head), 55 m_size(0) 56{ 57 initialize(); 58 59 PB_ASSOC_DBG_ONLY(assert_valid(true, true);) 60 } 61 62PB_ASSOC_CLASS_T_DEC 63PB_ASSOC_CLASS_C_DEC:: 64PB_ASSOC_CLASS_NAME(const Cmp_Fn& r_cmp_fn) : 65 Cmp_Fn(r_cmp_fn), 66 m_p_head(s_node_allocator.allocate(1)), 67 m_end_it(m_p_head), 68 m_rend_it(m_p_head), 69 m_size(0) 70{ 71 initialize(); 72 73 PB_ASSOC_DBG_ONLY(assert_valid(true, true);) 74 } 75 76PB_ASSOC_CLASS_T_DEC 77PB_ASSOC_CLASS_C_DEC:: 78PB_ASSOC_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const Node_Updator& r_node_updator) : 79 Cmp_Fn(r_cmp_fn), 80 Node_Updator(r_node_updator), 81 m_p_head(s_node_allocator.allocate(1)), 82 m_end_it(m_p_head), 83 m_rend_it(m_p_head), 84 m_size(0) 85{ 86 initialize(); 87 88 PB_ASSOC_DBG_ONLY(assert_valid(true, true);) 89 } 90 91PB_ASSOC_CLASS_T_DEC 92PB_ASSOC_CLASS_C_DEC:: 93PB_ASSOC_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other) : 94#ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_ 95 my_map_debug_base(r_other), 96#endif // #ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_ 97 Cmp_Fn(r_other), 98 Node_Updator(r_other), 99 m_p_head(s_node_allocator.allocate(1)), 100 m_end_it(m_p_head), 101 m_rend_it(m_p_head), 102 m_size(0) 103{ 104 initialize(); 105 106 m_size = r_other.m_size; 107 108 PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);) 109 110 try 111 { 112 m_p_head->m_p_parent = 113 recursive_copy_node(r_other.m_p_head->m_p_parent); 114 115 if (m_p_head->m_p_parent != NULL) 116 m_p_head->m_p_parent->m_p_parent = m_p_head; 117 118 m_size = r_other.m_size; 119 120 initialize_min_max(); 121 } 122 catch(...) 123 { 124 PB_ASSOC_DBG_ONLY(my_map_debug_base::clear();) 125 126 s_node_allocator.deallocate(m_p_head, 1); 127 128 throw; 129 } 130 131 PB_ASSOC_DBG_ONLY(assert_valid(true, true);) 132 } 133 134PB_ASSOC_CLASS_T_DEC 135void 136PB_ASSOC_CLASS_C_DEC:: 137swap(PB_ASSOC_CLASS_C_DEC& r_other) 138{ 139 PB_ASSOC_DBG_ONLY(assert_valid(true, true);) 140 PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);) 141 142 PB_ASSOC_DBG_ONLY(my_map_debug_base::swap(r_other);) 143 144 std::swap(m_p_head, r_other.m_p_head); 145 146 std::swap(m_size, r_other.m_size); 147 148 std::swap(m_end_it, r_other.m_end_it); 149 150 std::swap(m_rend_it, r_other.m_rend_it); 151 152 std::swap((Cmp_Fn& )(*this), (Cmp_Fn& )r_other); 153 154 Node_Updator::swap(r_other); 155 156 PB_ASSOC_DBG_ONLY(assert_valid(true, true);) 157 PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);) 158 } 159 160PB_ASSOC_CLASS_T_DEC 161PB_ASSOC_CLASS_C_DEC:: 162~PB_ASSOC_CLASS_NAME() 163{ 164 clear(); 165 166 s_node_allocator.deallocate(m_p_head, 1); 167} 168 169PB_ASSOC_CLASS_T_DEC 170void 171PB_ASSOC_CLASS_C_DEC:: 172initialize() 173{ 174 m_p_head->m_p_parent = NULL; 175 m_p_head->m_p_left = m_p_head; 176 m_p_head->m_p_right = m_p_head; 177 178 m_size = 0; 179} 180 181PB_ASSOC_CLASS_T_DEC 182typename PB_ASSOC_CLASS_C_DEC::node_pointer 183PB_ASSOC_CLASS_C_DEC:: 184recursive_copy_node(const node_pointer p_nd) 185{ 186 if (p_nd == NULL) 187 return (NULL); 188 189 node_pointer p_ret = s_node_allocator.allocate(1); 190 191 try 192 { 193 new (p_ret) node(*p_nd); 194 } 195 catch(...) 196 { 197 s_node_allocator.deallocate(p_ret, 1); 198 199 throw; 200 } 201 202 p_ret->m_p_left = p_ret->m_p_right = NULL; 203 204 try 205 { 206 p_ret->m_p_left = recursive_copy_node(p_nd->m_p_left); 207 208 p_ret->m_p_right = recursive_copy_node(p_nd->m_p_right); 209 } 210 catch(...) 211 { 212 clear_imp(p_ret); 213 214 throw; 215 } 216 217 if (p_ret->m_p_left != NULL) 218 p_ret->m_p_left->m_p_parent = p_ret; 219 220 if (p_ret->m_p_right != NULL) 221 p_ret->m_p_right->m_p_parent = p_ret; 222 223 PB_ASSOC_DBG_ONLY(assert_node_consistent(p_ret);) 224 225 return (p_ret); 226} 227 228PB_ASSOC_CLASS_T_DEC 229void 230PB_ASSOC_CLASS_C_DEC:: 231initialize_min_max() 232{ 233 if (m_p_head->m_p_parent == NULL) 234 { 235 m_p_head->m_p_left = m_p_head->m_p_right = m_p_head; 236 237 return; 238 } 239 240 { 241 node_pointer p_min = m_p_head->m_p_parent; 242 243 while (p_min->m_p_left != NULL) 244 p_min = p_min->m_p_left; 245 246 m_p_head->m_p_left = p_min; 247 } 248 249 { 250 node_pointer p_max = m_p_head->m_p_parent; 251 252 while (p_max->m_p_right != NULL) 253 p_max = p_max->m_p_right; 254 255 m_p_head->m_p_right = p_max; 256 } 257} 258 259