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