1// Profiling unordered_map/unordered_multimap implementation -*- C++ -*-
2
3// Copyright (C) 2009, 2010, 2011, 2012 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#ifndef __GXX_EXPERIMENTAL_CXX0X__
32# include <bits/c++0x_warning.h>
33#else
34# include <unordered_map>
35
36#include <profile/base.h>
37
38#define _GLIBCXX_BASE unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
39#define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
40
41namespace std _GLIBCXX_VISIBILITY(default)
42{
43namespace __profile
44{
45  /// Class std::unordered_map wrapper with performance instrumentation.
46  template<typename _Key, typename _Tp,
47	   typename _Hash  = std::hash<_Key>,
48	   typename _Pred = std::equal_to<_Key>,
49	   typename _Alloc =  std::allocator<_Key> >
50    class unordered_map
51    : public _GLIBCXX_STD_BASE
52    {
53      typedef typename _GLIBCXX_STD_BASE _Base;
54
55    public:
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;
65      typedef typename _Base::mapped_type      mapped_type;
66
67      typedef typename _Base::iterator iterator;
68      typedef typename _Base::const_iterator const_iterator;
69
70      explicit
71      unordered_map(size_type __n = 10,
72		    const hasher& __hf = hasher(),
73		    const key_equal& __eql = key_equal(),
74		    const allocator_type& __a = allocator_type())
75      : _Base(__n, __hf, __eql, __a)
76      {
77        __profcxx_hashtable_construct(this, _Base::bucket_count());
78        __profcxx_hashtable_construct2(this);
79      }
80
81      template<typename _InputIterator>
82        unordered_map(_InputIterator __f, _InputIterator __l,
83		      size_type __n = 0,
84		      const hasher& __hf = hasher(),
85		      const key_equal& __eql = key_equal(),
86		      const allocator_type& __a = allocator_type())
87      : _Base(__f, __l, __n, __hf, __eql, __a)
88      {
89        __profcxx_hashtable_construct(this, _Base::bucket_count());
90        __profcxx_hashtable_construct2(this);
91      }
92
93      unordered_map(const unordered_map& __x)
94      : _Base(__x)
95      {
96        __profcxx_hashtable_construct(this, _Base::bucket_count());
97        __profcxx_hashtable_construct2(this);
98      }
99
100      unordered_map(const _Base& __x)
101      : _Base(__x)
102      {
103        __profcxx_hashtable_construct(this, _Base::bucket_count());
104        __profcxx_hashtable_construct2(this);
105      }
106
107      unordered_map(unordered_map&& __x)
108      : _Base(std::move(__x))
109      {
110        __profcxx_hashtable_construct(this, _Base::bucket_count());
111        __profcxx_hashtable_construct2(this);
112      }
113
114      unordered_map(initializer_list<value_type> __l,
115		    size_type __n = 0,
116		    const hasher& __hf = hasher(),
117		    const key_equal& __eql = key_equal(),
118		    const allocator_type& __a = allocator_type())
119      : _Base(__l, __n, __hf, __eql, __a) { }
120
121      unordered_map&
122      operator=(const unordered_map& __x)
123      {
124	*static_cast<_Base*>(this) = __x;
125	return *this;
126      }
127
128      unordered_map&
129      operator=(unordered_map&& __x)
130      {
131	// NB: DR 1204.
132	// NB: DR 675.
133	this->clear();
134	this->swap(__x);
135	return *this;
136      }
137
138      unordered_map&
139      operator=(initializer_list<value_type> __l)
140      {
141	this->clear();
142	this->insert(__l);
143	return *this;
144      }
145
146      ~unordered_map() noexcept
147      {
148        __profcxx_hashtable_destruct(this, _Base::bucket_count(),
149				     _Base::size());
150        _M_profile_destruct();
151      }
152
153      _Base&
154      _M_base() noexcept       { return *this; }
155
156      const _Base&
157      _M_base() const noexcept { return *this; }
158
159      void
160      clear() noexcept
161      {
162        __profcxx_hashtable_destruct(this, _Base::bucket_count(),
163				     _Base::size());
164        _M_profile_destruct();
165        _Base::clear();
166      }
167
168      template<typename... _Args>
169	std::pair<iterator, bool>
170	emplace(_Args&&... __args)
171	{
172	  size_type __old_size = _Base::bucket_count();
173	  std::pair<iterator, bool> __res
174	    = _Base::emplace(std::forward<_Args>(__args)...);
175	  _M_profile_resize(__old_size);
176	  return __res;
177	}
178
179      template<typename... _Args>
180	iterator
181	emplace_hint(const_iterator __it, _Args&&... __args)
182	{
183	  size_type __old_size = _Base::bucket_count();
184	  iterator __res
185	    = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
186	  _M_profile_resize(__old_size);
187	  return __res;
188	}
189
190      void
191      insert(std::initializer_list<value_type> __l)
192      {
193        size_type __old_size = _Base::bucket_count();
194        _Base::insert(__l);
195        _M_profile_resize(__old_size);
196      }
197
198      std::pair<iterator, bool>
199      insert(const value_type& __obj)
200      {
201        size_type __old_size = _Base::bucket_count();
202        std::pair<iterator, bool> __res = _Base::insert(__obj);
203        _M_profile_resize(__old_size);
204        return __res;
205      }
206
207      iterator
208      insert(const_iterator __iter, const value_type& __v)
209      {
210        size_type __old_size = _Base::bucket_count();
211        iterator __res = _Base::insert(__iter, __v);
212        _M_profile_resize(__old_size);
213        return __res;
214      }
215
216      template<typename _Pair, typename = typename
217	       std::enable_if<std::is_constructible<value_type,
218						    _Pair&&>::value>::type>
219        std::pair<iterator, bool>
220        insert(_Pair&& __obj)
221        {
222	  size_type __old_size = _Base::bucket_count();
223	  std::pair<iterator, bool> __res
224	    = _Base::insert(std::forward<_Pair>(__obj));
225	  _M_profile_resize(__old_size);
226	  return __res;
227	}
228
229      template<typename _Pair, typename = typename
230	       std::enable_if<std::is_constructible<value_type,
231						    _Pair&&>::value>::type>
232        iterator
233        insert(const_iterator __iter, _Pair&& __v)
234        {
235	  size_type __old_size = _Base::bucket_count();
236	  iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
237	  _M_profile_resize(__old_size);
238	  return __res;
239	}
240
241      template<typename _InputIter>
242        void
243        insert(_InputIter __first, _InputIter __last)
244        {
245	  size_type __old_size = _Base::bucket_count();
246	  _Base::insert(__first, __last);
247	  _M_profile_resize(__old_size);
248	}
249
250      void
251      insert(const value_type* __first, const value_type* __last)
252      {
253        size_type __old_size = _Base::bucket_count();
254        _Base::insert(__first, __last);
255        _M_profile_resize(__old_size);
256      }
257
258      // operator[]
259      mapped_type&
260      operator[](const _Key& __k)
261      {
262        size_type __old_size = _Base::bucket_count();
263        mapped_type& __res = _M_base()[__k];
264        _M_profile_resize(__old_size);
265        return __res;
266      }
267
268      mapped_type&
269      operator[](_Key&& __k)
270      {
271        size_type __old_size = _Base::bucket_count();
272        mapped_type& __res = _M_base()[std::move(__k)];
273        _M_profile_resize(__old_size);
274        return __res;
275      }
276
277      void
278      swap(unordered_map& __x)
279      { _Base::swap(__x); }
280
281      void rehash(size_type __n)
282      {
283	size_type __old_size = _Base::bucket_count();
284	_Base::rehash(__n);
285	_M_profile_resize(__old_size);
286      }
287
288    private:
289      void
290      _M_profile_resize(size_type __old_size)
291      {
292	size_type __new_size = _Base::bucket_count();
293	if (__old_size != __new_size)
294	  __profcxx_hashtable_resize(this, __old_size, __new_size);
295      }
296
297      void
298      _M_profile_destruct()
299      {
300	size_type __hops = 0, __lc = 0, __chain = 0;
301	iterator __it = this->begin();
302	while (__it != this->end())
303	  {
304	    size_type __bkt = this->bucket(__it->first);
305	    auto __lit = this->begin(__bkt);
306	    auto __lend = this->end(__bkt);
307	    for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
308	      ++__chain;
309	    if (__chain)
310	      {
311		++__chain;
312		__lc = __lc > __chain ? __lc : __chain;
313		__hops += __chain * (__chain - 1) / 2;
314		__chain = 0;
315	      }
316	  }
317	__profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
318      }
319  };
320
321  template<typename _Key, typename _Tp, typename _Hash,
322	   typename _Pred, typename _Alloc>
323    inline void
324    swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
325	 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
326    { __x.swap(__y); }
327
328  template<typename _Key, typename _Tp, typename _Hash,
329	   typename _Pred, typename _Alloc>
330    inline bool
331    operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
332	       const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
333    { return __x._M_equal(__y); }
334
335  template<typename _Key, typename _Tp, typename _Hash,
336	   typename _Pred, typename _Alloc>
337    inline bool
338    operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
339	       const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
340    { return !(__x == __y); }
341
342#undef _GLIBCXX_BASE
343#undef _GLIBCXX_STD_BASE
344#define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
345#define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
346
347  /// Class std::unordered_multimap wrapper with performance instrumentation.
348  template<typename _Key, typename _Tp,
349	   typename _Hash  = std::hash<_Key>,
350	   typename _Pred = std::equal_to<_Key>,
351	   typename _Alloc =  std::allocator<_Key> >
352    class unordered_multimap
353    : public _GLIBCXX_STD_BASE
354    {
355      typedef typename _GLIBCXX_STD_BASE _Base;
356
357    public:
358      typedef typename _Base::size_type       size_type;
359      typedef typename _Base::hasher          hasher;
360      typedef typename _Base::key_equal       key_equal;
361      typedef typename _Base::allocator_type  allocator_type;
362      typedef typename _Base::key_type        key_type;
363      typedef typename _Base::value_type      value_type;
364      typedef typename _Base::difference_type difference_type;
365      typedef typename _Base::reference       reference;
366      typedef typename _Base::const_reference const_reference;
367
368      typedef typename _Base::iterator iterator;
369      typedef typename _Base::const_iterator const_iterator;
370
371      explicit
372      unordered_multimap(size_type __n = 10,
373			 const hasher& __hf = hasher(),
374			 const key_equal& __eql = key_equal(),
375			 const allocator_type& __a = allocator_type())
376      : _Base(__n, __hf, __eql, __a)
377      {
378        __profcxx_hashtable_construct(this, _Base::bucket_count());
379      }
380      template<typename _InputIterator>
381        unordered_multimap(_InputIterator __f, _InputIterator __l,
382			   size_type __n = 0,
383			   const hasher& __hf = hasher(),
384			   const key_equal& __eql = key_equal(),
385			   const allocator_type& __a = allocator_type())
386      : _Base(__f, __l, __n, __hf, __eql, __a)
387      {
388        __profcxx_hashtable_construct(this, _Base::bucket_count());
389      }
390
391      unordered_multimap(const unordered_multimap& __x)
392      : _Base(__x)
393      {
394        __profcxx_hashtable_construct(this, _Base::bucket_count());
395      }
396
397      unordered_multimap(const _Base& __x)
398      : _Base(__x)
399      {
400        __profcxx_hashtable_construct(this, _Base::bucket_count());
401      }
402
403      unordered_multimap(unordered_multimap&& __x)
404      : _Base(std::move(__x))
405      {
406        __profcxx_hashtable_construct(this, _Base::bucket_count());
407      }
408
409      unordered_multimap(initializer_list<value_type> __l,
410			 size_type __n = 0,
411			 const hasher& __hf = hasher(),
412			 const key_equal& __eql = key_equal(),
413			 const allocator_type& __a = allocator_type())
414      : _Base(__l, __n, __hf, __eql, __a) { }
415
416      unordered_multimap&
417      operator=(const unordered_multimap& __x)
418      {
419	*static_cast<_Base*>(this) = __x;
420	return *this;
421      }
422
423      unordered_multimap&
424      operator=(unordered_multimap&& __x)
425      {
426	// NB: DR 1204.
427	// NB: DR 675.
428	this->clear();
429	this->swap(__x);
430	return *this;
431      }
432
433      unordered_multimap&
434      operator=(initializer_list<value_type> __l)
435      {
436	this->clear();
437	this->insert(__l);
438	return *this;
439      }
440
441      ~unordered_multimap() noexcept
442      {
443        __profcxx_hashtable_destruct(this, _Base::bucket_count(),
444				     _Base::size());
445        _M_profile_destruct();
446      }
447
448      void
449      clear() noexcept
450      {
451        __profcxx_hashtable_destruct(this, _Base::bucket_count(),
452				     _Base::size());
453        _M_profile_destruct();
454        _Base::clear();
455      }
456
457      template<typename... _Args>
458	iterator
459	emplace(_Args&&... __args)
460	{
461	  size_type __old_size = _Base::bucket_count();
462	  iterator __res
463	    = _Base::emplace(std::forward<_Args>(__args)...);
464	  _M_profile_resize(__old_size);
465	  return __res;
466	}
467
468      template<typename... _Args>
469	iterator
470	emplace_hint(const_iterator __it, _Args&&... __args)
471	{
472	  size_type __old_size = _Base::bucket_count();
473	  iterator __res
474	    = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
475	  _M_profile_resize(__old_size);
476	  return __res;
477	}
478
479      void
480      insert(std::initializer_list<value_type> __l)
481      {
482        size_type __old_size = _Base::bucket_count();
483        _Base::insert(__l);
484        _M_profile_resize(__old_size);
485      }
486
487      iterator
488      insert(const value_type& __obj)
489      {
490        size_type __old_size = _Base::bucket_count();
491        iterator __res = _Base::insert(__obj);
492        _M_profile_resize(__old_size);
493        return __res;
494      }
495
496      iterator
497      insert(const_iterator __iter, const value_type& __v)
498      {
499        size_type __old_size = _Base::bucket_count();
500        iterator __res = _Base::insert(__iter, __v);
501        _M_profile_resize(__old_size);
502        return __res;
503      }
504
505      template<typename _Pair, typename = typename
506	       std::enable_if<std::is_constructible<value_type,
507						    _Pair&&>::value>::type>
508        iterator
509        insert(_Pair&& __obj)
510        {
511	  size_type __old_size = _Base::bucket_count();
512	  iterator __res = _Base::insert(std::forward<_Pair>(__obj));
513	  _M_profile_resize(__old_size);
514	  return __res;
515	}
516
517      template<typename _Pair, typename = typename
518	       std::enable_if<std::is_constructible<value_type,
519						    _Pair&&>::value>::type>
520        iterator
521        insert(const_iterator __iter, _Pair&& __v)
522        {
523	  size_type __old_size = _Base::bucket_count();
524	  iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
525	  _M_profile_resize(__old_size);
526	  return __res;
527	}
528
529      template<typename _InputIter>
530        void
531        insert(_InputIter __first, _InputIter __last)
532        {
533	  size_type __old_size = _Base::bucket_count();
534	  _Base::insert(__first, __last);
535	  _M_profile_resize(__old_size);
536	}
537
538      void
539      insert(const value_type* __first, const value_type* __last)
540      {
541        size_type __old_size = _Base::bucket_count();
542        _Base::insert(__first, __last);
543        _M_profile_resize(__old_size);
544      }
545
546      void
547      swap(unordered_multimap& __x)
548      { _Base::swap(__x); }
549
550      void rehash(size_type __n)
551      {
552        size_type __old_size = _Base::bucket_count();
553        _Base::rehash(__n);
554        _M_profile_resize(__old_size);
555      }
556
557    private:
558      void
559      _M_profile_resize(size_type __old_size)
560      {
561	size_type __new_size = _Base::bucket_count();
562        if (__old_size != __new_size)
563          __profcxx_hashtable_resize(this, __old_size, __new_size);
564      }
565
566      void
567      _M_profile_destruct()
568      {
569	size_type __hops = 0, __lc = 0, __chain = 0;
570	iterator __it = this->begin();
571	while (__it != this->end())
572	  {
573	    size_type __bkt = this->bucket(__it->first);
574	    auto __lit = this->begin(__bkt);
575	    auto __lend = this->end(__bkt);
576	    for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
577	      ++__chain;
578	    if (__chain)
579	      {
580		++__chain;
581		__lc = __lc > __chain ? __lc : __chain;
582		__hops += __chain * (__chain - 1) / 2;
583		__chain = 0;
584	      }
585	  }
586	__profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
587      }
588  };
589
590  template<typename _Key, typename _Tp, typename _Hash,
591	   typename _Pred, typename _Alloc>
592    inline void
593    swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
594	 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
595    { __x.swap(__y); }
596
597  template<typename _Key, typename _Tp, typename _Hash,
598	   typename _Pred, typename _Alloc>
599    inline bool
600    operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
601	       const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
602    { return __x._M_equal(__y); }
603
604  template<typename _Key, typename _Tp, typename _Hash,
605	   typename _Pred, typename _Alloc>
606    inline bool
607    operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
608	       const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
609    { return !(__x == __y); }
610
611} // namespace __profile
612} // namespace std
613
614#undef _GLIBCXX_BASE
615#undef _GLIBCXX_STD_BASE
616
617#endif // __GXX_EXPERIMENTAL_CXX0X__
618
619#endif
620