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