1 // Profiling multimap implementation -*- C++ -*-
2 
3 // Copyright (C) 2009-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 profile/multimap.h
26  *  This file is a GNU profile extension to the Standard C++ Library.
27  */
28 
29 #ifndef _GLIBCXX_PROFILE_MULTIMAP_H
30 #define _GLIBCXX_PROFILE_MULTIMAP_H 1
31 
32 #include <profile/base.h>
33 #include <profile/ordered_base.h>
34 
35 namespace std _GLIBCXX_VISIBILITY(default)
36 {
37 namespace __profile
38 {
39   /// Class std::multimap wrapper with performance instrumentation.
40   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
41 	   typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
42     class multimap
43     : public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator>,
44       public _Ordered_profile<map<_Key, _Tp, _Compare, _Allocator> >
45     {
46       typedef _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator> _Base;
47 
48       typedef typename _Base::iterator			_Base_iterator;
49       typedef typename _Base::const_iterator		_Base_const_iterator;
50 
51     public:
52       // types:
53       typedef _Key					key_type;
54       typedef _Tp					mapped_type;
55       typedef std::pair<const _Key, _Tp>		value_type;
56       typedef _Compare					key_compare;
57       typedef typename _Base::reference			reference;
58       typedef typename _Base::const_reference		const_reference;
59 
60       typedef __iterator_tracker<_Base_iterator,
61 				 multimap>		iterator;
62       typedef __iterator_tracker<_Base_const_iterator,
63 				 multimap>		const_iterator;
64       typedef std::reverse_iterator<iterator>		reverse_iterator;
65       typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;
66 
67       typedef typename _Base::size_type			size_type;
68       typedef typename _Base::difference_type		difference_type;
69 
70       // 23.3.1.1 construct/copy/destroy:
71 
72 #if __cplusplus < 201103L
73       multimap()
74       : _Base() { }
75       multimap(const multimap& __x)
76       : _Base(__x) { }
77       ~multimap() { }
78 #else
79       multimap() = default;
80       multimap(const multimap&) = default;
81       multimap(multimap&&) = default;
82       ~multimap() = default;
83 #endif
84 
85       explicit multimap(const _Compare& __comp,
86 			const _Allocator& __a = _Allocator())
87       : _Base(__comp, __a) { }
88 
89 #if __cplusplus >= 201103L
90       template<typename _InputIterator,
91 	       typename = std::_RequireInputIter<_InputIterator>>
92 #else
93       template<typename _InputIterator>
94 #endif
95 	multimap(_InputIterator __first, _InputIterator __last,
96 		 const _Compare& __comp = _Compare(),
97 		 const _Allocator& __a = _Allocator())
98 	: _Base(__first, __last, __comp, __a) { }
99 
100 #if __cplusplus >= 201103L
101       multimap(initializer_list<value_type> __l,
102 	       const _Compare& __c = _Compare(),
103 	       const _Allocator& __a = _Allocator())
104       : _Base(__l, __c, __a) { }
105 
106       explicit
107       multimap(const _Allocator& __a)
108       : _Base(__a) { }
109 
110       multimap(const multimap& __x, const _Allocator& __a)
111       : _Base(__x, __a) { }
112 
113       multimap(multimap&& __x, const _Allocator& __a)
114       noexcept( noexcept(_Base(std::move(__x), __a)) )
115       : _Base(std::move(__x), __a) { }
116 
117       multimap(initializer_list<value_type> __l, const _Allocator& __a)
118       : _Base(__l, __a) { }
119 
120       template<typename _InputIterator>
121 	multimap(_InputIterator __first, _InputIterator __last,
122 		 const _Allocator& __a)
123 	: _Base(__first, __last, __a) { }
124 #endif
125 
126       multimap(const _Base& __x)
127       : _Base(__x) { }
128 
129 #if __cplusplus < 201103L
130       multimap&
131       operator=(const multimap& __x)
132       {
133 	this->_M_profile_destruct();
134 	_M_base() = __x;
135 	this->_M_profile_construct();
136 	return *this;
137       }
138 #else
139       multimap&
140       operator=(const multimap&) = default;
141 
142       multimap&
143       operator=(multimap&&) = default;
144 
145       multimap&
146       operator=(initializer_list<value_type> __l)
147       {
148 	this->_M_profile_destruct();
149 	_M_base() = __l;
150 	this->_M_profile_construct();
151 	return *this;
152       }
153 #endif
154 
155       // iterators
156       iterator
157       begin() _GLIBCXX_NOEXCEPT
158       { return iterator(_Base::begin(), this); }
159 
160       const_iterator
161       begin() const _GLIBCXX_NOEXCEPT
162       { return const_iterator(_Base::begin(), this); }
163 
164       iterator
165       end() _GLIBCXX_NOEXCEPT
166       { return iterator(_Base::end(), this); }
167 
168       const_iterator
169       end() const _GLIBCXX_NOEXCEPT
170       { return const_iterator(_Base::end(), this); }
171 
172 #if __cplusplus >= 201103L
173       const_iterator
174       cbegin() const noexcept
175       { return const_iterator(_Base::cbegin(), this); }
176 
177       const_iterator
178       cend() const noexcept
179       { return const_iterator(_Base::cend(), this); }
180 #endif
181 
182       reverse_iterator
183       rbegin() _GLIBCXX_NOEXCEPT
184       {
185 	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
186 	return reverse_iterator(end());
187       }
188 
189       const_reverse_iterator
190       rbegin() const _GLIBCXX_NOEXCEPT
191       {
192 	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
193 	return const_reverse_iterator(end());
194       }
195 
196       reverse_iterator
197       rend() _GLIBCXX_NOEXCEPT
198       {
199 	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
200 	return reverse_iterator(begin());
201       }
202 
203       const_reverse_iterator
204       rend() const _GLIBCXX_NOEXCEPT
205       {
206 	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
207 	return const_reverse_iterator(begin());
208       }
209 
210 #if __cplusplus >= 201103L
211       const_reverse_iterator
212       crbegin() const noexcept
213       {
214 	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
215 	return const_reverse_iterator(cend());
216       }
217 
218       const_reverse_iterator
219       crend() const noexcept
220       {
221 	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
222 	return const_reverse_iterator(cbegin());
223       }
224 #endif
225 
226       // modifiers:
227 #if __cplusplus >= 201103L
228       template<typename... _Args>
229 	iterator
230 	emplace(_Args&&... __args)
231 	{
232 	  __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
233 	  return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
234 	}
235 
236       template<typename... _Args>
237 	iterator
238 	emplace_hint(const_iterator __pos, _Args&&... __args)
239 	{
240 	  auto size_before = this->size();
241 	  auto __res
242 	    = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...);
243 	  __profcxx_map2umap_insert(this->_M_map2umap_info,
244 		size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
245 	  return iterator(__res, this);
246 	}
247 #endif
248 
249       iterator
250       insert(const value_type& __x)
251       {
252 	__profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
253 	return iterator(_Base::insert(__x), this);
254       }
255 
256 #if __cplusplus >= 201103L
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 	{
263 	  __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
264 	  return iterator(_Base::insert(std::forward<_Pair>(__x)), this);
265 	}
266 #endif
267 
268 #if __cplusplus >= 201103L
269       void
270       insert(std::initializer_list<value_type> __list)
271       { insert(__list.begin(), __list.end()); }
272 #endif
273 
274       iterator
275 #if __cplusplus >= 201103L
276       insert(const_iterator __pos, const value_type& __x)
277 #else
278       insert(iterator __pos, const value_type& __x)
279 #endif
280       {
281 	size_type size_before = this->size();
282 	_Base_iterator __res = _Base::insert(__pos.base(), __x);
283 	__profcxx_map2umap_insert(this->_M_map2umap_info,
284 		size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
285 	return iterator(__res, this);
286       }
287 
288 #if __cplusplus >= 201103L
289       template<typename _Pair, typename = typename
290 	       std::enable_if<std::is_constructible<value_type,
291 						    _Pair&&>::value>::type>
292 	iterator
293 	insert(const_iterator __pos, _Pair&& __x)
294 	{
295 	  size_type size_before = this->size();
296 	  auto __res = _Base::insert(__pos.base(), std::forward<_Pair>(__x));
297 	  __profcxx_map2umap_insert(this->_M_map2umap_info,
298 		size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
299 	  return iterator(__res, this);
300 	}
301 #endif
302 
303       template<typename _InputIterator>
304 	void
305 	insert(_InputIterator __first, _InputIterator __last)
306 	{
307 	  for (; __first != __last; ++__first)
308 	    insert(*__first);
309 	}
310 
311 #if __cplusplus >= 201103L
312       iterator
313       erase(const_iterator __pos)
314       {
315 	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
316 	return iterator(_Base::erase(__pos.base()), this);
317       }
318 
319       iterator
320       erase(iterator __pos)
321       {
322 	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
323 	return iterator(_Base::erase(__pos.base()), this);
324       }
325 #else
326       void
327       erase(iterator __pos)
328       {
329 	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
330 	_Base::erase(__pos.base());
331       }
332 #endif
333 
334       size_type
335       erase(const key_type& __x)
336       {
337 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
338 	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
339 	return _Base::erase(__x);
340       }
341 
342 #if __cplusplus >= 201103L
343       iterator
344       erase(const_iterator __first, const_iterator __last)
345       {
346 	if (__first != __last)
347 	  {
348 	    iterator __ret;
349 	    for (; __first != __last;)
350 	      __ret = erase(__first++);
351 	    return __ret;
352 	  }
353 	else
354 	  return iterator(_Base::erase(__first.base(), __last.base()), this);
355       }
356 #else
357       void
358       erase(iterator __first, iterator __last)
359       {
360 	for (; __first != __last;)
361 	  erase(__first++);
362       }
363 #endif
364 
365       void
366       swap(multimap& __x)
367       _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
368       {
369 	std::swap(this->_M_map2umap_info, __x._M_map2umap_info);
370 	_Base::swap(__x);
371       }
372 
373       void
374       clear() _GLIBCXX_NOEXCEPT
375       {
376 	this->_M_profile_destruct();
377 	_Base::clear();
378 	this->_M_profile_construct();
379       }
380 
381       // 23.3.1.3 multimap operations:
382       iterator
383       find(const key_type& __x)
384       {
385 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
386 	return iterator(_Base::find(__x), this);
387       }
388 
389 #if __cplusplus > 201103L
390       template<typename _Kt,
391 	       typename _Req =
392 		 typename __has_is_transparent<_Compare, _Kt>::type>
393 	iterator
394 	find(const _Kt& __x)
395 	{
396 	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
397 	  return { _Base::find(__x), this };
398 	}
399 #endif
400 
401       const_iterator
402       find(const key_type& __x) const
403       {
404 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
405 	return const_iterator(_Base::find(__x), this);
406       }
407 
408 #if __cplusplus > 201103L
409       template<typename _Kt,
410 	       typename _Req =
411 		 typename __has_is_transparent<_Compare, _Kt>::type>
412 	const_iterator
413 	find(const _Kt& __x) const
414 	{
415 	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
416 	  return { _Base::find(__x), this };
417 	}
418 #endif
419 
420       size_type
421       count(const key_type& __x) const
422       {
423 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
424 	return _Base::count(__x);
425       }
426 
427 #if __cplusplus > 201103L
428       template<typename _Kt,
429 	       typename _Req =
430 		 typename __has_is_transparent<_Compare, _Kt>::type>
431 	size_type
432 	count(const _Kt& __x) const
433 	{
434 	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
435 	  return _Base::count(__x);
436 	}
437 #endif
438 
439       iterator
440       lower_bound(const key_type& __x)
441       {
442 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
443 	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
444 	return iterator(_Base::lower_bound(__x), this);
445       }
446 
447 #if __cplusplus > 201103L
448       template<typename _Kt,
449 	       typename _Req =
450 		 typename __has_is_transparent<_Compare, _Kt>::type>
451 	iterator
452 	lower_bound(const _Kt& __x)
453 	{
454 	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
455 	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
456 	  return { _Base::lower_bound(__x), this };
457 	}
458 #endif
459 
460       const_iterator
461       lower_bound(const key_type& __x) const
462       {
463 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
464 	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
465 	return const_iterator(_Base::lower_bound(__x), this);
466       }
467 
468 #if __cplusplus > 201103L
469       template<typename _Kt,
470 	       typename _Req =
471 		 typename __has_is_transparent<_Compare, _Kt>::type>
472 	const_iterator
473 	lower_bound(const _Kt& __x) const
474 	{
475 	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
476 	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
477 	  return { _Base::lower_bound(__x), this };
478 	}
479 #endif
480 
481       iterator
482       upper_bound(const key_type& __x)
483       {
484 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
485 	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
486 	return iterator(_Base::upper_bound(__x), this);
487       }
488 
489 #if __cplusplus > 201103L
490       template<typename _Kt,
491 	       typename _Req =
492 		 typename __has_is_transparent<_Compare, _Kt>::type>
493 	iterator
494 	upper_bound(const _Kt& __x)
495 	{
496 	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
497 	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
498 	  return { _Base::upper_bound(__x), this };
499 	}
500 #endif
501 
502       const_iterator
503       upper_bound(const key_type& __x) const
504       {
505 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
506 	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
507 	return const_iterator(_Base::upper_bound(__x), this);
508       }
509 
510 #if __cplusplus > 201103L
511       template<typename _Kt,
512 	       typename _Req =
513 		 typename __has_is_transparent<_Compare, _Kt>::type>
514 	const_iterator
515 	upper_bound(const _Kt& __x) const
516 	{
517 	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
518 	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
519 	  return { _Base::upper_bound(__x), this };
520 	}
521 #endif
522 
523       std::pair<iterator,iterator>
524       equal_range(const key_type& __x)
525       {
526 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
527 	std::pair<_Base_iterator, _Base_iterator> __base_ret
528 	  = _Base::equal_range(__x);
529 	return std::make_pair(iterator(__base_ret.first, this),
530 			      iterator(__base_ret.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 	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
541 	  auto __res = _Base::equal_range(__x);
542 	  return { { __res.first, this }, { __res.second, this } };
543 	}
544 #endif
545 
546       std::pair<const_iterator,const_iterator>
547       equal_range(const key_type& __x) const
548       {
549 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
550 	std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret
551 	  = _Base::equal_range(__x);
552 	return std::make_pair(const_iterator(__base_ret.first, this),
553 			      const_iterator(__base_ret.second, this));
554       }
555 
556 #if __cplusplus > 201103L
557       template<typename _Kt,
558 	       typename _Req =
559 		 typename __has_is_transparent<_Compare, _Kt>::type>
560 	std::pair<const_iterator, const_iterator>
561 	equal_range(const _Kt& __x) const
562 	{
563 	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
564 	  auto __res = _Base::equal_range(__x);
565 	  return { { __res.first, this }, { __res.second, this } };
566 	}
567 #endif
568 
569       _Base&
570       _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
571 
572       const _Base&
573       _M_base() const _GLIBCXX_NOEXCEPT	{ return *this; }
574 
575     private:
576       /** If hint is used we consider that the map and unordered_map
577        * operations have equivalent insertion cost so we do not update metrics
578        * about it.
579        * Note that to find out if hint has been used is libstdc++
580        * implementation dependent.
581        */
582       bool
583       _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res)
584       {
585 	return (__hint == __res
586 		|| (__hint == _M_base().end() && ++__res == _M_base().end())
587 		|| (__hint != _M_base().end() && (++__hint == __res
588 						  || ++__res == --__hint)));
589       }
590 
591       template<typename _K1, typename _T1, typename _C1, typename _A1>
592         friend bool
593         operator==(const multimap<_K1, _T1, _C1, _A1>&,
594 		   const multimap<_K1, _T1, _C1, _A1>&);
595 
596       template<typename _K1, typename _T1, typename _C1, typename _A1>
597         friend bool
598         operator<(const multimap<_K1, _T1, _C1, _A1>&,
599 		  const multimap<_K1, _T1, _C1, _A1>&);
600     };
601 
602   template<typename _Key, typename _Tp,
603 	   typename _Compare, typename _Allocator>
604     inline bool
605     operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
606 	       const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
607     {
608       __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
609       __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
610       return __lhs._M_base() == __rhs._M_base();
611     }
612 
613   template<typename _Key, typename _Tp,
614 	   typename _Compare, typename _Allocator>
615     inline bool
616     operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
617 	      const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
618     {
619       __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
620       __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
621       return __lhs._M_base() < __rhs._M_base();
622     }
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 == __rhs); }
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 !(__rhs < __lhs); }
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 < __rhs); }
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 __rhs < __lhs; }
651 
652   template<typename _Key, typename _Tp,
653 	   typename _Compare, typename _Allocator>
654     inline void
655     swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
656 	 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
657     _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
658     { __lhs.swap(__rhs); }
659 
660 } // namespace __profile
661 } // namespace std
662 
663 #endif
664