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