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 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_PR::_GLIBCXX_BASE
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::forward<_Base>(__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)
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 template<typename _InputIter>
194 insert(_InputIter __first, _InputIter __last)
196 size_type __old_size = _Base::bucket_count();
197 _Base::insert(__first, __last);
198 _M_profile_resize(__old_size, _Base::bucket_count());
202 insert(const value_type* __first, const value_type* __last)
204 size_type __old_size = _Base::bucket_count();
205 _Base::insert(__first, __last);
206 _M_profile_resize(__old_size, _Base::bucket_count());
209 void rehash(size_type __n)
211 size_type __old_size = _Base::bucket_count();
213 _M_profile_resize(__old_size, _Base::bucket_count());
218 _M_base() { return *this; }
221 _M_base() const { return *this; }
224 _M_profile_resize(size_type __old_size, size_type __new_size)
226 if (__old_size != __new_size)
227 __profcxx_hashtable_resize(this, __old_size, __new_size);
231 _M_profile_destruct()
233 size_type __hops = 0, __lc = 0, __chain = 0;
234 for (iterator __it = _M_base().begin(); __it != _M_base().end();
237 while (__it._M_cur_node->_M_next)
246 __lc = __lc > __chain ? __lc : __chain;
247 __hops += __chain * (__chain - 1) / 2;
251 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
256 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
258 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
259 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
262 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
264 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
265 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
266 { return __x._M_equal(__y); }
268 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
270 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
271 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
272 { return !(__x == __y); }
275 #undef _GLIBCXX_STD_BASE
276 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE
277 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
279 /** @brief Unordered_multiset wrapper with performance instrumentation. */
280 template<typename _Value,
281 typename _Hash = std::hash<_Value>,
282 typename _Pred = std::equal_to<_Value>,
283 typename _Alloc = std::allocator<_Value> >
284 class unordered_multiset
285 : public _GLIBCXX_STD_BASE
287 typedef typename _GLIBCXX_STD_BASE _Base;
290 typedef typename _Base::size_type size_type;
291 typedef typename _Base::hasher hasher;
292 typedef typename _Base::key_equal key_equal;
293 typedef typename _Base::allocator_type allocator_type;
294 typedef typename _Base::key_type key_type;
295 typedef typename _Base::value_type value_type;
296 typedef typename _Base::difference_type difference_type;
297 typedef typename _Base::reference reference;
298 typedef typename _Base::const_reference const_reference;
300 typedef typename _Base::iterator iterator;
301 typedef typename _Base::const_iterator const_iterator;
304 unordered_multiset(size_type __n = 10,
305 const hasher& __hf = hasher(),
306 const key_equal& __eql = key_equal(),
307 const allocator_type& __a = allocator_type())
308 : _Base(__n, __hf, __eql, __a)
310 __profcxx_hashtable_construct(this, _Base::bucket_count());
313 template<typename _InputIterator>
314 unordered_multiset(_InputIterator __f, _InputIterator __l,
316 const hasher& __hf = hasher(),
317 const key_equal& __eql = key_equal(),
318 const allocator_type& __a = allocator_type())
319 : _Base(__f, __l, __n, __hf, __eql, __a)
321 __profcxx_hashtable_construct(this, _Base::bucket_count());
324 unordered_multiset(const _Base& __x)
327 __profcxx_hashtable_construct(this, _Base::bucket_count());
330 unordered_multiset(unordered_multiset&& __x)
331 : _Base(std::forward<_Base>(__x))
333 __profcxx_hashtable_construct(this, _Base::bucket_count());
336 unordered_multiset(initializer_list<value_type> __l,
338 const hasher& __hf = hasher(),
339 const key_equal& __eql = key_equal(),
340 const allocator_type& __a = allocator_type())
341 : _Base(__l, __n, __hf, __eql, __a) { }
344 operator=(const unordered_multiset& __x)
346 *static_cast<_Base*>(this) = __x;
351 operator=(unordered_multiset&& __x)
361 operator=(initializer_list<value_type> __l)
368 ~unordered_multiset()
370 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
372 _M_profile_destruct();
376 swap(unordered_multiset& __x)
384 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
386 _M_profile_destruct();
391 insert(std::initializer_list<value_type> __l)
393 size_type __old_size = _Base::bucket_count();
395 _M_profile_resize(__old_size, _Base::bucket_count());
399 insert(const value_type& __obj)
401 size_type __old_size = _Base::bucket_count();
402 iterator __res = _Base::insert(__obj);
403 _M_profile_resize(__old_size, _Base::bucket_count());
408 insert(const_iterator __iter, const value_type& __v)
410 size_type __old_size = _Base::bucket_count();
411 iterator __res = _Base::insert(__iter, __v);
412 _M_profile_resize(__old_size, _Base::bucket_count());
416 template<typename _InputIter>
418 insert(_InputIter __first, _InputIter __last)
420 size_type __old_size = _Base::bucket_count();
421 _Base::insert(__first, __last);
422 _M_profile_resize(__old_size, _Base::bucket_count());
426 insert(const value_type* __first, const value_type* __last)
428 size_type __old_size = _Base::bucket_count();
429 _Base::insert(__first, __last);
430 _M_profile_resize(__old_size, _Base::bucket_count());
433 void rehash(size_type __n)
435 size_type __old_size = _Base::bucket_count();
437 _M_profile_resize(__old_size, _Base::bucket_count());
442 _M_base() { return *this; }
445 _M_base() const { return *this; }
448 _M_profile_resize(size_type __old_size, size_type __new_size)
450 if (__old_size != __new_size)
451 __profcxx_hashtable_resize(this, __old_size, __new_size);
455 _M_profile_destruct()
457 size_type __hops = 0, __lc = 0, __chain = 0;
458 for (iterator __it = _M_base().begin(); __it != _M_base().end();
461 while (__it._M_cur_node->_M_next)
470 __lc = __lc > __chain ? __lc : __chain;
471 __hops += __chain * (__chain - 1) / 2;
475 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
480 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
482 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
483 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
486 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
488 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
489 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
490 { return __x._M_equal(__y); }
492 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
494 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
495 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
496 { return !(__x == __y); }
498 } // namespace __profile
502 #undef _GLIBCXX_STD_BASE
504 #endif // __GXX_EXPERIMENTAL_CXX0X__