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 
53 _STLP_BEGIN_NAMESPACE
54 
55 _STLP_MOVE_TO_PRIV_NAMESPACE
56 
57 #if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
58 
59 template <class _Dummy> void _STLP_CALL
_Rotate_left(_Rb_tree_node_base * __x,_Rb_tree_node_base * & __root)60 _Rb_global<_Dummy>::_Rotate_left(_Rb_tree_node_base* __x,
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
_Rotate_right(_Rb_tree_node_base * __x,_Rb_tree_node_base * & __root)79 _Rb_global<_Dummy>::_Rotate_right(_Rb_tree_node_base* __x,
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
_Rebalance(_Rb_tree_node_base * __x,_Rb_tree_node_base * & __root)98 _Rb_global<_Dummy>::_Rebalance(_Rb_tree_node_base* __x,
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) {
103       _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right;
104       if (__y && __y->_M_color == _S_rb_tree_red) {
105         __x->_M_parent->_M_color = _S_rb_tree_black;
106         __y->_M_color = _S_rb_tree_black;
107         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
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         }
115         __x->_M_parent->_M_color = _S_rb_tree_black;
116         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
117         _Rotate_right(__x->_M_parent->_M_parent, __root);
118       }
119     }
120     else {
121       _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left;
122       if (__y && __y->_M_color == _S_rb_tree_red) {
123         __x->_M_parent->_M_color = _S_rb_tree_black;
124         __y->_M_color = _S_rb_tree_black;
125         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
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         }
133         __x->_M_parent->_M_color = _S_rb_tree_black;
134         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
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
_Rebalance_for_erase(_Rb_tree_node_base * __z,_Rb_tree_node_base * & __root,_Rb_tree_node_base * & __leftmost,_Rb_tree_node_base * & __rightmost)143 _Rb_global<_Dummy>::_Rebalance_for_erase(_Rb_tree_node_base* __z,
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 ||
231               __w->_M_right->_M_color == _S_rb_tree_black) {
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
_M_decrement(_Rb_tree_node_base * _M_node)278 _Rb_global<_Dummy>::_M_decrement(_Rb_tree_node_base* _M_node) {
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
_M_increment(_Rb_tree_node_base * _M_node)296 _Rb_global<_Dummy>::_M_increment(_Rb_tree_node_base* _M_node) {
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>
320 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>&
321 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::operator=(
322   const _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>& __x) {
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>
349 __iterator__
_M_insert(_Rb_tree_node_base * __parent,const _Value & __val,_Rb_tree_node_base * __on_left,_Rb_tree_node_base * __on_right)350 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::_M_insert(_Rb_tree_node_base * __parent,
351                                                                       const _Value& __val,
352                                                                       _Rb_tree_node_base * __on_left,
353                                                                       _Rb_tree_node_base * __on_right) {
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>
386 __iterator__
insert_equal(const _Value & __val)387 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::insert_equal(const _Value& __val) {
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>
404 pair<__iterator__, bool>
insert_unique(const _Value & __val)405 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::insert_unique(const _Value& __val) {
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>
431 __iterator__
insert_unique(iterator __position,const _Value & __val)432 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::insert_unique(iterator __position,
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>
538 __iterator__
insert_equal(iterator __position,const _Value & __val)539 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::insert_equal(iterator __position,
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>
623 _Rb_tree_node_base*
_M_copy(_Rb_tree_node_base * __x,_Rb_tree_node_base * __p)624 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::_M_copy(_Rb_tree_node_base* __x,
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
_M_erase(_Rb_tree_node_base * __x)655 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>::_M_erase(_Rb_tree_node_base *__x) {
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
__black_count(_Rb_tree_node_base * __node,_Rb_tree_node_base * __root)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>
__rb_verify()682 bool _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>::__rb_verify() const {
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 
718 _STLP_MOVE_TO_STD_NAMESPACE
719 _STLP_END_NAMESPACE
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:
731