1 // Profiling unordered_set/unordered_multiset implementation -*- C++ -*-
3 // Copyright (C) 2009-2013 Free Software Foundation, Inc.
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)
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.
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.
20 // You should have received a copy of the GNU General Public License along
21 // with this library; see the file COPYING3. If not see
22 // <http://www.gnu.org/licenses/>.
24 /** @file profile/unordered_set
25 * This file is a GNU profile extension to the Standard C++ Library.
28 #ifndef _GLIBCXX_PROFILE_UNORDERED_SET
29 #define _GLIBCXX_PROFILE_UNORDERED_SET 1
31 #if __cplusplus < 201103L
32 # include <bits/c++0x_warning.h>
34 # include <unordered_set>
36 #include <profile/base.h>
38 #define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc>
39 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
41 namespace std _GLIBCXX_VISIBILITY(default)
45 /** @brief Unordered_set wrapper with performance instrumentation. */
46 template<typename _Key,
47 typename _Hash = std::hash<_Key>,
48 typename _Pred = std::equal_to<_Key>,
49 typename _Alloc = std::allocator<_Key> >
51 : public _GLIBCXX_STD_BASE
53 typedef _GLIBCXX_STD_BASE _Base;
56 typedef typename _Base::size_type size_type;
57 typedef typename _Base::hasher hasher;
58 typedef typename _Base::key_equal key_equal;
59 typedef typename _Base::allocator_type allocator_type;
60 typedef typename _Base::key_type key_type;
61 typedef typename _Base::value_type value_type;
62 typedef typename _Base::difference_type difference_type;
63 typedef typename _Base::reference reference;
64 typedef typename _Base::const_reference const_reference;
66 typedef typename _Base::iterator iterator;
67 typedef typename _Base::const_iterator const_iterator;
70 unordered_set(size_type __n = 10,
71 const hasher& __hf = hasher(),
72 const key_equal& __eql = key_equal(),
73 const allocator_type& __a = allocator_type())
74 : _Base(__n, __hf, __eql, __a)
76 __profcxx_hashtable_construct(this, _Base::bucket_count());
77 __profcxx_hashtable_construct2(this);
80 template<typename _InputIterator>
81 unordered_set(_InputIterator __f, _InputIterator __l,
83 const hasher& __hf = hasher(),
84 const key_equal& __eql = key_equal(),
85 const allocator_type& __a = allocator_type())
86 : _Base(__f, __l, __n, __hf, __eql, __a)
88 __profcxx_hashtable_construct(this, _Base::bucket_count());
89 __profcxx_hashtable_construct2(this);
92 unordered_set(const unordered_set& __x)
95 __profcxx_hashtable_construct(this, _Base::bucket_count());
96 __profcxx_hashtable_construct2(this);
99 unordered_set(const _Base& __x)
102 __profcxx_hashtable_construct(this, _Base::bucket_count());
103 __profcxx_hashtable_construct2(this);
106 unordered_set(unordered_set&& __x)
107 : _Base(std::move(__x))
109 __profcxx_hashtable_construct(this, _Base::bucket_count());
110 __profcxx_hashtable_construct2(this);
113 unordered_set(initializer_list<value_type> __l,
115 const hasher& __hf = hasher(),
116 const key_equal& __eql = key_equal(),
117 const allocator_type& __a = allocator_type())
118 : _Base(__l, __n, __hf, __eql, __a) { }
121 operator=(const unordered_set& __x)
123 *static_cast<_Base*>(this) = __x;
128 operator=(unordered_set&& __x)
138 operator=(initializer_list<value_type> __l)
145 ~unordered_set() noexcept
147 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
149 _M_profile_destruct();
153 swap(unordered_set& __x)
161 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
163 _M_profile_destruct();
167 template<typename... _Args>
168 std::pair<iterator, bool>
169 emplace(_Args&&... __args)
171 size_type __old_size = _Base::bucket_count();
172 std::pair<iterator, bool> __res
173 = _Base::emplace(std::forward<_Args>(__args)...);
174 _M_profile_resize(__old_size);
178 template<typename... _Args>
180 emplace_hint(const_iterator __it, _Args&&... __args)
182 size_type __old_size = _Base::bucket_count();
184 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
185 _M_profile_resize(__old_size);
190 insert(std::initializer_list<value_type> __l)
192 size_type __old_size = _Base::bucket_count();
194 _M_profile_resize(__old_size);
197 std::pair<iterator, bool>
198 insert(const value_type& __obj)
200 size_type __old_size = _Base::bucket_count();
201 std::pair<iterator, bool> __res = _Base::insert(__obj);
202 _M_profile_resize(__old_size);
207 insert(const_iterator __iter, const value_type& __v)
209 size_type __old_size = _Base::bucket_count();
210 iterator __res = _Base::insert(__iter, __v);
211 _M_profile_resize(__old_size);
215 std::pair<iterator, bool>
216 insert(value_type&& __obj)
218 size_type __old_size = _Base::bucket_count();
219 std::pair<iterator, bool> __res = _Base::insert(std::move(__obj));
220 _M_profile_resize(__old_size);
225 insert(const_iterator __iter, value_type&& __v)
227 size_type __old_size = _Base::bucket_count();
228 iterator __res = _Base::insert(__iter, std::move(__v));
229 _M_profile_resize(__old_size);
233 template<typename _InputIter>
235 insert(_InputIter __first, _InputIter __last)
237 size_type __old_size = _Base::bucket_count();
238 _Base::insert(__first, __last);
239 _M_profile_resize(__old_size);
243 insert(const value_type* __first, const value_type* __last)
245 size_type __old_size = _Base::bucket_count();
246 _Base::insert(__first, __last);
247 _M_profile_resize(__old_size);
250 void rehash(size_type __n)
252 size_type __old_size = _Base::bucket_count();
254 _M_profile_resize(__old_size);
259 _M_profile_resize(size_type __old_size)
261 size_type __new_size = _Base::bucket_count();
262 if (__old_size != __new_size)
263 __profcxx_hashtable_resize(this, __old_size, __new_size);
267 _M_profile_destruct()
269 size_type __hops = 0, __lc = 0, __chain = 0;
270 iterator __it = this->begin();
271 while (__it != this->end())
273 size_type __bkt = this->bucket(*__it);
274 auto __lit = this->begin(__bkt);
275 auto __lend = this->end(__bkt);
276 for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
281 __lc = __lc > __chain ? __lc : __chain;
282 __hops += __chain * (__chain - 1) / 2;
286 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
290 template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
292 swap(unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
293 unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
296 template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
298 operator==(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
299 const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
300 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
302 template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
304 operator!=(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
305 const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
306 { return !(__x == __y); }
309 #undef _GLIBCXX_STD_BASE
310 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
311 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
313 /** @brief Unordered_multiset wrapper with performance instrumentation. */
314 template<typename _Value,
315 typename _Hash = std::hash<_Value>,
316 typename _Pred = std::equal_to<_Value>,
317 typename _Alloc = std::allocator<_Value> >
318 class unordered_multiset
319 : public _GLIBCXX_STD_BASE
321 typedef _GLIBCXX_STD_BASE _Base;
324 typedef typename _Base::size_type size_type;
325 typedef typename _Base::hasher hasher;
326 typedef typename _Base::key_equal key_equal;
327 typedef typename _Base::allocator_type allocator_type;
328 typedef typename _Base::key_type key_type;
329 typedef typename _Base::value_type value_type;
330 typedef typename _Base::difference_type difference_type;
331 typedef typename _Base::reference reference;
332 typedef typename _Base::const_reference const_reference;
334 typedef typename _Base::iterator iterator;
335 typedef typename _Base::const_iterator const_iterator;
338 unordered_multiset(size_type __n = 10,
339 const hasher& __hf = hasher(),
340 const key_equal& __eql = key_equal(),
341 const allocator_type& __a = allocator_type())
342 : _Base(__n, __hf, __eql, __a)
344 __profcxx_hashtable_construct(this, _Base::bucket_count());
347 template<typename _InputIterator>
348 unordered_multiset(_InputIterator __f, _InputIterator __l,
350 const hasher& __hf = hasher(),
351 const key_equal& __eql = key_equal(),
352 const allocator_type& __a = allocator_type())
353 : _Base(__f, __l, __n, __hf, __eql, __a)
355 __profcxx_hashtable_construct(this, _Base::bucket_count());
358 unordered_multiset(const unordered_multiset& __x)
361 __profcxx_hashtable_construct(this, _Base::bucket_count());
364 unordered_multiset(const _Base& __x)
367 __profcxx_hashtable_construct(this, _Base::bucket_count());
370 unordered_multiset(unordered_multiset&& __x)
371 : _Base(std::move(__x))
373 __profcxx_hashtable_construct(this, _Base::bucket_count());
376 unordered_multiset(initializer_list<value_type> __l,
378 const hasher& __hf = hasher(),
379 const key_equal& __eql = key_equal(),
380 const allocator_type& __a = allocator_type())
381 : _Base(__l, __n, __hf, __eql, __a) { }
384 operator=(const unordered_multiset& __x)
386 *static_cast<_Base*>(this) = __x;
391 operator=(unordered_multiset&& __x)
401 operator=(initializer_list<value_type> __l)
408 ~unordered_multiset() noexcept
410 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
412 _M_profile_destruct();
416 swap(unordered_multiset& __x)
424 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
426 _M_profile_destruct();
430 template<typename... _Args>
432 emplace(_Args&&... __args)
434 size_type __old_size = _Base::bucket_count();
435 iterator __res = _Base::emplace(std::forward<_Args>(__args)...);
436 _M_profile_resize(__old_size);
440 template<typename... _Args>
442 emplace_hint(const_iterator __it, _Args&&... __args)
444 size_type __old_size = _Base::bucket_count();
446 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
447 _M_profile_resize(__old_size);
452 insert(std::initializer_list<value_type> __l)
454 size_type __old_size = _Base::bucket_count();
456 _M_profile_resize(__old_size);
460 insert(const value_type& __obj)
462 size_type __old_size = _Base::bucket_count();
463 iterator __res = _Base::insert(__obj);
464 _M_profile_resize(__old_size);
469 insert(const_iterator __iter, const value_type& __v)
471 size_type __old_size = _Base::bucket_count();
472 iterator __res = _Base::insert(__iter, __v);
473 _M_profile_resize(__old_size);
478 insert(value_type&& __obj)
480 size_type __old_size = _Base::bucket_count();
481 iterator __res = _Base::insert(std::move(__obj));
482 _M_profile_resize(__old_size);
487 insert(const_iterator __iter, value_type&& __v)
489 size_type __old_size = _Base::bucket_count();
490 iterator __res = _Base::insert(__iter, std::move(__v));
491 _M_profile_resize(__old_size);
495 template<typename _InputIter>
497 insert(_InputIter __first, _InputIter __last)
499 size_type __old_size = _Base::bucket_count();
500 _Base::insert(__first, __last);
501 _M_profile_resize(__old_size);
505 insert(const value_type* __first, const value_type* __last)
507 size_type __old_size = _Base::bucket_count();
508 _Base::insert(__first, __last);
509 _M_profile_resize(__old_size);
512 void rehash(size_type __n)
514 size_type __old_size = _Base::bucket_count();
516 _M_profile_resize(__old_size);
521 _M_profile_resize(size_type __old_size)
523 size_type __new_size = _Base::bucket_count();
524 if (__old_size != __new_size)
525 __profcxx_hashtable_resize(this, __old_size, __new_size);
529 _M_profile_destruct()
531 size_type __hops = 0, __lc = 0, __chain = 0;
532 iterator __it = this->begin();
533 while (__it != this->end())
535 size_type __bkt = this->bucket(*__it);
536 auto __lit = this->begin(__bkt);
537 auto __lend = this->end(__bkt);
538 for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
543 __lc = __lc > __chain ? __lc : __chain;
544 __hops += __chain * (__chain - 1) / 2;
548 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
552 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
554 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
555 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
558 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
560 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
561 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
562 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
564 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
566 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
567 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
568 { return !(__x == __y); }
570 } // namespace __profile
574 #undef _GLIBCXX_STD_BASE