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