1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING. If not, write to 18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19// MA 02111-1307, USA. 20 21// As a special exception, you may use this file as part of a free 22// software library without restriction. Specifically, if other files 23// instantiate templates or use macros or inline functions from this 24// file, or you compile this file and link it with other files to 25// produce an executable, this file does not by itself cause the 26// resulting executable to be covered by the GNU General Public 27// License. This exception does not however invalidate any other 28// reasons why the executable file might be covered by the GNU General 29// Public License. 30 31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33// Permission to use, copy, modify, sell, and distribute this software 34// is hereby granted without fee, provided that the above copyright 35// notice appears in all copies, and that both that copyright notice 36// and this permission notice appear in supporting documentation. None 37// of the above authors, nor IBM Haifa Research Laboratories, make any 38// representation about the suitability of this software for any 39// purpose. It is provided "as is" without express or implied 40// warranty. 41 42/** 43 * @file erase_fn_imps.hpp 44 * Contains an implementation for thin_heap_. 45 */ 46 47PB_DS_CLASS_T_DEC 48void 49PB_DS_CLASS_C_DEC:: 50pop() 51{ 52 _GLIBCXX_DEBUG_ONLY(assert_valid();) 53 _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); 54 55 _GLIBCXX_DEBUG_ASSERT(m_p_max != NULL); 56 57 node_pointer p_nd = m_p_max; 58 59 remove_max_node(); 60 61 base_type::actual_erase_node(p_nd); 62 63 _GLIBCXX_DEBUG_ONLY(assert_valid();) 64 } 65 66PB_DS_CLASS_T_DEC 67inline void 68PB_DS_CLASS_C_DEC:: 69remove_max_node() 70{ 71 to_aux_except_max(); 72 73 make_from_aux(); 74} 75 76PB_DS_CLASS_T_DEC 77void 78PB_DS_CLASS_C_DEC:: 79to_aux_except_max() 80{ 81 node_pointer p_add = base_type::m_p_root; 82 83 while (p_add != m_p_max) 84 { 85 node_pointer p_next_add = p_add->m_p_next_sibling; 86 87 add_to_aux(p_add); 88 89 p_add = p_next_add; 90 } 91 92 p_add = m_p_max->m_p_l_child; 93 94 while (p_add != NULL) 95 { 96 node_pointer p_next_add = p_add->m_p_next_sibling; 97 98 p_add->m_metadata = p_add->m_p_l_child == NULL? 99 0 : 100 p_add->m_p_l_child->m_metadata + 1; 101 102 add_to_aux(p_add); 103 104 p_add = p_next_add; 105 } 106 107 p_add = m_p_max->m_p_next_sibling; 108 109 while (p_add != NULL) 110 { 111 node_pointer p_next_add = p_add->m_p_next_sibling; 112 113 add_to_aux(p_add); 114 115 p_add = p_next_add; 116 } 117} 118 119PB_DS_CLASS_T_DEC 120inline void 121PB_DS_CLASS_C_DEC:: 122add_to_aux(node_pointer p_nd) 123{ 124 size_type r = p_nd->m_metadata; 125 126 while (m_a_aux[r] != NULL) 127 { 128 _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound()); 129 130 if (Cmp_Fn::operator()(m_a_aux[r]->m_value, p_nd->m_value)) 131 make_child_of(m_a_aux[r], p_nd); 132 else 133 { 134 make_child_of(p_nd, m_a_aux[r]); 135 136 p_nd = m_a_aux[r]; 137 } 138 139 m_a_aux[r] = NULL; 140 141 ++r; 142 } 143 144 _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound()); 145 146 m_a_aux[r] = p_nd; 147} 148 149PB_DS_CLASS_T_DEC 150inline void 151PB_DS_CLASS_C_DEC:: 152make_child_of(node_pointer p_nd, node_pointer p_new_parent) 153{ 154 _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata == p_new_parent->m_metadata); 155 _GLIBCXX_DEBUG_ASSERT(m_a_aux[p_nd->m_metadata] == p_nd || 156 m_a_aux[p_nd->m_metadata] == p_new_parent); 157 158 ++p_new_parent->m_metadata; 159 160 base_type::make_child_of(p_nd, p_new_parent); 161} 162 163PB_DS_CLASS_T_DEC 164inline void 165PB_DS_CLASS_C_DEC:: 166make_from_aux() 167{ 168 base_type::m_p_root = m_p_max = NULL; 169 170 const size_type rnk_bnd = rank_bound(); 171 172 size_type i = 0; 173 174 while (i < rnk_bnd) 175 { 176 if (m_a_aux[i] != NULL) 177 { 178 make_root_and_link(m_a_aux[i]); 179 180 m_a_aux[i] = NULL; 181 } 182 183 ++i; 184 } 185 186 _GLIBCXX_DEBUG_ONLY(assert_aux_null();) 187 } 188 189PB_DS_CLASS_T_DEC 190inline void 191PB_DS_CLASS_C_DEC:: 192remove_node(node_pointer p_nd) 193{ 194 node_pointer p_parent = p_nd; 195 while (base_type::parent(p_parent) != NULL) 196 p_parent = base_type::parent(p_parent); 197 198 base_type::bubble_to_top(p_nd); 199 200 m_p_max = p_nd; 201 202 node_pointer p_fix = base_type::m_p_root; 203 while (p_fix != NULL&& p_fix->m_p_next_sibling != p_parent) 204 p_fix = p_fix->m_p_next_sibling; 205 206 if (p_fix != NULL) 207 p_fix->m_p_next_sibling = p_nd; 208 209 remove_max_node(); 210} 211 212PB_DS_CLASS_T_DEC 213inline void 214PB_DS_CLASS_C_DEC:: 215clear() 216{ 217 base_type::clear(); 218 219 m_p_max = NULL; 220} 221 222PB_DS_CLASS_T_DEC 223void 224PB_DS_CLASS_C_DEC:: 225erase(point_iterator it) 226{ 227 _GLIBCXX_DEBUG_ONLY(assert_valid();) 228 _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); 229 230 node_pointer p_nd = it.m_p_nd; 231 232 remove_node(p_nd); 233 234 base_type::actual_erase_node(p_nd); 235 236 _GLIBCXX_DEBUG_ONLY(assert_valid();) 237 } 238 239PB_DS_CLASS_T_DEC 240template<typename Pred> 241typename PB_DS_CLASS_C_DEC::size_type 242PB_DS_CLASS_C_DEC:: 243erase_if(Pred pred) 244{ 245 _GLIBCXX_DEBUG_ONLY(assert_valid();) 246 247 if (base_type::empty()) 248 { 249 _GLIBCXX_DEBUG_ONLY(assert_valid();) 250 251 return 0; 252 } 253 254 base_type::to_linked_list(); 255 256 node_pointer p_out = base_type::prune(pred); 257 258 size_type ersd = 0; 259 260 while (p_out != NULL) 261 { 262 ++ersd; 263 264 node_pointer p_next = p_out->m_p_next_sibling; 265 266 base_type::actual_erase_node(p_out); 267 268 p_out = p_next; 269 } 270 271 node_pointer p_cur = base_type::m_p_root; 272 273 m_p_max = base_type::m_p_root = NULL; 274 275 while (p_cur != NULL) 276 { 277 node_pointer p_next = p_cur->m_p_next_sibling; 278 279 make_root_and_link(p_cur); 280 281 p_cur = p_next; 282 } 283 284 _GLIBCXX_DEBUG_ONLY(assert_valid();) 285 286 return ersd; 287} 288 289PB_DS_CLASS_T_DEC 290inline typename PB_DS_CLASS_C_DEC::size_type 291PB_DS_CLASS_C_DEC:: 292rank_bound() 293{ 294 const std::size_t* const p_upper = 295 std::upper_bound( g_a_rank_bounds, g_a_rank_bounds + num_distinct_rank_bounds, base_type::m_size); 296 297 if (p_upper == g_a_rank_bounds + num_distinct_rank_bounds) 298 return max_rank; 299 300 return (p_upper - g_a_rank_bounds); 301} 302 303