1 // Debugging set implementation -*- C++ -*-
2
3 // Copyright (C) 2003-2019 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 <utility>
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 public:
62 // types:
63 typedef _Key key_type;
64 typedef _Key value_type;
65 typedef _Compare key_compare;
66 typedef _Compare value_compare;
67 typedef _Allocator allocator_type;
68 typedef typename _Base::reference reference;
69 typedef typename _Base::const_reference const_reference;
70
71 typedef __gnu_debug::_Safe_iterator<_Base_iterator, set>
72 iterator;
73 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set>
74 const_iterator;
75
76 typedef typename _Base::size_type size_type;
77 typedef typename _Base::difference_type difference_type;
78 typedef typename _Base::pointer pointer;
79 typedef typename _Base::const_pointer const_pointer;
80 typedef std::reverse_iterator<iterator> reverse_iterator;
81 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
82
83 // 23.3.3.1 construct/copy/destroy:
84
85 #if __cplusplus < 201103L
86 set() : _Base() { }
87
88 set(const set& __x)
89 : _Base(__x) { }
90
91 ~set() { }
92 #else
93 set() = default;
94 set(const set&) = default;
95 set(set&&) = default;
96
97 set(initializer_list<value_type> __l,
98 const _Compare& __comp = _Compare(),
99 const allocator_type& __a = allocator_type())
100 : _Base(__l, __comp, __a) { }
101
102 explicit
103 set(const allocator_type& __a)
104 : _Base(__a) { }
105
106 set(const set& __x, const allocator_type& __a)
107 : _Base(__x, __a) { }
108
109 set(set&& __x, const allocator_type& __a)
110 noexcept( noexcept(_Base(std::move(__x._M_base()), __a)) )
111 : _Safe(std::move(__x._M_safe()), __a),
112 _Base(std::move(__x._M_base()), __a) { }
113
114 set(initializer_list<value_type> __l, const allocator_type& __a)
115 : _Base(__l, __a) { }
116
117 template<typename _InputIterator>
118 set(_InputIterator __first, _InputIterator __last,
119 const allocator_type& __a)
120 : _Base(__gnu_debug::__base(
121 __glibcxx_check_valid_constructor_range(__first, __last)),
122 __gnu_debug::__base(__last), __a) { }
123
124 ~set() = default;
125 #endif
126
127 explicit set(const _Compare& __comp,
128 const _Allocator& __a = _Allocator())
129 : _Base(__comp, __a) { }
130
131 template<typename _InputIterator>
132 set(_InputIterator __first, _InputIterator __last,
133 const _Compare& __comp = _Compare(),
134 const _Allocator& __a = _Allocator())
135 : _Base(__gnu_debug::__base(
136 __glibcxx_check_valid_constructor_range(__first, __last)),
137 __gnu_debug::__base(__last),
138 __comp, __a) { }
139
140 set(const _Base& __x)
141 : _Base(__x) { }
142
143 #if __cplusplus < 201103L
144 set&
145 operator=(const set& __x)
146 {
147 this->_M_safe() = __x;
148 _M_base() = __x;
149 return *this;
150 }
151 #else
152 set&
153 operator=(const set&) = default;
154
155 set&
156 operator=(set&&) = default;
157
158 set&
159 operator=(initializer_list<value_type> __l)
160 {
161 _M_base() = __l;
162 this->_M_invalidate_all();
163 return *this;
164 }
165 #endif
166
167 using _Base::get_allocator;
168
169 // iterators:
170 iterator
171 begin() _GLIBCXX_NOEXCEPT
172 { return iterator(_Base::begin(), this); }
173
174 const_iterator
175 begin() const _GLIBCXX_NOEXCEPT
176 { return const_iterator(_Base::begin(), this); }
177
178 iterator
179 end() _GLIBCXX_NOEXCEPT
180 { return iterator(_Base::end(), this); }
181
182 const_iterator
183 end() const _GLIBCXX_NOEXCEPT
184 { return const_iterator(_Base::end(), this); }
185
186 reverse_iterator
187 rbegin() _GLIBCXX_NOEXCEPT
188 { return reverse_iterator(end()); }
189
190 const_reverse_iterator
191 rbegin() const _GLIBCXX_NOEXCEPT
192 { return const_reverse_iterator(end()); }
193
194 reverse_iterator
195 rend() _GLIBCXX_NOEXCEPT
196 { return reverse_iterator(begin()); }
197
198 const_reverse_iterator
199 rend() const _GLIBCXX_NOEXCEPT
200 { return const_reverse_iterator(begin()); }
201
202 #if __cplusplus >= 201103L
203 const_iterator
204 cbegin() const noexcept
205 { return const_iterator(_Base::begin(), this); }
206
207 const_iterator
208 cend() const noexcept
209 { return const_iterator(_Base::end(), this); }
210
211 const_reverse_iterator
212 crbegin() const noexcept
213 { return const_reverse_iterator(end()); }
214
215 const_reverse_iterator
216 crend() const noexcept
217 { return const_reverse_iterator(begin()); }
218 #endif
219
220 // capacity:
221 using _Base::empty;
222 using _Base::size;
223 using _Base::max_size;
224
225 // modifiers:
226 #if __cplusplus >= 201103L
227 template<typename... _Args>
228 std::pair<iterator, bool>
229 emplace(_Args&&... __args)
230 {
231 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
232 return { { __res.first, this }, __res.second };
233 }
234
235 template<typename... _Args>
236 iterator
237 emplace_hint(const_iterator __pos, _Args&&... __args)
238 {
239 __glibcxx_check_insert(__pos);
240 return
241 {
242 _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
243 this
244 };
245 }
246 #endif
247
248 std::pair<iterator, bool>
249 insert(const value_type& __x)
250 {
251 std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
252 return std::pair<iterator, bool>(iterator(__res.first, this),
253 __res.second);
254 }
255
256 #if __cplusplus >= 201103L
257 std::pair<iterator, bool>
258 insert(value_type&& __x)
259 {
260 auto __res = _Base::insert(std::move(__x));
261 return { { __res.first, this }, __res.second };
262 }
263 #endif
264
265 iterator
266 insert(const_iterator __position, const value_type& __x)
267 {
268 __glibcxx_check_insert(__position);
269 return iterator(_Base::insert(__position.base(), __x), this);
270 }
271
272 #if __cplusplus >= 201103L
273 iterator
274 insert(const_iterator __position, value_type&& __x)
275 {
276 __glibcxx_check_insert(__position);
277 return { _Base::insert(__position.base(), std::move(__x)), this };
278 }
279 #endif
280
281 template <typename _InputIterator>
282 void
283 insert(_InputIterator __first, _InputIterator __last)
284 {
285 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
286 __glibcxx_check_valid_range2(__first, __last, __dist);
287
288 if (__dist.second >= __gnu_debug::__dp_sign)
289 _Base::insert(__gnu_debug::__unsafe(__first),
290 __gnu_debug::__unsafe(__last));
291 else
292 _Base::insert(__first, __last);
293 }
294
295 #if __cplusplus >= 201103L
296 void
297 insert(initializer_list<value_type> __l)
298 { _Base::insert(__l); }
299 #endif
300
301 #if __cplusplus > 201402L
302 using node_type = typename _Base::node_type;
303 using insert_return_type = _Node_insert_return<iterator, node_type>;
304
305 node_type
306 extract(const_iterator __position)
307 {
308 __glibcxx_check_erase(__position);
309 this->_M_invalidate_if(_Equal(__position.base()));
310 return _Base::extract(__position.base());
311 }
312
313 node_type
314 extract(const key_type& __key)
315 {
316 const auto __position = find(__key);
317 if (__position != end())
318 return extract(__position);
319 return {};
320 }
321
322 insert_return_type
323 insert(node_type&& __nh)
324 {
325 auto __ret = _Base::insert(std::move(__nh));
326 iterator __pos = iterator(__ret.position, this);
327 return { __pos, __ret.inserted, std::move(__ret.node) };
328 }
329
330 iterator
331 insert(const_iterator __hint, node_type&& __nh)
332 {
333 __glibcxx_check_insert(__hint);
334 return { _Base::insert(__hint.base(), std::move(__nh)), this };
335 }
336
337 using _Base::merge;
338 #endif // C++17
339
340 #if __cplusplus >= 201103L
341 _GLIBCXX_ABI_TAG_CXX11
342 iterator
343 erase(const_iterator __position)
344 {
345 __glibcxx_check_erase(__position);
346 this->_M_invalidate_if(_Equal(__position.base()));
347 return { _Base::erase(__position.base()), this };
348 }
349 #else
350 void
351 erase(iterator __position)
352 {
353 __glibcxx_check_erase(__position);
354 this->_M_invalidate_if(_Equal(__position.base()));
355 _Base::erase(__position.base());
356 }
357 #endif
358
359 size_type
360 erase(const key_type& __x)
361 {
362 _Base_iterator __victim = _Base::find(__x);
363 if (__victim == _Base::end())
364 return 0;
365 else
366 {
367 this->_M_invalidate_if(_Equal(__victim));
368 _Base::erase(__victim);
369 return 1;
370 }
371 }
372
373 #if __cplusplus >= 201103L
374 _GLIBCXX_ABI_TAG_CXX11
375 iterator
376 erase(const_iterator __first, const_iterator __last)
377 {
378 // _GLIBCXX_RESOLVE_LIB_DEFECTS
379 // 151. can't currently clear() empty container
380 __glibcxx_check_erase_range(__first, __last);
381 for (_Base_const_iterator __victim = __first.base();
382 __victim != __last.base(); ++__victim)
383 {
384 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
385 _M_message(__gnu_debug::__msg_valid_range)
386 ._M_iterator(__first, "first")
387 ._M_iterator(__last, "last"));
388 this->_M_invalidate_if(_Equal(__victim));
389 }
390
391 return { _Base::erase(__first.base(), __last.base()), this };
392 }
393 #else
394 void
395 erase(iterator __first, iterator __last)
396 {
397 // _GLIBCXX_RESOLVE_LIB_DEFECTS
398 // 151. can't currently clear() empty container
399 __glibcxx_check_erase_range(__first, __last);
400 for (_Base_iterator __victim = __first.base();
401 __victim != __last.base(); ++__victim)
402 {
403 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
404 _M_message(__gnu_debug::__msg_valid_range)
405 ._M_iterator(__first, "first")
406 ._M_iterator(__last, "last"));
407 this->_M_invalidate_if(_Equal(__victim));
408 }
409 _Base::erase(__first.base(), __last.base());
410 }
411 #endif
412
413 void
414 swap(set& __x)
415 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
416 {
417 _Safe::_M_swap(__x);
418 _Base::swap(__x);
419 }
420
421 void
422 clear() _GLIBCXX_NOEXCEPT
423 {
424 this->_M_invalidate_all();
425 _Base::clear();
426 }
427
428 // observers:
429 using _Base::key_comp;
430 using _Base::value_comp;
431
432 // set operations:
433 iterator
434 find(const key_type& __x)
435 { return iterator(_Base::find(__x), this); }
436
437 // _GLIBCXX_RESOLVE_LIB_DEFECTS
438 // 214. set::find() missing const overload
439 const_iterator
440 find(const key_type& __x) const
441 { return const_iterator(_Base::find(__x), this); }
442
443 #if __cplusplus > 201103L
444 template<typename _Kt,
445 typename _Req =
446 typename __has_is_transparent<_Compare, _Kt>::type>
447 iterator
448 find(const _Kt& __x)
449 { return { _Base::find(__x), this }; }
450
451 template<typename _Kt,
452 typename _Req =
453 typename __has_is_transparent<_Compare, _Kt>::type>
454 const_iterator
455 find(const _Kt& __x) const
456 { return { _Base::find(__x), this }; }
457 #endif
458
459 using _Base::count;
460
461 iterator
462 lower_bound(const key_type& __x)
463 { return iterator(_Base::lower_bound(__x), this); }
464
465 // _GLIBCXX_RESOLVE_LIB_DEFECTS
466 // 214. set::find() missing const overload
467 const_iterator
468 lower_bound(const key_type& __x) const
469 { return const_iterator(_Base::lower_bound(__x), this); }
470
471 #if __cplusplus > 201103L
472 template<typename _Kt,
473 typename _Req =
474 typename __has_is_transparent<_Compare, _Kt>::type>
475 iterator
476 lower_bound(const _Kt& __x)
477 { return { _Base::lower_bound(__x), this }; }
478
479 template<typename _Kt,
480 typename _Req =
481 typename __has_is_transparent<_Compare, _Kt>::type>
482 const_iterator
483 lower_bound(const _Kt& __x) const
484 { return { _Base::lower_bound(__x), this }; }
485 #endif
486
487 iterator
488 upper_bound(const key_type& __x)
489 { return iterator(_Base::upper_bound(__x), this); }
490
491 // _GLIBCXX_RESOLVE_LIB_DEFECTS
492 // 214. set::find() missing const overload
493 const_iterator
494 upper_bound(const key_type& __x) const
495 { return const_iterator(_Base::upper_bound(__x), this); }
496
497 #if __cplusplus > 201103L
498 template<typename _Kt,
499 typename _Req =
500 typename __has_is_transparent<_Compare, _Kt>::type>
501 iterator
502 upper_bound(const _Kt& __x)
503 { return { _Base::upper_bound(__x), this }; }
504
505 template<typename _Kt,
506 typename _Req =
507 typename __has_is_transparent<_Compare, _Kt>::type>
508 const_iterator
509 upper_bound(const _Kt& __x) const
510 { return { _Base::upper_bound(__x), this }; }
511 #endif
512
513 std::pair<iterator, iterator>
514 equal_range(const key_type& __x)
515 {
516 std::pair<_Base_iterator, _Base_iterator> __res =
517 _Base::equal_range(__x);
518 return std::make_pair(iterator(__res.first, this),
519 iterator(__res.second, this));
520 }
521
522 // _GLIBCXX_RESOLVE_LIB_DEFECTS
523 // 214. set::find() missing const overload
524 std::pair<const_iterator, const_iterator>
525 equal_range(const key_type& __x) const
526 {
527 std::pair<_Base_const_iterator, _Base_const_iterator> __res =
528 _Base::equal_range(__x);
529 return std::make_pair(const_iterator(__res.first, this),
530 const_iterator(__res.second, this));
531 }
532
533 #if __cplusplus > 201103L
534 template<typename _Kt,
535 typename _Req =
536 typename __has_is_transparent<_Compare, _Kt>::type>
537 std::pair<iterator, iterator>
538 equal_range(const _Kt& __x)
539 {
540 auto __res = _Base::equal_range(__x);
541 return { { __res.first, this }, { __res.second, this } };
542 }
543
544 template<typename _Kt,
545 typename _Req =
546 typename __has_is_transparent<_Compare, _Kt>::type>
547 std::pair<const_iterator, const_iterator>
548 equal_range(const _Kt& __x) const
549 {
550 auto __res = _Base::equal_range(__x);
551 return { { __res.first, this }, { __res.second, this } };
552 }
553 #endif
554
555 _Base&
556 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
557
558 const _Base&
559 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
560 };
561
562 #if __cpp_deduction_guides >= 201606
563
564 template<typename _InputIterator,
565 typename _Compare =
566 less<typename iterator_traits<_InputIterator>::value_type>,
567 typename _Allocator =
568 allocator<typename iterator_traits<_InputIterator>::value_type>,
569 typename = _RequireInputIter<_InputIterator>,
570 typename = _RequireNotAllocator<_Compare>,
571 typename = _RequireAllocator<_Allocator>>
572 set(_InputIterator, _InputIterator,
573 _Compare = _Compare(), _Allocator = _Allocator())
574 -> set<typename iterator_traits<_InputIterator>::value_type,
575 _Compare, _Allocator>;
576
577 template<typename _Key, typename _Compare = less<_Key>,
578 typename _Allocator = allocator<_Key>,
579 typename = _RequireNotAllocator<_Compare>,
580 typename = _RequireAllocator<_Allocator>>
581 set(initializer_list<_Key>,
582 _Compare = _Compare(), _Allocator = _Allocator())
583 -> set<_Key, _Compare, _Allocator>;
584
585 template<typename _InputIterator, typename _Allocator,
586 typename = _RequireInputIter<_InputIterator>,
587 typename = _RequireAllocator<_Allocator>>
588 set(_InputIterator, _InputIterator, _Allocator)
589 -> set<typename iterator_traits<_InputIterator>::value_type,
590 less<typename iterator_traits<_InputIterator>::value_type>,
591 _Allocator>;
592
593 template<typename _Key, typename _Allocator,
594 typename = _RequireAllocator<_Allocator>>
595 set(initializer_list<_Key>, _Allocator)
596 -> set<_Key, less<_Key>, _Allocator>;
597
598 #endif
599
600 template<typename _Key, typename _Compare, typename _Allocator>
601 inline bool
602 operator==(const set<_Key, _Compare, _Allocator>& __lhs,
603 const set<_Key, _Compare, _Allocator>& __rhs)
604 { return __lhs._M_base() == __rhs._M_base(); }
605
606 template<typename _Key, typename _Compare, typename _Allocator>
607 inline bool
608 operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
609 const set<_Key, _Compare, _Allocator>& __rhs)
610 { return __lhs._M_base() != __rhs._M_base(); }
611
612 template<typename _Key, typename _Compare, typename _Allocator>
613 inline bool
614 operator<(const set<_Key, _Compare, _Allocator>& __lhs,
615 const set<_Key, _Compare, _Allocator>& __rhs)
616 { return __lhs._M_base() < __rhs._M_base(); }
617
618 template<typename _Key, typename _Compare, typename _Allocator>
619 inline bool
620 operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
621 const set<_Key, _Compare, _Allocator>& __rhs)
622 { return __lhs._M_base() <= __rhs._M_base(); }
623
624 template<typename _Key, typename _Compare, typename _Allocator>
625 inline bool
626 operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
627 const set<_Key, _Compare, _Allocator>& __rhs)
628 { return __lhs._M_base() >= __rhs._M_base(); }
629
630 template<typename _Key, typename _Compare, typename _Allocator>
631 inline bool
632 operator>(const set<_Key, _Compare, _Allocator>& __lhs,
633 const set<_Key, _Compare, _Allocator>& __rhs)
634 { return __lhs._M_base() > __rhs._M_base(); }
635
636 template<typename _Key, typename _Compare, typename _Allocator>
637 void
638 swap(set<_Key, _Compare, _Allocator>& __x,
639 set<_Key, _Compare, _Allocator>& __y)
640 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
641 { return __x.swap(__y); }
642
643 } // namespace __debug
644 } // namespace std
645
646 #endif
647