xref: /netbsd-src/external/gpl3/gcc.old/dist/libstdc++-v3/include/profile/multiset.h (revision bdc22b2e01993381dcefeff2bc9b56ca75a4235c) 
1 // Profiling multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2009-2015 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 #if __cplusplus >= 201103L
230 	noexcept( noexcept(declval<_Base>().swap(__x)) )
231 #endif
232       {
233 	_Base::swap(__x);
234 	this->_M_swap(__x);
235       }
236 
237       // modifiers:
238 #if __cplusplus >= 201103L
239       template<typename... _Args>
240 	iterator
241 	emplace(_Args&&... __args)
242 	{
243 	  // The cost is the same whether or not the element is inserted so we
244 	  // always report insertion of 1 element.
245 	  __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
246 	  return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
247 	}
248 
249       template<typename... _Args>
250 	iterator
251 	emplace_hint(const_iterator __pos, _Args&&... __args)
252 	{
253 	  auto size_before = this->size();
254 	  auto __res
255 	    = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...);
256 	  __profcxx_map2umap_insert(this->_M_map2umap_info,
257 		size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
258 	  return iterator(__res, this);
259 	}
260 #endif
261 
262       iterator
263       insert(const value_type& __x)
264       {
265 	__profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
266 	return iterator(_Base::insert(__x), this);
267       }
268 
269 #if __cplusplus >= 201103L
270       iterator
271       insert(value_type&& __x)
272       {
273 	__profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
274 	return iterator(_Base::insert(std::move(__x)), this);
275       }
276 #endif
277 
278       iterator
279       insert(const_iterator __pos, const value_type& __x)
280       {
281 	size_type size_before = this->size();
282 	_Base_iterator __res = _Base::insert(__pos.base(), __x);
283 
284 	__profcxx_map2umap_insert(this->_M_map2umap_info,
285 		size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
286 	return iterator(__res, this);
287       }
288 
289 #if __cplusplus >= 201103L
290       iterator
291       insert(const_iterator __pos, value_type&& __x)
292       {
293 	auto size_before = this->size();
294 	auto __res = _Base::insert(__pos.base(), std::move(__x));
295 	__profcxx_map2umap_insert(this->_M_map2umap_info,
296 		size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
297 	return iterator(__res, this);
298       }
299 #endif
300 
301 #if __cplusplus >= 201103L
302       template<typename _InputIterator,
303 	       typename = std::_RequireInputIter<_InputIterator>>
304 #else
305       template<typename _InputIterator>
306 #endif
307 	void
308 	insert(_InputIterator __first, _InputIterator __last)
309 	{
310 	  for (; __first != __last; ++__first)
311 	    insert(*__first);
312 	}
313 
314 #if __cplusplus >= 201103L
315       void
316       insert(initializer_list<value_type> __l)
317       { insert(__l.begin(), __l.end()); }
318 #endif
319 
320 #if __cplusplus >= 201103L
321       iterator
322       erase(const_iterator __pos)
323       {
324 	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
325 	return iterator(_Base::erase(__pos.base()), this);
326       }
327 #else
328       void
329       erase(iterator __pos)
330       {
331 	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
332 	_Base::erase(__pos.base());
333       }
334 #endif
335 
336       size_type
337       erase(const key_type& __x)
338       {
339 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
340 	__profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
341 	return _Base::erase(__x);
342       }
343 
344 #if __cplusplus >= 201103L
345       iterator
346       erase(const_iterator __first, const_iterator __last)
347       {
348 	if (__first != __last)
349 	  {
350 	    iterator __ret;
351 	    for (; __first != __last;)
352 	      __ret = erase(__first++);
353 	    return __ret;
354 	  }
355 	else
356 	  return iterator(_Base::erase(__first.base(), __last.base()), this);
357       }
358 #else
359       void
360       erase(iterator __first, iterator __last)
361       {
362 	for (; __first != __last;)
363 	  erase(__first++);
364       }
365 #endif
366 
367       void
368       clear() _GLIBCXX_NOEXCEPT
369       {
370 	this->_M_profile_destruct();
371 	_Base::clear();
372 	this->_M_profile_construct();
373       }
374 
375       size_type
376       count(const key_type& __x) const
377       {
378 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
379 	return _Base::count(__x);
380       }
381 
382       // multiset operations:
383       iterator
384       find(const key_type& __x)
385       {
386 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
387 	return iterator(_Base::find(__x), this);
388       }
389 
390       // _GLIBCXX_RESOLVE_LIB_DEFECTS
391       // 214. set::find() missing const overload
392       const_iterator
393       find(const key_type& __x) const
394       {
395 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
396 	return const_iterator(_Base::find(__x), this);
397       }
398 
399       iterator
400       lower_bound(const key_type& __x)
401       {
402 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
403 	return iterator(_Base::lower_bound(__x), this);
404       }
405 
406       // _GLIBCXX_RESOLVE_LIB_DEFECTS
407       // 214. set::find() missing const overload
408       const_iterator
409       lower_bound(const key_type& __x) const
410       {
411 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
412 	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
413 	return const_iterator(_Base::lower_bound(__x), this);
414       }
415 
416       iterator
417       upper_bound(const key_type& __x)
418       {
419 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
420 	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
421 	return iterator(_Base::upper_bound(__x), this);
422       }
423 
424       // _GLIBCXX_RESOLVE_LIB_DEFECTS
425       // 214. set::find() missing const overload
426       const_iterator
427       upper_bound(const key_type& __x) const
428       {
429 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
430 	__profcxx_map2umap_invalidate(this->_M_map2umap_info);
431 	return const_iterator(_Base::upper_bound(__x), this);
432       }
433 
434       std::pair<iterator,iterator>
435       equal_range(const key_type& __x)
436       {
437 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
438 	std::pair<_Base_iterator, _Base_iterator> __base_ret
439 	  = _Base::equal_range(__x);
440 	return std::make_pair(iterator(__base_ret.first, this),
441 			      iterator(__base_ret.second, this));
442       }
443 
444       // _GLIBCXX_RESOLVE_LIB_DEFECTS
445       // 214. set::find() missing const overload
446       std::pair<const_iterator,const_iterator>
447       equal_range(const key_type& __x) const
448       {
449 	__profcxx_map2umap_find(this->_M_map2umap_info, this->size());
450 	std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret
451 	  = _Base::equal_range(__x);
452 	return std::make_pair(const_iterator(__base_ret.first, this),
453 			      const_iterator(__base_ret.second, this));
454       }
455 
456       _Base&
457       _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
458 
459       const _Base&
460       _M_base() const _GLIBCXX_NOEXCEPT	{ return *this; }
461 
462     private:
463       /** If hint is used we consider that the map and unordered_map
464        * operations have equivalent insertion cost so we do not update metrics
465        * about it.
466        * Note that to find out if hint has been used is libstdc++
467        * implementation dependent.
468        */
469       bool
470       _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res)
471       {
472 	return (__hint == __res
473 		|| (__hint == _M_base().end() && ++__res == _M_base().end())
474 		|| (__hint != _M_base().end() && (++__hint == __res
475 						  || ++__res == --__hint)));
476       }
477 
478       template<typename _K1, typename _C1, typename _A1>
479         friend bool
480         operator==(const multiset<_K1, _C1, _A1>&,
481 		   const multiset<_K1, _C1, _A1>&);
482 
483       template<typename _K1, typename _C1, typename _A1>
484         friend bool
485         operator< (const multiset<_K1, _C1, _A1>&,
486 		   const multiset<_K1, _C1, _A1>&);
487     };
488 
489   template<typename _Key, typename _Compare, typename _Allocator>
490     inline bool
491     operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
492 	       const multiset<_Key, _Compare, _Allocator>& __rhs)
493     {
494       __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
495       __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
496       return __lhs._M_base() == __rhs._M_base();
497     }
498 
499   template<typename _Key, typename _Compare, typename _Allocator>
500     inline bool
501     operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
502 	      const multiset<_Key, _Compare, _Allocator>& __rhs)
503     {
504       __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
505       __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
506       return __lhs._M_base() < __rhs._M_base();
507     }
508 
509   template<typename _Key, typename _Compare, typename _Allocator>
510     inline bool
511     operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
512 	       const multiset<_Key, _Compare, _Allocator>& __rhs)
513     { return !(__lhs == __rhs); }
514 
515   template<typename _Key, typename _Compare, typename _Allocator>
516     inline bool
517     operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
518 	       const multiset<_Key, _Compare, _Allocator>& __rhs)
519     { return !(__rhs < __lhs); }
520 
521   template<typename _Key, typename _Compare, typename _Allocator>
522     inline bool
523     operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
524 	       const multiset<_Key, _Compare, _Allocator>& __rhs)
525     { return !(__lhs < __rhs); }
526 
527   template<typename _Key, typename _Compare, typename _Allocator>
528     inline bool
529     operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
530 	      const multiset<_Key, _Compare, _Allocator>& __rhs)
531     { return __rhs < __lhs; }
532 
533   template<typename _Key, typename _Compare, typename _Allocator>
534     void
535     swap(multiset<_Key, _Compare, _Allocator>& __x,
536 	 multiset<_Key, _Compare, _Allocator>& __y)
537     { return __x.swap(__y); }
538 
539 } // namespace __profile
540 } // namespace std
541 
542 #endif
543