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