libstdc++
profile/unordered_set
1 // Profiling unordered_set/unordered_multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2009-2013 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 along
21 // with this library; see the file COPYING3. If not see
22 // <http://www.gnu.org/licenses/>.
23 
24 /** @file profile/unordered_set
25  * This file is a GNU profile extension to the Standard C++ Library.
26  */
27 
28 #ifndef _GLIBCXX_PROFILE_UNORDERED_SET
29 #define _GLIBCXX_PROFILE_UNORDERED_SET 1
30 
31 #if __cplusplus < 201103L
32 # include <bits/c++0x_warning.h>
33 #else
34 # include <unordered_set>
35 
36 #include <profile/base.h>
37 #include <profile/unordered_base.h>
38 
39 #define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc>
40 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
41 
42 namespace std _GLIBCXX_VISIBILITY(default)
43 {
44 namespace __profile
45 {
46  /** @brief Unordered_set wrapper with performance instrumentation. */
47  template<typename _Key,
48  typename _Hash = std::hash<_Key>,
49  typename _Pred = std::equal_to<_Key>,
50  typename _Alloc = std::allocator<_Key> >
51  class unordered_set
52  : public _GLIBCXX_STD_BASE,
53  public _Unordered_profile<unordered_set<_Key, _Hash, _Pred, _Alloc>,
54  true>
55  {
56  typedef _GLIBCXX_STD_BASE _Base;
57 
58  _Base&
59  _M_base() noexcept { return *this; }
60 
61  const _Base&
62  _M_base() const noexcept { return *this; }
63 
64  public:
65  typedef typename _Base::size_type size_type;
66  typedef typename _Base::hasher hasher;
67  typedef typename _Base::key_equal key_equal;
68  typedef typename _Base::allocator_type allocator_type;
69  typedef typename _Base::key_type key_type;
70  typedef typename _Base::value_type value_type;
71  typedef typename _Base::difference_type difference_type;
72  typedef typename _Base::reference reference;
73  typedef typename _Base::const_reference const_reference;
74 
75  typedef typename _Base::iterator iterator;
76  typedef typename _Base::const_iterator const_iterator;
77 
78  explicit
79  unordered_set(size_type __n = 10,
80  const hasher& __hf = hasher(),
81  const key_equal& __eql = key_equal(),
82  const allocator_type& __a = allocator_type())
83  : _Base(__n, __hf, __eql, __a)
84  { }
85 
86  template<typename _InputIterator>
87  unordered_set(_InputIterator __f, _InputIterator __l,
88  size_type __n = 0,
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)
93  { }
94 
95  unordered_set(const unordered_set&) = default;
96 
97  unordered_set(const _Base& __x)
98  : _Base(__x)
99  { }
100 
101  unordered_set(unordered_set&&) = default;
102 
103  unordered_set(initializer_list<value_type> __l,
104  size_type __n = 0,
105  const hasher& __hf = hasher(),
106  const key_equal& __eql = key_equal(),
107  const allocator_type& __a = allocator_type())
108  : _Base(__l, __n, __hf, __eql, __a)
109  { }
110 
111  unordered_set&
112  operator=(const unordered_set&) = default;
113 
114  unordered_set&
115  operator=(unordered_set&&) = default;
116 
117  unordered_set&
118  operator=(initializer_list<value_type> __l)
119  {
120  _M_base() = __l;
121  return *this;
122  }
123 
124  void
125  swap(unordered_set& __x)
126  { _Base::swap(__x); }
127 
128  void
129  clear() noexcept
130  {
131  __profcxx_hashtable_destruct(this, _Base::bucket_count(),
132  _Base::size());
133  this->_M_profile_destruct();
134  _Base::clear();
135  }
136 
137  template<typename... _Args>
138  std::pair<iterator, bool>
139  emplace(_Args&&... __args)
140  {
141  size_type __old_size = _Base::bucket_count();
142  std::pair<iterator, bool> __res
143  = _Base::emplace(std::forward<_Args>(__args)...);
144  _M_profile_resize(__old_size);
145  return __res;
146  }
147 
148  template<typename... _Args>
149  iterator
150  emplace_hint(const_iterator __it, _Args&&... __args)
151  {
152  size_type __old_size = _Base::bucket_count();
153  iterator __res
154  = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
155  _M_profile_resize(__old_size);
156  return __res;
157  }
158 
159  void
160  insert(std::initializer_list<value_type> __l)
161  {
162  size_type __old_size = _Base::bucket_count();
163  _Base::insert(__l);
164  _M_profile_resize(__old_size);
165  }
166 
167  std::pair<iterator, bool>
168  insert(const value_type& __obj)
169  {
170  size_type __old_size = _Base::bucket_count();
171  std::pair<iterator, bool> __res = _Base::insert(__obj);
172  _M_profile_resize(__old_size);
173  return __res;
174  }
175 
176  iterator
177  insert(const_iterator __iter, const value_type& __v)
178  {
179  size_type __old_size = _Base::bucket_count();
180  iterator __res = _Base::insert(__iter, __v);
181  _M_profile_resize(__old_size);
182  return __res;
183  }
184 
185  std::pair<iterator, bool>
186  insert(value_type&& __obj)
187  {
188  size_type __old_size = _Base::bucket_count();
189  std::pair<iterator, bool> __res = _Base::insert(std::move(__obj));
190  _M_profile_resize(__old_size);
191  return __res;
192  }
193 
194  iterator
195  insert(const_iterator __iter, value_type&& __v)
196  {
197  size_type __old_size = _Base::bucket_count();
198  iterator __res = _Base::insert(__iter, std::move(__v));
199  _M_profile_resize(__old_size);
200  return __res;
201  }
202 
203  template<typename _InputIter>
204  void
205  insert(_InputIter __first, _InputIter __last)
206  {
207  size_type __old_size = _Base::bucket_count();
208  _Base::insert(__first, __last);
209  _M_profile_resize(__old_size);
210  }
211 
212  void
213  rehash(size_type __n)
214  {
215  size_type __old_size = _Base::bucket_count();
216  _Base::rehash(__n);
217  _M_profile_resize(__old_size);
218  }
219 
220  private:
221  void
222  _M_profile_resize(size_type __old_size)
223  {
224  size_type __new_size = _Base::bucket_count();
225  if (__old_size != __new_size)
226  __profcxx_hashtable_resize(this, __old_size, __new_size);
227  }
228  };
229 
230  template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
231  inline void
232  swap(unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
233  unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
234  { __x.swap(__y); }
235 
236  template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
237  inline bool
238  operator==(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
239  const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
240  { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
241 
242  template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
243  inline bool
244  operator!=(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
245  const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
246  { return !(__x == __y); }
247 
248 #undef _GLIBCXX_BASE
249 #undef _GLIBCXX_STD_BASE
250 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
251 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
252 
253  /** @brief Unordered_multiset wrapper with performance instrumentation. */
254  template<typename _Value,
255  typename _Hash = std::hash<_Value>,
256  typename _Pred = std::equal_to<_Value>,
257  typename _Alloc = std::allocator<_Value> >
258  class unordered_multiset
259  : public _GLIBCXX_STD_BASE,
260  public _Unordered_profile<unordered_multiset<_Value,
261  _Hash, _Pred, _Alloc>,
262  false>
263  {
264  typedef _GLIBCXX_STD_BASE _Base;
265 
266  _Base&
267  _M_base() noexcept { return *this; }
268 
269  const _Base&
270  _M_base() const noexcept { return *this; }
271 
272  public:
273  typedef typename _Base::size_type size_type;
274  typedef typename _Base::hasher hasher;
275  typedef typename _Base::key_equal key_equal;
276  typedef typename _Base::allocator_type allocator_type;
277  typedef typename _Base::key_type key_type;
278  typedef typename _Base::value_type value_type;
279  typedef typename _Base::difference_type difference_type;
280  typedef typename _Base::reference reference;
281  typedef typename _Base::const_reference const_reference;
282 
283  typedef typename _Base::iterator iterator;
284  typedef typename _Base::const_iterator const_iterator;
285 
286  explicit
287  unordered_multiset(size_type __n = 10,
288  const hasher& __hf = hasher(),
289  const key_equal& __eql = key_equal(),
290  const allocator_type& __a = allocator_type())
291  : _Base(__n, __hf, __eql, __a)
292  { }
293 
294  template<typename _InputIterator>
295  unordered_multiset(_InputIterator __f, _InputIterator __l,
296  size_type __n = 0,
297  const hasher& __hf = hasher(),
298  const key_equal& __eql = key_equal(),
299  const allocator_type& __a = allocator_type())
300  : _Base(__f, __l, __n, __hf, __eql, __a)
301  { }
302 
303  unordered_multiset(const unordered_multiset&) = default;
304 
305  unordered_multiset(const _Base& __x)
306  : _Base(__x)
307  { }
308 
309  unordered_multiset(unordered_multiset&&) = default;
310 
311  unordered_multiset(initializer_list<value_type> __l,
312  size_type __n = 0,
313  const hasher& __hf = hasher(),
314  const key_equal& __eql = key_equal(),
315  const allocator_type& __a = allocator_type())
316  : _Base(__l, __n, __hf, __eql, __a)
317  { }
318 
319  unordered_multiset&
320  operator=(const unordered_multiset&) = default;
321 
322  unordered_multiset&
323  operator=(unordered_multiset&&) = default;
324 
325  unordered_multiset&
326  operator=(initializer_list<value_type> __l)
327  {
328  _M_base() = __l;
329  return *this;
330  }
331 
332  void
333  swap(unordered_multiset& __x)
334  { _Base::swap(__x); }
335 
336  void
337  clear() noexcept
338  {
339  __profcxx_hashtable_destruct(this, _Base::bucket_count(),
340  _Base::size());
341  this->_M_profile_destruct();
342  _Base::clear();
343  }
344 
345  template<typename... _Args>
346  iterator
347  emplace(_Args&&... __args)
348  {
349  size_type __old_size = _Base::bucket_count();
350  iterator __res = _Base::emplace(std::forward<_Args>(__args)...);
351  _M_profile_resize(__old_size);
352  return __res;
353  }
354 
355  template<typename... _Args>
356  iterator
357  emplace_hint(const_iterator __it, _Args&&... __args)
358  {
359  size_type __old_size = _Base::bucket_count();
360  iterator __res
361  = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
362  _M_profile_resize(__old_size);
363  return __res;
364  }
365 
366  void
367  insert(std::initializer_list<value_type> __l)
368  {
369  size_type __old_size = _Base::bucket_count();
370  _Base::insert(__l);
371  _M_profile_resize(__old_size);
372  }
373 
374  iterator
375  insert(const value_type& __obj)
376  {
377  size_type __old_size = _Base::bucket_count();
378  iterator __res = _Base::insert(__obj);
379  _M_profile_resize(__old_size);
380  return __res;
381  }
382 
383  iterator
384  insert(const_iterator __iter, const value_type& __v)
385  {
386  size_type __old_size = _Base::bucket_count();
387  iterator __res = _Base::insert(__iter, __v);
388  _M_profile_resize(__old_size);
389  return __res;
390  }
391 
392  iterator
393  insert(value_type&& __obj)
394  {
395  size_type __old_size = _Base::bucket_count();
396  iterator __res = _Base::insert(std::move(__obj));
397  _M_profile_resize(__old_size);
398  return __res;
399  }
400 
401  iterator
402  insert(const_iterator __iter, value_type&& __v)
403  {
404  size_type __old_size = _Base::bucket_count();
405  iterator __res = _Base::insert(__iter, std::move(__v));
406  _M_profile_resize(__old_size);
407  return __res;
408  }
409 
410  template<typename _InputIter>
411  void
412  insert(_InputIter __first, _InputIter __last)
413  {
414  size_type __old_size = _Base::bucket_count();
415  _Base::insert(__first, __last);
416  _M_profile_resize(__old_size);
417  }
418 
419  void
420  rehash(size_type __n)
421  {
422  size_type __old_size = _Base::bucket_count();
423  _Base::rehash(__n);
424  _M_profile_resize(__old_size);
425  }
426 
427  private:
428  void
429  _M_profile_resize(size_type __old_size)
430  {
431  size_type __new_size = _Base::bucket_count();
432  if (__old_size != __new_size)
433  __profcxx_hashtable_resize(this, __old_size, __new_size);
434  }
435  };
436 
437  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
438  inline void
439  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
440  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
441  { __x.swap(__y); }
442 
443  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
444  inline bool
445  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
446  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
447  { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
448 
449  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
450  inline bool
451  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
452  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
453  { return !(__x == __y); }
454 
455 } // namespace __profile
456 } // namespace std
457 
458 #undef _GLIBCXX_BASE
459 #undef _GLIBCXX_STD_BASE
460 
461 #endif // C++11
462 
463 #endif