1*38fd1498Szrj // RB tree implementation -*- C++ -*-
2*38fd1498Szrj
3*38fd1498Szrj // Copyright (C) 2001-2018 Free Software Foundation, Inc.
4*38fd1498Szrj //
5*38fd1498Szrj // This file is part of the GNU ISO C++ Library. This library is free
6*38fd1498Szrj // software; you can redistribute it and/or modify it under the
7*38fd1498Szrj // terms of the GNU General Public License as published by the
8*38fd1498Szrj // Free Software Foundation; either version 3, or (at your option)
9*38fd1498Szrj // any later version.
10*38fd1498Szrj
11*38fd1498Szrj // This library is distributed in the hope that it will be useful,
12*38fd1498Szrj // but WITHOUT ANY WARRANTY; without even the implied warranty of
13*38fd1498Szrj // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14*38fd1498Szrj // GNU General Public License for more details.
15*38fd1498Szrj
16*38fd1498Szrj // Under Section 7 of GPL version 3, you are granted additional
17*38fd1498Szrj // permissions described in the GCC Runtime Library Exception, version
18*38fd1498Szrj // 3.1, as published by the Free Software Foundation.
19*38fd1498Szrj
20*38fd1498Szrj // You should have received a copy of the GNU General Public License and
21*38fd1498Szrj // a copy of the GCC Runtime Library Exception along with this program;
22*38fd1498Szrj // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23*38fd1498Szrj // <http://www.gnu.org/licenses/>.
24*38fd1498Szrj
25*38fd1498Szrj /*
26*38fd1498Szrj *
27*38fd1498Szrj * Copyright (c) 1996,1997
28*38fd1498Szrj * Silicon Graphics Computer Systems, Inc.
29*38fd1498Szrj *
30*38fd1498Szrj * Permission to use, copy, modify, distribute and sell this software
31*38fd1498Szrj * and its documentation for any purpose is hereby granted without fee,
32*38fd1498Szrj * provided that the above copyright notice appear in all copies and
33*38fd1498Szrj * that both that copyright notice and this permission notice appear
34*38fd1498Szrj * in supporting documentation. Silicon Graphics makes no
35*38fd1498Szrj * representations about the suitability of this software for any
36*38fd1498Szrj * purpose. It is provided "as is" without express or implied warranty.
37*38fd1498Szrj *
38*38fd1498Szrj *
39*38fd1498Szrj * Copyright (c) 1994
40*38fd1498Szrj * Hewlett-Packard Company
41*38fd1498Szrj *
42*38fd1498Szrj * Permission to use, copy, modify, distribute and sell this software
43*38fd1498Szrj * and its documentation for any purpose is hereby granted without fee,
44*38fd1498Szrj * provided that the above copyright notice appear in all copies and
45*38fd1498Szrj * that both that copyright notice and this permission notice appear
46*38fd1498Szrj * in supporting documentation. Hewlett-Packard Company makes no
47*38fd1498Szrj * representations about the suitability of this software for any
48*38fd1498Szrj * purpose. It is provided "as is" without express or implied warranty.
49*38fd1498Szrj *
50*38fd1498Szrj *
51*38fd1498Szrj */
52*38fd1498Szrj
53*38fd1498Szrj /** @file bits/stl_tree.h
54*38fd1498Szrj * This is an internal header file, included by other library headers.
55*38fd1498Szrj * Do not attempt to use it directly. @headername{map,set}
56*38fd1498Szrj */
57*38fd1498Szrj
58*38fd1498Szrj #ifndef _STL_TREE_H
59*38fd1498Szrj #define _STL_TREE_H 1
60*38fd1498Szrj
61*38fd1498Szrj #pragma GCC system_header
62*38fd1498Szrj
63*38fd1498Szrj #include <bits/stl_algobase.h>
64*38fd1498Szrj #include <bits/allocator.h>
65*38fd1498Szrj #include <bits/stl_function.h>
66*38fd1498Szrj #include <bits/cpp_type_traits.h>
67*38fd1498Szrj #include <ext/alloc_traits.h>
68*38fd1498Szrj #if __cplusplus >= 201103L
69*38fd1498Szrj # include <ext/aligned_buffer.h>
70*38fd1498Szrj #endif
71*38fd1498Szrj #if __cplusplus > 201402L
72*38fd1498Szrj # include <bits/node_handle.h>
73*38fd1498Szrj #endif
74*38fd1498Szrj
_GLIBCXX_VISIBILITY(default)75*38fd1498Szrj namespace std _GLIBCXX_VISIBILITY(default)
76*38fd1498Szrj {
77*38fd1498Szrj _GLIBCXX_BEGIN_NAMESPACE_VERSION
78*38fd1498Szrj
79*38fd1498Szrj #if __cplusplus > 201103L
80*38fd1498Szrj # define __cpp_lib_generic_associative_lookup 201304
81*38fd1498Szrj #endif
82*38fd1498Szrj
83*38fd1498Szrj // Red-black tree class, designed for use in implementing STL
84*38fd1498Szrj // associative containers (set, multiset, map, and multimap). The
85*38fd1498Szrj // insertion and deletion algorithms are based on those in Cormen,
86*38fd1498Szrj // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
87*38fd1498Szrj // 1990), except that
88*38fd1498Szrj //
89*38fd1498Szrj // (1) the header cell is maintained with links not only to the root
90*38fd1498Szrj // but also to the leftmost node of the tree, to enable constant
91*38fd1498Szrj // time begin(), and to the rightmost node of the tree, to enable
92*38fd1498Szrj // linear time performance when used with the generic set algorithms
93*38fd1498Szrj // (set_union, etc.)
94*38fd1498Szrj //
95*38fd1498Szrj // (2) when a node being deleted has two children its successor node
96*38fd1498Szrj // is relinked into its place, rather than copied, so that the only
97*38fd1498Szrj // iterators invalidated are those referring to the deleted node.
98*38fd1498Szrj
99*38fd1498Szrj enum _Rb_tree_color { _S_red = false, _S_black = true };
100*38fd1498Szrj
101*38fd1498Szrj struct _Rb_tree_node_base
102*38fd1498Szrj {
103*38fd1498Szrj typedef _Rb_tree_node_base* _Base_ptr;
104*38fd1498Szrj typedef const _Rb_tree_node_base* _Const_Base_ptr;
105*38fd1498Szrj
106*38fd1498Szrj _Rb_tree_color _M_color;
107*38fd1498Szrj _Base_ptr _M_parent;
108*38fd1498Szrj _Base_ptr _M_left;
109*38fd1498Szrj _Base_ptr _M_right;
110*38fd1498Szrj
111*38fd1498Szrj static _Base_ptr
112*38fd1498Szrj _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
113*38fd1498Szrj {
114*38fd1498Szrj while (__x->_M_left != 0) __x = __x->_M_left;
115*38fd1498Szrj return __x;
116*38fd1498Szrj }
117*38fd1498Szrj
118*38fd1498Szrj static _Const_Base_ptr
119*38fd1498Szrj _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
120*38fd1498Szrj {
121*38fd1498Szrj while (__x->_M_left != 0) __x = __x->_M_left;
122*38fd1498Szrj return __x;
123*38fd1498Szrj }
124*38fd1498Szrj
125*38fd1498Szrj static _Base_ptr
126*38fd1498Szrj _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
127*38fd1498Szrj {
128*38fd1498Szrj while (__x->_M_right != 0) __x = __x->_M_right;
129*38fd1498Szrj return __x;
130*38fd1498Szrj }
131*38fd1498Szrj
132*38fd1498Szrj static _Const_Base_ptr
133*38fd1498Szrj _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
134*38fd1498Szrj {
135*38fd1498Szrj while (__x->_M_right != 0) __x = __x->_M_right;
136*38fd1498Szrj return __x;
137*38fd1498Szrj }
138*38fd1498Szrj };
139*38fd1498Szrj
140*38fd1498Szrj // Helper type offering value initialization guarantee on the compare functor.
141*38fd1498Szrj template<typename _Key_compare>
142*38fd1498Szrj struct _Rb_tree_key_compare
143*38fd1498Szrj {
144*38fd1498Szrj _Key_compare _M_key_compare;
145*38fd1498Szrj
146*38fd1498Szrj _Rb_tree_key_compare()
147*38fd1498Szrj _GLIBCXX_NOEXCEPT_IF(
148*38fd1498Szrj is_nothrow_default_constructible<_Key_compare>::value)
149*38fd1498Szrj : _M_key_compare()
150*38fd1498Szrj { }
151*38fd1498Szrj
152*38fd1498Szrj _Rb_tree_key_compare(const _Key_compare& __comp)
153*38fd1498Szrj : _M_key_compare(__comp)
154*38fd1498Szrj { }
155*38fd1498Szrj
156*38fd1498Szrj #if __cplusplus >= 201103L
157*38fd1498Szrj // Copy constructor added for consistency with C++98 mode.
158*38fd1498Szrj _Rb_tree_key_compare(const _Rb_tree_key_compare&) = default;
159*38fd1498Szrj
160*38fd1498Szrj _Rb_tree_key_compare(_Rb_tree_key_compare&& __x)
161*38fd1498Szrj noexcept(is_nothrow_copy_constructible<_Key_compare>::value)
162*38fd1498Szrj : _M_key_compare(__x._M_key_compare)
163*38fd1498Szrj { }
164*38fd1498Szrj #endif
165*38fd1498Szrj };
166*38fd1498Szrj
167*38fd1498Szrj // Helper type to manage default initialization of node count and header.
168*38fd1498Szrj struct _Rb_tree_header
169*38fd1498Szrj {
170*38fd1498Szrj _Rb_tree_node_base _M_header;
171*38fd1498Szrj size_t _M_node_count; // Keeps track of size of tree.
172*38fd1498Szrj
173*38fd1498Szrj _Rb_tree_header() _GLIBCXX_NOEXCEPT
174*38fd1498Szrj {
175*38fd1498Szrj _M_header._M_color = _S_red;
176*38fd1498Szrj _M_reset();
177*38fd1498Szrj }
178*38fd1498Szrj
179*38fd1498Szrj #if __cplusplus >= 201103L
180*38fd1498Szrj _Rb_tree_header(_Rb_tree_header&& __x) noexcept
181*38fd1498Szrj {
182*38fd1498Szrj if (__x._M_header._M_parent != nullptr)
183*38fd1498Szrj _M_move_data(__x);
184*38fd1498Szrj else
185*38fd1498Szrj {
186*38fd1498Szrj _M_header._M_color = _S_red;
187*38fd1498Szrj _M_reset();
188*38fd1498Szrj }
189*38fd1498Szrj }
190*38fd1498Szrj #endif
191*38fd1498Szrj
192*38fd1498Szrj void
193*38fd1498Szrj _M_move_data(_Rb_tree_header& __from)
194*38fd1498Szrj {
195*38fd1498Szrj _M_header._M_color = __from._M_header._M_color;
196*38fd1498Szrj _M_header._M_parent = __from._M_header._M_parent;
197*38fd1498Szrj _M_header._M_left = __from._M_header._M_left;
198*38fd1498Szrj _M_header._M_right = __from._M_header._M_right;
199*38fd1498Szrj _M_header._M_parent->_M_parent = &_M_header;
200*38fd1498Szrj _M_node_count = __from._M_node_count;
201*38fd1498Szrj
202*38fd1498Szrj __from._M_reset();
203*38fd1498Szrj }
204*38fd1498Szrj
205*38fd1498Szrj void
206*38fd1498Szrj _M_reset()
207*38fd1498Szrj {
208*38fd1498Szrj _M_header._M_parent = 0;
209*38fd1498Szrj _M_header._M_left = &_M_header;
210*38fd1498Szrj _M_header._M_right = &_M_header;
211*38fd1498Szrj _M_node_count = 0;
212*38fd1498Szrj }
213*38fd1498Szrj };
214*38fd1498Szrj
215*38fd1498Szrj template<typename _Val>
216*38fd1498Szrj struct _Rb_tree_node : public _Rb_tree_node_base
217*38fd1498Szrj {
218*38fd1498Szrj typedef _Rb_tree_node<_Val>* _Link_type;
219*38fd1498Szrj
220*38fd1498Szrj #if __cplusplus < 201103L
221*38fd1498Szrj _Val _M_value_field;
222*38fd1498Szrj
223*38fd1498Szrj _Val*
224*38fd1498Szrj _M_valptr()
225*38fd1498Szrj { return std::__addressof(_M_value_field); }
226*38fd1498Szrj
227*38fd1498Szrj const _Val*
228*38fd1498Szrj _M_valptr() const
229*38fd1498Szrj { return std::__addressof(_M_value_field); }
230*38fd1498Szrj #else
231*38fd1498Szrj __gnu_cxx::__aligned_membuf<_Val> _M_storage;
232*38fd1498Szrj
233*38fd1498Szrj _Val*
234*38fd1498Szrj _M_valptr()
235*38fd1498Szrj { return _M_storage._M_ptr(); }
236*38fd1498Szrj
237*38fd1498Szrj const _Val*
238*38fd1498Szrj _M_valptr() const
239*38fd1498Szrj { return _M_storage._M_ptr(); }
240*38fd1498Szrj #endif
241*38fd1498Szrj };
242*38fd1498Szrj
243*38fd1498Szrj _GLIBCXX_PURE _Rb_tree_node_base*
244*38fd1498Szrj _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
245*38fd1498Szrj
246*38fd1498Szrj _GLIBCXX_PURE const _Rb_tree_node_base*
247*38fd1498Szrj _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
248*38fd1498Szrj
249*38fd1498Szrj _GLIBCXX_PURE _Rb_tree_node_base*
250*38fd1498Szrj _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
251*38fd1498Szrj
252*38fd1498Szrj _GLIBCXX_PURE const _Rb_tree_node_base*
253*38fd1498Szrj _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
254*38fd1498Szrj
255*38fd1498Szrj template<typename _Tp>
256*38fd1498Szrj struct _Rb_tree_iterator
257*38fd1498Szrj {
258*38fd1498Szrj typedef _Tp value_type;
259*38fd1498Szrj typedef _Tp& reference;
260*38fd1498Szrj typedef _Tp* pointer;
261*38fd1498Szrj
262*38fd1498Szrj typedef bidirectional_iterator_tag iterator_category;
263*38fd1498Szrj typedef ptrdiff_t difference_type;
264*38fd1498Szrj
265*38fd1498Szrj typedef _Rb_tree_iterator<_Tp> _Self;
266*38fd1498Szrj typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
267*38fd1498Szrj typedef _Rb_tree_node<_Tp>* _Link_type;
268*38fd1498Szrj
269*38fd1498Szrj _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
270*38fd1498Szrj : _M_node() { }
271*38fd1498Szrj
272*38fd1498Szrj explicit
273*38fd1498Szrj _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
274*38fd1498Szrj : _M_node(__x) { }
275*38fd1498Szrj
276*38fd1498Szrj reference
277*38fd1498Szrj operator*() const _GLIBCXX_NOEXCEPT
278*38fd1498Szrj { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
279*38fd1498Szrj
280*38fd1498Szrj pointer
281*38fd1498Szrj operator->() const _GLIBCXX_NOEXCEPT
282*38fd1498Szrj { return static_cast<_Link_type> (_M_node)->_M_valptr(); }
283*38fd1498Szrj
284*38fd1498Szrj _Self&
285*38fd1498Szrj operator++() _GLIBCXX_NOEXCEPT
286*38fd1498Szrj {
287*38fd1498Szrj _M_node = _Rb_tree_increment(_M_node);
288*38fd1498Szrj return *this;
289*38fd1498Szrj }
290*38fd1498Szrj
291*38fd1498Szrj _Self
292*38fd1498Szrj operator++(int) _GLIBCXX_NOEXCEPT
293*38fd1498Szrj {
294*38fd1498Szrj _Self __tmp = *this;
295*38fd1498Szrj _M_node = _Rb_tree_increment(_M_node);
296*38fd1498Szrj return __tmp;
297*38fd1498Szrj }
298*38fd1498Szrj
299*38fd1498Szrj _Self&
300*38fd1498Szrj operator--() _GLIBCXX_NOEXCEPT
301*38fd1498Szrj {
302*38fd1498Szrj _M_node = _Rb_tree_decrement(_M_node);
303*38fd1498Szrj return *this;
304*38fd1498Szrj }
305*38fd1498Szrj
306*38fd1498Szrj _Self
307*38fd1498Szrj operator--(int) _GLIBCXX_NOEXCEPT
308*38fd1498Szrj {
309*38fd1498Szrj _Self __tmp = *this;
310*38fd1498Szrj _M_node = _Rb_tree_decrement(_M_node);
311*38fd1498Szrj return __tmp;
312*38fd1498Szrj }
313*38fd1498Szrj
314*38fd1498Szrj bool
315*38fd1498Szrj operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
316*38fd1498Szrj { return _M_node == __x._M_node; }
317*38fd1498Szrj
318*38fd1498Szrj bool
319*38fd1498Szrj operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
320*38fd1498Szrj { return _M_node != __x._M_node; }
321*38fd1498Szrj
322*38fd1498Szrj _Base_ptr _M_node;
323*38fd1498Szrj };
324*38fd1498Szrj
325*38fd1498Szrj template<typename _Tp>
326*38fd1498Szrj struct _Rb_tree_const_iterator
327*38fd1498Szrj {
328*38fd1498Szrj typedef _Tp value_type;
329*38fd1498Szrj typedef const _Tp& reference;
330*38fd1498Szrj typedef const _Tp* pointer;
331*38fd1498Szrj
332*38fd1498Szrj typedef _Rb_tree_iterator<_Tp> iterator;
333*38fd1498Szrj
334*38fd1498Szrj typedef bidirectional_iterator_tag iterator_category;
335*38fd1498Szrj typedef ptrdiff_t difference_type;
336*38fd1498Szrj
337*38fd1498Szrj typedef _Rb_tree_const_iterator<_Tp> _Self;
338*38fd1498Szrj typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
339*38fd1498Szrj typedef const _Rb_tree_node<_Tp>* _Link_type;
340*38fd1498Szrj
341*38fd1498Szrj _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
342*38fd1498Szrj : _M_node() { }
343*38fd1498Szrj
344*38fd1498Szrj explicit
345*38fd1498Szrj _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
346*38fd1498Szrj : _M_node(__x) { }
347*38fd1498Szrj
348*38fd1498Szrj _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
349*38fd1498Szrj : _M_node(__it._M_node) { }
350*38fd1498Szrj
351*38fd1498Szrj iterator
352*38fd1498Szrj _M_const_cast() const _GLIBCXX_NOEXCEPT
353*38fd1498Szrj { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
354*38fd1498Szrj
355*38fd1498Szrj reference
356*38fd1498Szrj operator*() const _GLIBCXX_NOEXCEPT
357*38fd1498Szrj { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
358*38fd1498Szrj
359*38fd1498Szrj pointer
360*38fd1498Szrj operator->() const _GLIBCXX_NOEXCEPT
361*38fd1498Szrj { return static_cast<_Link_type>(_M_node)->_M_valptr(); }
362*38fd1498Szrj
363*38fd1498Szrj _Self&
364*38fd1498Szrj operator++() _GLIBCXX_NOEXCEPT
365*38fd1498Szrj {
366*38fd1498Szrj _M_node = _Rb_tree_increment(_M_node);
367*38fd1498Szrj return *this;
368*38fd1498Szrj }
369*38fd1498Szrj
370*38fd1498Szrj _Self
371*38fd1498Szrj operator++(int) _GLIBCXX_NOEXCEPT
372*38fd1498Szrj {
373*38fd1498Szrj _Self __tmp = *this;
374*38fd1498Szrj _M_node = _Rb_tree_increment(_M_node);
375*38fd1498Szrj return __tmp;
376*38fd1498Szrj }
377*38fd1498Szrj
378*38fd1498Szrj _Self&
379*38fd1498Szrj operator--() _GLIBCXX_NOEXCEPT
380*38fd1498Szrj {
381*38fd1498Szrj _M_node = _Rb_tree_decrement(_M_node);
382*38fd1498Szrj return *this;
383*38fd1498Szrj }
384*38fd1498Szrj
385*38fd1498Szrj _Self
386*38fd1498Szrj operator--(int) _GLIBCXX_NOEXCEPT
387*38fd1498Szrj {
388*38fd1498Szrj _Self __tmp = *this;
389*38fd1498Szrj _M_node = _Rb_tree_decrement(_M_node);
390*38fd1498Szrj return __tmp;
391*38fd1498Szrj }
392*38fd1498Szrj
393*38fd1498Szrj bool
394*38fd1498Szrj operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
395*38fd1498Szrj { return _M_node == __x._M_node; }
396*38fd1498Szrj
397*38fd1498Szrj bool
398*38fd1498Szrj operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
399*38fd1498Szrj { return _M_node != __x._M_node; }
400*38fd1498Szrj
401*38fd1498Szrj _Base_ptr _M_node;
402*38fd1498Szrj };
403*38fd1498Szrj
404*38fd1498Szrj template<typename _Val>
405*38fd1498Szrj inline bool
406*38fd1498Szrj operator==(const _Rb_tree_iterator<_Val>& __x,
407*38fd1498Szrj const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
408*38fd1498Szrj { return __x._M_node == __y._M_node; }
409*38fd1498Szrj
410*38fd1498Szrj template<typename _Val>
411*38fd1498Szrj inline bool
412*38fd1498Szrj operator!=(const _Rb_tree_iterator<_Val>& __x,
413*38fd1498Szrj const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
414*38fd1498Szrj { return __x._M_node != __y._M_node; }
415*38fd1498Szrj
416*38fd1498Szrj void
417*38fd1498Szrj _Rb_tree_insert_and_rebalance(const bool __insert_left,
418*38fd1498Szrj _Rb_tree_node_base* __x,
419*38fd1498Szrj _Rb_tree_node_base* __p,
420*38fd1498Szrj _Rb_tree_node_base& __header) throw ();
421*38fd1498Szrj
422*38fd1498Szrj _Rb_tree_node_base*
423*38fd1498Szrj _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
424*38fd1498Szrj _Rb_tree_node_base& __header) throw ();
425*38fd1498Szrj
426*38fd1498Szrj #if __cplusplus > 201103L
427*38fd1498Szrj template<typename _Cmp, typename _SfinaeType, typename = __void_t<>>
428*38fd1498Szrj struct __has_is_transparent
429*38fd1498Szrj { };
430*38fd1498Szrj
431*38fd1498Szrj template<typename _Cmp, typename _SfinaeType>
432*38fd1498Szrj struct __has_is_transparent<_Cmp, _SfinaeType,
433*38fd1498Szrj __void_t<typename _Cmp::is_transparent>>
434*38fd1498Szrj { typedef void type; };
435*38fd1498Szrj #endif
436*38fd1498Szrj
437*38fd1498Szrj #if __cplusplus > 201402L
438*38fd1498Szrj template<typename _Tree1, typename _Cmp2>
439*38fd1498Szrj struct _Rb_tree_merge_helper { };
440*38fd1498Szrj #endif
441*38fd1498Szrj
442*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
443*38fd1498Szrj typename _Compare, typename _Alloc = allocator<_Val> >
444*38fd1498Szrj class _Rb_tree
445*38fd1498Szrj {
446*38fd1498Szrj typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
447*38fd1498Szrj rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
448*38fd1498Szrj
449*38fd1498Szrj typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
450*38fd1498Szrj
451*38fd1498Szrj #if __cplusplus >= 201103L
452*38fd1498Szrj static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{},
453*38fd1498Szrj "comparison object must be invocable with two arguments of key type");
454*38fd1498Szrj # if __cplusplus >= 201703L
455*38fd1498Szrj // _GLIBCXX_RESOLVE_LIB_DEFECTS
456*38fd1498Szrj // 2542. Missing const requirements for associative containers
457*38fd1498Szrj static_assert(is_invocable_v<const _Compare&, const _Key&, const _Key&>,
458*38fd1498Szrj "comparison object must be invocable as const");
459*38fd1498Szrj # endif // C++17
460*38fd1498Szrj #endif // C++11
461*38fd1498Szrj
462*38fd1498Szrj protected:
463*38fd1498Szrj typedef _Rb_tree_node_base* _Base_ptr;
464*38fd1498Szrj typedef const _Rb_tree_node_base* _Const_Base_ptr;
465*38fd1498Szrj typedef _Rb_tree_node<_Val>* _Link_type;
466*38fd1498Szrj typedef const _Rb_tree_node<_Val>* _Const_Link_type;
467*38fd1498Szrj
468*38fd1498Szrj private:
469*38fd1498Szrj // Functor recycling a pool of nodes and using allocation once the pool
470*38fd1498Szrj // is empty.
471*38fd1498Szrj struct _Reuse_or_alloc_node
472*38fd1498Szrj {
473*38fd1498Szrj _Reuse_or_alloc_node(_Rb_tree& __t)
474*38fd1498Szrj : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
475*38fd1498Szrj {
476*38fd1498Szrj if (_M_root)
477*38fd1498Szrj {
478*38fd1498Szrj _M_root->_M_parent = 0;
479*38fd1498Szrj
480*38fd1498Szrj if (_M_nodes->_M_left)
481*38fd1498Szrj _M_nodes = _M_nodes->_M_left;
482*38fd1498Szrj }
483*38fd1498Szrj else
484*38fd1498Szrj _M_nodes = 0;
485*38fd1498Szrj }
486*38fd1498Szrj
487*38fd1498Szrj #if __cplusplus >= 201103L
488*38fd1498Szrj _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete;
489*38fd1498Szrj #endif
490*38fd1498Szrj
491*38fd1498Szrj ~_Reuse_or_alloc_node()
492*38fd1498Szrj { _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
493*38fd1498Szrj
494*38fd1498Szrj template<typename _Arg>
495*38fd1498Szrj _Link_type
496*38fd1498Szrj #if __cplusplus < 201103L
497*38fd1498Szrj operator()(const _Arg& __arg)
498*38fd1498Szrj #else
499*38fd1498Szrj operator()(_Arg&& __arg)
500*38fd1498Szrj #endif
501*38fd1498Szrj {
502*38fd1498Szrj _Link_type __node = static_cast<_Link_type>(_M_extract());
503*38fd1498Szrj if (__node)
504*38fd1498Szrj {
505*38fd1498Szrj _M_t._M_destroy_node(__node);
506*38fd1498Szrj _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
507*38fd1498Szrj return __node;
508*38fd1498Szrj }
509*38fd1498Szrj
510*38fd1498Szrj return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
511*38fd1498Szrj }
512*38fd1498Szrj
513*38fd1498Szrj private:
514*38fd1498Szrj _Base_ptr
515*38fd1498Szrj _M_extract()
516*38fd1498Szrj {
517*38fd1498Szrj if (!_M_nodes)
518*38fd1498Szrj return _M_nodes;
519*38fd1498Szrj
520*38fd1498Szrj _Base_ptr __node = _M_nodes;
521*38fd1498Szrj _M_nodes = _M_nodes->_M_parent;
522*38fd1498Szrj if (_M_nodes)
523*38fd1498Szrj {
524*38fd1498Szrj if (_M_nodes->_M_right == __node)
525*38fd1498Szrj {
526*38fd1498Szrj _M_nodes->_M_right = 0;
527*38fd1498Szrj
528*38fd1498Szrj if (_M_nodes->_M_left)
529*38fd1498Szrj {
530*38fd1498Szrj _M_nodes = _M_nodes->_M_left;
531*38fd1498Szrj
532*38fd1498Szrj while (_M_nodes->_M_right)
533*38fd1498Szrj _M_nodes = _M_nodes->_M_right;
534*38fd1498Szrj
535*38fd1498Szrj if (_M_nodes->_M_left)
536*38fd1498Szrj _M_nodes = _M_nodes->_M_left;
537*38fd1498Szrj }
538*38fd1498Szrj }
539*38fd1498Szrj else // __node is on the left.
540*38fd1498Szrj _M_nodes->_M_left = 0;
541*38fd1498Szrj }
542*38fd1498Szrj else
543*38fd1498Szrj _M_root = 0;
544*38fd1498Szrj
545*38fd1498Szrj return __node;
546*38fd1498Szrj }
547*38fd1498Szrj
548*38fd1498Szrj _Base_ptr _M_root;
549*38fd1498Szrj _Base_ptr _M_nodes;
550*38fd1498Szrj _Rb_tree& _M_t;
551*38fd1498Szrj };
552*38fd1498Szrj
553*38fd1498Szrj // Functor similar to the previous one but without any pool of nodes to
554*38fd1498Szrj // recycle.
555*38fd1498Szrj struct _Alloc_node
556*38fd1498Szrj {
557*38fd1498Szrj _Alloc_node(_Rb_tree& __t)
558*38fd1498Szrj : _M_t(__t) { }
559*38fd1498Szrj
560*38fd1498Szrj template<typename _Arg>
561*38fd1498Szrj _Link_type
562*38fd1498Szrj #if __cplusplus < 201103L
563*38fd1498Szrj operator()(const _Arg& __arg) const
564*38fd1498Szrj #else
565*38fd1498Szrj operator()(_Arg&& __arg) const
566*38fd1498Szrj #endif
567*38fd1498Szrj { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
568*38fd1498Szrj
569*38fd1498Szrj private:
570*38fd1498Szrj _Rb_tree& _M_t;
571*38fd1498Szrj };
572*38fd1498Szrj
573*38fd1498Szrj public:
574*38fd1498Szrj typedef _Key key_type;
575*38fd1498Szrj typedef _Val value_type;
576*38fd1498Szrj typedef value_type* pointer;
577*38fd1498Szrj typedef const value_type* const_pointer;
578*38fd1498Szrj typedef value_type& reference;
579*38fd1498Szrj typedef const value_type& const_reference;
580*38fd1498Szrj typedef size_t size_type;
581*38fd1498Szrj typedef ptrdiff_t difference_type;
582*38fd1498Szrj typedef _Alloc allocator_type;
583*38fd1498Szrj
584*38fd1498Szrj _Node_allocator&
585*38fd1498Szrj _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
586*38fd1498Szrj { return this->_M_impl; }
587*38fd1498Szrj
588*38fd1498Szrj const _Node_allocator&
589*38fd1498Szrj _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
590*38fd1498Szrj { return this->_M_impl; }
591*38fd1498Szrj
592*38fd1498Szrj allocator_type
593*38fd1498Szrj get_allocator() const _GLIBCXX_NOEXCEPT
594*38fd1498Szrj { return allocator_type(_M_get_Node_allocator()); }
595*38fd1498Szrj
596*38fd1498Szrj protected:
597*38fd1498Szrj _Link_type
598*38fd1498Szrj _M_get_node()
599*38fd1498Szrj { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
600*38fd1498Szrj
601*38fd1498Szrj void
602*38fd1498Szrj _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
603*38fd1498Szrj { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
604*38fd1498Szrj
605*38fd1498Szrj #if __cplusplus < 201103L
606*38fd1498Szrj void
607*38fd1498Szrj _M_construct_node(_Link_type __node, const value_type& __x)
608*38fd1498Szrj {
609*38fd1498Szrj __try
610*38fd1498Szrj { get_allocator().construct(__node->_M_valptr(), __x); }
611*38fd1498Szrj __catch(...)
612*38fd1498Szrj {
613*38fd1498Szrj _M_put_node(__node);
614*38fd1498Szrj __throw_exception_again;
615*38fd1498Szrj }
616*38fd1498Szrj }
617*38fd1498Szrj
618*38fd1498Szrj _Link_type
619*38fd1498Szrj _M_create_node(const value_type& __x)
620*38fd1498Szrj {
621*38fd1498Szrj _Link_type __tmp = _M_get_node();
622*38fd1498Szrj _M_construct_node(__tmp, __x);
623*38fd1498Szrj return __tmp;
624*38fd1498Szrj }
625*38fd1498Szrj
626*38fd1498Szrj void
627*38fd1498Szrj _M_destroy_node(_Link_type __p)
628*38fd1498Szrj { get_allocator().destroy(__p->_M_valptr()); }
629*38fd1498Szrj #else
630*38fd1498Szrj template<typename... _Args>
631*38fd1498Szrj void
632*38fd1498Szrj _M_construct_node(_Link_type __node, _Args&&... __args)
633*38fd1498Szrj {
634*38fd1498Szrj __try
635*38fd1498Szrj {
636*38fd1498Szrj ::new(__node) _Rb_tree_node<_Val>;
637*38fd1498Szrj _Alloc_traits::construct(_M_get_Node_allocator(),
638*38fd1498Szrj __node->_M_valptr(),
639*38fd1498Szrj std::forward<_Args>(__args)...);
640*38fd1498Szrj }
641*38fd1498Szrj __catch(...)
642*38fd1498Szrj {
643*38fd1498Szrj __node->~_Rb_tree_node<_Val>();
644*38fd1498Szrj _M_put_node(__node);
645*38fd1498Szrj __throw_exception_again;
646*38fd1498Szrj }
647*38fd1498Szrj }
648*38fd1498Szrj
649*38fd1498Szrj template<typename... _Args>
650*38fd1498Szrj _Link_type
651*38fd1498Szrj _M_create_node(_Args&&... __args)
652*38fd1498Szrj {
653*38fd1498Szrj _Link_type __tmp = _M_get_node();
654*38fd1498Szrj _M_construct_node(__tmp, std::forward<_Args>(__args)...);
655*38fd1498Szrj return __tmp;
656*38fd1498Szrj }
657*38fd1498Szrj
658*38fd1498Szrj void
659*38fd1498Szrj _M_destroy_node(_Link_type __p) noexcept
660*38fd1498Szrj {
661*38fd1498Szrj _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
662*38fd1498Szrj __p->~_Rb_tree_node<_Val>();
663*38fd1498Szrj }
664*38fd1498Szrj #endif
665*38fd1498Szrj
666*38fd1498Szrj void
667*38fd1498Szrj _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
668*38fd1498Szrj {
669*38fd1498Szrj _M_destroy_node(__p);
670*38fd1498Szrj _M_put_node(__p);
671*38fd1498Szrj }
672*38fd1498Szrj
673*38fd1498Szrj template<typename _NodeGen>
674*38fd1498Szrj _Link_type
675*38fd1498Szrj _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
676*38fd1498Szrj {
677*38fd1498Szrj _Link_type __tmp = __node_gen(*__x->_M_valptr());
678*38fd1498Szrj __tmp->_M_color = __x->_M_color;
679*38fd1498Szrj __tmp->_M_left = 0;
680*38fd1498Szrj __tmp->_M_right = 0;
681*38fd1498Szrj return __tmp;
682*38fd1498Szrj }
683*38fd1498Szrj
684*38fd1498Szrj protected:
685*38fd1498Szrj #if _GLIBCXX_INLINE_VERSION
686*38fd1498Szrj template<typename _Key_compare>
687*38fd1498Szrj #else
688*38fd1498Szrj // Unused _Is_pod_comparator is kept as it is part of mangled name.
689*38fd1498Szrj template<typename _Key_compare,
690*38fd1498Szrj bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
691*38fd1498Szrj #endif
692*38fd1498Szrj struct _Rb_tree_impl
693*38fd1498Szrj : public _Node_allocator
694*38fd1498Szrj , public _Rb_tree_key_compare<_Key_compare>
695*38fd1498Szrj , public _Rb_tree_header
696*38fd1498Szrj {
697*38fd1498Szrj typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare;
698*38fd1498Szrj
699*38fd1498Szrj _Rb_tree_impl()
700*38fd1498Szrj _GLIBCXX_NOEXCEPT_IF(
701*38fd1498Szrj is_nothrow_default_constructible<_Node_allocator>::value
702*38fd1498Szrj && is_nothrow_default_constructible<_Base_key_compare>::value )
703*38fd1498Szrj : _Node_allocator()
704*38fd1498Szrj { }
705*38fd1498Szrj
706*38fd1498Szrj _Rb_tree_impl(const _Rb_tree_impl& __x)
707*38fd1498Szrj : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x))
708*38fd1498Szrj , _Base_key_compare(__x._M_key_compare)
709*38fd1498Szrj { }
710*38fd1498Szrj
711*38fd1498Szrj #if __cplusplus < 201103L
712*38fd1498Szrj _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
713*38fd1498Szrj : _Node_allocator(__a), _Base_key_compare(__comp)
714*38fd1498Szrj { }
715*38fd1498Szrj #else
716*38fd1498Szrj _Rb_tree_impl(_Rb_tree_impl&&) = default;
717*38fd1498Szrj
718*38fd1498Szrj _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
719*38fd1498Szrj : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
720*38fd1498Szrj { }
721*38fd1498Szrj #endif
722*38fd1498Szrj };
723*38fd1498Szrj
724*38fd1498Szrj _Rb_tree_impl<_Compare> _M_impl;
725*38fd1498Szrj
726*38fd1498Szrj protected:
727*38fd1498Szrj _Base_ptr&
728*38fd1498Szrj _M_root() _GLIBCXX_NOEXCEPT
729*38fd1498Szrj { return this->_M_impl._M_header._M_parent; }
730*38fd1498Szrj
731*38fd1498Szrj _Const_Base_ptr
732*38fd1498Szrj _M_root() const _GLIBCXX_NOEXCEPT
733*38fd1498Szrj { return this->_M_impl._M_header._M_parent; }
734*38fd1498Szrj
735*38fd1498Szrj _Base_ptr&
736*38fd1498Szrj _M_leftmost() _GLIBCXX_NOEXCEPT
737*38fd1498Szrj { return this->_M_impl._M_header._M_left; }
738*38fd1498Szrj
739*38fd1498Szrj _Const_Base_ptr
740*38fd1498Szrj _M_leftmost() const _GLIBCXX_NOEXCEPT
741*38fd1498Szrj { return this->_M_impl._M_header._M_left; }
742*38fd1498Szrj
743*38fd1498Szrj _Base_ptr&
744*38fd1498Szrj _M_rightmost() _GLIBCXX_NOEXCEPT
745*38fd1498Szrj { return this->_M_impl._M_header._M_right; }
746*38fd1498Szrj
747*38fd1498Szrj _Const_Base_ptr
748*38fd1498Szrj _M_rightmost() const _GLIBCXX_NOEXCEPT
749*38fd1498Szrj { return this->_M_impl._M_header._M_right; }
750*38fd1498Szrj
751*38fd1498Szrj _Link_type
752*38fd1498Szrj _M_begin() _GLIBCXX_NOEXCEPT
753*38fd1498Szrj { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
754*38fd1498Szrj
755*38fd1498Szrj _Const_Link_type
756*38fd1498Szrj _M_begin() const _GLIBCXX_NOEXCEPT
757*38fd1498Szrj {
758*38fd1498Szrj return static_cast<_Const_Link_type>
759*38fd1498Szrj (this->_M_impl._M_header._M_parent);
760*38fd1498Szrj }
761*38fd1498Szrj
762*38fd1498Szrj _Base_ptr
763*38fd1498Szrj _M_end() _GLIBCXX_NOEXCEPT
764*38fd1498Szrj { return &this->_M_impl._M_header; }
765*38fd1498Szrj
766*38fd1498Szrj _Const_Base_ptr
767*38fd1498Szrj _M_end() const _GLIBCXX_NOEXCEPT
768*38fd1498Szrj { return &this->_M_impl._M_header; }
769*38fd1498Szrj
770*38fd1498Szrj static const_reference
771*38fd1498Szrj _S_value(_Const_Link_type __x)
772*38fd1498Szrj { return *__x->_M_valptr(); }
773*38fd1498Szrj
774*38fd1498Szrj static const _Key&
775*38fd1498Szrj _S_key(_Const_Link_type __x)
776*38fd1498Szrj { return _KeyOfValue()(_S_value(__x)); }
777*38fd1498Szrj
778*38fd1498Szrj static _Link_type
779*38fd1498Szrj _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
780*38fd1498Szrj { return static_cast<_Link_type>(__x->_M_left); }
781*38fd1498Szrj
782*38fd1498Szrj static _Const_Link_type
783*38fd1498Szrj _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
784*38fd1498Szrj { return static_cast<_Const_Link_type>(__x->_M_left); }
785*38fd1498Szrj
786*38fd1498Szrj static _Link_type
787*38fd1498Szrj _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
788*38fd1498Szrj { return static_cast<_Link_type>(__x->_M_right); }
789*38fd1498Szrj
790*38fd1498Szrj static _Const_Link_type
791*38fd1498Szrj _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
792*38fd1498Szrj { return static_cast<_Const_Link_type>(__x->_M_right); }
793*38fd1498Szrj
794*38fd1498Szrj static const_reference
795*38fd1498Szrj _S_value(_Const_Base_ptr __x)
796*38fd1498Szrj { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); }
797*38fd1498Szrj
798*38fd1498Szrj static const _Key&
799*38fd1498Szrj _S_key(_Const_Base_ptr __x)
800*38fd1498Szrj { return _KeyOfValue()(_S_value(__x)); }
801*38fd1498Szrj
802*38fd1498Szrj static _Base_ptr
803*38fd1498Szrj _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
804*38fd1498Szrj { return _Rb_tree_node_base::_S_minimum(__x); }
805*38fd1498Szrj
806*38fd1498Szrj static _Const_Base_ptr
807*38fd1498Szrj _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
808*38fd1498Szrj { return _Rb_tree_node_base::_S_minimum(__x); }
809*38fd1498Szrj
810*38fd1498Szrj static _Base_ptr
811*38fd1498Szrj _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
812*38fd1498Szrj { return _Rb_tree_node_base::_S_maximum(__x); }
813*38fd1498Szrj
814*38fd1498Szrj static _Const_Base_ptr
815*38fd1498Szrj _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
816*38fd1498Szrj { return _Rb_tree_node_base::_S_maximum(__x); }
817*38fd1498Szrj
818*38fd1498Szrj public:
819*38fd1498Szrj typedef _Rb_tree_iterator<value_type> iterator;
820*38fd1498Szrj typedef _Rb_tree_const_iterator<value_type> const_iterator;
821*38fd1498Szrj
822*38fd1498Szrj typedef std::reverse_iterator<iterator> reverse_iterator;
823*38fd1498Szrj typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
824*38fd1498Szrj
825*38fd1498Szrj #if __cplusplus > 201402L
826*38fd1498Szrj using node_type = _Node_handle<_Key, _Val, _Node_allocator>;
827*38fd1498Szrj using insert_return_type = _Node_insert_return<
828*38fd1498Szrj conditional_t<is_same_v<_Key, _Val>, const_iterator, iterator>,
829*38fd1498Szrj node_type>;
830*38fd1498Szrj #endif
831*38fd1498Szrj
832*38fd1498Szrj pair<_Base_ptr, _Base_ptr>
833*38fd1498Szrj _M_get_insert_unique_pos(const key_type& __k);
834*38fd1498Szrj
835*38fd1498Szrj pair<_Base_ptr, _Base_ptr>
836*38fd1498Szrj _M_get_insert_equal_pos(const key_type& __k);
837*38fd1498Szrj
838*38fd1498Szrj pair<_Base_ptr, _Base_ptr>
839*38fd1498Szrj _M_get_insert_hint_unique_pos(const_iterator __pos,
840*38fd1498Szrj const key_type& __k);
841*38fd1498Szrj
842*38fd1498Szrj pair<_Base_ptr, _Base_ptr>
843*38fd1498Szrj _M_get_insert_hint_equal_pos(const_iterator __pos,
844*38fd1498Szrj const key_type& __k);
845*38fd1498Szrj
846*38fd1498Szrj private:
847*38fd1498Szrj #if __cplusplus >= 201103L
848*38fd1498Szrj template<typename _Arg, typename _NodeGen>
849*38fd1498Szrj iterator
850*38fd1498Szrj _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
851*38fd1498Szrj
852*38fd1498Szrj iterator
853*38fd1498Szrj _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
854*38fd1498Szrj
855*38fd1498Szrj template<typename _Arg>
856*38fd1498Szrj iterator
857*38fd1498Szrj _M_insert_lower(_Base_ptr __y, _Arg&& __v);
858*38fd1498Szrj
859*38fd1498Szrj template<typename _Arg>
860*38fd1498Szrj iterator
861*38fd1498Szrj _M_insert_equal_lower(_Arg&& __x);
862*38fd1498Szrj
863*38fd1498Szrj iterator
864*38fd1498Szrj _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
865*38fd1498Szrj
866*38fd1498Szrj iterator
867*38fd1498Szrj _M_insert_equal_lower_node(_Link_type __z);
868*38fd1498Szrj #else
869*38fd1498Szrj template<typename _NodeGen>
870*38fd1498Szrj iterator
871*38fd1498Szrj _M_insert_(_Base_ptr __x, _Base_ptr __y,
872*38fd1498Szrj const value_type& __v, _NodeGen&);
873*38fd1498Szrj
874*38fd1498Szrj // _GLIBCXX_RESOLVE_LIB_DEFECTS
875*38fd1498Szrj // 233. Insertion hints in associative containers.
876*38fd1498Szrj iterator
877*38fd1498Szrj _M_insert_lower(_Base_ptr __y, const value_type& __v);
878*38fd1498Szrj
879*38fd1498Szrj iterator
880*38fd1498Szrj _M_insert_equal_lower(const value_type& __x);
881*38fd1498Szrj #endif
882*38fd1498Szrj
883*38fd1498Szrj template<typename _NodeGen>
884*38fd1498Szrj _Link_type
885*38fd1498Szrj _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
886*38fd1498Szrj
887*38fd1498Szrj template<typename _NodeGen>
888*38fd1498Szrj _Link_type
889*38fd1498Szrj _M_copy(const _Rb_tree& __x, _NodeGen& __gen)
890*38fd1498Szrj {
891*38fd1498Szrj _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen);
892*38fd1498Szrj _M_leftmost() = _S_minimum(__root);
893*38fd1498Szrj _M_rightmost() = _S_maximum(__root);
894*38fd1498Szrj _M_impl._M_node_count = __x._M_impl._M_node_count;
895*38fd1498Szrj return __root;
896*38fd1498Szrj }
897*38fd1498Szrj
898*38fd1498Szrj _Link_type
899*38fd1498Szrj _M_copy(const _Rb_tree& __x)
900*38fd1498Szrj {
901*38fd1498Szrj _Alloc_node __an(*this);
902*38fd1498Szrj return _M_copy(__x, __an);
903*38fd1498Szrj }
904*38fd1498Szrj
905*38fd1498Szrj void
906*38fd1498Szrj _M_erase(_Link_type __x);
907*38fd1498Szrj
908*38fd1498Szrj iterator
909*38fd1498Szrj _M_lower_bound(_Link_type __x, _Base_ptr __y,
910*38fd1498Szrj const _Key& __k);
911*38fd1498Szrj
912*38fd1498Szrj const_iterator
913*38fd1498Szrj _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
914*38fd1498Szrj const _Key& __k) const;
915*38fd1498Szrj
916*38fd1498Szrj iterator
917*38fd1498Szrj _M_upper_bound(_Link_type __x, _Base_ptr __y,
918*38fd1498Szrj const _Key& __k);
919*38fd1498Szrj
920*38fd1498Szrj const_iterator
921*38fd1498Szrj _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
922*38fd1498Szrj const _Key& __k) const;
923*38fd1498Szrj
924*38fd1498Szrj public:
925*38fd1498Szrj // allocation/deallocation
926*38fd1498Szrj #if __cplusplus < 201103L
927*38fd1498Szrj _Rb_tree() { }
928*38fd1498Szrj #else
929*38fd1498Szrj _Rb_tree() = default;
930*38fd1498Szrj #endif
931*38fd1498Szrj
932*38fd1498Szrj _Rb_tree(const _Compare& __comp,
933*38fd1498Szrj const allocator_type& __a = allocator_type())
934*38fd1498Szrj : _M_impl(__comp, _Node_allocator(__a)) { }
935*38fd1498Szrj
936*38fd1498Szrj _Rb_tree(const _Rb_tree& __x)
937*38fd1498Szrj : _M_impl(__x._M_impl)
938*38fd1498Szrj {
939*38fd1498Szrj if (__x._M_root() != 0)
940*38fd1498Szrj _M_root() = _M_copy(__x);
941*38fd1498Szrj }
942*38fd1498Szrj
943*38fd1498Szrj #if __cplusplus >= 201103L
944*38fd1498Szrj _Rb_tree(const allocator_type& __a)
945*38fd1498Szrj : _M_impl(_Compare(), _Node_allocator(__a))
946*38fd1498Szrj { }
947*38fd1498Szrj
948*38fd1498Szrj _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
949*38fd1498Szrj : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
950*38fd1498Szrj {
951*38fd1498Szrj if (__x._M_root() != nullptr)
952*38fd1498Szrj _M_root() = _M_copy(__x);
953*38fd1498Szrj }
954*38fd1498Szrj
955*38fd1498Szrj _Rb_tree(_Rb_tree&&) = default;
956*38fd1498Szrj
957*38fd1498Szrj _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
958*38fd1498Szrj : _Rb_tree(std::move(__x), _Node_allocator(__a))
959*38fd1498Szrj { }
960*38fd1498Szrj
961*38fd1498Szrj _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
962*38fd1498Szrj #endif
963*38fd1498Szrj
964*38fd1498Szrj ~_Rb_tree() _GLIBCXX_NOEXCEPT
965*38fd1498Szrj { _M_erase(_M_begin()); }
966*38fd1498Szrj
967*38fd1498Szrj _Rb_tree&
968*38fd1498Szrj operator=(const _Rb_tree& __x);
969*38fd1498Szrj
970*38fd1498Szrj // Accessors.
971*38fd1498Szrj _Compare
972*38fd1498Szrj key_comp() const
973*38fd1498Szrj { return _M_impl._M_key_compare; }
974*38fd1498Szrj
975*38fd1498Szrj iterator
976*38fd1498Szrj begin() _GLIBCXX_NOEXCEPT
977*38fd1498Szrj { return iterator(this->_M_impl._M_header._M_left); }
978*38fd1498Szrj
979*38fd1498Szrj const_iterator
980*38fd1498Szrj begin() const _GLIBCXX_NOEXCEPT
981*38fd1498Szrj { return const_iterator(this->_M_impl._M_header._M_left); }
982*38fd1498Szrj
983*38fd1498Szrj iterator
984*38fd1498Szrj end() _GLIBCXX_NOEXCEPT
985*38fd1498Szrj { return iterator(&this->_M_impl._M_header); }
986*38fd1498Szrj
987*38fd1498Szrj const_iterator
988*38fd1498Szrj end() const _GLIBCXX_NOEXCEPT
989*38fd1498Szrj { return const_iterator(&this->_M_impl._M_header); }
990*38fd1498Szrj
991*38fd1498Szrj reverse_iterator
992*38fd1498Szrj rbegin() _GLIBCXX_NOEXCEPT
993*38fd1498Szrj { return reverse_iterator(end()); }
994*38fd1498Szrj
995*38fd1498Szrj const_reverse_iterator
996*38fd1498Szrj rbegin() const _GLIBCXX_NOEXCEPT
997*38fd1498Szrj { return const_reverse_iterator(end()); }
998*38fd1498Szrj
999*38fd1498Szrj reverse_iterator
1000*38fd1498Szrj rend() _GLIBCXX_NOEXCEPT
1001*38fd1498Szrj { return reverse_iterator(begin()); }
1002*38fd1498Szrj
1003*38fd1498Szrj const_reverse_iterator
1004*38fd1498Szrj rend() const _GLIBCXX_NOEXCEPT
1005*38fd1498Szrj { return const_reverse_iterator(begin()); }
1006*38fd1498Szrj
1007*38fd1498Szrj bool
1008*38fd1498Szrj empty() const _GLIBCXX_NOEXCEPT
1009*38fd1498Szrj { return _M_impl._M_node_count == 0; }
1010*38fd1498Szrj
1011*38fd1498Szrj size_type
1012*38fd1498Szrj size() const _GLIBCXX_NOEXCEPT
1013*38fd1498Szrj { return _M_impl._M_node_count; }
1014*38fd1498Szrj
1015*38fd1498Szrj size_type
1016*38fd1498Szrj max_size() const _GLIBCXX_NOEXCEPT
1017*38fd1498Szrj { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
1018*38fd1498Szrj
1019*38fd1498Szrj void
1020*38fd1498Szrj swap(_Rb_tree& __t)
1021*38fd1498Szrj _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value);
1022*38fd1498Szrj
1023*38fd1498Szrj // Insert/erase.
1024*38fd1498Szrj #if __cplusplus >= 201103L
1025*38fd1498Szrj template<typename _Arg>
1026*38fd1498Szrj pair<iterator, bool>
1027*38fd1498Szrj _M_insert_unique(_Arg&& __x);
1028*38fd1498Szrj
1029*38fd1498Szrj template<typename _Arg>
1030*38fd1498Szrj iterator
1031*38fd1498Szrj _M_insert_equal(_Arg&& __x);
1032*38fd1498Szrj
1033*38fd1498Szrj template<typename _Arg, typename _NodeGen>
1034*38fd1498Szrj iterator
1035*38fd1498Szrj _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1036*38fd1498Szrj
1037*38fd1498Szrj template<typename _Arg>
1038*38fd1498Szrj iterator
1039*38fd1498Szrj _M_insert_unique_(const_iterator __pos, _Arg&& __x)
1040*38fd1498Szrj {
1041*38fd1498Szrj _Alloc_node __an(*this);
1042*38fd1498Szrj return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
1043*38fd1498Szrj }
1044*38fd1498Szrj
1045*38fd1498Szrj template<typename _Arg, typename _NodeGen>
1046*38fd1498Szrj iterator
1047*38fd1498Szrj _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1048*38fd1498Szrj
1049*38fd1498Szrj template<typename _Arg>
1050*38fd1498Szrj iterator
1051*38fd1498Szrj _M_insert_equal_(const_iterator __pos, _Arg&& __x)
1052*38fd1498Szrj {
1053*38fd1498Szrj _Alloc_node __an(*this);
1054*38fd1498Szrj return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
1055*38fd1498Szrj }
1056*38fd1498Szrj
1057*38fd1498Szrj template<typename... _Args>
1058*38fd1498Szrj pair<iterator, bool>
1059*38fd1498Szrj _M_emplace_unique(_Args&&... __args);
1060*38fd1498Szrj
1061*38fd1498Szrj template<typename... _Args>
1062*38fd1498Szrj iterator
1063*38fd1498Szrj _M_emplace_equal(_Args&&... __args);
1064*38fd1498Szrj
1065*38fd1498Szrj template<typename... _Args>
1066*38fd1498Szrj iterator
1067*38fd1498Szrj _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
1068*38fd1498Szrj
1069*38fd1498Szrj template<typename... _Args>
1070*38fd1498Szrj iterator
1071*38fd1498Szrj _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
1072*38fd1498Szrj #else
1073*38fd1498Szrj pair<iterator, bool>
1074*38fd1498Szrj _M_insert_unique(const value_type& __x);
1075*38fd1498Szrj
1076*38fd1498Szrj iterator
1077*38fd1498Szrj _M_insert_equal(const value_type& __x);
1078*38fd1498Szrj
1079*38fd1498Szrj template<typename _NodeGen>
1080*38fd1498Szrj iterator
1081*38fd1498Szrj _M_insert_unique_(const_iterator __pos, const value_type& __x,
1082*38fd1498Szrj _NodeGen&);
1083*38fd1498Szrj
1084*38fd1498Szrj iterator
1085*38fd1498Szrj _M_insert_unique_(const_iterator __pos, const value_type& __x)
1086*38fd1498Szrj {
1087*38fd1498Szrj _Alloc_node __an(*this);
1088*38fd1498Szrj return _M_insert_unique_(__pos, __x, __an);
1089*38fd1498Szrj }
1090*38fd1498Szrj
1091*38fd1498Szrj template<typename _NodeGen>
1092*38fd1498Szrj iterator
1093*38fd1498Szrj _M_insert_equal_(const_iterator __pos, const value_type& __x,
1094*38fd1498Szrj _NodeGen&);
1095*38fd1498Szrj iterator
1096*38fd1498Szrj _M_insert_equal_(const_iterator __pos, const value_type& __x)
1097*38fd1498Szrj {
1098*38fd1498Szrj _Alloc_node __an(*this);
1099*38fd1498Szrj return _M_insert_equal_(__pos, __x, __an);
1100*38fd1498Szrj }
1101*38fd1498Szrj #endif
1102*38fd1498Szrj
1103*38fd1498Szrj template<typename _InputIterator>
1104*38fd1498Szrj void
1105*38fd1498Szrj _M_insert_unique(_InputIterator __first, _InputIterator __last);
1106*38fd1498Szrj
1107*38fd1498Szrj template<typename _InputIterator>
1108*38fd1498Szrj void
1109*38fd1498Szrj _M_insert_equal(_InputIterator __first, _InputIterator __last);
1110*38fd1498Szrj
1111*38fd1498Szrj private:
1112*38fd1498Szrj void
1113*38fd1498Szrj _M_erase_aux(const_iterator __position);
1114*38fd1498Szrj
1115*38fd1498Szrj void
1116*38fd1498Szrj _M_erase_aux(const_iterator __first, const_iterator __last);
1117*38fd1498Szrj
1118*38fd1498Szrj public:
1119*38fd1498Szrj #if __cplusplus >= 201103L
1120*38fd1498Szrj // _GLIBCXX_RESOLVE_LIB_DEFECTS
1121*38fd1498Szrj // DR 130. Associative erase should return an iterator.
1122*38fd1498Szrj _GLIBCXX_ABI_TAG_CXX11
1123*38fd1498Szrj iterator
1124*38fd1498Szrj erase(const_iterator __position)
1125*38fd1498Szrj {
1126*38fd1498Szrj __glibcxx_assert(__position != end());
1127*38fd1498Szrj const_iterator __result = __position;
1128*38fd1498Szrj ++__result;
1129*38fd1498Szrj _M_erase_aux(__position);
1130*38fd1498Szrj return __result._M_const_cast();
1131*38fd1498Szrj }
1132*38fd1498Szrj
1133*38fd1498Szrj // LWG 2059.
1134*38fd1498Szrj _GLIBCXX_ABI_TAG_CXX11
1135*38fd1498Szrj iterator
1136*38fd1498Szrj erase(iterator __position)
1137*38fd1498Szrj {
1138*38fd1498Szrj __glibcxx_assert(__position != end());
1139*38fd1498Szrj iterator __result = __position;
1140*38fd1498Szrj ++__result;
1141*38fd1498Szrj _M_erase_aux(__position);
1142*38fd1498Szrj return __result;
1143*38fd1498Szrj }
1144*38fd1498Szrj #else
1145*38fd1498Szrj void
1146*38fd1498Szrj erase(iterator __position)
1147*38fd1498Szrj {
1148*38fd1498Szrj __glibcxx_assert(__position != end());
1149*38fd1498Szrj _M_erase_aux(__position);
1150*38fd1498Szrj }
1151*38fd1498Szrj
1152*38fd1498Szrj void
1153*38fd1498Szrj erase(const_iterator __position)
1154*38fd1498Szrj {
1155*38fd1498Szrj __glibcxx_assert(__position != end());
1156*38fd1498Szrj _M_erase_aux(__position);
1157*38fd1498Szrj }
1158*38fd1498Szrj #endif
1159*38fd1498Szrj size_type
1160*38fd1498Szrj erase(const key_type& __x);
1161*38fd1498Szrj
1162*38fd1498Szrj #if __cplusplus >= 201103L
1163*38fd1498Szrj // _GLIBCXX_RESOLVE_LIB_DEFECTS
1164*38fd1498Szrj // DR 130. Associative erase should return an iterator.
1165*38fd1498Szrj _GLIBCXX_ABI_TAG_CXX11
1166*38fd1498Szrj iterator
1167*38fd1498Szrj erase(const_iterator __first, const_iterator __last)
1168*38fd1498Szrj {
1169*38fd1498Szrj _M_erase_aux(__first, __last);
1170*38fd1498Szrj return __last._M_const_cast();
1171*38fd1498Szrj }
1172*38fd1498Szrj #else
1173*38fd1498Szrj void
1174*38fd1498Szrj erase(iterator __first, iterator __last)
1175*38fd1498Szrj { _M_erase_aux(__first, __last); }
1176*38fd1498Szrj
1177*38fd1498Szrj void
1178*38fd1498Szrj erase(const_iterator __first, const_iterator __last)
1179*38fd1498Szrj { _M_erase_aux(__first, __last); }
1180*38fd1498Szrj #endif
1181*38fd1498Szrj void
1182*38fd1498Szrj erase(const key_type* __first, const key_type* __last);
1183*38fd1498Szrj
1184*38fd1498Szrj void
1185*38fd1498Szrj clear() _GLIBCXX_NOEXCEPT
1186*38fd1498Szrj {
1187*38fd1498Szrj _M_erase(_M_begin());
1188*38fd1498Szrj _M_impl._M_reset();
1189*38fd1498Szrj }
1190*38fd1498Szrj
1191*38fd1498Szrj // Set operations.
1192*38fd1498Szrj iterator
1193*38fd1498Szrj find(const key_type& __k);
1194*38fd1498Szrj
1195*38fd1498Szrj const_iterator
1196*38fd1498Szrj find(const key_type& __k) const;
1197*38fd1498Szrj
1198*38fd1498Szrj size_type
1199*38fd1498Szrj count(const key_type& __k) const;
1200*38fd1498Szrj
1201*38fd1498Szrj iterator
1202*38fd1498Szrj lower_bound(const key_type& __k)
1203*38fd1498Szrj { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1204*38fd1498Szrj
1205*38fd1498Szrj const_iterator
1206*38fd1498Szrj lower_bound(const key_type& __k) const
1207*38fd1498Szrj { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1208*38fd1498Szrj
1209*38fd1498Szrj iterator
1210*38fd1498Szrj upper_bound(const key_type& __k)
1211*38fd1498Szrj { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1212*38fd1498Szrj
1213*38fd1498Szrj const_iterator
1214*38fd1498Szrj upper_bound(const key_type& __k) const
1215*38fd1498Szrj { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1216*38fd1498Szrj
1217*38fd1498Szrj pair<iterator, iterator>
1218*38fd1498Szrj equal_range(const key_type& __k);
1219*38fd1498Szrj
1220*38fd1498Szrj pair<const_iterator, const_iterator>
1221*38fd1498Szrj equal_range(const key_type& __k) const;
1222*38fd1498Szrj
1223*38fd1498Szrj #if __cplusplus > 201103L
1224*38fd1498Szrj template<typename _Kt,
1225*38fd1498Szrj typename _Req =
1226*38fd1498Szrj typename __has_is_transparent<_Compare, _Kt>::type>
1227*38fd1498Szrj iterator
1228*38fd1498Szrj _M_find_tr(const _Kt& __k)
1229*38fd1498Szrj {
1230*38fd1498Szrj const _Rb_tree* __const_this = this;
1231*38fd1498Szrj return __const_this->_M_find_tr(__k)._M_const_cast();
1232*38fd1498Szrj }
1233*38fd1498Szrj
1234*38fd1498Szrj template<typename _Kt,
1235*38fd1498Szrj typename _Req =
1236*38fd1498Szrj typename __has_is_transparent<_Compare, _Kt>::type>
1237*38fd1498Szrj const_iterator
1238*38fd1498Szrj _M_find_tr(const _Kt& __k) const
1239*38fd1498Szrj {
1240*38fd1498Szrj auto __j = _M_lower_bound_tr(__k);
1241*38fd1498Szrj if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
1242*38fd1498Szrj __j = end();
1243*38fd1498Szrj return __j;
1244*38fd1498Szrj }
1245*38fd1498Szrj
1246*38fd1498Szrj template<typename _Kt,
1247*38fd1498Szrj typename _Req =
1248*38fd1498Szrj typename __has_is_transparent<_Compare, _Kt>::type>
1249*38fd1498Szrj size_type
1250*38fd1498Szrj _M_count_tr(const _Kt& __k) const
1251*38fd1498Szrj {
1252*38fd1498Szrj auto __p = _M_equal_range_tr(__k);
1253*38fd1498Szrj return std::distance(__p.first, __p.second);
1254*38fd1498Szrj }
1255*38fd1498Szrj
1256*38fd1498Szrj template<typename _Kt,
1257*38fd1498Szrj typename _Req =
1258*38fd1498Szrj typename __has_is_transparent<_Compare, _Kt>::type>
1259*38fd1498Szrj iterator
1260*38fd1498Szrj _M_lower_bound_tr(const _Kt& __k)
1261*38fd1498Szrj {
1262*38fd1498Szrj const _Rb_tree* __const_this = this;
1263*38fd1498Szrj return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
1264*38fd1498Szrj }
1265*38fd1498Szrj
1266*38fd1498Szrj template<typename _Kt,
1267*38fd1498Szrj typename _Req =
1268*38fd1498Szrj typename __has_is_transparent<_Compare, _Kt>::type>
1269*38fd1498Szrj const_iterator
1270*38fd1498Szrj _M_lower_bound_tr(const _Kt& __k) const
1271*38fd1498Szrj {
1272*38fd1498Szrj auto __x = _M_begin();
1273*38fd1498Szrj auto __y = _M_end();
1274*38fd1498Szrj while (__x != 0)
1275*38fd1498Szrj if (!_M_impl._M_key_compare(_S_key(__x), __k))
1276*38fd1498Szrj {
1277*38fd1498Szrj __y = __x;
1278*38fd1498Szrj __x = _S_left(__x);
1279*38fd1498Szrj }
1280*38fd1498Szrj else
1281*38fd1498Szrj __x = _S_right(__x);
1282*38fd1498Szrj return const_iterator(__y);
1283*38fd1498Szrj }
1284*38fd1498Szrj
1285*38fd1498Szrj template<typename _Kt,
1286*38fd1498Szrj typename _Req =
1287*38fd1498Szrj typename __has_is_transparent<_Compare, _Kt>::type>
1288*38fd1498Szrj iterator
1289*38fd1498Szrj _M_upper_bound_tr(const _Kt& __k)
1290*38fd1498Szrj {
1291*38fd1498Szrj const _Rb_tree* __const_this = this;
1292*38fd1498Szrj return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
1293*38fd1498Szrj }
1294*38fd1498Szrj
1295*38fd1498Szrj template<typename _Kt,
1296*38fd1498Szrj typename _Req =
1297*38fd1498Szrj typename __has_is_transparent<_Compare, _Kt>::type>
1298*38fd1498Szrj const_iterator
1299*38fd1498Szrj _M_upper_bound_tr(const _Kt& __k) const
1300*38fd1498Szrj {
1301*38fd1498Szrj auto __x = _M_begin();
1302*38fd1498Szrj auto __y = _M_end();
1303*38fd1498Szrj while (__x != 0)
1304*38fd1498Szrj if (_M_impl._M_key_compare(__k, _S_key(__x)))
1305*38fd1498Szrj {
1306*38fd1498Szrj __y = __x;
1307*38fd1498Szrj __x = _S_left(__x);
1308*38fd1498Szrj }
1309*38fd1498Szrj else
1310*38fd1498Szrj __x = _S_right(__x);
1311*38fd1498Szrj return const_iterator(__y);
1312*38fd1498Szrj }
1313*38fd1498Szrj
1314*38fd1498Szrj template<typename _Kt,
1315*38fd1498Szrj typename _Req =
1316*38fd1498Szrj typename __has_is_transparent<_Compare, _Kt>::type>
1317*38fd1498Szrj pair<iterator, iterator>
1318*38fd1498Szrj _M_equal_range_tr(const _Kt& __k)
1319*38fd1498Szrj {
1320*38fd1498Szrj const _Rb_tree* __const_this = this;
1321*38fd1498Szrj auto __ret = __const_this->_M_equal_range_tr(__k);
1322*38fd1498Szrj return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
1323*38fd1498Szrj }
1324*38fd1498Szrj
1325*38fd1498Szrj template<typename _Kt,
1326*38fd1498Szrj typename _Req =
1327*38fd1498Szrj typename __has_is_transparent<_Compare, _Kt>::type>
1328*38fd1498Szrj pair<const_iterator, const_iterator>
1329*38fd1498Szrj _M_equal_range_tr(const _Kt& __k) const
1330*38fd1498Szrj {
1331*38fd1498Szrj auto __low = _M_lower_bound_tr(__k);
1332*38fd1498Szrj auto __high = __low;
1333*38fd1498Szrj auto& __cmp = _M_impl._M_key_compare;
1334*38fd1498Szrj while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
1335*38fd1498Szrj ++__high;
1336*38fd1498Szrj return { __low, __high };
1337*38fd1498Szrj }
1338*38fd1498Szrj #endif
1339*38fd1498Szrj
1340*38fd1498Szrj // Debugging.
1341*38fd1498Szrj bool
1342*38fd1498Szrj __rb_verify() const;
1343*38fd1498Szrj
1344*38fd1498Szrj #if __cplusplus >= 201103L
1345*38fd1498Szrj _Rb_tree&
1346*38fd1498Szrj operator=(_Rb_tree&&)
1347*38fd1498Szrj noexcept(_Alloc_traits::_S_nothrow_move()
1348*38fd1498Szrj && is_nothrow_move_assignable<_Compare>::value);
1349*38fd1498Szrj
1350*38fd1498Szrj template<typename _Iterator>
1351*38fd1498Szrj void
1352*38fd1498Szrj _M_assign_unique(_Iterator, _Iterator);
1353*38fd1498Szrj
1354*38fd1498Szrj template<typename _Iterator>
1355*38fd1498Szrj void
1356*38fd1498Szrj _M_assign_equal(_Iterator, _Iterator);
1357*38fd1498Szrj
1358*38fd1498Szrj private:
1359*38fd1498Szrj // Move elements from container with equal allocator.
1360*38fd1498Szrj void
1361*38fd1498Szrj _M_move_data(_Rb_tree& __x, std::true_type)
1362*38fd1498Szrj { _M_impl._M_move_data(__x._M_impl); }
1363*38fd1498Szrj
1364*38fd1498Szrj // Move elements from container with possibly non-equal allocator,
1365*38fd1498Szrj // which might result in a copy not a move.
1366*38fd1498Szrj void
1367*38fd1498Szrj _M_move_data(_Rb_tree&, std::false_type);
1368*38fd1498Szrj
1369*38fd1498Szrj // Move assignment from container with equal allocator.
1370*38fd1498Szrj void
1371*38fd1498Szrj _M_move_assign(_Rb_tree&, std::true_type);
1372*38fd1498Szrj
1373*38fd1498Szrj // Move assignment from container with possibly non-equal allocator,
1374*38fd1498Szrj // which might result in a copy not a move.
1375*38fd1498Szrj void
1376*38fd1498Szrj _M_move_assign(_Rb_tree&, std::false_type);
1377*38fd1498Szrj #endif
1378*38fd1498Szrj
1379*38fd1498Szrj #if __cplusplus > 201402L
1380*38fd1498Szrj public:
1381*38fd1498Szrj /// Re-insert an extracted node.
1382*38fd1498Szrj insert_return_type
1383*38fd1498Szrj _M_reinsert_node_unique(node_type&& __nh)
1384*38fd1498Szrj {
1385*38fd1498Szrj insert_return_type __ret;
1386*38fd1498Szrj if (__nh.empty())
1387*38fd1498Szrj __ret.position = end();
1388*38fd1498Szrj else
1389*38fd1498Szrj {
1390*38fd1498Szrj __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1391*38fd1498Szrj
1392*38fd1498Szrj auto __res = _M_get_insert_unique_pos(__nh._M_key());
1393*38fd1498Szrj if (__res.second)
1394*38fd1498Szrj {
1395*38fd1498Szrj __ret.position
1396*38fd1498Szrj = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1397*38fd1498Szrj __nh._M_ptr = nullptr;
1398*38fd1498Szrj __ret.inserted = true;
1399*38fd1498Szrj }
1400*38fd1498Szrj else
1401*38fd1498Szrj {
1402*38fd1498Szrj __ret.node = std::move(__nh);
1403*38fd1498Szrj __ret.position = iterator(__res.first);
1404*38fd1498Szrj __ret.inserted = false;
1405*38fd1498Szrj }
1406*38fd1498Szrj }
1407*38fd1498Szrj return __ret;
1408*38fd1498Szrj }
1409*38fd1498Szrj
1410*38fd1498Szrj /// Re-insert an extracted node.
1411*38fd1498Szrj iterator
1412*38fd1498Szrj _M_reinsert_node_equal(node_type&& __nh)
1413*38fd1498Szrj {
1414*38fd1498Szrj iterator __ret;
1415*38fd1498Szrj if (__nh.empty())
1416*38fd1498Szrj __ret = end();
1417*38fd1498Szrj else
1418*38fd1498Szrj {
1419*38fd1498Szrj __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1420*38fd1498Szrj auto __res = _M_get_insert_equal_pos(__nh._M_key());
1421*38fd1498Szrj if (__res.second)
1422*38fd1498Szrj __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1423*38fd1498Szrj else
1424*38fd1498Szrj __ret = _M_insert_equal_lower_node(__nh._M_ptr);
1425*38fd1498Szrj __nh._M_ptr = nullptr;
1426*38fd1498Szrj }
1427*38fd1498Szrj return __ret;
1428*38fd1498Szrj }
1429*38fd1498Szrj
1430*38fd1498Szrj /// Re-insert an extracted node.
1431*38fd1498Szrj iterator
1432*38fd1498Szrj _M_reinsert_node_hint_unique(const_iterator __hint, node_type&& __nh)
1433*38fd1498Szrj {
1434*38fd1498Szrj iterator __ret;
1435*38fd1498Szrj if (__nh.empty())
1436*38fd1498Szrj __ret = end();
1437*38fd1498Szrj else
1438*38fd1498Szrj {
1439*38fd1498Szrj __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1440*38fd1498Szrj auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key());
1441*38fd1498Szrj if (__res.second)
1442*38fd1498Szrj {
1443*38fd1498Szrj __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1444*38fd1498Szrj __nh._M_ptr = nullptr;
1445*38fd1498Szrj }
1446*38fd1498Szrj else
1447*38fd1498Szrj __ret = iterator(__res.first);
1448*38fd1498Szrj }
1449*38fd1498Szrj return __ret;
1450*38fd1498Szrj }
1451*38fd1498Szrj
1452*38fd1498Szrj /// Re-insert an extracted node.
1453*38fd1498Szrj iterator
1454*38fd1498Szrj _M_reinsert_node_hint_equal(const_iterator __hint, node_type&& __nh)
1455*38fd1498Szrj {
1456*38fd1498Szrj iterator __ret;
1457*38fd1498Szrj if (__nh.empty())
1458*38fd1498Szrj __ret = end();
1459*38fd1498Szrj else
1460*38fd1498Szrj {
1461*38fd1498Szrj __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1462*38fd1498Szrj auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key());
1463*38fd1498Szrj if (__res.second)
1464*38fd1498Szrj __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1465*38fd1498Szrj else
1466*38fd1498Szrj __ret = _M_insert_equal_lower_node(__nh._M_ptr);
1467*38fd1498Szrj __nh._M_ptr = nullptr;
1468*38fd1498Szrj }
1469*38fd1498Szrj return __ret;
1470*38fd1498Szrj }
1471*38fd1498Szrj
1472*38fd1498Szrj /// Extract a node.
1473*38fd1498Szrj node_type
1474*38fd1498Szrj extract(const_iterator __pos)
1475*38fd1498Szrj {
1476*38fd1498Szrj auto __ptr = _Rb_tree_rebalance_for_erase(
1477*38fd1498Szrj __pos._M_const_cast()._M_node, _M_impl._M_header);
1478*38fd1498Szrj --_M_impl._M_node_count;
1479*38fd1498Szrj return { static_cast<_Link_type>(__ptr), _M_get_Node_allocator() };
1480*38fd1498Szrj }
1481*38fd1498Szrj
1482*38fd1498Szrj /// Extract a node.
1483*38fd1498Szrj node_type
1484*38fd1498Szrj extract(const key_type& __k)
1485*38fd1498Szrj {
1486*38fd1498Szrj node_type __nh;
1487*38fd1498Szrj auto __pos = find(__k);
1488*38fd1498Szrj if (__pos != end())
1489*38fd1498Szrj __nh = extract(const_iterator(__pos));
1490*38fd1498Szrj return __nh;
1491*38fd1498Szrj }
1492*38fd1498Szrj
1493*38fd1498Szrj template<typename _Compare2>
1494*38fd1498Szrj using _Compatible_tree
1495*38fd1498Szrj = _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>;
1496*38fd1498Szrj
1497*38fd1498Szrj template<typename, typename>
1498*38fd1498Szrj friend class _Rb_tree_merge_helper;
1499*38fd1498Szrj
1500*38fd1498Szrj /// Merge from a compatible container into one with unique keys.
1501*38fd1498Szrj template<typename _Compare2>
1502*38fd1498Szrj void
1503*38fd1498Szrj _M_merge_unique(_Compatible_tree<_Compare2>& __src) noexcept
1504*38fd1498Szrj {
1505*38fd1498Szrj using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
1506*38fd1498Szrj for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1507*38fd1498Szrj {
1508*38fd1498Szrj auto __pos = __i++;
1509*38fd1498Szrj auto __res = _M_get_insert_unique_pos(_KeyOfValue()(*__pos));
1510*38fd1498Szrj if (__res.second)
1511*38fd1498Szrj {
1512*38fd1498Szrj auto& __src_impl = _Merge_helper::_S_get_impl(__src);
1513*38fd1498Szrj auto __ptr = _Rb_tree_rebalance_for_erase(
1514*38fd1498Szrj __pos._M_node, __src_impl._M_header);
1515*38fd1498Szrj --__src_impl._M_node_count;
1516*38fd1498Szrj _M_insert_node(__res.first, __res.second,
1517*38fd1498Szrj static_cast<_Link_type>(__ptr));
1518*38fd1498Szrj }
1519*38fd1498Szrj }
1520*38fd1498Szrj }
1521*38fd1498Szrj
1522*38fd1498Szrj /// Merge from a compatible container into one with equivalent keys.
1523*38fd1498Szrj template<typename _Compare2>
1524*38fd1498Szrj void
1525*38fd1498Szrj _M_merge_equal(_Compatible_tree<_Compare2>& __src) noexcept
1526*38fd1498Szrj {
1527*38fd1498Szrj using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
1528*38fd1498Szrj for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1529*38fd1498Szrj {
1530*38fd1498Szrj auto __pos = __i++;
1531*38fd1498Szrj auto __res = _M_get_insert_equal_pos(_KeyOfValue()(*__pos));
1532*38fd1498Szrj if (__res.second)
1533*38fd1498Szrj {
1534*38fd1498Szrj auto& __src_impl = _Merge_helper::_S_get_impl(__src);
1535*38fd1498Szrj auto __ptr = _Rb_tree_rebalance_for_erase(
1536*38fd1498Szrj __pos._M_node, __src_impl._M_header);
1537*38fd1498Szrj --__src_impl._M_node_count;
1538*38fd1498Szrj _M_insert_node(__res.first, __res.second,
1539*38fd1498Szrj static_cast<_Link_type>(__ptr));
1540*38fd1498Szrj }
1541*38fd1498Szrj }
1542*38fd1498Szrj }
1543*38fd1498Szrj #endif // C++17
1544*38fd1498Szrj };
1545*38fd1498Szrj
1546*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1547*38fd1498Szrj typename _Compare, typename _Alloc>
1548*38fd1498Szrj inline bool
1549*38fd1498Szrj operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1550*38fd1498Szrj const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1551*38fd1498Szrj {
1552*38fd1498Szrj return __x.size() == __y.size()
1553*38fd1498Szrj && std::equal(__x.begin(), __x.end(), __y.begin());
1554*38fd1498Szrj }
1555*38fd1498Szrj
1556*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1557*38fd1498Szrj typename _Compare, typename _Alloc>
1558*38fd1498Szrj inline bool
1559*38fd1498Szrj operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1560*38fd1498Szrj const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1561*38fd1498Szrj {
1562*38fd1498Szrj return std::lexicographical_compare(__x.begin(), __x.end(),
1563*38fd1498Szrj __y.begin(), __y.end());
1564*38fd1498Szrj }
1565*38fd1498Szrj
1566*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1567*38fd1498Szrj typename _Compare, typename _Alloc>
1568*38fd1498Szrj inline bool
1569*38fd1498Szrj operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1570*38fd1498Szrj const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1571*38fd1498Szrj { return !(__x == __y); }
1572*38fd1498Szrj
1573*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1574*38fd1498Szrj typename _Compare, typename _Alloc>
1575*38fd1498Szrj inline bool
1576*38fd1498Szrj operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1577*38fd1498Szrj const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1578*38fd1498Szrj { return __y < __x; }
1579*38fd1498Szrj
1580*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1581*38fd1498Szrj typename _Compare, typename _Alloc>
1582*38fd1498Szrj inline bool
1583*38fd1498Szrj operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1584*38fd1498Szrj const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1585*38fd1498Szrj { return !(__y < __x); }
1586*38fd1498Szrj
1587*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1588*38fd1498Szrj typename _Compare, typename _Alloc>
1589*38fd1498Szrj inline bool
1590*38fd1498Szrj operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1591*38fd1498Szrj const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1592*38fd1498Szrj { return !(__x < __y); }
1593*38fd1498Szrj
1594*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1595*38fd1498Szrj typename _Compare, typename _Alloc>
1596*38fd1498Szrj inline void
1597*38fd1498Szrj swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1598*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1599*38fd1498Szrj { __x.swap(__y); }
1600*38fd1498Szrj
1601*38fd1498Szrj #if __cplusplus >= 201103L
1602*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1603*38fd1498Szrj typename _Compare, typename _Alloc>
1604*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1605*38fd1498Szrj _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
1606*38fd1498Szrj : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
1607*38fd1498Szrj {
1608*38fd1498Szrj using __eq = typename _Alloc_traits::is_always_equal;
1609*38fd1498Szrj if (__x._M_root() != nullptr)
1610*38fd1498Szrj _M_move_data(__x, __eq());
1611*38fd1498Szrj }
1612*38fd1498Szrj
1613*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1614*38fd1498Szrj typename _Compare, typename _Alloc>
1615*38fd1498Szrj void
1616*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1617*38fd1498Szrj _M_move_data(_Rb_tree& __x, std::false_type)
1618*38fd1498Szrj {
1619*38fd1498Szrj if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1620*38fd1498Szrj _M_move_data(__x, std::true_type());
1621*38fd1498Szrj else
1622*38fd1498Szrj {
1623*38fd1498Szrj _Alloc_node __an(*this);
1624*38fd1498Szrj auto __lbd =
1625*38fd1498Szrj [&__an](const value_type& __cval)
1626*38fd1498Szrj {
1627*38fd1498Szrj auto& __val = const_cast<value_type&>(__cval);
1628*38fd1498Szrj return __an(std::move_if_noexcept(__val));
1629*38fd1498Szrj };
1630*38fd1498Szrj _M_root() = _M_copy(__x, __lbd);
1631*38fd1498Szrj }
1632*38fd1498Szrj }
1633*38fd1498Szrj
1634*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1635*38fd1498Szrj typename _Compare, typename _Alloc>
1636*38fd1498Szrj inline void
1637*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1638*38fd1498Szrj _M_move_assign(_Rb_tree& __x, true_type)
1639*38fd1498Szrj {
1640*38fd1498Szrj clear();
1641*38fd1498Szrj if (__x._M_root() != nullptr)
1642*38fd1498Szrj _M_move_data(__x, std::true_type());
1643*38fd1498Szrj std::__alloc_on_move(_M_get_Node_allocator(),
1644*38fd1498Szrj __x._M_get_Node_allocator());
1645*38fd1498Szrj }
1646*38fd1498Szrj
1647*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1648*38fd1498Szrj typename _Compare, typename _Alloc>
1649*38fd1498Szrj void
1650*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1651*38fd1498Szrj _M_move_assign(_Rb_tree& __x, false_type)
1652*38fd1498Szrj {
1653*38fd1498Szrj if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1654*38fd1498Szrj return _M_move_assign(__x, true_type{});
1655*38fd1498Szrj
1656*38fd1498Szrj // Try to move each node reusing existing nodes and copying __x nodes
1657*38fd1498Szrj // structure.
1658*38fd1498Szrj _Reuse_or_alloc_node __roan(*this);
1659*38fd1498Szrj _M_impl._M_reset();
1660*38fd1498Szrj if (__x._M_root() != nullptr)
1661*38fd1498Szrj {
1662*38fd1498Szrj auto __lbd =
1663*38fd1498Szrj [&__roan](const value_type& __cval)
1664*38fd1498Szrj {
1665*38fd1498Szrj auto& __val = const_cast<value_type&>(__cval);
1666*38fd1498Szrj return __roan(std::move_if_noexcept(__val));
1667*38fd1498Szrj };
1668*38fd1498Szrj _M_root() = _M_copy(__x, __lbd);
1669*38fd1498Szrj __x.clear();
1670*38fd1498Szrj }
1671*38fd1498Szrj }
1672*38fd1498Szrj
1673*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1674*38fd1498Szrj typename _Compare, typename _Alloc>
1675*38fd1498Szrj inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1676*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1677*38fd1498Szrj operator=(_Rb_tree&& __x)
1678*38fd1498Szrj noexcept(_Alloc_traits::_S_nothrow_move()
1679*38fd1498Szrj && is_nothrow_move_assignable<_Compare>::value)
1680*38fd1498Szrj {
1681*38fd1498Szrj _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare);
1682*38fd1498Szrj _M_move_assign(__x, __bool_constant<_Alloc_traits::_S_nothrow_move()>());
1683*38fd1498Szrj return *this;
1684*38fd1498Szrj }
1685*38fd1498Szrj
1686*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1687*38fd1498Szrj typename _Compare, typename _Alloc>
1688*38fd1498Szrj template<typename _Iterator>
1689*38fd1498Szrj void
1690*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1691*38fd1498Szrj _M_assign_unique(_Iterator __first, _Iterator __last)
1692*38fd1498Szrj {
1693*38fd1498Szrj _Reuse_or_alloc_node __roan(*this);
1694*38fd1498Szrj _M_impl._M_reset();
1695*38fd1498Szrj for (; __first != __last; ++__first)
1696*38fd1498Szrj _M_insert_unique_(end(), *__first, __roan);
1697*38fd1498Szrj }
1698*38fd1498Szrj
1699*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1700*38fd1498Szrj typename _Compare, typename _Alloc>
1701*38fd1498Szrj template<typename _Iterator>
1702*38fd1498Szrj void
1703*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1704*38fd1498Szrj _M_assign_equal(_Iterator __first, _Iterator __last)
1705*38fd1498Szrj {
1706*38fd1498Szrj _Reuse_or_alloc_node __roan(*this);
1707*38fd1498Szrj _M_impl._M_reset();
1708*38fd1498Szrj for (; __first != __last; ++__first)
1709*38fd1498Szrj _M_insert_equal_(end(), *__first, __roan);
1710*38fd1498Szrj }
1711*38fd1498Szrj #endif
1712*38fd1498Szrj
1713*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1714*38fd1498Szrj typename _Compare, typename _Alloc>
1715*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1716*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1717*38fd1498Szrj operator=(const _Rb_tree& __x)
1718*38fd1498Szrj {
1719*38fd1498Szrj if (this != &__x)
1720*38fd1498Szrj {
1721*38fd1498Szrj // Note that _Key may be a constant type.
1722*38fd1498Szrj #if __cplusplus >= 201103L
1723*38fd1498Szrj if (_Alloc_traits::_S_propagate_on_copy_assign())
1724*38fd1498Szrj {
1725*38fd1498Szrj auto& __this_alloc = this->_M_get_Node_allocator();
1726*38fd1498Szrj auto& __that_alloc = __x._M_get_Node_allocator();
1727*38fd1498Szrj if (!_Alloc_traits::_S_always_equal()
1728*38fd1498Szrj && __this_alloc != __that_alloc)
1729*38fd1498Szrj {
1730*38fd1498Szrj // Replacement allocator cannot free existing storage, we need
1731*38fd1498Szrj // to erase nodes first.
1732*38fd1498Szrj clear();
1733*38fd1498Szrj std::__alloc_on_copy(__this_alloc, __that_alloc);
1734*38fd1498Szrj }
1735*38fd1498Szrj }
1736*38fd1498Szrj #endif
1737*38fd1498Szrj
1738*38fd1498Szrj _Reuse_or_alloc_node __roan(*this);
1739*38fd1498Szrj _M_impl._M_reset();
1740*38fd1498Szrj _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1741*38fd1498Szrj if (__x._M_root() != 0)
1742*38fd1498Szrj _M_root() = _M_copy(__x, __roan);
1743*38fd1498Szrj }
1744*38fd1498Szrj
1745*38fd1498Szrj return *this;
1746*38fd1498Szrj }
1747*38fd1498Szrj
1748*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1749*38fd1498Szrj typename _Compare, typename _Alloc>
1750*38fd1498Szrj #if __cplusplus >= 201103L
1751*38fd1498Szrj template<typename _Arg, typename _NodeGen>
1752*38fd1498Szrj #else
1753*38fd1498Szrj template<typename _NodeGen>
1754*38fd1498Szrj #endif
1755*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1756*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1757*38fd1498Szrj _M_insert_(_Base_ptr __x, _Base_ptr __p,
1758*38fd1498Szrj #if __cplusplus >= 201103L
1759*38fd1498Szrj _Arg&& __v,
1760*38fd1498Szrj #else
1761*38fd1498Szrj const _Val& __v,
1762*38fd1498Szrj #endif
1763*38fd1498Szrj _NodeGen& __node_gen)
1764*38fd1498Szrj {
1765*38fd1498Szrj bool __insert_left = (__x != 0 || __p == _M_end()
1766*38fd1498Szrj || _M_impl._M_key_compare(_KeyOfValue()(__v),
1767*38fd1498Szrj _S_key(__p)));
1768*38fd1498Szrj
1769*38fd1498Szrj _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
1770*38fd1498Szrj
1771*38fd1498Szrj _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1772*38fd1498Szrj this->_M_impl._M_header);
1773*38fd1498Szrj ++_M_impl._M_node_count;
1774*38fd1498Szrj return iterator(__z);
1775*38fd1498Szrj }
1776*38fd1498Szrj
1777*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1778*38fd1498Szrj typename _Compare, typename _Alloc>
1779*38fd1498Szrj #if __cplusplus >= 201103L
1780*38fd1498Szrj template<typename _Arg>
1781*38fd1498Szrj #endif
1782*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1783*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1784*38fd1498Szrj #if __cplusplus >= 201103L
1785*38fd1498Szrj _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1786*38fd1498Szrj #else
1787*38fd1498Szrj _M_insert_lower(_Base_ptr __p, const _Val& __v)
1788*38fd1498Szrj #endif
1789*38fd1498Szrj {
1790*38fd1498Szrj bool __insert_left = (__p == _M_end()
1791*38fd1498Szrj || !_M_impl._M_key_compare(_S_key(__p),
1792*38fd1498Szrj _KeyOfValue()(__v)));
1793*38fd1498Szrj
1794*38fd1498Szrj _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1795*38fd1498Szrj
1796*38fd1498Szrj _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1797*38fd1498Szrj this->_M_impl._M_header);
1798*38fd1498Szrj ++_M_impl._M_node_count;
1799*38fd1498Szrj return iterator(__z);
1800*38fd1498Szrj }
1801*38fd1498Szrj
1802*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1803*38fd1498Szrj typename _Compare, typename _Alloc>
1804*38fd1498Szrj #if __cplusplus >= 201103L
1805*38fd1498Szrj template<typename _Arg>
1806*38fd1498Szrj #endif
1807*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1808*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1809*38fd1498Szrj #if __cplusplus >= 201103L
1810*38fd1498Szrj _M_insert_equal_lower(_Arg&& __v)
1811*38fd1498Szrj #else
1812*38fd1498Szrj _M_insert_equal_lower(const _Val& __v)
1813*38fd1498Szrj #endif
1814*38fd1498Szrj {
1815*38fd1498Szrj _Link_type __x = _M_begin();
1816*38fd1498Szrj _Base_ptr __y = _M_end();
1817*38fd1498Szrj while (__x != 0)
1818*38fd1498Szrj {
1819*38fd1498Szrj __y = __x;
1820*38fd1498Szrj __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1821*38fd1498Szrj _S_left(__x) : _S_right(__x);
1822*38fd1498Szrj }
1823*38fd1498Szrj return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1824*38fd1498Szrj }
1825*38fd1498Szrj
1826*38fd1498Szrj template<typename _Key, typename _Val, typename _KoV,
1827*38fd1498Szrj typename _Compare, typename _Alloc>
1828*38fd1498Szrj template<typename _NodeGen>
1829*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1830*38fd1498Szrj _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1831*38fd1498Szrj _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
1832*38fd1498Szrj {
1833*38fd1498Szrj // Structural copy. __x and __p must be non-null.
1834*38fd1498Szrj _Link_type __top = _M_clone_node(__x, __node_gen);
1835*38fd1498Szrj __top->_M_parent = __p;
1836*38fd1498Szrj
1837*38fd1498Szrj __try
1838*38fd1498Szrj {
1839*38fd1498Szrj if (__x->_M_right)
1840*38fd1498Szrj __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
1841*38fd1498Szrj __p = __top;
1842*38fd1498Szrj __x = _S_left(__x);
1843*38fd1498Szrj
1844*38fd1498Szrj while (__x != 0)
1845*38fd1498Szrj {
1846*38fd1498Szrj _Link_type __y = _M_clone_node(__x, __node_gen);
1847*38fd1498Szrj __p->_M_left = __y;
1848*38fd1498Szrj __y->_M_parent = __p;
1849*38fd1498Szrj if (__x->_M_right)
1850*38fd1498Szrj __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
1851*38fd1498Szrj __p = __y;
1852*38fd1498Szrj __x = _S_left(__x);
1853*38fd1498Szrj }
1854*38fd1498Szrj }
1855*38fd1498Szrj __catch(...)
1856*38fd1498Szrj {
1857*38fd1498Szrj _M_erase(__top);
1858*38fd1498Szrj __throw_exception_again;
1859*38fd1498Szrj }
1860*38fd1498Szrj return __top;
1861*38fd1498Szrj }
1862*38fd1498Szrj
1863*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1864*38fd1498Szrj typename _Compare, typename _Alloc>
1865*38fd1498Szrj void
1866*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1867*38fd1498Szrj _M_erase(_Link_type __x)
1868*38fd1498Szrj {
1869*38fd1498Szrj // Erase without rebalancing.
1870*38fd1498Szrj while (__x != 0)
1871*38fd1498Szrj {
1872*38fd1498Szrj _M_erase(_S_right(__x));
1873*38fd1498Szrj _Link_type __y = _S_left(__x);
1874*38fd1498Szrj _M_drop_node(__x);
1875*38fd1498Szrj __x = __y;
1876*38fd1498Szrj }
1877*38fd1498Szrj }
1878*38fd1498Szrj
1879*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1880*38fd1498Szrj typename _Compare, typename _Alloc>
1881*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue,
1882*38fd1498Szrj _Compare, _Alloc>::iterator
1883*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1884*38fd1498Szrj _M_lower_bound(_Link_type __x, _Base_ptr __y,
1885*38fd1498Szrj const _Key& __k)
1886*38fd1498Szrj {
1887*38fd1498Szrj while (__x != 0)
1888*38fd1498Szrj if (!_M_impl._M_key_compare(_S_key(__x), __k))
1889*38fd1498Szrj __y = __x, __x = _S_left(__x);
1890*38fd1498Szrj else
1891*38fd1498Szrj __x = _S_right(__x);
1892*38fd1498Szrj return iterator(__y);
1893*38fd1498Szrj }
1894*38fd1498Szrj
1895*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1896*38fd1498Szrj typename _Compare, typename _Alloc>
1897*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue,
1898*38fd1498Szrj _Compare, _Alloc>::const_iterator
1899*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1900*38fd1498Szrj _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1901*38fd1498Szrj const _Key& __k) const
1902*38fd1498Szrj {
1903*38fd1498Szrj while (__x != 0)
1904*38fd1498Szrj if (!_M_impl._M_key_compare(_S_key(__x), __k))
1905*38fd1498Szrj __y = __x, __x = _S_left(__x);
1906*38fd1498Szrj else
1907*38fd1498Szrj __x = _S_right(__x);
1908*38fd1498Szrj return const_iterator(__y);
1909*38fd1498Szrj }
1910*38fd1498Szrj
1911*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1912*38fd1498Szrj typename _Compare, typename _Alloc>
1913*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue,
1914*38fd1498Szrj _Compare, _Alloc>::iterator
1915*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1916*38fd1498Szrj _M_upper_bound(_Link_type __x, _Base_ptr __y,
1917*38fd1498Szrj const _Key& __k)
1918*38fd1498Szrj {
1919*38fd1498Szrj while (__x != 0)
1920*38fd1498Szrj if (_M_impl._M_key_compare(__k, _S_key(__x)))
1921*38fd1498Szrj __y = __x, __x = _S_left(__x);
1922*38fd1498Szrj else
1923*38fd1498Szrj __x = _S_right(__x);
1924*38fd1498Szrj return iterator(__y);
1925*38fd1498Szrj }
1926*38fd1498Szrj
1927*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1928*38fd1498Szrj typename _Compare, typename _Alloc>
1929*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue,
1930*38fd1498Szrj _Compare, _Alloc>::const_iterator
1931*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1932*38fd1498Szrj _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1933*38fd1498Szrj const _Key& __k) const
1934*38fd1498Szrj {
1935*38fd1498Szrj while (__x != 0)
1936*38fd1498Szrj if (_M_impl._M_key_compare(__k, _S_key(__x)))
1937*38fd1498Szrj __y = __x, __x = _S_left(__x);
1938*38fd1498Szrj else
1939*38fd1498Szrj __x = _S_right(__x);
1940*38fd1498Szrj return const_iterator(__y);
1941*38fd1498Szrj }
1942*38fd1498Szrj
1943*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1944*38fd1498Szrj typename _Compare, typename _Alloc>
1945*38fd1498Szrj pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1946*38fd1498Szrj _Compare, _Alloc>::iterator,
1947*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue,
1948*38fd1498Szrj _Compare, _Alloc>::iterator>
1949*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1950*38fd1498Szrj equal_range(const _Key& __k)
1951*38fd1498Szrj {
1952*38fd1498Szrj _Link_type __x = _M_begin();
1953*38fd1498Szrj _Base_ptr __y = _M_end();
1954*38fd1498Szrj while (__x != 0)
1955*38fd1498Szrj {
1956*38fd1498Szrj if (_M_impl._M_key_compare(_S_key(__x), __k))
1957*38fd1498Szrj __x = _S_right(__x);
1958*38fd1498Szrj else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1959*38fd1498Szrj __y = __x, __x = _S_left(__x);
1960*38fd1498Szrj else
1961*38fd1498Szrj {
1962*38fd1498Szrj _Link_type __xu(__x);
1963*38fd1498Szrj _Base_ptr __yu(__y);
1964*38fd1498Szrj __y = __x, __x = _S_left(__x);
1965*38fd1498Szrj __xu = _S_right(__xu);
1966*38fd1498Szrj return pair<iterator,
1967*38fd1498Szrj iterator>(_M_lower_bound(__x, __y, __k),
1968*38fd1498Szrj _M_upper_bound(__xu, __yu, __k));
1969*38fd1498Szrj }
1970*38fd1498Szrj }
1971*38fd1498Szrj return pair<iterator, iterator>(iterator(__y),
1972*38fd1498Szrj iterator(__y));
1973*38fd1498Szrj }
1974*38fd1498Szrj
1975*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
1976*38fd1498Szrj typename _Compare, typename _Alloc>
1977*38fd1498Szrj pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1978*38fd1498Szrj _Compare, _Alloc>::const_iterator,
1979*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue,
1980*38fd1498Szrj _Compare, _Alloc>::const_iterator>
1981*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1982*38fd1498Szrj equal_range(const _Key& __k) const
1983*38fd1498Szrj {
1984*38fd1498Szrj _Const_Link_type __x = _M_begin();
1985*38fd1498Szrj _Const_Base_ptr __y = _M_end();
1986*38fd1498Szrj while (__x != 0)
1987*38fd1498Szrj {
1988*38fd1498Szrj if (_M_impl._M_key_compare(_S_key(__x), __k))
1989*38fd1498Szrj __x = _S_right(__x);
1990*38fd1498Szrj else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1991*38fd1498Szrj __y = __x, __x = _S_left(__x);
1992*38fd1498Szrj else
1993*38fd1498Szrj {
1994*38fd1498Szrj _Const_Link_type __xu(__x);
1995*38fd1498Szrj _Const_Base_ptr __yu(__y);
1996*38fd1498Szrj __y = __x, __x = _S_left(__x);
1997*38fd1498Szrj __xu = _S_right(__xu);
1998*38fd1498Szrj return pair<const_iterator,
1999*38fd1498Szrj const_iterator>(_M_lower_bound(__x, __y, __k),
2000*38fd1498Szrj _M_upper_bound(__xu, __yu, __k));
2001*38fd1498Szrj }
2002*38fd1498Szrj }
2003*38fd1498Szrj return pair<const_iterator, const_iterator>(const_iterator(__y),
2004*38fd1498Szrj const_iterator(__y));
2005*38fd1498Szrj }
2006*38fd1498Szrj
2007*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2008*38fd1498Szrj typename _Compare, typename _Alloc>
2009*38fd1498Szrj void
2010*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2011*38fd1498Szrj swap(_Rb_tree& __t)
2012*38fd1498Szrj _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
2013*38fd1498Szrj {
2014*38fd1498Szrj if (_M_root() == 0)
2015*38fd1498Szrj {
2016*38fd1498Szrj if (__t._M_root() != 0)
2017*38fd1498Szrj _M_impl._M_move_data(__t._M_impl);
2018*38fd1498Szrj }
2019*38fd1498Szrj else if (__t._M_root() == 0)
2020*38fd1498Szrj __t._M_impl._M_move_data(_M_impl);
2021*38fd1498Szrj else
2022*38fd1498Szrj {
2023*38fd1498Szrj std::swap(_M_root(),__t._M_root());
2024*38fd1498Szrj std::swap(_M_leftmost(),__t._M_leftmost());
2025*38fd1498Szrj std::swap(_M_rightmost(),__t._M_rightmost());
2026*38fd1498Szrj
2027*38fd1498Szrj _M_root()->_M_parent = _M_end();
2028*38fd1498Szrj __t._M_root()->_M_parent = __t._M_end();
2029*38fd1498Szrj std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
2030*38fd1498Szrj }
2031*38fd1498Szrj // No need to swap header's color as it does not change.
2032*38fd1498Szrj std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
2033*38fd1498Szrj
2034*38fd1498Szrj _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
2035*38fd1498Szrj __t._M_get_Node_allocator());
2036*38fd1498Szrj }
2037*38fd1498Szrj
2038*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2039*38fd1498Szrj typename _Compare, typename _Alloc>
2040*38fd1498Szrj pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2041*38fd1498Szrj _Compare, _Alloc>::_Base_ptr,
2042*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue,
2043*38fd1498Szrj _Compare, _Alloc>::_Base_ptr>
2044*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2045*38fd1498Szrj _M_get_insert_unique_pos(const key_type& __k)
2046*38fd1498Szrj {
2047*38fd1498Szrj typedef pair<_Base_ptr, _Base_ptr> _Res;
2048*38fd1498Szrj _Link_type __x = _M_begin();
2049*38fd1498Szrj _Base_ptr __y = _M_end();
2050*38fd1498Szrj bool __comp = true;
2051*38fd1498Szrj while (__x != 0)
2052*38fd1498Szrj {
2053*38fd1498Szrj __y = __x;
2054*38fd1498Szrj __comp = _M_impl._M_key_compare(__k, _S_key(__x));
2055*38fd1498Szrj __x = __comp ? _S_left(__x) : _S_right(__x);
2056*38fd1498Szrj }
2057*38fd1498Szrj iterator __j = iterator(__y);
2058*38fd1498Szrj if (__comp)
2059*38fd1498Szrj {
2060*38fd1498Szrj if (__j == begin())
2061*38fd1498Szrj return _Res(__x, __y);
2062*38fd1498Szrj else
2063*38fd1498Szrj --__j;
2064*38fd1498Szrj }
2065*38fd1498Szrj if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
2066*38fd1498Szrj return _Res(__x, __y);
2067*38fd1498Szrj return _Res(__j._M_node, 0);
2068*38fd1498Szrj }
2069*38fd1498Szrj
2070*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2071*38fd1498Szrj typename _Compare, typename _Alloc>
2072*38fd1498Szrj pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2073*38fd1498Szrj _Compare, _Alloc>::_Base_ptr,
2074*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue,
2075*38fd1498Szrj _Compare, _Alloc>::_Base_ptr>
2076*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2077*38fd1498Szrj _M_get_insert_equal_pos(const key_type& __k)
2078*38fd1498Szrj {
2079*38fd1498Szrj typedef pair<_Base_ptr, _Base_ptr> _Res;
2080*38fd1498Szrj _Link_type __x = _M_begin();
2081*38fd1498Szrj _Base_ptr __y = _M_end();
2082*38fd1498Szrj while (__x != 0)
2083*38fd1498Szrj {
2084*38fd1498Szrj __y = __x;
2085*38fd1498Szrj __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
2086*38fd1498Szrj _S_left(__x) : _S_right(__x);
2087*38fd1498Szrj }
2088*38fd1498Szrj return _Res(__x, __y);
2089*38fd1498Szrj }
2090*38fd1498Szrj
2091*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2092*38fd1498Szrj typename _Compare, typename _Alloc>
2093*38fd1498Szrj #if __cplusplus >= 201103L
2094*38fd1498Szrj template<typename _Arg>
2095*38fd1498Szrj #endif
2096*38fd1498Szrj pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2097*38fd1498Szrj _Compare, _Alloc>::iterator, bool>
2098*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2099*38fd1498Szrj #if __cplusplus >= 201103L
2100*38fd1498Szrj _M_insert_unique(_Arg&& __v)
2101*38fd1498Szrj #else
2102*38fd1498Szrj _M_insert_unique(const _Val& __v)
2103*38fd1498Szrj #endif
2104*38fd1498Szrj {
2105*38fd1498Szrj typedef pair<iterator, bool> _Res;
2106*38fd1498Szrj pair<_Base_ptr, _Base_ptr> __res
2107*38fd1498Szrj = _M_get_insert_unique_pos(_KeyOfValue()(__v));
2108*38fd1498Szrj
2109*38fd1498Szrj if (__res.second)
2110*38fd1498Szrj {
2111*38fd1498Szrj _Alloc_node __an(*this);
2112*38fd1498Szrj return _Res(_M_insert_(__res.first, __res.second,
2113*38fd1498Szrj _GLIBCXX_FORWARD(_Arg, __v), __an),
2114*38fd1498Szrj true);
2115*38fd1498Szrj }
2116*38fd1498Szrj
2117*38fd1498Szrj return _Res(iterator(__res.first), false);
2118*38fd1498Szrj }
2119*38fd1498Szrj
2120*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2121*38fd1498Szrj typename _Compare, typename _Alloc>
2122*38fd1498Szrj #if __cplusplus >= 201103L
2123*38fd1498Szrj template<typename _Arg>
2124*38fd1498Szrj #endif
2125*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2126*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2127*38fd1498Szrj #if __cplusplus >= 201103L
2128*38fd1498Szrj _M_insert_equal(_Arg&& __v)
2129*38fd1498Szrj #else
2130*38fd1498Szrj _M_insert_equal(const _Val& __v)
2131*38fd1498Szrj #endif
2132*38fd1498Szrj {
2133*38fd1498Szrj pair<_Base_ptr, _Base_ptr> __res
2134*38fd1498Szrj = _M_get_insert_equal_pos(_KeyOfValue()(__v));
2135*38fd1498Szrj _Alloc_node __an(*this);
2136*38fd1498Szrj return _M_insert_(__res.first, __res.second,
2137*38fd1498Szrj _GLIBCXX_FORWARD(_Arg, __v), __an);
2138*38fd1498Szrj }
2139*38fd1498Szrj
2140*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2141*38fd1498Szrj typename _Compare, typename _Alloc>
2142*38fd1498Szrj pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2143*38fd1498Szrj _Compare, _Alloc>::_Base_ptr,
2144*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue,
2145*38fd1498Szrj _Compare, _Alloc>::_Base_ptr>
2146*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2147*38fd1498Szrj _M_get_insert_hint_unique_pos(const_iterator __position,
2148*38fd1498Szrj const key_type& __k)
2149*38fd1498Szrj {
2150*38fd1498Szrj iterator __pos = __position._M_const_cast();
2151*38fd1498Szrj typedef pair<_Base_ptr, _Base_ptr> _Res;
2152*38fd1498Szrj
2153*38fd1498Szrj // end()
2154*38fd1498Szrj if (__pos._M_node == _M_end())
2155*38fd1498Szrj {
2156*38fd1498Szrj if (size() > 0
2157*38fd1498Szrj && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
2158*38fd1498Szrj return _Res(0, _M_rightmost());
2159*38fd1498Szrj else
2160*38fd1498Szrj return _M_get_insert_unique_pos(__k);
2161*38fd1498Szrj }
2162*38fd1498Szrj else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
2163*38fd1498Szrj {
2164*38fd1498Szrj // First, try before...
2165*38fd1498Szrj iterator __before = __pos;
2166*38fd1498Szrj if (__pos._M_node == _M_leftmost()) // begin()
2167*38fd1498Szrj return _Res(_M_leftmost(), _M_leftmost());
2168*38fd1498Szrj else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
2169*38fd1498Szrj {
2170*38fd1498Szrj if (_S_right(__before._M_node) == 0)
2171*38fd1498Szrj return _Res(0, __before._M_node);
2172*38fd1498Szrj else
2173*38fd1498Szrj return _Res(__pos._M_node, __pos._M_node);
2174*38fd1498Szrj }
2175*38fd1498Szrj else
2176*38fd1498Szrj return _M_get_insert_unique_pos(__k);
2177*38fd1498Szrj }
2178*38fd1498Szrj else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2179*38fd1498Szrj {
2180*38fd1498Szrj // ... then try after.
2181*38fd1498Szrj iterator __after = __pos;
2182*38fd1498Szrj if (__pos._M_node == _M_rightmost())
2183*38fd1498Szrj return _Res(0, _M_rightmost());
2184*38fd1498Szrj else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
2185*38fd1498Szrj {
2186*38fd1498Szrj if (_S_right(__pos._M_node) == 0)
2187*38fd1498Szrj return _Res(0, __pos._M_node);
2188*38fd1498Szrj else
2189*38fd1498Szrj return _Res(__after._M_node, __after._M_node);
2190*38fd1498Szrj }
2191*38fd1498Szrj else
2192*38fd1498Szrj return _M_get_insert_unique_pos(__k);
2193*38fd1498Szrj }
2194*38fd1498Szrj else
2195*38fd1498Szrj // Equivalent keys.
2196*38fd1498Szrj return _Res(__pos._M_node, 0);
2197*38fd1498Szrj }
2198*38fd1498Szrj
2199*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2200*38fd1498Szrj typename _Compare, typename _Alloc>
2201*38fd1498Szrj #if __cplusplus >= 201103L
2202*38fd1498Szrj template<typename _Arg, typename _NodeGen>
2203*38fd1498Szrj #else
2204*38fd1498Szrj template<typename _NodeGen>
2205*38fd1498Szrj #endif
2206*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2207*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2208*38fd1498Szrj _M_insert_unique_(const_iterator __position,
2209*38fd1498Szrj #if __cplusplus >= 201103L
2210*38fd1498Szrj _Arg&& __v,
2211*38fd1498Szrj #else
2212*38fd1498Szrj const _Val& __v,
2213*38fd1498Szrj #endif
2214*38fd1498Szrj _NodeGen& __node_gen)
2215*38fd1498Szrj {
2216*38fd1498Szrj pair<_Base_ptr, _Base_ptr> __res
2217*38fd1498Szrj = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
2218*38fd1498Szrj
2219*38fd1498Szrj if (__res.second)
2220*38fd1498Szrj return _M_insert_(__res.first, __res.second,
2221*38fd1498Szrj _GLIBCXX_FORWARD(_Arg, __v),
2222*38fd1498Szrj __node_gen);
2223*38fd1498Szrj return iterator(__res.first);
2224*38fd1498Szrj }
2225*38fd1498Szrj
2226*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2227*38fd1498Szrj typename _Compare, typename _Alloc>
2228*38fd1498Szrj pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2229*38fd1498Szrj _Compare, _Alloc>::_Base_ptr,
2230*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue,
2231*38fd1498Szrj _Compare, _Alloc>::_Base_ptr>
2232*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2233*38fd1498Szrj _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
2234*38fd1498Szrj {
2235*38fd1498Szrj iterator __pos = __position._M_const_cast();
2236*38fd1498Szrj typedef pair<_Base_ptr, _Base_ptr> _Res;
2237*38fd1498Szrj
2238*38fd1498Szrj // end()
2239*38fd1498Szrj if (__pos._M_node == _M_end())
2240*38fd1498Szrj {
2241*38fd1498Szrj if (size() > 0
2242*38fd1498Szrj && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
2243*38fd1498Szrj return _Res(0, _M_rightmost());
2244*38fd1498Szrj else
2245*38fd1498Szrj return _M_get_insert_equal_pos(__k);
2246*38fd1498Szrj }
2247*38fd1498Szrj else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2248*38fd1498Szrj {
2249*38fd1498Szrj // First, try before...
2250*38fd1498Szrj iterator __before = __pos;
2251*38fd1498Szrj if (__pos._M_node == _M_leftmost()) // begin()
2252*38fd1498Szrj return _Res(_M_leftmost(), _M_leftmost());
2253*38fd1498Szrj else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
2254*38fd1498Szrj {
2255*38fd1498Szrj if (_S_right(__before._M_node) == 0)
2256*38fd1498Szrj return _Res(0, __before._M_node);
2257*38fd1498Szrj else
2258*38fd1498Szrj return _Res(__pos._M_node, __pos._M_node);
2259*38fd1498Szrj }
2260*38fd1498Szrj else
2261*38fd1498Szrj return _M_get_insert_equal_pos(__k);
2262*38fd1498Szrj }
2263*38fd1498Szrj else
2264*38fd1498Szrj {
2265*38fd1498Szrj // ... then try after.
2266*38fd1498Szrj iterator __after = __pos;
2267*38fd1498Szrj if (__pos._M_node == _M_rightmost())
2268*38fd1498Szrj return _Res(0, _M_rightmost());
2269*38fd1498Szrj else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
2270*38fd1498Szrj {
2271*38fd1498Szrj if (_S_right(__pos._M_node) == 0)
2272*38fd1498Szrj return _Res(0, __pos._M_node);
2273*38fd1498Szrj else
2274*38fd1498Szrj return _Res(__after._M_node, __after._M_node);
2275*38fd1498Szrj }
2276*38fd1498Szrj else
2277*38fd1498Szrj return _Res(0, 0);
2278*38fd1498Szrj }
2279*38fd1498Szrj }
2280*38fd1498Szrj
2281*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2282*38fd1498Szrj typename _Compare, typename _Alloc>
2283*38fd1498Szrj #if __cplusplus >= 201103L
2284*38fd1498Szrj template<typename _Arg, typename _NodeGen>
2285*38fd1498Szrj #else
2286*38fd1498Szrj template<typename _NodeGen>
2287*38fd1498Szrj #endif
2288*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2289*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2290*38fd1498Szrj _M_insert_equal_(const_iterator __position,
2291*38fd1498Szrj #if __cplusplus >= 201103L
2292*38fd1498Szrj _Arg&& __v,
2293*38fd1498Szrj #else
2294*38fd1498Szrj const _Val& __v,
2295*38fd1498Szrj #endif
2296*38fd1498Szrj _NodeGen& __node_gen)
2297*38fd1498Szrj {
2298*38fd1498Szrj pair<_Base_ptr, _Base_ptr> __res
2299*38fd1498Szrj = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
2300*38fd1498Szrj
2301*38fd1498Szrj if (__res.second)
2302*38fd1498Szrj return _M_insert_(__res.first, __res.second,
2303*38fd1498Szrj _GLIBCXX_FORWARD(_Arg, __v),
2304*38fd1498Szrj __node_gen);
2305*38fd1498Szrj
2306*38fd1498Szrj return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
2307*38fd1498Szrj }
2308*38fd1498Szrj
2309*38fd1498Szrj #if __cplusplus >= 201103L
2310*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2311*38fd1498Szrj typename _Compare, typename _Alloc>
2312*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2313*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2314*38fd1498Szrj _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
2315*38fd1498Szrj {
2316*38fd1498Szrj bool __insert_left = (__x != 0 || __p == _M_end()
2317*38fd1498Szrj || _M_impl._M_key_compare(_S_key(__z),
2318*38fd1498Szrj _S_key(__p)));
2319*38fd1498Szrj
2320*38fd1498Szrj _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2321*38fd1498Szrj this->_M_impl._M_header);
2322*38fd1498Szrj ++_M_impl._M_node_count;
2323*38fd1498Szrj return iterator(__z);
2324*38fd1498Szrj }
2325*38fd1498Szrj
2326*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2327*38fd1498Szrj typename _Compare, typename _Alloc>
2328*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2329*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2330*38fd1498Szrj _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
2331*38fd1498Szrj {
2332*38fd1498Szrj bool __insert_left = (__p == _M_end()
2333*38fd1498Szrj || !_M_impl._M_key_compare(_S_key(__p),
2334*38fd1498Szrj _S_key(__z)));
2335*38fd1498Szrj
2336*38fd1498Szrj _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2337*38fd1498Szrj this->_M_impl._M_header);
2338*38fd1498Szrj ++_M_impl._M_node_count;
2339*38fd1498Szrj return iterator(__z);
2340*38fd1498Szrj }
2341*38fd1498Szrj
2342*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2343*38fd1498Szrj typename _Compare, typename _Alloc>
2344*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2345*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2346*38fd1498Szrj _M_insert_equal_lower_node(_Link_type __z)
2347*38fd1498Szrj {
2348*38fd1498Szrj _Link_type __x = _M_begin();
2349*38fd1498Szrj _Base_ptr __y = _M_end();
2350*38fd1498Szrj while (__x != 0)
2351*38fd1498Szrj {
2352*38fd1498Szrj __y = __x;
2353*38fd1498Szrj __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
2354*38fd1498Szrj _S_left(__x) : _S_right(__x);
2355*38fd1498Szrj }
2356*38fd1498Szrj return _M_insert_lower_node(__y, __z);
2357*38fd1498Szrj }
2358*38fd1498Szrj
2359*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2360*38fd1498Szrj typename _Compare, typename _Alloc>
2361*38fd1498Szrj template<typename... _Args>
2362*38fd1498Szrj pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2363*38fd1498Szrj _Compare, _Alloc>::iterator, bool>
2364*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2365*38fd1498Szrj _M_emplace_unique(_Args&&... __args)
2366*38fd1498Szrj {
2367*38fd1498Szrj _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2368*38fd1498Szrj
2369*38fd1498Szrj __try
2370*38fd1498Szrj {
2371*38fd1498Szrj typedef pair<iterator, bool> _Res;
2372*38fd1498Szrj auto __res = _M_get_insert_unique_pos(_S_key(__z));
2373*38fd1498Szrj if (__res.second)
2374*38fd1498Szrj return _Res(_M_insert_node(__res.first, __res.second, __z), true);
2375*38fd1498Szrj
2376*38fd1498Szrj _M_drop_node(__z);
2377*38fd1498Szrj return _Res(iterator(__res.first), false);
2378*38fd1498Szrj }
2379*38fd1498Szrj __catch(...)
2380*38fd1498Szrj {
2381*38fd1498Szrj _M_drop_node(__z);
2382*38fd1498Szrj __throw_exception_again;
2383*38fd1498Szrj }
2384*38fd1498Szrj }
2385*38fd1498Szrj
2386*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2387*38fd1498Szrj typename _Compare, typename _Alloc>
2388*38fd1498Szrj template<typename... _Args>
2389*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2390*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2391*38fd1498Szrj _M_emplace_equal(_Args&&... __args)
2392*38fd1498Szrj {
2393*38fd1498Szrj _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2394*38fd1498Szrj
2395*38fd1498Szrj __try
2396*38fd1498Szrj {
2397*38fd1498Szrj auto __res = _M_get_insert_equal_pos(_S_key(__z));
2398*38fd1498Szrj return _M_insert_node(__res.first, __res.second, __z);
2399*38fd1498Szrj }
2400*38fd1498Szrj __catch(...)
2401*38fd1498Szrj {
2402*38fd1498Szrj _M_drop_node(__z);
2403*38fd1498Szrj __throw_exception_again;
2404*38fd1498Szrj }
2405*38fd1498Szrj }
2406*38fd1498Szrj
2407*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2408*38fd1498Szrj typename _Compare, typename _Alloc>
2409*38fd1498Szrj template<typename... _Args>
2410*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2411*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2412*38fd1498Szrj _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
2413*38fd1498Szrj {
2414*38fd1498Szrj _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2415*38fd1498Szrj
2416*38fd1498Szrj __try
2417*38fd1498Szrj {
2418*38fd1498Szrj auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
2419*38fd1498Szrj
2420*38fd1498Szrj if (__res.second)
2421*38fd1498Szrj return _M_insert_node(__res.first, __res.second, __z);
2422*38fd1498Szrj
2423*38fd1498Szrj _M_drop_node(__z);
2424*38fd1498Szrj return iterator(__res.first);
2425*38fd1498Szrj }
2426*38fd1498Szrj __catch(...)
2427*38fd1498Szrj {
2428*38fd1498Szrj _M_drop_node(__z);
2429*38fd1498Szrj __throw_exception_again;
2430*38fd1498Szrj }
2431*38fd1498Szrj }
2432*38fd1498Szrj
2433*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2434*38fd1498Szrj typename _Compare, typename _Alloc>
2435*38fd1498Szrj template<typename... _Args>
2436*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2437*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2438*38fd1498Szrj _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
2439*38fd1498Szrj {
2440*38fd1498Szrj _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2441*38fd1498Szrj
2442*38fd1498Szrj __try
2443*38fd1498Szrj {
2444*38fd1498Szrj auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
2445*38fd1498Szrj
2446*38fd1498Szrj if (__res.second)
2447*38fd1498Szrj return _M_insert_node(__res.first, __res.second, __z);
2448*38fd1498Szrj
2449*38fd1498Szrj return _M_insert_equal_lower_node(__z);
2450*38fd1498Szrj }
2451*38fd1498Szrj __catch(...)
2452*38fd1498Szrj {
2453*38fd1498Szrj _M_drop_node(__z);
2454*38fd1498Szrj __throw_exception_again;
2455*38fd1498Szrj }
2456*38fd1498Szrj }
2457*38fd1498Szrj #endif
2458*38fd1498Szrj
2459*38fd1498Szrj template<typename _Key, typename _Val, typename _KoV,
2460*38fd1498Szrj typename _Cmp, typename _Alloc>
2461*38fd1498Szrj template<class _II>
2462*38fd1498Szrj void
2463*38fd1498Szrj _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2464*38fd1498Szrj _M_insert_unique(_II __first, _II __last)
2465*38fd1498Szrj {
2466*38fd1498Szrj _Alloc_node __an(*this);
2467*38fd1498Szrj for (; __first != __last; ++__first)
2468*38fd1498Szrj _M_insert_unique_(end(), *__first, __an);
2469*38fd1498Szrj }
2470*38fd1498Szrj
2471*38fd1498Szrj template<typename _Key, typename _Val, typename _KoV,
2472*38fd1498Szrj typename _Cmp, typename _Alloc>
2473*38fd1498Szrj template<class _II>
2474*38fd1498Szrj void
2475*38fd1498Szrj _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2476*38fd1498Szrj _M_insert_equal(_II __first, _II __last)
2477*38fd1498Szrj {
2478*38fd1498Szrj _Alloc_node __an(*this);
2479*38fd1498Szrj for (; __first != __last; ++__first)
2480*38fd1498Szrj _M_insert_equal_(end(), *__first, __an);
2481*38fd1498Szrj }
2482*38fd1498Szrj
2483*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2484*38fd1498Szrj typename _Compare, typename _Alloc>
2485*38fd1498Szrj void
2486*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2487*38fd1498Szrj _M_erase_aux(const_iterator __position)
2488*38fd1498Szrj {
2489*38fd1498Szrj _Link_type __y =
2490*38fd1498Szrj static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
2491*38fd1498Szrj (const_cast<_Base_ptr>(__position._M_node),
2492*38fd1498Szrj this->_M_impl._M_header));
2493*38fd1498Szrj _M_drop_node(__y);
2494*38fd1498Szrj --_M_impl._M_node_count;
2495*38fd1498Szrj }
2496*38fd1498Szrj
2497*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2498*38fd1498Szrj typename _Compare, typename _Alloc>
2499*38fd1498Szrj void
2500*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2501*38fd1498Szrj _M_erase_aux(const_iterator __first, const_iterator __last)
2502*38fd1498Szrj {
2503*38fd1498Szrj if (__first == begin() && __last == end())
2504*38fd1498Szrj clear();
2505*38fd1498Szrj else
2506*38fd1498Szrj while (__first != __last)
2507*38fd1498Szrj _M_erase_aux(__first++);
2508*38fd1498Szrj }
2509*38fd1498Szrj
2510*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2511*38fd1498Szrj typename _Compare, typename _Alloc>
2512*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2513*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2514*38fd1498Szrj erase(const _Key& __x)
2515*38fd1498Szrj {
2516*38fd1498Szrj pair<iterator, iterator> __p = equal_range(__x);
2517*38fd1498Szrj const size_type __old_size = size();
2518*38fd1498Szrj _M_erase_aux(__p.first, __p.second);
2519*38fd1498Szrj return __old_size - size();
2520*38fd1498Szrj }
2521*38fd1498Szrj
2522*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2523*38fd1498Szrj typename _Compare, typename _Alloc>
2524*38fd1498Szrj void
2525*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2526*38fd1498Szrj erase(const _Key* __first, const _Key* __last)
2527*38fd1498Szrj {
2528*38fd1498Szrj while (__first != __last)
2529*38fd1498Szrj erase(*__first++);
2530*38fd1498Szrj }
2531*38fd1498Szrj
2532*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2533*38fd1498Szrj typename _Compare, typename _Alloc>
2534*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue,
2535*38fd1498Szrj _Compare, _Alloc>::iterator
2536*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2537*38fd1498Szrj find(const _Key& __k)
2538*38fd1498Szrj {
2539*38fd1498Szrj iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2540*38fd1498Szrj return (__j == end()
2541*38fd1498Szrj || _M_impl._M_key_compare(__k,
2542*38fd1498Szrj _S_key(__j._M_node))) ? end() : __j;
2543*38fd1498Szrj }
2544*38fd1498Szrj
2545*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2546*38fd1498Szrj typename _Compare, typename _Alloc>
2547*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue,
2548*38fd1498Szrj _Compare, _Alloc>::const_iterator
2549*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2550*38fd1498Szrj find(const _Key& __k) const
2551*38fd1498Szrj {
2552*38fd1498Szrj const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2553*38fd1498Szrj return (__j == end()
2554*38fd1498Szrj || _M_impl._M_key_compare(__k,
2555*38fd1498Szrj _S_key(__j._M_node))) ? end() : __j;
2556*38fd1498Szrj }
2557*38fd1498Szrj
2558*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2559*38fd1498Szrj typename _Compare, typename _Alloc>
2560*38fd1498Szrj typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2561*38fd1498Szrj _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2562*38fd1498Szrj count(const _Key& __k) const
2563*38fd1498Szrj {
2564*38fd1498Szrj pair<const_iterator, const_iterator> __p = equal_range(__k);
2565*38fd1498Szrj const size_type __n = std::distance(__p.first, __p.second);
2566*38fd1498Szrj return __n;
2567*38fd1498Szrj }
2568*38fd1498Szrj
2569*38fd1498Szrj _GLIBCXX_PURE unsigned int
2570*38fd1498Szrj _Rb_tree_black_count(const _Rb_tree_node_base* __node,
2571*38fd1498Szrj const _Rb_tree_node_base* __root) throw ();
2572*38fd1498Szrj
2573*38fd1498Szrj template<typename _Key, typename _Val, typename _KeyOfValue,
2574*38fd1498Szrj typename _Compare, typename _Alloc>
2575*38fd1498Szrj bool
2576*38fd1498Szrj _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
2577*38fd1498Szrj {
2578*38fd1498Szrj if (_M_impl._M_node_count == 0 || begin() == end())
2579*38fd1498Szrj return _M_impl._M_node_count == 0 && begin() == end()
2580*38fd1498Szrj && this->_M_impl._M_header._M_left == _M_end()
2581*38fd1498Szrj && this->_M_impl._M_header._M_right == _M_end();
2582*38fd1498Szrj
2583*38fd1498Szrj unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
2584*38fd1498Szrj for (const_iterator __it = begin(); __it != end(); ++__it)
2585*38fd1498Szrj {
2586*38fd1498Szrj _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
2587*38fd1498Szrj _Const_Link_type __L = _S_left(__x);
2588*38fd1498Szrj _Const_Link_type __R = _S_right(__x);
2589*38fd1498Szrj
2590*38fd1498Szrj if (__x->_M_color == _S_red)
2591*38fd1498Szrj if ((__L && __L->_M_color == _S_red)
2592*38fd1498Szrj || (__R && __R->_M_color == _S_red))
2593*38fd1498Szrj return false;
2594*38fd1498Szrj
2595*38fd1498Szrj if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
2596*38fd1498Szrj return false;
2597*38fd1498Szrj if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
2598*38fd1498Szrj return false;
2599*38fd1498Szrj
2600*38fd1498Szrj if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
2601*38fd1498Szrj return false;
2602*38fd1498Szrj }
2603*38fd1498Szrj
2604*38fd1498Szrj if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2605*38fd1498Szrj return false;
2606*38fd1498Szrj if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2607*38fd1498Szrj return false;
2608*38fd1498Szrj return true;
2609*38fd1498Szrj }
2610*38fd1498Szrj
2611*38fd1498Szrj #if __cplusplus > 201402L
2612*38fd1498Szrj // Allow access to internals of compatible _Rb_tree specializations.
2613*38fd1498Szrj template<typename _Key, typename _Val, typename _Sel, typename _Cmp1,
2614*38fd1498Szrj typename _Alloc, typename _Cmp2>
2615*38fd1498Szrj struct _Rb_tree_merge_helper<_Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>,
2616*38fd1498Szrj _Cmp2>
2617*38fd1498Szrj {
2618*38fd1498Szrj private:
2619*38fd1498Szrj friend class _Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>;
2620*38fd1498Szrj
2621*38fd1498Szrj static auto&
2622*38fd1498Szrj _S_get_impl(_Rb_tree<_Key, _Val, _Sel, _Cmp2, _Alloc>& __tree)
2623*38fd1498Szrj { return __tree._M_impl; }
2624*38fd1498Szrj };
2625*38fd1498Szrj #endif // C++17
2626*38fd1498Szrj
2627*38fd1498Szrj _GLIBCXX_END_NAMESPACE_VERSION
2628*38fd1498Szrj } // namespace
2629*38fd1498Szrj
2630*38fd1498Szrj #endif
2631