1 // Profiling unordered_set/unordered_multiset implementation -*- C++ -*-
3 // Copyright (C) 2009, 2010, 2011 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 2, 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 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
30 /** @file profile/unordered_set
31 * This file is a GNU profile extension to the Standard C++ Library.
34 #ifndef _GLIBCXX_PROFILE_UNORDERED_SET
35 #define _GLIBCXX_PROFILE_UNORDERED_SET 1
37 #ifndef __GXX_EXPERIMENTAL_CXX0X__
38 # include <bits/c++0x_warning.h>
40 # include <unordered_set>
42 #include <profile/base.h>
44 #define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc>
45 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
47 namespace std _GLIBCXX_VISIBILITY(default)
51 /** @brief Unordered_set wrapper with performance instrumentation. */
52 template<typename _Key,
53 typename _Hash = std::hash<_Key>,
54 typename _Pred = std::equal_to<_Key>,
55 typename _Alloc = std::allocator<_Key> >
57 : public _GLIBCXX_STD_BASE
59 typedef typename _GLIBCXX_STD_BASE _Base;
62 typedef typename _Base::size_type size_type;
63 typedef typename _Base::hasher hasher;
64 typedef typename _Base::key_equal key_equal;
65 typedef typename _Base::allocator_type allocator_type;
66 typedef typename _Base::key_type key_type;
67 typedef typename _Base::value_type value_type;
68 typedef typename _Base::difference_type difference_type;
69 typedef typename _Base::reference reference;
70 typedef typename _Base::const_reference const_reference;
72 typedef typename _Base::iterator iterator;
73 typedef typename _Base::const_iterator const_iterator;
76 unordered_set(size_type __n = 10,
77 const hasher& __hf = hasher(),
78 const key_equal& __eql = key_equal(),
79 const allocator_type& __a = allocator_type())
80 : _Base(__n, __hf, __eql, __a)
82 __profcxx_hashtable_construct(this, _Base::bucket_count());
83 __profcxx_hashtable_construct2(this);
86 template<typename _InputIterator>
87 unordered_set(_InputIterator __f, _InputIterator __l,
89 const hasher& __hf = hasher(),
90 const key_equal& __eql = key_equal(),
91 const allocator_type& __a = allocator_type())
92 : _Base(__f, __l, __n, __hf, __eql, __a)
94 __profcxx_hashtable_construct(this, _Base::bucket_count());
95 __profcxx_hashtable_construct2(this);
98 unordered_set(const _Base& __x)
101 __profcxx_hashtable_construct(this, _Base::bucket_count());
102 __profcxx_hashtable_construct2(this);
105 unordered_set(unordered_set&& __x)
106 : _Base(std::move(__x))
108 __profcxx_hashtable_construct(this, _Base::bucket_count());
109 __profcxx_hashtable_construct2(this);
112 unordered_set(initializer_list<value_type> __l,
114 const hasher& __hf = hasher(),
115 const key_equal& __eql = key_equal(),
116 const allocator_type& __a = allocator_type())
117 : _Base(__l, __n, __hf, __eql, __a) { }
120 operator=(const unordered_set& __x)
122 *static_cast<_Base*>(this) = __x;
127 operator=(unordered_set&& __x)
137 operator=(initializer_list<value_type> __l)
144 ~unordered_set() noexcept
146 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
148 _M_profile_destruct();
152 swap(unordered_set& __x)
160 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
162 _M_profile_destruct();
167 insert(std::initializer_list<value_type> __l)
169 size_type __old_size = _Base::bucket_count();
171 _M_profile_resize(__old_size, _Base::bucket_count());
174 std::pair<iterator, bool>
175 insert(const value_type& __obj)
177 size_type __old_size = _Base::bucket_count();
178 std::pair<iterator, bool> __res = _Base::insert(__obj);
179 _M_profile_resize(__old_size, _Base::bucket_count());
184 insert(const_iterator __iter, const value_type& __v)
186 size_type __old_size = _Base::bucket_count();
187 iterator __res = _Base::insert(__iter, __v);
188 _M_profile_resize(__old_size, _Base::bucket_count());
192 std::pair<iterator, bool>
193 insert(value_type&& __obj)
195 size_type __old_size = _Base::bucket_count();
196 std::pair<iterator, bool> __res = _Base::insert(std::move(__obj));
197 _M_profile_resize(__old_size, _Base::bucket_count());
202 insert(const_iterator __iter, value_type&& __v)
204 size_type __old_size = _Base::bucket_count();
205 iterator __res = _Base::insert(__iter, std::move(__v));
206 _M_profile_resize(__old_size, _Base::bucket_count());
210 template<typename _InputIter>
212 insert(_InputIter __first, _InputIter __last)
214 size_type __old_size = _Base::bucket_count();
215 _Base::insert(__first, __last);
216 _M_profile_resize(__old_size, _Base::bucket_count());
220 insert(const value_type* __first, const value_type* __last)
222 size_type __old_size = _Base::bucket_count();
223 _Base::insert(__first, __last);
224 _M_profile_resize(__old_size, _Base::bucket_count());
227 void rehash(size_type __n)
229 size_type __old_size = _Base::bucket_count();
231 _M_profile_resize(__old_size, _Base::bucket_count());
236 _M_base() noexcept { return *this; }
239 _M_base() const noexcept { return *this; }
242 _M_profile_resize(size_type __old_size, size_type __new_size)
244 if (__old_size != __new_size)
245 __profcxx_hashtable_resize(this, __old_size, __new_size);
249 _M_profile_destruct()
251 size_type __hops = 0, __lc = 0, __chain = 0;
252 for (iterator __it = _M_base().begin(); __it != _M_base().end();
255 while (__it._M_cur_node->_M_next)
264 __lc = __lc > __chain ? __lc : __chain;
265 __hops += __chain * (__chain - 1) / 2;
269 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
274 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
276 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
277 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
280 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
282 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
283 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
284 { return __x._M_equal(__y); }
286 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
288 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
289 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
290 { return !(__x == __y); }
293 #undef _GLIBCXX_STD_BASE
294 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
295 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
297 /** @brief Unordered_multiset wrapper with performance instrumentation. */
298 template<typename _Value,
299 typename _Hash = std::hash<_Value>,
300 typename _Pred = std::equal_to<_Value>,
301 typename _Alloc = std::allocator<_Value> >
302 class unordered_multiset
303 : public _GLIBCXX_STD_BASE
305 typedef typename _GLIBCXX_STD_BASE _Base;
308 typedef typename _Base::size_type size_type;
309 typedef typename _Base::hasher hasher;
310 typedef typename _Base::key_equal key_equal;
311 typedef typename _Base::allocator_type allocator_type;
312 typedef typename _Base::key_type key_type;
313 typedef typename _Base::value_type value_type;
314 typedef typename _Base::difference_type difference_type;
315 typedef typename _Base::reference reference;
316 typedef typename _Base::const_reference const_reference;
318 typedef typename _Base::iterator iterator;
319 typedef typename _Base::const_iterator const_iterator;
322 unordered_multiset(size_type __n = 10,
323 const hasher& __hf = hasher(),
324 const key_equal& __eql = key_equal(),
325 const allocator_type& __a = allocator_type())
326 : _Base(__n, __hf, __eql, __a)
328 __profcxx_hashtable_construct(this, _Base::bucket_count());
331 template<typename _InputIterator>
332 unordered_multiset(_InputIterator __f, _InputIterator __l,
334 const hasher& __hf = hasher(),
335 const key_equal& __eql = key_equal(),
336 const allocator_type& __a = allocator_type())
337 : _Base(__f, __l, __n, __hf, __eql, __a)
339 __profcxx_hashtable_construct(this, _Base::bucket_count());
342 unordered_multiset(const _Base& __x)
345 __profcxx_hashtable_construct(this, _Base::bucket_count());
348 unordered_multiset(unordered_multiset&& __x)
349 : _Base(std::move(__x))
351 __profcxx_hashtable_construct(this, _Base::bucket_count());
354 unordered_multiset(initializer_list<value_type> __l,
356 const hasher& __hf = hasher(),
357 const key_equal& __eql = key_equal(),
358 const allocator_type& __a = allocator_type())
359 : _Base(__l, __n, __hf, __eql, __a) { }
362 operator=(const unordered_multiset& __x)
364 *static_cast<_Base*>(this) = __x;
369 operator=(unordered_multiset&& __x)
379 operator=(initializer_list<value_type> __l)
386 ~unordered_multiset() noexcept
388 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
390 _M_profile_destruct();
394 swap(unordered_multiset& __x)
402 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
404 _M_profile_destruct();
409 insert(std::initializer_list<value_type> __l)
411 size_type __old_size = _Base::bucket_count();
413 _M_profile_resize(__old_size, _Base::bucket_count());
417 insert(const value_type& __obj)
419 size_type __old_size = _Base::bucket_count();
420 iterator __res = _Base::insert(__obj);
421 _M_profile_resize(__old_size, _Base::bucket_count());
426 insert(const_iterator __iter, const value_type& __v)
428 size_type __old_size = _Base::bucket_count();
429 iterator __res = _Base::insert(__iter, __v);
430 _M_profile_resize(__old_size, _Base::bucket_count());
435 insert(value_type&& __obj)
437 size_type __old_size = _Base::bucket_count();
438 iterator __res = _Base::insert(std::move(__obj));
439 _M_profile_resize(__old_size, _Base::bucket_count());
444 insert(const_iterator __iter, value_type&& __v)
446 size_type __old_size = _Base::bucket_count();
447 iterator __res = _Base::insert(__iter, std::move(__v));
448 _M_profile_resize(__old_size, _Base::bucket_count());
452 template<typename _InputIter>
454 insert(_InputIter __first, _InputIter __last)
456 size_type __old_size = _Base::bucket_count();
457 _Base::insert(__first, __last);
458 _M_profile_resize(__old_size, _Base::bucket_count());
462 insert(const value_type* __first, const value_type* __last)
464 size_type __old_size = _Base::bucket_count();
465 _Base::insert(__first, __last);
466 _M_profile_resize(__old_size, _Base::bucket_count());
469 void rehash(size_type __n)
471 size_type __old_size = _Base::bucket_count();
473 _M_profile_resize(__old_size, _Base::bucket_count());
478 _M_base() noexcept { return *this; }
481 _M_base() const noexcept { return *this; }
484 _M_profile_resize(size_type __old_size, size_type __new_size)
486 if (__old_size != __new_size)
487 __profcxx_hashtable_resize(this, __old_size, __new_size);
491 _M_profile_destruct()
493 size_type __hops = 0, __lc = 0, __chain = 0;
494 for (iterator __it = _M_base().begin(); __it != _M_base().end();
497 while (__it._M_cur_node->_M_next)
506 __lc = __lc > __chain ? __lc : __chain;
507 __hops += __chain * (__chain - 1) / 2;
511 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
516 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
518 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
519 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
522 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
524 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
525 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
526 { return __x._M_equal(__y); }
528 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
530 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
531 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
532 { return !(__x == __y); }
534 } // namespace __profile
538 #undef _GLIBCXX_STD_BASE
540 #endif // __GXX_EXPERIMENTAL_CXX0X__