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