ReactOS  0.4.15-dev-1150-g593bcce
_tree.c
Go to the documentation of this file.
1 /*
2  *
3  *
4  * Copyright (c) 1994
5  * Hewlett-Packard Company
6  *
7  * Copyright (c) 1996,1997
8  * Silicon Graphics Computer Systems, Inc.
9  *
10  * Copyright (c) 1997
11  * Moscow Center for SPARC Technology
12  *
13  * Copyright (c) 1999
14  * Boris Fomitchev
15  *
16  * This material is provided "as is", with absolutely no warranty expressed
17  * or implied. Any use is at your own risk.
18  *
19  * Permission to use or copy this software for any purpose is hereby granted
20  * without fee, provided the above notices are retained on all copies.
21  * Permission to modify the code and to distribute modified code is granted,
22  * provided the above notices are retained, and a notice that the code was
23  * modified is included with the above copyright notice.
24  *
25  * Modified CRP 7/10/00 for improved conformance / efficiency on insert_unique /
26  * insert_equal with valid hint -- efficiency is improved all around, and it is
27  * should now be standard conforming for complexity on insert point immediately
28  * after hint (amortized constant time).
29  *
30  */
31 #ifndef _STLP_TREE_C
32 #define _STLP_TREE_C
33 
34 #ifndef _STLP_INTERNAL_TREE_H
35 # include <stl/_tree.h>
36 #endif
37 
38 #if defined (_STLP_DEBUG)
39 # define _Rb_tree _STLP_NON_DBG_NAME(Rb_tree)
40 #endif
41 
42 // fbp: these defines are for outline methods definitions.
43 // needed for definitions to be portable. Should not be used in method bodies.
44 #if defined (_STLP_NESTED_TYPE_PARAM_BUG)
45 # define __iterator__ _Rb_tree_iterator<_Value, _STLP_HEADER_TYPENAME _Traits::_NonConstTraits>
46 # define __size_type__ size_t
47 # define iterator __iterator__
48 #else
49 # define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc>::iterator
50 # define __size_type__ _STLP_TYPENAME_ON_RETURN_TYPE _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc>::size_type
51 #endif
52 
54 
56 
57 #if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
58 
59 template <class _Dummy> void _STLP_CALL
61  _Rb_tree_node_base*& __root) {
62  _Rb_tree_node_base* __y = __x->_M_right;
63  __x->_M_right = __y->_M_left;
64  if (__y->_M_left != 0)
65  __y->_M_left->_M_parent = __x;
66  __y->_M_parent = __x->_M_parent;
67 
68  if (__x == __root)
69  __root = __y;
70  else if (__x == __x->_M_parent->_M_left)
71  __x->_M_parent->_M_left = __y;
72  else
73  __x->_M_parent->_M_right = __y;
74  __y->_M_left = __x;
75  __x->_M_parent = __y;
76 }
77 
78 template <class _Dummy> void _STLP_CALL
80  _Rb_tree_node_base*& __root) {
81  _Rb_tree_node_base* __y = __x->_M_left;
82  __x->_M_left = __y->_M_right;
83  if (__y->_M_right != 0)
84  __y->_M_right->_M_parent = __x;
85  __y->_M_parent = __x->_M_parent;
86 
87  if (__x == __root)
88  __root = __y;
89  else if (__x == __x->_M_parent->_M_right)
90  __x->_M_parent->_M_right = __y;
91  else
92  __x->_M_parent->_M_left = __y;
93  __y->_M_right = __x;
94  __x->_M_parent = __y;
95 }
96 
97 template <class _Dummy> void _STLP_CALL
99  _Rb_tree_node_base*& __root) {
100  __x->_M_color = _S_rb_tree_red;
101  while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) {
102  if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) {
104  if (__y && __y->_M_color == _S_rb_tree_red) {
106  __y->_M_color = _S_rb_tree_black;
108  __x = __x->_M_parent->_M_parent;
109  }
110  else {
111  if (__x == __x->_M_parent->_M_right) {
112  __x = __x->_M_parent;
113  _Rotate_left(__x, __root);
114  }
117  _Rotate_right(__x->_M_parent->_M_parent, __root);
118  }
119  }
120  else {
122  if (__y && __y->_M_color == _S_rb_tree_red) {
124  __y->_M_color = _S_rb_tree_black;
126  __x = __x->_M_parent->_M_parent;
127  }
128  else {
129  if (__x == __x->_M_parent->_M_left) {
130  __x = __x->_M_parent;
131  _Rotate_right(__x, __root);
132  }
135  _Rotate_left(__x->_M_parent->_M_parent, __root);
136  }
137  }
138  }
139  __root->_M_color = _S_rb_tree_black;
140 }
141 
142 template <class _Dummy> _Rb_tree_node_base* _STLP_CALL
144  _Rb_tree_node_base*& __root,
145  _Rb_tree_node_base*& __leftmost,
146  _Rb_tree_node_base*& __rightmost) {
147  _Rb_tree_node_base* __y = __z;
148  _Rb_tree_node_base* __x;
149  _Rb_tree_node_base* __x_parent;
150 
151  if (__y->_M_left == 0) // __z has at most one non-null child. y == z.
152  __x = __y->_M_right; // __x might be null.
153  else {
154  if (__y->_M_right == 0) // __z has exactly one non-null child. y == z.
155  __x = __y->_M_left; // __x is not null.
156  else { // __z has two non-null children. Set __y to
157  __y = _Rb_tree_node_base::_S_minimum(__y->_M_right); // __z's successor. __x might be null.
158  __x = __y->_M_right;
159  }
160  }
161 
162  if (__y != __z) { // relink y in place of z. y is z's successor
163  __z->_M_left->_M_parent = __y;
164  __y->_M_left = __z->_M_left;
165  if (__y != __z->_M_right) {
166  __x_parent = __y->_M_parent;
167  if (__x) __x->_M_parent = __y->_M_parent;
168  __y->_M_parent->_M_left = __x; // __y must be a child of _M_left
169  __y->_M_right = __z->_M_right;
170  __z->_M_right->_M_parent = __y;
171  }
172  else
173  __x_parent = __y;
174  if (__root == __z)
175  __root = __y;
176  else if (__z->_M_parent->_M_left == __z)
177  __z->_M_parent->_M_left = __y;
178  else
179  __z->_M_parent->_M_right = __y;
180  __y->_M_parent = __z->_M_parent;
181  _STLP_STD::swap(__y->_M_color, __z->_M_color);
182  __y = __z;
183  // __y now points to node to be actually deleted
184  }
185  else { // __y == __z
186  __x_parent = __y->_M_parent;
187  if (__x) __x->_M_parent = __y->_M_parent;
188  if (__root == __z)
189  __root = __x;
190  else {
191  if (__z->_M_parent->_M_left == __z)
192  __z->_M_parent->_M_left = __x;
193  else
194  __z->_M_parent->_M_right = __x;
195  }
196 
197  if (__leftmost == __z) {
198  if (__z->_M_right == 0) // __z->_M_left must be null also
199  __leftmost = __z->_M_parent;
200  // makes __leftmost == _M_header if __z == __root
201  else
202  __leftmost = _Rb_tree_node_base::_S_minimum(__x);
203  }
204  if (__rightmost == __z) {
205  if (__z->_M_left == 0) // __z->_M_right must be null also
206  __rightmost = __z->_M_parent;
207  // makes __rightmost == _M_header if __z == __root
208  else // __x == __z->_M_left
209  __rightmost = _Rb_tree_node_base::_S_maximum(__x);
210  }
211  }
212 
213  if (__y->_M_color != _S_rb_tree_red) {
214  while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black))
215  if (__x == __x_parent->_M_left) {
216  _Rb_tree_node_base* __w = __x_parent->_M_right;
217  if (__w->_M_color == _S_rb_tree_red) {
218  __w->_M_color = _S_rb_tree_black;
219  __x_parent->_M_color = _S_rb_tree_red;
220  _Rotate_left(__x_parent, __root);
221  __w = __x_parent->_M_right;
222  }
223  if ((__w->_M_left == 0 ||
224  __w->_M_left->_M_color == _S_rb_tree_black) && (__w->_M_right == 0 ||
225  __w->_M_right->_M_color == _S_rb_tree_black)) {
226  __w->_M_color = _S_rb_tree_red;
227  __x = __x_parent;
228  __x_parent = __x_parent->_M_parent;
229  } else {
230  if (__w->_M_right == 0 ||
232  if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
233  __w->_M_color = _S_rb_tree_red;
234  _Rotate_right(__w, __root);
235  __w = __x_parent->_M_right;
236  }
237  __w->_M_color = __x_parent->_M_color;
238  __x_parent->_M_color = _S_rb_tree_black;
239  if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
240  _Rotate_left(__x_parent, __root);
241  break;
242  }
243  } else { // same as above, with _M_right <-> _M_left.
244  _Rb_tree_node_base* __w = __x_parent->_M_left;
245  if (__w->_M_color == _S_rb_tree_red) {
246  __w->_M_color = _S_rb_tree_black;
247  __x_parent->_M_color = _S_rb_tree_red;
248  _Rotate_right(__x_parent, __root);
249  __w = __x_parent->_M_left;
250  }
251  if ((__w->_M_right == 0 ||
252  __w->_M_right->_M_color == _S_rb_tree_black) && (__w->_M_left == 0 ||
253  __w->_M_left->_M_color == _S_rb_tree_black)) {
254  __w->_M_color = _S_rb_tree_red;
255  __x = __x_parent;
256  __x_parent = __x_parent->_M_parent;
257  } else {
258  if (__w->_M_left == 0 ||
259  __w->_M_left->_M_color == _S_rb_tree_black) {
260  if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
261  __w->_M_color = _S_rb_tree_red;
262  _Rotate_left(__w, __root);
263  __w = __x_parent->_M_left;
264  }
265  __w->_M_color = __x_parent->_M_color;
266  __x_parent->_M_color = _S_rb_tree_black;
267  if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
268  _Rotate_right(__x_parent, __root);
269  break;
270  }
271  }
272  if (__x) __x->_M_color = _S_rb_tree_black;
273  }
274  return __y;
275 }
276 
277 template <class _Dummy> _Rb_tree_node_base* _STLP_CALL
279  if (_M_node->_M_color == _S_rb_tree_red && _M_node->_M_parent->_M_parent == _M_node)
280  _M_node = _M_node->_M_right;
281  else if (_M_node->_M_left != 0) {
282  _M_node = _Rb_tree_node_base::_S_maximum(_M_node->_M_left);
283  }
284  else {
285  _Base_ptr __y = _M_node->_M_parent;
286  while (_M_node == __y->_M_left) {
287  _M_node = __y;
288  __y = __y->_M_parent;
289  }
290  _M_node = __y;
291  }
292  return _M_node;
293 }
294 
295 template <class _Dummy> _Rb_tree_node_base* _STLP_CALL
297  if (_M_node->_M_right != 0) {
298  _M_node = _Rb_tree_node_base::_S_minimum(_M_node->_M_right);
299  }
300  else {
301  _Base_ptr __y = _M_node->_M_parent;
302  while (_M_node == __y->_M_right) {
303  _M_node = __y;
304  __y = __y->_M_parent;
305  }
306  // check special case: This is necessary if _M_node is the
307  // _M_head and the tree contains only a single node __y. In
308  // that case parent, left and right all point to __y!
309  if (_M_node->_M_right != __y)
310  _M_node = __y;
311  }
312  return _M_node;
313 }
314 
315 #endif /* _STLP_EXPOSE_GLOBALS_IMPLEMENTATION */
316 
317 
318 template <class _Key, class _Compare,
319  class _Value, class _KeyOfValue, class _Traits, class _Alloc>
323  if (this != &__x) {
324  // Note that _Key may be a constant type.
325  clear();
326  _M_node_count = 0;
327  _M_key_compare = __x._M_key_compare;
328  if (__x._M_root() == 0) {
329  _M_root() = 0;
330  _M_leftmost() = &this->_M_header._M_data;
331  _M_rightmost() = &this->_M_header._M_data;
332  }
333  else {
334  _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data);
335  _M_leftmost() = _S_minimum(_M_root());
336  _M_rightmost() = _S_maximum(_M_root());
337  _M_node_count = __x._M_node_count;
338  }
339  }
340  return *this;
341 }
342 
343 // CRP 7/10/00 inserted argument __on_right, which is another hint (meant to
344 // act like __on_left and ignore a portion of the if conditions -- specify
345 // __on_right != 0 to bypass comparison as false or __on_left != 0 to bypass
346 // comparison as true)
347 template <class _Key, class _Compare,
348  class _Value, class _KeyOfValue, class _Traits, class _Alloc>
351  const _Value& __val,
354  // We do not create the node here as, depending on tests, we might call
355  // _M_key_compare that can throw an exception.
356  _Base_ptr __new_node;
357 
358  if ( __parent == &this->_M_header._M_data ) {
359  __new_node = _M_create_node(__val);
360  _S_left(__parent) = __new_node; // also makes _M_leftmost() = __new_node
361  _M_root() = __new_node;
362  _M_rightmost() = __new_node;
363  }
364  else if ( __on_right == 0 && // If __on_right != 0, the remainder fails to false
365  ( __on_left != 0 || // If __on_left != 0, the remainder succeeds to true
366  _M_key_compare( _KeyOfValue()(__val), _S_key(__parent) ) ) ) {
367  __new_node = _M_create_node(__val);
368  _S_left(__parent) = __new_node;
369  if (__parent == _M_leftmost())
370  _M_leftmost() = __new_node; // maintain _M_leftmost() pointing to min node
371  }
372  else {
373  __new_node = _M_create_node(__val);
374  _S_right(__parent) = __new_node;
375  if (__parent == _M_rightmost())
376  _M_rightmost() = __new_node; // maintain _M_rightmost() pointing to max node
377  }
378  _S_parent(__new_node) = __parent;
379  _Rb_global_inst::_Rebalance(__new_node, this->_M_header._M_data._M_parent);
380  ++_M_node_count;
381  return iterator(__new_node);
382 }
383 
384 template <class _Key, class _Compare,
385  class _Value, class _KeyOfValue, class _Traits, class _Alloc>
388  _Base_ptr __y = &this->_M_header._M_data;
389  _Base_ptr __x = _M_root();
390  while (__x != 0) {
391  __y = __x;
392  if (_M_key_compare(_KeyOfValue()(__val), _S_key(__x))) {
393  __x = _S_left(__x);
394  }
395  else
396  __x = _S_right(__x);
397  }
398  return _M_insert(__y, __val, __x);
399 }
400 
401 
402 template <class _Key, class _Compare,
403  class _Value, class _KeyOfValue, class _Traits, class _Alloc>
406  _Base_ptr __y = &this->_M_header._M_data;
407  _Base_ptr __x = _M_root();
408  bool __comp = true;
409  while (__x != 0) {
410  __y = __x;
411  __comp = _M_key_compare(_KeyOfValue()(__val), _S_key(__x));
412  __x = __comp ? _S_left(__x) : _S_right(__x);
413  }
414  iterator __j = iterator(__y);
415  if (__comp) {
416  if (__j == begin())
417  return pair<iterator,bool>(_M_insert(__y, __val, /* __x*/ __y), true);
418  else
419  --__j;
420  }
421  if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__val))) {
422  return pair<iterator,bool>(_M_insert(__y, __val, __x), true);
423  }
424  return pair<iterator,bool>(__j, false);
425 }
426 
427 // Modifications CRP 7/10/00 as noted to improve conformance and
428 // efficiency.
429 template <class _Key, class _Compare,
430  class _Value, class _KeyOfValue, class _Traits, class _Alloc>
433  const _Value& __val) {
434  if (__position._M_node == this->_M_header._M_data._M_left) { // begin()
435 
436  // if the container is empty, fall back on insert_unique.
437  if (empty())
438  return insert_unique(__val).first;
439 
440  if (_M_key_compare(_KeyOfValue()(__val), _S_key(__position._M_node))) {
441  return _M_insert(__position._M_node, __val, __position._M_node);
442  }
443  // first argument just needs to be non-null
444  else {
445  bool __comp_pos_v = _M_key_compare( _S_key(__position._M_node), _KeyOfValue()(__val) );
446 
447  if (__comp_pos_v == false) // compare > and compare < both false so compare equal
448  return __position;
449  //Below __comp_pos_v == true
450 
451  // Standard-conformance - does the insertion point fall immediately AFTER
452  // the hint?
453  iterator __after = __position;
454  ++__after;
455 
456  // Check for only one member -- in that case, __position points to itself,
457  // and attempting to increment will cause an infinite loop.
458  if (__after._M_node == &this->_M_header._M_data)
459  // Check guarantees exactly one member, so comparison was already
460  // performed and we know the result; skip repeating it in _M_insert
461  // by specifying a non-zero fourth argument.
462  return _M_insert(__position._M_node, __val, 0, __position._M_node);
463 
464  // All other cases:
465 
466  // Optimization to catch insert-equivalent -- save comparison results,
467  // and we get this for free.
468  if (_M_key_compare( _KeyOfValue()(__val), _S_key(__after._M_node) )) {
469  if (_S_right(__position._M_node) == 0)
470  return _M_insert(__position._M_node, __val, 0, __position._M_node);
471  else
472  return _M_insert(__after._M_node, __val, __after._M_node);
473  }
474  else {
475  return insert_unique(__val).first;
476  }
477  }
478  }
479  else if (__position._M_node == &this->_M_header._M_data) { // end()
480  if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__val))) {
481  // pass along to _M_insert that it can skip comparing
482  // v, Key ; since compare Key, v was true, compare v, Key must be false.
483  return _M_insert(_M_rightmost(), __val, 0, __position._M_node); // Last argument only needs to be non-null
484  }
485  else
486  return insert_unique(__val).first;
487  }
488  else {
489  iterator __before = __position;
490  --__before;
491 
492  bool __comp_v_pos = _M_key_compare(_KeyOfValue()(__val), _S_key(__position._M_node));
493 
494  if (__comp_v_pos
495  && _M_key_compare( _S_key(__before._M_node), _KeyOfValue()(__val) )) {
496 
497  if (_S_right(__before._M_node) == 0)
498  return _M_insert(__before._M_node, __val, 0, __before._M_node); // Last argument only needs to be non-null
499  else
500  return _M_insert(__position._M_node, __val, __position._M_node);
501  // first argument just needs to be non-null
502  }
503  else {
504  // Does the insertion point fall immediately AFTER the hint?
505  iterator __after = __position;
506  ++__after;
507  // Optimization to catch equivalent cases and avoid unnecessary comparisons
508  bool __comp_pos_v = !__comp_v_pos; // Stored this result earlier
509  // If the earlier comparison was true, this comparison doesn't need to be
510  // performed because it must be false. However, if the earlier comparison
511  // was false, we need to perform this one because in the equal case, both will
512  // be false.
513  if (!__comp_v_pos) {
514  __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val));
515  }
516 
517  if ( (!__comp_v_pos) // comp_v_pos true implies comp_v_pos false
518  && __comp_pos_v
519  && (__after._M_node == &this->_M_header._M_data ||
520  _M_key_compare( _KeyOfValue()(__val), _S_key(__after._M_node) ))) {
521  if (_S_right(__position._M_node) == 0)
522  return _M_insert(__position._M_node, __val, 0, __position._M_node);
523  else
524  return _M_insert(__after._M_node, __val, __after._M_node);
525  } else {
526  // Test for equivalent case
527  if (__comp_v_pos == __comp_pos_v)
528  return __position;
529  else
530  return insert_unique(__val).first;
531  }
532  }
533  }
534 }
535 
536 template <class _Key, class _Compare,
537  class _Value, class _KeyOfValue, class _Traits, class _Alloc>
540  const _Value& __val) {
541  if (__position._M_node == this->_M_header._M_data._M_left) { // begin()
542 
543  // Check for zero members
544  if (size() <= 0)
545  return insert_equal(__val);
546 
547  if (!_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val)))
548  return _M_insert(__position._M_node, __val, __position._M_node);
549  else {
550  // Check for only one member
551  if (__position._M_node->_M_left == __position._M_node)
552  // Unlike insert_unique, can't avoid doing a comparison here.
553  return _M_insert(__position._M_node, __val);
554 
555  // All other cases:
556  // Standard-conformance - does the insertion point fall immediately AFTER
557  // the hint?
558  iterator __after = __position;
559  ++__after;
560 
561  // Already know that compare(pos, v) must be true!
562  // Therefore, we want to know if compare(after, v) is false.
563  // (i.e., we now pos < v, now we want to know if v <= after)
564  // If not, invalid hint.
565  if ( __after._M_node == &this->_M_header._M_data ||
566  !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__val) ) ) {
567  if (_S_right(__position._M_node) == 0)
568  return _M_insert(__position._M_node, __val, 0, __position._M_node);
569  else
570  return _M_insert(__after._M_node, __val, __after._M_node);
571  }
572  else { // Invalid hint
573  return insert_equal(__val);
574  }
575  }
576  }
577  else if (__position._M_node == &this->_M_header._M_data) { // end()
578  if (!_M_key_compare(_KeyOfValue()(__val), _S_key(_M_rightmost())))
579  return _M_insert(_M_rightmost(), __val, 0, __position._M_node); // Last argument only needs to be non-null
580  else {
581  return insert_equal(__val);
582  }
583  }
584  else {
585  iterator __before = __position;
586  --__before;
587  // store the result of the comparison between pos and v so
588  // that we don't have to do it again later. Note that this reverses the shortcut
589  // on the if, possibly harming efficiency in comparisons; I think the harm will
590  // be negligible, and to do what I want to do (save the result of a comparison so
591  // that it can be re-used) there is no alternative. Test here is for before <= v <= pos.
592  bool __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val));
593  if (!__comp_pos_v &&
594  !_M_key_compare(_KeyOfValue()(__val), _S_key(__before._M_node))) {
595  if (_S_right(__before._M_node) == 0)
596  return _M_insert(__before._M_node, __val, 0, __before._M_node); // Last argument only needs to be non-null
597  else
598  return _M_insert(__position._M_node, __val, __position._M_node);
599  }
600  else {
601  // Does the insertion point fall immediately AFTER the hint?
602  // Test for pos < v <= after
603  iterator __after = __position;
604  ++__after;
605 
606  if (__comp_pos_v &&
607  ( __after._M_node == &this->_M_header._M_data ||
608  !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__val) ) ) ) {
609  if (_S_right(__position._M_node) == 0)
610  return _M_insert(__position._M_node, __val, 0, __position._M_node);
611  else
612  return _M_insert(__after._M_node, __val, __after._M_node);
613  }
614  else { // Invalid hint
615  return insert_equal(__val);
616  }
617  }
618  }
619 }
620 
621 template <class _Key, class _Compare,
622  class _Value, class _KeyOfValue, class _Traits, class _Alloc>
625  _Rb_tree_node_base* __p) {
626  // structural copy. __x and __p must be non-null.
627  _Base_ptr __top = _M_clone_node(__x);
628  _S_parent(__top) = __p;
629 
630  _STLP_TRY {
631  if (_S_right(__x))
632  _S_right(__top) = _M_copy(_S_right(__x), __top);
633  __p = __top;
634  __x = _S_left(__x);
635 
636  while (__x != 0) {
637  _Base_ptr __y = _M_clone_node(__x);
638  _S_left(__p) = __y;
639  _S_parent(__y) = __p;
640  if (_S_right(__x))
641  _S_right(__y) = _M_copy(_S_right(__x), __y);
642  __p = __y;
643  __x = _S_left(__x);
644  }
645  }
646  _STLP_UNWIND(_M_erase(__top))
647 
648  return __top;
649 }
650 
651 // this has to stay out-of-line : it's recursive
652 template <class _Key, class _Compare,
653  class _Value, class _KeyOfValue, class _Traits, class _Alloc>
654 void
656  // erase without rebalancing
657  while (__x != 0) {
658  _M_erase(_S_right(__x));
659  _Base_ptr __y = _S_left(__x);
660  _STLP_STD::_Destroy(&_S_value(__x));
661  this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x),1);
662  __x = __y;
663  }
664 }
665 
666 #if defined (_STLP_DEBUG)
667 inline int
668 __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root) {
669  if (__node == 0)
670  return 0;
671  else {
672  int __bc = __node->_M_color == _S_rb_tree_black ? 1 : 0;
673  if (__node == __root)
674  return __bc;
675  else
676  return __bc + __black_count(__node->_M_parent, __root);
677  }
678 }
679 
680 template <class _Key, class _Compare,
681  class _Value, class _KeyOfValue, class _Traits, class _Alloc>
683  if (_M_node_count == 0 || begin() == end())
684  return ((_M_node_count == 0) &&
685  (begin() == end()) &&
686  (this->_M_header._M_data._M_left == &this->_M_header._M_data) &&
687  (this->_M_header._M_data._M_right == &this->_M_header._M_data));
688 
689  int __len = __black_count(_M_leftmost(), _M_root());
690  for (const_iterator __it = begin(); __it != end(); ++__it) {
691  _Base_ptr __x = __it._M_node;
692  _Base_ptr __L = _S_left(__x);
693  _Base_ptr __R = _S_right(__x);
694 
695  if (__x->_M_color == _S_rb_tree_red)
696  if ((__L && __L->_M_color == _S_rb_tree_red) ||
697  (__R && __R->_M_color == _S_rb_tree_red))
698  return false;
699 
700  if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
701  return false;
702  if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
703  return false;
704 
705  if (!__L && !__R && __black_count(__x, _M_root()) != __len)
706  return false;
707  }
708 
709  if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
710  return false;
711  if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
712  return false;
713 
714  return true;
715 }
716 #endif /* _STLP_DEBUG */
717 
720 
721 #undef _Rb_tree
722 #undef __iterator__
723 #undef iterator
724 #undef __size_type__
725 
726 #endif /* _STLP_TREE_C */
727 
728 // Local Variables:
729 // mode:C++
730 // End:
#define _S_rb_tree_black
Definition: _tree.h:82
#define swap(a, b)
Definition: qsort.c:63
_Base_ptr _M_copy(_Base_ptr __x, _Base_ptr __p)
Definition: _tree.c:624
static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
Definition: _tree.h:98
iterator insert_equal(const value_type &__x)
Definition: _tree.c:387
#define _Alloc
Definition: _bvector.h:330
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
GLuint GLuint end
Definition: gl.h:1545
iterator _M_insert(_Base_ptr __parent, const value_type &__val, _Base_ptr __on_left=0, _Base_ptr __on_right=0)
Definition: _tree.c:350
_Color_type _M_color
Definition: _tree.h:88
_Base_ptr _M_right
Definition: _tree.h:91
#define _STLP_MOVE_TO_PRIV_NAMESPACE
Definition: features.h:524
_Base_ptr _M_left
Definition: _tree.h:90
_Base_ptr _M_node
Definition: _tree.h:140
static _Base_ptr _STLP_CALL _M_increment(_Base_ptr)
#define __iterator__
Definition: _tree.c:49
#define _STLP_UNWIND(action)
Definition: features.h:824
static void _STLP_CALL _Rotate_left(_Base_ptr __x, _Base_ptr &__root)
static clock_t begin
Definition: xmllint.c:466
static _Base_ptr _STLP_CALL _Rebalance_for_erase(_Base_ptr __z, _Base_ptr &__root, _Base_ptr &__leftmost, _Base_ptr &__rightmost)
_Base_ptr _M_parent
Definition: _tree.h:89
#define _STLP_MOVE_TO_STD_NAMESPACE
Definition: features.h:525
size_type _M_node_count
Definition: _tree.h:332
GLsizeiptr size
Definition: glext.h:5919
_Self & operator=(const _Self &__x)
Definition: _tree.c:321
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
Definition: _tree.h:93
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)
void _Destroy(_Tp *__pointer)
Definition: _construct.h:63
static void _STLP_CALL _Rotate_right(_Base_ptr __x, _Base_ptr &__root)
pair< iterator, bool > insert_unique(const value_type &__x)
Definition: _tree.c:405
static _Base_ptr _STLP_CALL _M_decrement(_Base_ptr)
_Base_ptr _M_root() const
Definition: _tree.h:335
#define _STLP_END_NAMESPACE
Definition: features.h:503
#define _STLP_TRY
Definition: features.h:817
Definition: _pair.h:47
BOOL empty
Definition: button.c:170
void _M_erase(_Base_ptr __x)
Definition: _tree.c:655
static void _STLP_CALL _Rebalance(_Base_ptr __x, _Base_ptr &__root)
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
int _Value
Definition: setjmp.h:188
#define _STLP_CALL
Definition: _bc.h:131
#define _S_rb_tree_red
Definition: _tree.h:81
_Compare _M_key_compare
Definition: _tree.h:333