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