1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2011 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the terms 8 // of the GNU General Public License as published by the Free Software 9 // Foundation; either version 3, or (at your option) any later 10 // version. 11 12 // This library is distributed in the hope that it will be useful, but 13 // WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 // General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 27 28 // Permission to use, copy, modify, sell, and distribute this software 29 // is hereby granted without fee, provided that the above copyright 30 // notice appears in all copies, and that both that copyright notice 31 // and this permission notice appear in supporting documentation. None 32 // of the above authors, nor IBM Haifa Research Laboratories, make any 33 // representation about the suitability of this software for any 34 // purpose. It is provided "as is" without express or implied 35 // warranty. 36 37 /** 38 * @file erase_fn_imps.hpp 39 * Contains an implementation class for a binary_heap. 40 */ 41 42 PB_DS_CLASS_T_DEC 43 void 44 PB_DS_CLASS_C_DEC:: 45 clear() 46 { 47 for (size_type i = 0; i < m_size; ++i) 48 erase_at(m_a_entries, i, s_no_throw_copies_ind); 49 50 __try 51 { 52 const size_type actual_size = resize_policy::get_new_size_for_arbitrary(0); 53 54 entry_pointer a_entries = s_entry_allocator.allocate(actual_size); 55 56 resize_policy::notify_arbitrary(actual_size); 57 58 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 59 60 m_actual_size = actual_size; 61 62 m_a_entries = a_entries; 63 } 64 __catch(...) 65 { } 66 67 m_size = 0; 68 69 _GLIBCXX_DEBUG_ONLY(assert_valid();) 70 } 71 72 PB_DS_CLASS_T_DEC 73 void 74 PB_DS_CLASS_C_DEC:: 75 erase_at(entry_pointer a_entries, size_type i, false_type) 76 { 77 a_entries[i]->~value_type(); 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, 98 static_cast<entry_cmp& >(*this)); 99 100 resize_for_erase_if_needed(); 101 102 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 103 --m_size; 104 105 _GLIBCXX_DEBUG_ONLY(assert_valid();) 106 } 107 108 PB_DS_CLASS_T_DEC 109 template<typename Pred> 110 typename PB_DS_CLASS_C_DEC::size_type 111 PB_DS_CLASS_C_DEC:: 112 erase_if(Pred pred) 113 { 114 _GLIBCXX_DEBUG_ONLY(assert_valid();) 115 116 typedef typename entry_pred<value_type, Pred, simple_value, Allocator>::type 117 pred_t; 118 119 const size_type left = partition(pred_t(pred)); 120 121 _GLIBCXX_DEBUG_ASSERT(m_size >= left); 122 123 const size_type ersd = m_size - left; 124 125 for (size_type i = left; i < m_size; ++i) 126 erase_at(m_a_entries, i, s_no_throw_copies_ind); 127 128 __try 129 { 130 const size_type actual_size = 131 resize_policy::get_new_size_for_arbitrary(left); 132 133 entry_pointer a_entries = s_entry_allocator.allocate(actual_size); 134 135 std::copy(m_a_entries, m_a_entries + left, a_entries); 136 137 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 138 139 m_actual_size = actual_size; 140 141 resize_policy::notify_arbitrary(m_actual_size); 142 } 143 __catch(...) 144 { }; 145 146 m_size = left; 147 148 std::make_heap(m_a_entries, m_a_entries + m_size, 149 static_cast<entry_cmp& >(*this)); 150 151 _GLIBCXX_DEBUG_ONLY(assert_valid();) 152 153 return ersd; 154 } 155 156 PB_DS_CLASS_T_DEC 157 inline void 158 PB_DS_CLASS_C_DEC:: 159 erase(point_iterator it) 160 { 161 _GLIBCXX_DEBUG_ONLY(assert_valid();) 162 _GLIBCXX_DEBUG_ASSERT(!empty()); 163 164 const size_type fix_pos = it.m_p_e - m_a_entries; 165 166 std::swap(*it.m_p_e, m_a_entries[m_size - 1]); 167 168 erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind); 169 170 resize_for_erase_if_needed(); 171 172 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 173 --m_size; 174 175 _GLIBCXX_DEBUG_ASSERT(fix_pos <= m_size); 176 177 if (fix_pos != m_size) 178 fix(m_a_entries + fix_pos); 179 180 _GLIBCXX_DEBUG_ONLY(assert_valid();) 181 } 182 183 PB_DS_CLASS_T_DEC 184 inline void 185 PB_DS_CLASS_C_DEC:: 186 resize_for_erase_if_needed() 187 { 188 if (!resize_policy::resize_needed_for_shrink(m_size)) 189 return; 190 191 __try 192 { 193 const size_type new_actual_size = 194 resize_policy::get_new_size_for_shrink(); 195 196 entry_pointer a_new_entries = s_entry_allocator.allocate(new_actual_size); 197 198 resize_policy::notify_shrink_resize(); 199 200 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 201 std::copy(m_a_entries, m_a_entries + m_size - 1, a_new_entries); 202 203 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 204 205 m_actual_size = new_actual_size; 206 207 m_a_entries = a_new_entries; 208 } 209 __catch(...) 210 { } 211 } 212 213 PB_DS_CLASS_T_DEC 214 template<typename Pred> 215 typename PB_DS_CLASS_C_DEC::size_type 216 PB_DS_CLASS_C_DEC:: 217 partition(Pred pred) 218 { 219 size_type left = 0; 220 size_type right = m_size - 1; 221 222 while (right + 1 != left) 223 { 224 _GLIBCXX_DEBUG_ASSERT(left <= m_size); 225 226 if (!pred(m_a_entries[left])) 227 ++left; 228 else if (pred(m_a_entries[right])) 229 --right; 230 else 231 { 232 _GLIBCXX_DEBUG_ASSERT(left < right); 233 234 std::swap(m_a_entries[left], m_a_entries[right]); 235 236 ++left; 237 --right; 238 } 239 } 240 241 return left; 242 } 243
