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