1 // Profiling unordered_set/unordered_multiset implementation -*- C++ -*-
3 // Copyright (C) 2009, 2010 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 #ifndef __GXX_EXPERIMENTAL_CXX0X__
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 typename _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 _Base& __x)
95 __profcxx_hashtable_construct(this, _Base::bucket_count());
96 __profcxx_hashtable_construct2(this);
99 unordered_set(unordered_set&& __x)
100 : _Base(std::move(__x))
102 __profcxx_hashtable_construct(this, _Base::bucket_count());
103 __profcxx_hashtable_construct2(this);
106 unordered_set(initializer_list<value_type> __l,
108 const hasher& __hf = hasher(),
109 const key_equal& __eql = key_equal(),
110 const allocator_type& __a = allocator_type())
111 : _Base(__l, __n, __hf, __eql, __a) { }
114 operator=(const unordered_set& __x)
116 *static_cast<_Base*>(this) = __x;
121 operator=(unordered_set&& __x)
131 operator=(initializer_list<value_type> __l)
140 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
142 _M_profile_destruct();
146 swap(unordered_set& __x)
154 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
156 _M_profile_destruct();
161 insert(std::initializer_list<value_type> __l)
163 size_type __old_size = _Base::bucket_count();
165 _M_profile_resize(__old_size, _Base::bucket_count());
168 std::pair<iterator, bool>
169 insert(const value_type& __obj)
171 size_type __old_size = _Base::bucket_count();
172 std::pair<iterator, bool> __res = _Base::insert(__obj);
173 _M_profile_resize(__old_size, _Base::bucket_count());
178 insert(const_iterator __iter, const value_type& __v)
180 size_type __old_size = _Base::bucket_count();
181 iterator __res = _Base::insert(__iter, __v);
182 _M_profile_resize(__old_size, _Base::bucket_count());
186 std::pair<iterator, bool>
187 insert(value_type&& __obj)
189 size_type __old_size = _Base::bucket_count();
190 std::pair<iterator, bool> __res = _Base::insert(std::move(__obj));
191 _M_profile_resize(__old_size, _Base::bucket_count());
196 insert(const_iterator __iter, value_type&& __v)
198 size_type __old_size = _Base::bucket_count();
199 iterator __res = _Base::insert(__iter, std::move(__v));
200 _M_profile_resize(__old_size, _Base::bucket_count());
204 template<typename _InputIter>
206 insert(_InputIter __first, _InputIter __last)
208 size_type __old_size = _Base::bucket_count();
209 _Base::insert(__first, __last);
210 _M_profile_resize(__old_size, _Base::bucket_count());
214 insert(const value_type* __first, const value_type* __last)
216 size_type __old_size = _Base::bucket_count();
217 _Base::insert(__first, __last);
218 _M_profile_resize(__old_size, _Base::bucket_count());
221 void rehash(size_type __n)
223 size_type __old_size = _Base::bucket_count();
225 _M_profile_resize(__old_size, _Base::bucket_count());
230 _M_base() { return *this; }
233 _M_base() const { return *this; }
236 _M_profile_resize(size_type __old_size, size_type __new_size)
238 if (__old_size != __new_size)
239 __profcxx_hashtable_resize(this, __old_size, __new_size);
243 _M_profile_destruct()
245 size_type __hops = 0, __lc = 0, __chain = 0;
246 for (iterator __it = _M_base().begin(); __it != _M_base().end();
249 while (__it._M_cur_node->_M_next)
258 __lc = __lc > __chain ? __lc : __chain;
259 __hops += __chain * (__chain - 1) / 2;
263 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
268 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
270 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
271 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
274 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
276 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
277 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
278 { return __x._M_equal(__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 == __y); }
287 #undef _GLIBCXX_STD_BASE
288 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
289 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
291 /** @brief Unordered_multiset wrapper with performance instrumentation. */
292 template<typename _Value,
293 typename _Hash = std::hash<_Value>,
294 typename _Pred = std::equal_to<_Value>,
295 typename _Alloc = std::allocator<_Value> >
296 class unordered_multiset
297 : public _GLIBCXX_STD_BASE
299 typedef typename _GLIBCXX_STD_BASE _Base;
302 typedef typename _Base::size_type size_type;
303 typedef typename _Base::hasher hasher;
304 typedef typename _Base::key_equal key_equal;
305 typedef typename _Base::allocator_type allocator_type;
306 typedef typename _Base::key_type key_type;
307 typedef typename _Base::value_type value_type;
308 typedef typename _Base::difference_type difference_type;
309 typedef typename _Base::reference reference;
310 typedef typename _Base::const_reference const_reference;
312 typedef typename _Base::iterator iterator;
313 typedef typename _Base::const_iterator const_iterator;
316 unordered_multiset(size_type __n = 10,
317 const hasher& __hf = hasher(),
318 const key_equal& __eql = key_equal(),
319 const allocator_type& __a = allocator_type())
320 : _Base(__n, __hf, __eql, __a)
322 __profcxx_hashtable_construct(this, _Base::bucket_count());
325 template<typename _InputIterator>
326 unordered_multiset(_InputIterator __f, _InputIterator __l,
328 const hasher& __hf = hasher(),
329 const key_equal& __eql = key_equal(),
330 const allocator_type& __a = allocator_type())
331 : _Base(__f, __l, __n, __hf, __eql, __a)
333 __profcxx_hashtable_construct(this, _Base::bucket_count());
336 unordered_multiset(const _Base& __x)
339 __profcxx_hashtable_construct(this, _Base::bucket_count());
342 unordered_multiset(unordered_multiset&& __x)
343 : _Base(std::move(__x))
345 __profcxx_hashtable_construct(this, _Base::bucket_count());
348 unordered_multiset(initializer_list<value_type> __l,
350 const hasher& __hf = hasher(),
351 const key_equal& __eql = key_equal(),
352 const allocator_type& __a = allocator_type())
353 : _Base(__l, __n, __hf, __eql, __a) { }
356 operator=(const unordered_multiset& __x)
358 *static_cast<_Base*>(this) = __x;
363 operator=(unordered_multiset&& __x)
373 operator=(initializer_list<value_type> __l)
380 ~unordered_multiset()
382 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
384 _M_profile_destruct();
388 swap(unordered_multiset& __x)
396 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
398 _M_profile_destruct();
403 insert(std::initializer_list<value_type> __l)
405 size_type __old_size = _Base::bucket_count();
407 _M_profile_resize(__old_size, _Base::bucket_count());
411 insert(const value_type& __obj)
413 size_type __old_size = _Base::bucket_count();
414 iterator __res = _Base::insert(__obj);
415 _M_profile_resize(__old_size, _Base::bucket_count());
420 insert(const_iterator __iter, const value_type& __v)
422 size_type __old_size = _Base::bucket_count();
423 iterator __res = _Base::insert(__iter, __v);
424 _M_profile_resize(__old_size, _Base::bucket_count());
429 insert(value_type&& __obj)
431 size_type __old_size = _Base::bucket_count();
432 iterator __res = _Base::insert(std::move(__obj));
433 _M_profile_resize(__old_size, _Base::bucket_count());
438 insert(const_iterator __iter, value_type&& __v)
440 size_type __old_size = _Base::bucket_count();
441 iterator __res = _Base::insert(__iter, std::move(__v));
442 _M_profile_resize(__old_size, _Base::bucket_count());
446 template<typename _InputIter>
448 insert(_InputIter __first, _InputIter __last)
450 size_type __old_size = _Base::bucket_count();
451 _Base::insert(__first, __last);
452 _M_profile_resize(__old_size, _Base::bucket_count());
456 insert(const value_type* __first, const value_type* __last)
458 size_type __old_size = _Base::bucket_count();
459 _Base::insert(__first, __last);
460 _M_profile_resize(__old_size, _Base::bucket_count());
463 void rehash(size_type __n)
465 size_type __old_size = _Base::bucket_count();
467 _M_profile_resize(__old_size, _Base::bucket_count());
472 _M_base() { return *this; }
475 _M_base() const { return *this; }
478 _M_profile_resize(size_type __old_size, size_type __new_size)
480 if (__old_size != __new_size)
481 __profcxx_hashtable_resize(this, __old_size, __new_size);
485 _M_profile_destruct()
487 size_type __hops = 0, __lc = 0, __chain = 0;
488 for (iterator __it = _M_base().begin(); __it != _M_base().end();
491 while (__it._M_cur_node->_M_next)
500 __lc = __lc > __chain ? __lc : __chain;
501 __hops += __chain * (__chain - 1) / 2;
505 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
510 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
512 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
513 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
516 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
518 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
519 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
520 { return __x._M_equal(__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 == __y); }
528 } // namespace __profile
532 #undef _GLIBCXX_STD_BASE
534 #endif // __GXX_EXPERIMENTAL_CXX0X__