OpenCores
URL https://opencores.org/ocsvn/scarts/scarts/trunk

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [libstdc++-v3/] [include/] [ext/] [pb_assoc/] [detail/] [rb_tree_map_/] [erase_fn_imps.hpp] - Blame information for rev 17

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 17 jlechner 
// -*- C++ -*-
2 
 
3 
// Copyright (C) 2005 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
7 
// terms of the GNU General Public License as published by the
8 
// Free Software Foundation; either version 2, or (at your option)
9 
// any later version.
10 
 
11 
// This library is distributed in the hope that it will be useful,
12 
// but WITHOUT ANY WARRANTY; without even the implied warranty of
13 
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 
// GNU General Public License for more details.
15 
 
16 
// You should have received a copy of the GNU General Public License along
17 
// with this library; see the file COPYING.  If not, write to the Free
18 
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
19 
// USA.
20 
 
21 
// As a special exception, you may use this file as part of a free software
22 
// library without restriction.  Specifically, if other files instantiate
23 
// templates or use macros or inline functions from this file, or you compile
24 
// this file and link it with other files to produce an executable, this
25 
// file does not by itself cause the resulting executable to be covered by
26 
// the GNU General Public License.  This exception does not however
27 
// invalidate any other reasons why the executable file might be covered by
28 
// the GNU General Public License.
29 
 
30 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
31 
 
32 
// Permission to use, copy, modify, sell, and distribute this software
33 
// is hereby granted without fee, provided that the above copyright
34 
// notice appears in all copies, and that both that copyright notice and
35 
// this permission notice appear in supporting documentation. None of
36 
// the above authors, nor IBM Haifa Research Laboratories, make any
37 
// representation about the suitability of this software for any
38 
// purpose. It is provided "as is" without express or implied warranty.
39 
 
40 
/**
41 
 * @file erase_fn_imps.hpp
42 
 * Contains an implementation for rb_tree_.
43 
 */
44 
 
45 
PB_ASSOC_CLASS_T_DEC
46 
inline typename PB_ASSOC_CLASS_C_DEC::size_type
47 
PB_ASSOC_CLASS_C_DEC::
48 
erase(const_key_reference r_key)
49 
{
50 
  iterator it = find(r_key);
51 
 
52 
  if (it == PB_ASSOC_BASE_C_DEC::find_end())
53 
    return (0);
54 
 
55 
  erase(it);
56 
 
57 
  return (1);
58 
}
59 
 
60 
PB_ASSOC_CLASS_T_DEC
61 
inline typename PB_ASSOC_CLASS_C_DEC::const_iterator
62 
PB_ASSOC_CLASS_C_DEC::
63 
erase(const_iterator it)
64 
{
65 
  PB_ASSOC_DBG_ONLY(assert_valid());
66 
  PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
67 
 
68 
    if (it == PB_ASSOC_BASE_C_DEC::find_end())
69 
      return (it);
70 
 
71 
  const_iterator ret_it = it;
72 
 
73 
  ++ret_it;
74 
 
75 
  erase_node(it.m_p_nd);
76 
 
77 
  PB_ASSOC_DBG_ONLY(assert_valid());
78 
  PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
79 
 
80 
    return (ret_it);
81 
}
82 
 
83 
#ifdef PB_ASSOC_DATA_TRUE_INDICATOR
84 
PB_ASSOC_CLASS_T_DEC
85 
inline typename PB_ASSOC_CLASS_C_DEC::iterator
86 
PB_ASSOC_CLASS_C_DEC::
87 
erase(iterator it)
88 
{
89 
  PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
90 
  PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_iterators();)
91 
 
92 
    if (it == PB_ASSOC_BASE_C_DEC::find_end())
93 
      return (it);
94 
 
95 
  iterator ret_it = it;
96 
 
97 
  ++ret_it;
98 
 
99 
  erase_node(it.m_p_nd);
100 
 
101 
  PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
102 
  PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_iterators();)
103 
 
104 
    return (ret_it);
105 
}
106 
#endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
107 
 
108 
PB_ASSOC_CLASS_T_DEC
109 
inline typename PB_ASSOC_CLASS_C_DEC::const_reverse_iterator
110 
PB_ASSOC_CLASS_C_DEC::
111 
erase(const_reverse_iterator it)
112 
{
113 
  PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
114 
  PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_iterators();)
115 
 
116 
    if (it == PB_ASSOC_BASE_C_DEC::find_rend())
117 
      return (it);
118 
 
119 
  const_reverse_iterator ret_it = it;
120 
 
121 
  ++ret_it;
122 
 
123 
  erase_node(it.m_p_nd);
124 
 
125 
  PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
126 
  PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_iterators();)
127 
 
128 
    return (ret_it);
129 
}
130 
 
131 
#ifdef PB_ASSOC_DATA_TRUE_INDICATOR
132 
PB_ASSOC_CLASS_T_DEC
133 
inline typename PB_ASSOC_CLASS_C_DEC::reverse_iterator
134 
PB_ASSOC_CLASS_C_DEC::
135 
erase(reverse_iterator it)
136 
{
137 
  PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
138 
 
139 
  if (it == PB_ASSOC_BASE_C_DEC::find_rend())
140 
    return (it);
141 
 
142 
  reverse_iterator ret_it = it;
143 
 
144 
  ++ret_it;
145 
 
146 
  erase_node(it.m_p_nd);
147 
 
148 
  PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
149 
 
150 
  return (ret_it);
151 
}
152 
#endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
153 
 
154 
PB_ASSOC_CLASS_T_DEC
155 
template<class Pred>
156 
inline typename PB_ASSOC_CLASS_C_DEC::size_type
157 
PB_ASSOC_CLASS_C_DEC::
158 
erase_if(Pred pred)
159 
{
160 
  PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();)
161 
 
162 
    size_type num_ersd = 0;
163 
 
164 
  iterator it = PB_ASSOC_BASE_C_DEC::begin();
165 
 
166 
  while (it != PB_ASSOC_BASE_C_DEC::end())
167 
    if (pred(*it))
168 
      {
169 
        ++num_ersd;
170 
 
171 
        it = erase(it);
172 
      }
173 
    else
174 
      ++it;
175 
 
176 
  PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();)
177 
 
178 
    return (num_ersd);
179 
}
180 
 
181 
PB_ASSOC_CLASS_T_DEC
182 
void
183 
PB_ASSOC_CLASS_C_DEC::
184 
erase_node(node_pointer p_nd)
185 
{
186 
  remove_node(p_nd);
187 
 
188 
  PB_ASSOC_BASE_C_DEC::actual_erase_node(p_nd);
189 
 
190 
  PB_ASSOC_DBG_ONLY(assert_valid());
191 
  PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
192 
    }
193 
 
194 
PB_ASSOC_CLASS_T_DEC
195 
void
196 
PB_ASSOC_CLASS_C_DEC::
197 
remove_node(node_pointer p_z)
198 
{
199 
  update_min_max_for_erased_node(p_z);
200 
 
201 
  node_pointer p_y = p_z;
202 
 
203 
  node_pointer p_x = NULL;
204 
 
205 
  node_pointer p_new_x_parent = NULL;
206 
 
207 
  if (p_y->m_p_left == NULL)
208 
    p_x = p_y->m_p_right;
209 
  else if (p_y->m_p_right == NULL)
210 
    p_x = p_y->m_p_left;
211 
  else
212 
    {
213 
      p_y = p_y->m_p_right;
214 
 
215 
      while (p_y->m_p_left != NULL)
216 
        p_y = p_y->m_p_left;
217 
 
218 
      p_x = p_y->m_p_right;
219 
    }
220 
 
221 
  if (p_y == p_z)
222 
    {
223 
      p_new_x_parent = p_y->m_p_parent;
224 
 
225 
      if (p_x != NULL)
226 
        p_x->m_p_parent = p_y->m_p_parent;
227 
 
228 
      if (PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent == p_z)
229 
        PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent = p_x;
230 
      else if (p_z->m_p_parent->m_p_left == p_z)
231 
        {
232 
          p_y->m_p_left = p_z->m_p_parent;
233 
 
234 
          p_z->m_p_parent->m_p_left = p_x;
235 
        }
236 
      else
237 
        {
238 
          p_y->m_p_left = NULL;
239 
 
240 
          p_z->m_p_parent->m_p_right = p_x;
241 
        }
242 
    }
243 
  else
244 
    {
245 
      p_z->m_p_left->m_p_parent = p_y;
246 
 
247 
      p_y->m_p_left = p_z->m_p_left;
248 
 
249 
      if (p_y != p_z->m_p_right)
250 
        {
251 
          p_new_x_parent = p_y->m_p_parent;
252 
 
253 
          if (p_x != NULL)
254 
            p_x->m_p_parent = p_y->m_p_parent;
255 
 
256 
          p_y->m_p_parent->m_p_left = p_x;
257 
 
258 
          p_y->m_p_right = p_z->m_p_right;
259 
 
260 
          p_z->m_p_right->m_p_parent = p_y;
261 
        }
262 
      else
263 
        p_new_x_parent = p_y;
264 
 
265 
      if (PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent == p_z)
266 
        PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent = p_y;
267 
      else if (p_z->m_p_parent->m_p_left == p_z)
268 
        p_z->m_p_parent->m_p_left = p_y;
269 
      else
270 
        p_z->m_p_parent->m_p_right = p_y;
271 
 
272 
      p_y->m_p_parent = p_z->m_p_parent;
273 
 
274 
      std::swap(p_y->m_red, p_z->m_red);
275 
 
276 
      p_y = p_z;
277 
    }
278 
 
279 
  update_to_top(p_new_x_parent, (Node_Updator* )this);
280 
 
281 
  if (p_y->m_red)
282 
    return;
283 
 
284 
  remove_fixup(p_x, p_new_x_parent);
285 
}
286 
 
287 
PB_ASSOC_CLASS_T_DEC
288 
void
289 
PB_ASSOC_CLASS_C_DEC::
290 
remove_fixup(node_pointer p_x, node_pointer p_new_x_parent)
291 
{
292 
  PB_ASSOC_DBG_ASSERT(p_x == NULL || p_x->m_p_parent == p_new_x_parent);
293 
 
294 
  while (p_x != PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent&&
295 
         is_effectively_black(p_x))
296 
    if (p_x == p_new_x_parent->m_p_left)
297 
      {
298 
        node_pointer p_w = p_new_x_parent->m_p_right;
299 
 
300 
        if (p_w->m_red)
301 
          {
302 
            p_w->m_red = false;
303 
 
304 
            p_new_x_parent->m_red = true;
305 
 
306 
            PB_ASSOC_BASE_C_DEC::rotate_left(p_new_x_parent);
307 
 
308 
            p_w = p_new_x_parent->m_p_right;
309 
          }
310 
 
311 
        if (is_effectively_black(p_w->m_p_left)&&
312 
            is_effectively_black(p_w->m_p_right))
313 
          {
314 
            p_w->m_red = true;
315 
 
316 
            p_x = p_new_x_parent;
317 
 
318 
            p_new_x_parent = p_new_x_parent->m_p_parent;
319 
          }
320 
        else
321 
          {
322 
            if (is_effectively_black(p_w->m_p_right))
323 
              {
324 
                if (p_w->m_p_left != NULL)
325 
                  p_w->m_p_left->m_red = false;
326 
 
327 
                p_w->m_red = true;
328 
 
329 
                PB_ASSOC_BASE_C_DEC::rotate_right(p_w);
330 
 
331 
                p_w = p_new_x_parent->m_p_right;
332 
              }
333 
 
334 
            p_w->m_red = p_new_x_parent->m_red;
335 
 
336 
            p_new_x_parent->m_red = false;
337 
 
338 
            if (p_w->m_p_right != NULL)
339 
              p_w->m_p_right->m_red = false;
340 
 
341 
            PB_ASSOC_BASE_C_DEC::rotate_left(p_new_x_parent);
342 
 
343 
            update_to_top(p_new_x_parent, (Node_Updator* )this);
344 
 
345 
            break;
346 
          }
347 
      }
348 
    else
349 
      {
350 
        node_pointer p_w = p_new_x_parent->m_p_left;
351 
 
352 
        if (p_w->m_red == true)
353 
          {
354 
            p_w->m_red = false;
355 
 
356 
            p_new_x_parent->m_red = true;
357 
 
358 
            PB_ASSOC_BASE_C_DEC::rotate_right(p_new_x_parent);
359 
 
360 
            p_w = p_new_x_parent->m_p_left;
361 
          }
362 
 
363 
        if (is_effectively_black(p_w->m_p_right)&&
364 
            is_effectively_black(p_w->m_p_left))
365 
          {
366 
            p_w->m_red = true;
367 
 
368 
            p_x = p_new_x_parent;
369 
 
370 
            p_new_x_parent = p_new_x_parent->m_p_parent;
371 
          }
372 
        else
373 
          {
374 
            if (is_effectively_black(p_w->m_p_left))
375 
              {
376 
                if (p_w->m_p_right != NULL)
377 
                  p_w->m_p_right->m_red = false;
378 
 
379 
                p_w->m_red = true;
380 
 
381 
                PB_ASSOC_BASE_C_DEC::rotate_left(p_w);
382 
 
383 
                p_w = p_new_x_parent->m_p_left;
384 
              }
385 
 
386 
            p_w->m_red = p_new_x_parent->m_red;
387 
 
388 
            p_new_x_parent->m_red = false;
389 
 
390 
            if (p_w->m_p_left != NULL)
391 
              p_w->m_p_left->m_red = false;
392 
 
393 
            PB_ASSOC_BASE_C_DEC::rotate_right(p_new_x_parent);
394 
 
395 
            update_to_top(p_new_x_parent, (Node_Updator* )this);
396 
 
397 
            break;
398 
          }
399 
      }
400 
 
401 
  if (p_x != NULL)
402 
    p_x->m_red = false;
403 
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.