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