1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2007, 2008, 2009 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 erase_fn_imps.hpp 38 * Contains an implementation class for a binary_heap. 39 */ 40 41 PB_DS_CLASS_T_DEC 42 void 43 PB_DS_CLASS_C_DEC:: 44 clear() 45 { 46 for (size_type i = 0; i < m_size; ++i) 47 erase_at(m_a_entries, i, s_no_throw_copies_ind); 48 49 __try 50 { 51 const size_type actual_size = resize_policy::get_new_size_for_arbitrary(0); 52 53 entry_pointer a_entries = s_entry_allocator.allocate(actual_size); 54 55 resize_policy::notify_arbitrary(actual_size); 56 57 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 58 59 m_actual_size = actual_size; 60 61 m_a_entries = a_entries; 62 } 63 __catch(...) 64 { } 65 66 m_size = 0; 67 68 _GLIBCXX_DEBUG_ONLY(assert_valid();) 69 } 70 71 PB_DS_CLASS_T_DEC 72 void 73 PB_DS_CLASS_C_DEC:: 74 erase_at(entry_pointer a_entries, size_type i, false_type) 75 { 76 a_entries[i]->~value_type(); 77 78 s_value_allocator.deallocate(a_entries[i], 1); 79 } 80 81 PB_DS_CLASS_T_DEC 82 void 83 PB_DS_CLASS_C_DEC:: 84 erase_at(entry_pointer, size_type, true_type) 85 { } 86 87 PB_DS_CLASS_T_DEC 88 inline void 89 PB_DS_CLASS_C_DEC:: 90 pop() 91 { 92 _GLIBCXX_DEBUG_ONLY(assert_valid();) 93 _GLIBCXX_DEBUG_ASSERT(!empty()); 94 95 erase_at(m_a_entries, 0, s_no_throw_copies_ind); 96 97 std::pop_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this)); 98 99 resize_for_erase_if_needed(); 100 101 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 102 --m_size; 103 104 _GLIBCXX_DEBUG_ONLY(assert_valid();) 105 } 106 107 PB_DS_CLASS_T_DEC 108 template<typename Pred> 109 typename PB_DS_CLASS_C_DEC::size_type 110 PB_DS_CLASS_C_DEC:: 111 erase_if(Pred pred) 112 { 113 _GLIBCXX_DEBUG_ONLY(assert_valid();) 114 115 typedef 116 typename entry_pred< 117 value_type, 118 Pred, 119 simple_value, 120 Allocator>::type 121 pred_t; 122 123 const size_type left = partition(pred_t(pred)); 124 125 _GLIBCXX_DEBUG_ASSERT(m_size >= left); 126 127 const size_type ersd = m_size - left; 128 129 for (size_type i = left; i < m_size; ++i) 130 erase_at(m_a_entries, i, s_no_throw_copies_ind); 131 132 __try 133 { 134 const size_type actual_size = 135 resize_policy::get_new_size_for_arbitrary(left); 136 137 entry_pointer a_entries = s_entry_allocator.allocate(actual_size); 138 139 std::copy(m_a_entries, m_a_entries + left, a_entries); 140 141 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 142 143 m_actual_size = actual_size; 144 145 resize_policy::notify_arbitrary(m_actual_size); 146 } 147 __catch(...) 148 { }; 149 150 m_size = left; 151 152 std::make_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this)); 153 154 _GLIBCXX_DEBUG_ONLY(assert_valid();) 155 156 return ersd; 157 } 158 159 PB_DS_CLASS_T_DEC 160 inline void 161 PB_DS_CLASS_C_DEC:: 162 erase(point_iterator it) 163 { 164 _GLIBCXX_DEBUG_ONLY(assert_valid();) 165 _GLIBCXX_DEBUG_ASSERT(!empty()); 166 167 const size_type fix_pos = it.m_p_e - m_a_entries; 168 169 std::swap(*it.m_p_e, m_a_entries[m_size - 1]); 170 171 erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind); 172 173 resize_for_erase_if_needed(); 174 175 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 176 --m_size; 177 178 _GLIBCXX_DEBUG_ASSERT(fix_pos <= m_size); 179 180 if (fix_pos != m_size) 181 fix(m_a_entries + fix_pos); 182 183 _GLIBCXX_DEBUG_ONLY(assert_valid();) 184 } 185 186 PB_DS_CLASS_T_DEC 187 inline void 188 PB_DS_CLASS_C_DEC:: 189 resize_for_erase_if_needed() 190 { 191 if (!resize_policy::resize_needed_for_shrink(m_size)) 192 return; 193 194 __try 195 { 196 const size_type new_actual_size = 197 resize_policy::get_new_size_for_shrink(); 198 199 entry_pointer a_new_entries = s_entry_allocator.allocate(new_actual_size); 200 201 resize_policy::notify_shrink_resize(); 202 203 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 204 std::copy(m_a_entries, m_a_entries + m_size - 1, a_new_entries); 205 206 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 207 208 m_actual_size = new_actual_size; 209 210 m_a_entries = a_new_entries; 211 } 212 __catch(...) 213 { } 214 } 215 216 PB_DS_CLASS_T_DEC 217 template<typename Pred> 218 typename PB_DS_CLASS_C_DEC::size_type 219 PB_DS_CLASS_C_DEC:: 220 partition(Pred pred) 221 { 222 size_type left = 0; 223 size_type right = m_size - 1; 224 225 while (right + 1 != left) 226 { 227 _GLIBCXX_DEBUG_ASSERT(left <= m_size); 228 229 if (!pred(m_a_entries[left])) 230 ++left; 231 else if (pred(m_a_entries[right])) 232 --right; 233 else 234 { 235 _GLIBCXX_DEBUG_ASSERT(left < right); 236 237 std::swap(m_a_entries[left], m_a_entries[right]); 238 239 ++left; 240 --right; 241 } 242 } 243 244 return left; 245 } 246 247
