]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
a5544970 | 3 | // Copyright (C) 2005-2019 Free Software Foundation, Inc. |
4569a895 AT |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
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 | ||
748086b7 JJ |
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. | |
4569a895 | 19 | |
748086b7 JJ |
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/>. | |
4569a895 AT |
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 | /** | |
a345e45d | 37 | * @file ov_tree_map_/erase_fn_imps.hpp |
4569a895 AT |
38 | * Contains an implementation class for ov_tree_. |
39 | */ | |
40 | ||
41 | PB_DS_CLASS_T_DEC | |
42 | void | |
43 | PB_DS_CLASS_C_DEC:: | |
44 | clear() | |
45 | { | |
f5886803 | 46 | PB_DS_ASSERT_VALID((*this)) |
1b24692f BK |
47 | if (m_size == 0) |
48 | { | |
1b24692f BK |
49 | return; |
50 | } | |
51 | else | |
52 | { | |
53 | reallocate_metadata((node_update* )this, 0); | |
54 | cond_dtor<size_type> cd(m_a_values, m_end_it, m_size); | |
55 | } | |
4569a895 | 56 | |
551fe1a2 | 57 | _GLIBCXX_DEBUG_ONLY(debug_base::clear();) |
8fc81078 | 58 | m_a_values = 0; |
4569a895 | 59 | m_size = 0; |
4569a895 | 60 | m_end_it = m_a_values; |
f5886803 | 61 | PB_DS_ASSERT_VALID((*this)) |
1b24692f | 62 | } |
4569a895 AT |
63 | |
64 | PB_DS_CLASS_T_DEC | |
65 | template<typename Pred> | |
66 | inline typename PB_DS_CLASS_C_DEC::size_type | |
67 | PB_DS_CLASS_C_DEC:: | |
68 | erase_if(Pred pred) | |
69 | { | |
f5886803 | 70 | PB_DS_ASSERT_VALID((*this)) |
4569a895 AT |
71 | |
72 | #ifdef PB_DS_REGRESSION | |
a345e45d BK |
73 | typename _Alloc::group_adjustor adjust(m_size); |
74 | #endif | |
4569a895 AT |
75 | |
76 | size_type new_size = 0; | |
4569a895 | 77 | size_type num_val_ersd = 0; |
a345e45d | 78 | |
f5886803 | 79 | for (iterator source_it = begin(); source_it != m_end_it; ++source_it) |
4569a895 AT |
80 | if (!pred(*source_it)) |
81 | ++new_size; | |
82 | else | |
83 | ++num_val_ersd; | |
84 | ||
85 | if (new_size == 0) | |
86 | { | |
87 | clear(); | |
1b24692f | 88 | return num_val_ersd; |
4569a895 AT |
89 | } |
90 | ||
91 | value_vector a_new_values = s_value_alloc.allocate(new_size); | |
4569a895 | 92 | iterator target_it = a_new_values; |
4569a895 | 93 | cond_dtor<size_type> cd(a_new_values, target_it, new_size); |
551fe1a2 | 94 | _GLIBCXX_DEBUG_ONLY(debug_base::clear()); |
f5886803 | 95 | for (iterator source_it = begin(); source_it != m_end_it; ++source_it) |
4569a895 AT |
96 | { |
97 | if (!pred(*source_it)) | |
a345e45d BK |
98 | { |
99 | new (const_cast<void*>(static_cast<const void*>(target_it))) | |
4569a895 AT |
100 | value_type(*source_it); |
101 | ||
551fe1a2 | 102 | _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(*source_it))); |
4569a895 | 103 | ++target_it; |
a345e45d | 104 | } |
4569a895 AT |
105 | } |
106 | ||
a345e45d | 107 | reallocate_metadata((node_update*)this, new_size); |
4569a895 AT |
108 | cd.set_no_action(); |
109 | ||
110 | { | |
111 | cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size); | |
112 | } | |
113 | ||
114 | m_a_values = a_new_values; | |
4569a895 | 115 | m_size = new_size; |
4569a895 | 116 | m_end_it = target_it; |
a345e45d | 117 | update(node_begin(), (node_update*)this); |
f5886803 | 118 | PB_DS_ASSERT_VALID((*this)) |
1b24692f | 119 | return num_val_ersd; |
4569a895 AT |
120 | } |
121 | ||
122 | PB_DS_CLASS_T_DEC | |
123 | template<typename It> | |
124 | It | |
125 | PB_DS_CLASS_C_DEC:: | |
126 | erase_imp(It it) | |
127 | { | |
f5886803 | 128 | PB_DS_ASSERT_VALID((*this)) |
1b24692f BK |
129 | if (it == end()) |
130 | return end(); | |
4569a895 | 131 | |
f5886803 | 132 | PB_DS_CHECK_KEY_EXISTS(PB_DS_V2F(*it)) |
4569a895 AT |
133 | |
134 | #ifdef PB_DS_REGRESSION | |
a345e45d BK |
135 | typename _Alloc::group_adjustor adjust(m_size); |
136 | #endif | |
4569a895 | 137 | |
47bea7b8 | 138 | _GLIBCXX_DEBUG_ASSERT(m_size > 0); |
4569a895 | 139 | value_vector a_values = s_value_alloc.allocate(m_size - 1); |
4569a895 AT |
140 | iterator source_it = begin(); |
141 | iterator source_end_it = end(); | |
142 | iterator target_it = a_values; | |
143 | iterator ret_it = end(); | |
144 | ||
145 | cond_dtor<size_type> cd(a_values, target_it, m_size - 1); | |
146 | ||
47bea7b8 | 147 | _GLIBCXX_DEBUG_ONLY(size_type cnt = 0;) |
4569a895 | 148 | |
1b24692f BK |
149 | while (source_it != source_end_it) |
150 | { | |
151 | if (source_it != it) | |
152 | { | |
a345e45d | 153 | _GLIBCXX_DEBUG_ONLY(++cnt;) |
1b24692f | 154 | _GLIBCXX_DEBUG_ASSERT(cnt != m_size); |
a345e45d | 155 | new (const_cast<void*>(static_cast<const void*>(target_it))) |
4569a895 AT |
156 | value_type(*source_it); |
157 | ||
a345e45d | 158 | ++target_it; |
1b24692f BK |
159 | } |
160 | else | |
161 | ret_it = target_it; | |
162 | ++source_it; | |
163 | } | |
4569a895 | 164 | |
47bea7b8 | 165 | _GLIBCXX_DEBUG_ASSERT(m_size > 0); |
a345e45d | 166 | reallocate_metadata((node_update*)this, m_size - 1); |
4569a895 | 167 | cd.set_no_action(); |
a345e45d | 168 | _GLIBCXX_DEBUG_ONLY(debug_base::erase_existing(PB_DS_V2F(*it));) |
1b24692f BK |
169 | { |
170 | cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size); | |
171 | } | |
4569a895 AT |
172 | |
173 | m_a_values = a_values; | |
4569a895 | 174 | --m_size; |
4569a895 | 175 | m_end_it = m_a_values + m_size; |
a345e45d | 176 | update(node_begin(), (node_update*)this); |
f5886803 | 177 | PB_DS_ASSERT_VALID((*this)) |
1b24692f | 178 | return It(ret_it); |
4569a895 AT |
179 | } |
180 | ||
181 | PB_DS_CLASS_T_DEC | |
182 | bool | |
183 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 184 | erase(key_const_reference r_key) |
4569a895 AT |
185 | { |
186 | point_iterator it = find(r_key); | |
4569a895 | 187 | if (it == end()) |
1b24692f | 188 | return false; |
4569a895 | 189 | erase(it); |
1b24692f | 190 | return true; |
4569a895 | 191 | } |