erase_fn_imps.hpp revision 169691 
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 class for bin_search_tree_.
45 */
46
47PB_DS_CLASS_T_DEC
48inline bool
49PB_DS_CLASS_C_DEC::
50erase(const_key_reference r_key)
51{
52  node_pointer p_nd = find_imp(r_key);
53  if (p_nd == NULL || p_nd->m_type == pat_trie_internal_node_type)
54    {
55      _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key));
56      return false;
57    }
58
59  _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type);
60  if (!synth_e_access_traits::equal_keys(PB_DS_V2F(reinterpret_cast<leaf_pointer>(p_nd)->value()), r_key))
61    {
62      _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key));
63      return false;
64    }
65
66  _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key));
67  erase_leaf(static_cast<leaf_pointer>(p_nd));
68  _GLIBCXX_DEBUG_ONLY(assert_valid();)
69  return true;
70}
71
72PB_DS_CLASS_T_DEC
73void
74PB_DS_CLASS_C_DEC::
75erase_fixup(internal_node_pointer p_nd)
76{
77  _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) >= 1);
78  if (std::distance(p_nd->begin(), p_nd->end()) == 1)
79    {
80      node_pointer p_parent = p_nd->m_p_parent;
81      if (p_parent == m_p_head)
82	m_p_head->m_p_parent =* p_nd->begin();
83      else
84        {
85	  _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == pat_trie_internal_node_type);
86	  node_pointer p_new_child =* p_nd->begin();
87	  static_cast<internal_node_pointer>(p_parent)->replace_child(
88								      p_new_child,
89								      pref_begin(p_new_child),
90								      pref_end(p_new_child),
91								      this);
92        }
93      (*p_nd->begin())->m_p_parent = p_nd->m_p_parent;
94      p_nd->~internal_node();
95      s_internal_node_allocator.deallocate(p_nd, 1);
96
97      if (p_parent == m_p_head)
98	return;
99
100      _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == pat_trie_internal_node_type);
101      p_nd = static_cast<internal_node_pointer>(p_parent);
102    }
103
104  while (true)
105    {
106      _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) > 1);
107      p_nd->update_prefixes(this);
108      apply_update(p_nd, (node_update* )this);
109      _GLIBCXX_DEBUG_ONLY(p_nd->assert_valid(this);)
110      if (p_nd->m_p_parent->m_type == pat_trie_head_node_type)
111        return;
112
113      _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent->m_type ==
114		       pat_trie_internal_node_type);
115
116      p_nd = static_cast<internal_node_pointer>(p_nd->m_p_parent);
117    }
118}
119
120PB_DS_CLASS_T_DEC
121inline void
122PB_DS_CLASS_C_DEC::
123actual_erase_leaf(leaf_pointer p_l)
124{
125  _GLIBCXX_DEBUG_ASSERT(m_size > 0);
126  --m_size;
127  _GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_l->value())));
128  p_l->~leaf();
129  s_leaf_allocator.deallocate(p_l, 1);
130}
131
132PB_DS_CLASS_T_DEC
133void
134PB_DS_CLASS_C_DEC::
135clear()
136{
137  _GLIBCXX_DEBUG_ONLY(assert_valid();)
138  if (empty())
139    return;
140
141  clear_imp(m_p_head->m_p_parent);
142  m_size = 0;
143  initialize();
144  _GLIBCXX_DEBUG_ONLY(map_debug_base::clear();)
145  _GLIBCXX_DEBUG_ONLY(assert_valid();)
146}
147
148PB_DS_CLASS_T_DEC
149void
150PB_DS_CLASS_C_DEC::
151clear_imp(node_pointer p_nd)
152{
153  if (p_nd->m_type == pat_trie_internal_node_type)
154    {
155      _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type);
156      for (typename internal_node::iterator it =
157	     static_cast<internal_node_pointer>(p_nd)->begin();
158	   it != static_cast<internal_node_pointer>(p_nd)->end();
159	   ++it)
160        {
161	  node_pointer p_child =* it;
162	  clear_imp(p_child);
163        }
164      s_internal_node_allocator.deallocate(static_cast<internal_node_pointer>(p_nd), 1);
165      return;
166    }
167
168  _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type);
169  static_cast<leaf_pointer>(p_nd)->~leaf();
170  s_leaf_allocator.deallocate(static_cast<leaf_pointer>(p_nd), 1);
171}
172
173PB_DS_CLASS_T_DEC
174inline typename PB_DS_CLASS_C_DEC::const_iterator
175PB_DS_CLASS_C_DEC::
176erase(const_iterator it)
177{
178  _GLIBCXX_DEBUG_ONLY(assert_valid());
179
180  if (it == end())
181    return it;
182
183  const_iterator ret_it = it;
184  ++ret_it;
185  _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type);
186  erase_leaf(static_cast<leaf_pointer>(it.m_p_nd));
187  _GLIBCXX_DEBUG_ONLY(assert_valid());
188  return ret_it;
189}
190
191#ifdef PB_DS_DATA_TRUE_INDICATOR
192PB_DS_CLASS_T_DEC
193inline typename PB_DS_CLASS_C_DEC::iterator
194PB_DS_CLASS_C_DEC::
195erase(iterator it)
196{
197  _GLIBCXX_DEBUG_ONLY(assert_valid());
198
199  if (it == end())
200    return it;
201  iterator ret_it = it;
202  ++ret_it;
203  _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type);
204  erase_leaf(static_cast<leaf_pointer>(it.m_p_nd));
205  _GLIBCXX_DEBUG_ONLY(assert_valid());
206  return ret_it;
207}
208#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
209
210PB_DS_CLASS_T_DEC
211inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator
212PB_DS_CLASS_C_DEC::
213erase(const_reverse_iterator it)
214{
215  _GLIBCXX_DEBUG_ONLY(assert_valid());
216
217  if (it.m_p_nd == m_p_head)
218    return it;
219  const_reverse_iterator ret_it = it;
220  ++ret_it;
221
222  _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type);
223  erase_leaf(static_cast<leaf_pointer>(it.m_p_nd));
224  _GLIBCXX_DEBUG_ONLY(assert_valid());
225  return ret_it;
226}
227
228#ifdef PB_DS_DATA_TRUE_INDICATOR
229PB_DS_CLASS_T_DEC
230inline typename PB_DS_CLASS_C_DEC::reverse_iterator
231PB_DS_CLASS_C_DEC::
232erase(reverse_iterator it)
233{
234  _GLIBCXX_DEBUG_ONLY(assert_valid());
235
236  if (it.m_p_nd == m_p_head)
237    return it;
238  reverse_iterator ret_it = it;
239  ++ret_it;
240
241  _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type);
242  erase_leaf(static_cast<leaf_pointer>(it.m_p_nd));
243  _GLIBCXX_DEBUG_ONLY(assert_valid());
244  return ret_it;
245}
246#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
247
248PB_DS_CLASS_T_DEC
249template<typename Pred>
250inline typename PB_DS_CLASS_C_DEC::size_type
251PB_DS_CLASS_C_DEC::
252erase_if(Pred pred)
253{
254  size_type num_ersd = 0;
255  _GLIBCXX_DEBUG_ONLY(assert_valid();)
256
257  iterator it = begin();
258  while (it != end())
259    {
260      _GLIBCXX_DEBUG_ONLY(assert_valid();)
261        if (pred(*it))
262	  {
263            ++num_ersd;
264            it = erase(it);
265	  }
266        else
267	  ++it;
268    }
269
270  _GLIBCXX_DEBUG_ONLY(assert_valid();)
271  return num_ersd;
272}
273
274PB_DS_CLASS_T_DEC
275void
276PB_DS_CLASS_C_DEC::
277erase_leaf(leaf_pointer p_l)
278{
279  update_min_max_for_erased_leaf(p_l);
280  if (p_l->m_p_parent->m_type == pat_trie_head_node_type)
281    {
282      _GLIBCXX_DEBUG_ASSERT(size() == 1);
283      clear();
284      return;
285    }
286
287  _GLIBCXX_DEBUG_ASSERT(size() > 1);
288  _GLIBCXX_DEBUG_ASSERT(p_l->m_p_parent->m_type ==
289		   pat_trie_internal_node_type);
290
291  internal_node_pointer p_parent =
292    static_cast<internal_node_pointer>(p_l->m_p_parent);
293
294  p_parent->remove_child(p_l);
295  erase_fixup(p_parent);
296  actual_erase_leaf(p_l);
297}
298
299PB_DS_CLASS_T_DEC
300void
301PB_DS_CLASS_C_DEC::
302update_min_max_for_erased_leaf(leaf_pointer p_l)
303{
304  if (m_size == 1)
305    {
306      m_p_head->m_p_min = m_p_head;
307      m_p_head->m_p_max = m_p_head;
308      return;
309    }
310
311  if (p_l == static_cast<const_leaf_pointer>(m_p_head->m_p_min))
312    {
313      iterator it(p_l);
314      ++it;
315      m_p_head->m_p_min = it.m_p_nd;
316      return;
317    }
318
319  if (p_l == static_cast<const_leaf_pointer>(m_p_head->m_p_max))
320    {
321      iterator it(p_l);
322      --it;
323      m_p_head->m_p_max = it.m_p_nd;
324    }
325}
326