1 // Debugging set implementation -*- C++ -*-
2
3 // Copyright (C) 2003-2022 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24
25 /** @file debug/set.h
26 * This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29 #ifndef _GLIBCXX_DEBUG_SET_H
30 #define _GLIBCXX_DEBUG_SET_H 1
31
32 #include <debug/safe_sequence.h>
33 #include <debug/safe_container.h>
34 #include <debug/safe_iterator.h>
35 #include <bits/stl_pair.h>
36
_GLIBCXX_VISIBILITY(default)37 namespace std _GLIBCXX_VISIBILITY(default)
38 {
39 namespace __debug
40 {
41 /// Class std::set with safety/checking/debug instrumentation.
42 template<typename _Key, typename _Compare = std::less<_Key>,
43 typename _Allocator = std::allocator<_Key> >
44 class set
45 : public __gnu_debug::_Safe_container<
46 set<_Key, _Compare, _Allocator>, _Allocator,
47 __gnu_debug::_Safe_node_sequence>,
48 public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>
49 {
50 typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base;
51 typedef __gnu_debug::_Safe_container<
52 set, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe;
53
54 typedef typename _Base::const_iterator _Base_const_iterator;
55 typedef typename _Base::iterator _Base_iterator;
56 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
57
58 template<typename _ItT, typename _SeqT, typename _CatT>
59 friend class ::__gnu_debug::_Safe_iterator;
60
61 // Reference wrapper for base class. Disambiguates set(const _Base&)
62 // from copy constructor by requiring a user-defined conversion.
63 // See PR libstdc++/90102.
64 struct _Base_ref
65 {
66 _Base_ref(const _Base& __r) : _M_ref(__r) { }
67
68 const _Base& _M_ref;
69 };
70
71 public:
72 // types:
73 typedef _Key key_type;
74 typedef _Key value_type;
75 typedef _Compare key_compare;
76 typedef _Compare value_compare;
77 typedef _Allocator allocator_type;
78 typedef typename _Base::reference reference;
79 typedef typename _Base::const_reference const_reference;
80
81 typedef __gnu_debug::_Safe_iterator<_Base_iterator, set>
82 iterator;
83 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set>
84 const_iterator;
85
86 typedef typename _Base::size_type size_type;
87 typedef typename _Base::difference_type difference_type;
88 typedef typename _Base::pointer pointer;
89 typedef typename _Base::const_pointer const_pointer;
90 typedef std::reverse_iterator<iterator> reverse_iterator;
91 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
92
93 // 23.3.3.1 construct/copy/destroy:
94
95 #if __cplusplus < 201103L
96 set() : _Base() { }
97
98 set(const set& __x)
99 : _Base(__x) { }
100
101 ~set() { }
102 #else
103 set() = default;
104 set(const set&) = default;
105 set(set&&) = default;
106
107 set(initializer_list<value_type> __l,
108 const _Compare& __comp = _Compare(),
109 const allocator_type& __a = allocator_type())
110 : _Base(__l, __comp, __a) { }
111
112 explicit
113 set(const allocator_type& __a)
114 : _Base(__a) { }
115
116 set(const set& __x, const __type_identity_t<allocator_type>& __a)
117 : _Base(__x, __a) { }
118
119 set(set&& __x, const __type_identity_t<allocator_type>& __a)
120 noexcept( noexcept(_Base(std::move(__x), __a)) )
121 : _Safe(std::move(__x), __a),
122 _Base(std::move(__x), __a) { }
123
124 set(initializer_list<value_type> __l, const allocator_type& __a)
125 : _Base(__l, __a) { }
126
127 template<typename _InputIterator>
128 set(_InputIterator __first, _InputIterator __last,
129 const allocator_type& __a)
130 : _Base(__gnu_debug::__base(
131 __glibcxx_check_valid_constructor_range(__first, __last)),
132 __gnu_debug::__base(__last), __a) { }
133
134 ~set() = default;
135 #endif
136
137 explicit set(const _Compare& __comp,
138 const _Allocator& __a = _Allocator())
139 : _Base(__comp, __a) { }
140
141 template<typename _InputIterator>
142 set(_InputIterator __first, _InputIterator __last,
143 const _Compare& __comp = _Compare(),
144 const _Allocator& __a = _Allocator())
145 : _Base(__gnu_debug::__base(
146 __glibcxx_check_valid_constructor_range(__first, __last)),
147 __gnu_debug::__base(__last),
148 __comp, __a) { }
149
150 set(_Base_ref __x)
151 : _Base(__x._M_ref) { }
152
153 #if __cplusplus >= 201103L
154 set&
155 operator=(const set&) = default;
156
157 set&
158 operator=(set&&) = default;
159
160 set&
161 operator=(initializer_list<value_type> __l)
162 {
163 _Base::operator=(__l);
164 this->_M_invalidate_all();
165 return *this;
166 }
167 #endif
168
169 using _Base::get_allocator;
170
171 // iterators:
172 iterator
173 begin() _GLIBCXX_NOEXCEPT
174 { return iterator(_Base::begin(), this); }
175
176 const_iterator
177 begin() const _GLIBCXX_NOEXCEPT
178 { return const_iterator(_Base::begin(), this); }
179
180 iterator
181 end() _GLIBCXX_NOEXCEPT
182 { return iterator(_Base::end(), this); }
183
184 const_iterator
185 end() const _GLIBCXX_NOEXCEPT
186 { return const_iterator(_Base::end(), this); }
187
188 reverse_iterator
189 rbegin() _GLIBCXX_NOEXCEPT
190 { return reverse_iterator(end()); }
191
192 const_reverse_iterator
193 rbegin() const _GLIBCXX_NOEXCEPT
194 { return const_reverse_iterator(end()); }
195
196 reverse_iterator
197 rend() _GLIBCXX_NOEXCEPT
198 { return reverse_iterator(begin()); }
199
200 const_reverse_iterator
201 rend() const _GLIBCXX_NOEXCEPT
202 { return const_reverse_iterator(begin()); }
203
204 #if __cplusplus >= 201103L
205 const_iterator
206 cbegin() const noexcept
207 { return const_iterator(_Base::begin(), this); }
208
209 const_iterator
210 cend() const noexcept
211 { return const_iterator(_Base::end(), this); }
212
213 const_reverse_iterator
214 crbegin() const noexcept
215 { return const_reverse_iterator(end()); }
216
217 const_reverse_iterator
218 crend() const noexcept
219 { return const_reverse_iterator(begin()); }
220 #endif
221
222 // capacity:
223 using _Base::empty;
224 using _Base::size;
225 using _Base::max_size;
226
227 // modifiers:
228 #if __cplusplus >= 201103L
229 template<typename... _Args>
230 std::pair<iterator, bool>
231 emplace(_Args&&... __args)
232 {
233 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
234 return { { __res.first, this }, __res.second };
235 }
236
237 template<typename... _Args>
238 iterator
239 emplace_hint(const_iterator __pos, _Args&&... __args)
240 {
241 __glibcxx_check_insert(__pos);
242 return
243 {
244 _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
245 this
246 };
247 }
248 #endif
249
250 std::pair<iterator, bool>
251 insert(const value_type& __x)
252 {
253 std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
254 return std::pair<iterator, bool>(iterator(__res.first, this),
255 __res.second);
256 }
257
258 #if __cplusplus >= 201103L
259 std::pair<iterator, bool>
260 insert(value_type&& __x)
261 {
262 auto __res = _Base::insert(std::move(__x));
263 return { { __res.first, this }, __res.second };
264 }
265 #endif
266
267 iterator
268 insert(const_iterator __position, const value_type& __x)
269 {
270 __glibcxx_check_insert(__position);
271 return iterator(_Base::insert(__position.base(), __x), this);
272 }
273
274 #if __cplusplus >= 201103L
275 iterator
276 insert(const_iterator __position, value_type&& __x)
277 {
278 __glibcxx_check_insert(__position);
279 return { _Base::insert(__position.base(), std::move(__x)), this };
280 }
281 #endif
282
283 template <typename _InputIterator>
284 void
285 insert(_InputIterator __first, _InputIterator __last)
286 {
287 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
288 __glibcxx_check_valid_range2(__first, __last, __dist);
289
290 if (__dist.second >= __gnu_debug::__dp_sign)
291 _Base::insert(__gnu_debug::__unsafe(__first),
292 __gnu_debug::__unsafe(__last));
293 else
294 _Base::insert(__first, __last);
295 }
296
297 #if __cplusplus >= 201103L
298 void
299 insert(initializer_list<value_type> __l)
300 { _Base::insert(__l); }
301 #endif
302
303 #if __cplusplus > 201402L
304 using node_type = typename _Base::node_type;
305 using insert_return_type = _Node_insert_return<iterator, node_type>;
306
307 node_type
308 extract(const_iterator __position)
309 {
310 __glibcxx_check_erase(__position);
311 this->_M_invalidate_if(_Equal(__position.base()));
312 return _Base::extract(__position.base());
313 }
314
315 node_type
316 extract(const key_type& __key)
317 {
318 const auto __position = find(__key);
319 if (__position != end())
320 return extract(__position);
321 return {};
322 }
323
324 insert_return_type
325 insert(node_type&& __nh)
326 {
327 auto __ret = _Base::insert(std::move(__nh));
328 iterator __pos = iterator(__ret.position, this);
329 return { __pos, __ret.inserted, std::move(__ret.node) };
330 }
331
332 iterator
333 insert(const_iterator __hint, node_type&& __nh)
334 {
335 __glibcxx_check_insert(__hint);
336 return { _Base::insert(__hint.base(), std::move(__nh)), this };
337 }
338
339 using _Base::merge;
340 #endif // C++17
341
342 #if __cplusplus >= 201103L
343 _GLIBCXX_ABI_TAG_CXX11
344 iterator
345 erase(const_iterator __position)
346 {
347 __glibcxx_check_erase(__position);
348 return { erase(__position.base()), this };
349 }
350
351 _Base_iterator
352 erase(_Base_const_iterator __position)
353 {
354 __glibcxx_check_erase2(__position);
355 this->_M_invalidate_if(_Equal(__position));
356 return _Base::erase(__position);
357 }
358 #else
359 void
360 erase(iterator __position)
361 {
362 __glibcxx_check_erase(__position);
363 this->_M_invalidate_if(_Equal(__position.base()));
364 _Base::erase(__position.base());
365 }
366 #endif
367
368 size_type
369 erase(const key_type& __x)
370 {
371 _Base_iterator __victim = _Base::find(__x);
372 if (__victim == _Base::end())
373 return 0;
374 else
375 {
376 this->_M_invalidate_if(_Equal(__victim));
377 _Base::erase(__victim);
378 return 1;
379 }
380 }
381
382 #if __cplusplus >= 201103L
383 _GLIBCXX_ABI_TAG_CXX11
384 iterator
385 erase(const_iterator __first, const_iterator __last)
386 {
387 // _GLIBCXX_RESOLVE_LIB_DEFECTS
388 // 151. can't currently clear() empty container
389 __glibcxx_check_erase_range(__first, __last);
390 for (_Base_const_iterator __victim = __first.base();
391 __victim != __last.base(); ++__victim)
392 {
393 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
394 _M_message(__gnu_debug::__msg_valid_range)
395 ._M_iterator(__first, "first")
396 ._M_iterator(__last, "last"));
397 this->_M_invalidate_if(_Equal(__victim));
398 }
399
400 return { _Base::erase(__first.base(), __last.base()), this };
401 }
402 #else
403 void
404 erase(iterator __first, iterator __last)
405 {
406 // _GLIBCXX_RESOLVE_LIB_DEFECTS
407 // 151. can't currently clear() empty container
408 __glibcxx_check_erase_range(__first, __last);
409 for (_Base_iterator __victim = __first.base();
410 __victim != __last.base(); ++__victim)
411 {
412 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
413 _M_message(__gnu_debug::__msg_valid_range)
414 ._M_iterator(__first, "first")
415 ._M_iterator(__last, "last"));
416 this->_M_invalidate_if(_Equal(__victim));
417 }
418 _Base::erase(__first.base(), __last.base());
419 }
420 #endif
421
422 void
423 swap(set& __x)
424 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
425 {
426 _Safe::_M_swap(__x);
427 _Base::swap(__x);
428 }
429
430 void
431 clear() _GLIBCXX_NOEXCEPT
432 {
433 this->_M_invalidate_all();
434 _Base::clear();
435 }
436
437 // observers:
438 using _Base::key_comp;
439 using _Base::value_comp;
440
441 // set operations:
442 iterator
443 find(const key_type& __x)
444 { return iterator(_Base::find(__x), this); }
445
446 // _GLIBCXX_RESOLVE_LIB_DEFECTS
447 // 214. set::find() missing const overload
448 const_iterator
449 find(const key_type& __x) const
450 { return const_iterator(_Base::find(__x), this); }
451
452 #if __cplusplus > 201103L
453 template<typename _Kt,
454 typename _Req =
455 typename __has_is_transparent<_Compare, _Kt>::type>
456 iterator
457 find(const _Kt& __x)
458 { return { _Base::find(__x), this }; }
459
460 template<typename _Kt,
461 typename _Req =
462 typename __has_is_transparent<_Compare, _Kt>::type>
463 const_iterator
464 find(const _Kt& __x) const
465 { return { _Base::find(__x), this }; }
466 #endif
467
468 using _Base::count;
469
470 iterator
471 lower_bound(const key_type& __x)
472 { return iterator(_Base::lower_bound(__x), this); }
473
474 // _GLIBCXX_RESOLVE_LIB_DEFECTS
475 // 214. set::find() missing const overload
476 const_iterator
477 lower_bound(const key_type& __x) const
478 { return const_iterator(_Base::lower_bound(__x), this); }
479
480 #if __cplusplus > 201103L
481 template<typename _Kt,
482 typename _Req =
483 typename __has_is_transparent<_Compare, _Kt>::type>
484 iterator
485 lower_bound(const _Kt& __x)
486 { return { _Base::lower_bound(__x), this }; }
487
488 template<typename _Kt,
489 typename _Req =
490 typename __has_is_transparent<_Compare, _Kt>::type>
491 const_iterator
492 lower_bound(const _Kt& __x) const
493 { return { _Base::lower_bound(__x), this }; }
494 #endif
495
496 iterator
497 upper_bound(const key_type& __x)
498 { return iterator(_Base::upper_bound(__x), this); }
499
500 // _GLIBCXX_RESOLVE_LIB_DEFECTS
501 // 214. set::find() missing const overload
502 const_iterator
503 upper_bound(const key_type& __x) const
504 { return const_iterator(_Base::upper_bound(__x), this); }
505
506 #if __cplusplus > 201103L
507 template<typename _Kt,
508 typename _Req =
509 typename __has_is_transparent<_Compare, _Kt>::type>
510 iterator
511 upper_bound(const _Kt& __x)
512 { return { _Base::upper_bound(__x), this }; }
513
514 template<typename _Kt,
515 typename _Req =
516 typename __has_is_transparent<_Compare, _Kt>::type>
517 const_iterator
518 upper_bound(const _Kt& __x) const
519 { return { _Base::upper_bound(__x), this }; }
520 #endif
521
522 std::pair<iterator, iterator>
523 equal_range(const key_type& __x)
524 {
525 std::pair<_Base_iterator, _Base_iterator> __res =
526 _Base::equal_range(__x);
527 return std::make_pair(iterator(__res.first, this),
528 iterator(__res.second, this));
529 }
530
531 // _GLIBCXX_RESOLVE_LIB_DEFECTS
532 // 214. set::find() missing const overload
533 std::pair<const_iterator, const_iterator>
534 equal_range(const key_type& __x) const
535 {
536 std::pair<_Base_const_iterator, _Base_const_iterator> __res =
537 _Base::equal_range(__x);
538 return std::make_pair(const_iterator(__res.first, this),
539 const_iterator(__res.second, this));
540 }
541
542 #if __cplusplus > 201103L
543 template<typename _Kt,
544 typename _Req =
545 typename __has_is_transparent<_Compare, _Kt>::type>
546 std::pair<iterator, iterator>
547 equal_range(const _Kt& __x)
548 {
549 auto __res = _Base::equal_range(__x);
550 return { { __res.first, this }, { __res.second, this } };
551 }
552
553 template<typename _Kt,
554 typename _Req =
555 typename __has_is_transparent<_Compare, _Kt>::type>
556 std::pair<const_iterator, const_iterator>
557 equal_range(const _Kt& __x) const
558 {
559 auto __res = _Base::equal_range(__x);
560 return { { __res.first, this }, { __res.second, this } };
561 }
562 #endif
563
564 _Base&
565 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
566
567 const _Base&
568 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
569 };
570
571 #if __cpp_deduction_guides >= 201606
572
573 template<typename _InputIterator,
574 typename _Compare =
575 less<typename iterator_traits<_InputIterator>::value_type>,
576 typename _Allocator =
577 allocator<typename iterator_traits<_InputIterator>::value_type>,
578 typename = _RequireInputIter<_InputIterator>,
579 typename = _RequireNotAllocator<_Compare>,
580 typename = _RequireAllocator<_Allocator>>
581 set(_InputIterator, _InputIterator,
582 _Compare = _Compare(), _Allocator = _Allocator())
583 -> set<typename iterator_traits<_InputIterator>::value_type,
584 _Compare, _Allocator>;
585
586 template<typename _Key, typename _Compare = less<_Key>,
587 typename _Allocator = allocator<_Key>,
588 typename = _RequireNotAllocator<_Compare>,
589 typename = _RequireAllocator<_Allocator>>
590 set(initializer_list<_Key>,
591 _Compare = _Compare(), _Allocator = _Allocator())
592 -> set<_Key, _Compare, _Allocator>;
593
594 template<typename _InputIterator, typename _Allocator,
595 typename = _RequireInputIter<_InputIterator>,
596 typename = _RequireAllocator<_Allocator>>
597 set(_InputIterator, _InputIterator, _Allocator)
598 -> set<typename iterator_traits<_InputIterator>::value_type,
599 less<typename iterator_traits<_InputIterator>::value_type>,
600 _Allocator>;
601
602 template<typename _Key, typename _Allocator,
603 typename = _RequireAllocator<_Allocator>>
604 set(initializer_list<_Key>, _Allocator)
605 -> set<_Key, less<_Key>, _Allocator>;
606
607 #endif // deduction guides
608
609 template<typename _Key, typename _Compare, typename _Allocator>
610 inline bool
611 operator==(const set<_Key, _Compare, _Allocator>& __lhs,
612 const set<_Key, _Compare, _Allocator>& __rhs)
613 { return __lhs._M_base() == __rhs._M_base(); }
614
615 #if __cpp_lib_three_way_comparison
616 template<typename _Key, typename _Compare, typename _Alloc>
617 inline __detail::__synth3way_t<_Key>
618 operator<=>(const set<_Key, _Compare, _Alloc>& __lhs,
619 const set<_Key, _Compare, _Alloc>& __rhs)
620 { return __lhs._M_base() <=> __rhs._M_base(); }
621 #else
622 template<typename _Key, typename _Compare, typename _Allocator>
623 inline bool
624 operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
625 const set<_Key, _Compare, _Allocator>& __rhs)
626 { return __lhs._M_base() != __rhs._M_base(); }
627
628 template<typename _Key, typename _Compare, typename _Allocator>
629 inline bool
630 operator<(const set<_Key, _Compare, _Allocator>& __lhs,
631 const set<_Key, _Compare, _Allocator>& __rhs)
632 { return __lhs._M_base() < __rhs._M_base(); }
633
634 template<typename _Key, typename _Compare, typename _Allocator>
635 inline bool
636 operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
637 const set<_Key, _Compare, _Allocator>& __rhs)
638 { return __lhs._M_base() <= __rhs._M_base(); }
639
640 template<typename _Key, typename _Compare, typename _Allocator>
641 inline bool
642 operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
643 const set<_Key, _Compare, _Allocator>& __rhs)
644 { return __lhs._M_base() >= __rhs._M_base(); }
645
646 template<typename _Key, typename _Compare, typename _Allocator>
647 inline bool
648 operator>(const set<_Key, _Compare, _Allocator>& __lhs,
649 const set<_Key, _Compare, _Allocator>& __rhs)
650 { return __lhs._M_base() > __rhs._M_base(); }
651 #endif // three-way comparison
652
653 template<typename _Key, typename _Compare, typename _Allocator>
654 void
655 swap(set<_Key, _Compare, _Allocator>& __x,
656 set<_Key, _Compare, _Allocator>& __y)
657 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
658 { return __x.swap(__y); }
659
660 } // namespace __debug
661 } // namespace std
662
663 #endif
664