libstdc++
profile/unordered_set
Go to the documentation of this file.
00001 // Profiling unordered_set/unordered_multiset implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2009, 2010, 2011 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 //
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License along
00021 // with this library; see the file COPYING3.  If not see
00022 // <http://www.gnu.org/licenses/>.
00023 
00024 /** @file profile/unordered_set
00025  *  This file is a GNU profile extension to the Standard C++ Library.
00026  */
00027 
00028 #ifndef _GLIBCXX_PROFILE_UNORDERED_SET
00029 #define _GLIBCXX_PROFILE_UNORDERED_SET 1
00030 
00031 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00032 # include <bits/c++0x_warning.h>
00033 #else
00034 # include <unordered_set>
00035 
00036 #include <profile/base.h>
00037 
00038 #define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc>
00039 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
00040 
00041 namespace std _GLIBCXX_VISIBILITY(default)
00042 {
00043 namespace __profile
00044 {
00045   /** @brief Unordered_set wrapper with performance instrumentation.  */
00046   template<typename _Key, 
00047        typename _Hash  = std::hash<_Key>,
00048        typename _Pred = std::equal_to<_Key>,
00049        typename _Alloc =  std::allocator<_Key> >
00050     class unordered_set
00051     : public _GLIBCXX_STD_BASE
00052     {
00053       typedef typename _GLIBCXX_STD_BASE _Base;
00054 
00055     public:
00056       typedef typename _Base::size_type       size_type;
00057       typedef typename _Base::hasher          hasher;
00058       typedef typename _Base::key_equal       key_equal;
00059       typedef typename _Base::allocator_type  allocator_type;
00060       typedef typename _Base::key_type        key_type;
00061       typedef typename _Base::value_type      value_type;
00062       typedef typename _Base::difference_type difference_type;
00063       typedef typename _Base::reference       reference;
00064       typedef typename _Base::const_reference const_reference;
00065 
00066       typedef typename _Base::iterator iterator;
00067       typedef typename _Base::const_iterator const_iterator;
00068 
00069       explicit
00070       unordered_set(size_type __n = 10,
00071             const hasher& __hf = hasher(),
00072             const key_equal& __eql = key_equal(),
00073             const allocator_type& __a = allocator_type())
00074       : _Base(__n, __hf, __eql, __a)
00075       {
00076         __profcxx_hashtable_construct(this, _Base::bucket_count());
00077         __profcxx_hashtable_construct2(this);
00078       }
00079 
00080       template<typename _InputIterator>
00081         unordered_set(_InputIterator __f, _InputIterator __l,
00082               size_type __n = 0,
00083               const hasher& __hf = hasher(),
00084               const key_equal& __eql = key_equal(),
00085               const allocator_type& __a = allocator_type())
00086       : _Base(__f, __l, __n, __hf, __eql, __a)
00087       {
00088         __profcxx_hashtable_construct(this, _Base::bucket_count());
00089         __profcxx_hashtable_construct2(this);
00090       }
00091 
00092       unordered_set(const unordered_set& __x)
00093       : _Base(__x) 
00094       { 
00095         __profcxx_hashtable_construct(this, _Base::bucket_count());
00096         __profcxx_hashtable_construct2(this);
00097       }
00098 
00099       unordered_set(const _Base& __x)
00100       : _Base(__x) 
00101       { 
00102         __profcxx_hashtable_construct(this, _Base::bucket_count());
00103         __profcxx_hashtable_construct2(this);
00104       }
00105 
00106       unordered_set(unordered_set&& __x)
00107       : _Base(std::move(__x)) 
00108       { 
00109         __profcxx_hashtable_construct(this, _Base::bucket_count());
00110         __profcxx_hashtable_construct2(this);
00111       }
00112 
00113       unordered_set(initializer_list<value_type> __l,
00114             size_type __n = 0,
00115             const hasher& __hf = hasher(),
00116             const key_equal& __eql = key_equal(),
00117             const allocator_type& __a = allocator_type())
00118       : _Base(__l, __n, __hf, __eql, __a) { }
00119 
00120       unordered_set&
00121       operator=(const unordered_set& __x)
00122       {
00123     *static_cast<_Base*>(this) = __x;
00124     return *this;
00125       }
00126 
00127       unordered_set&
00128       operator=(unordered_set&& __x)
00129       {
00130     // NB: DR 1204.
00131     // NB: DR 675.
00132     this->clear();
00133     this->swap(__x);
00134     return *this;
00135       }
00136 
00137       unordered_set&
00138       operator=(initializer_list<value_type> __l)
00139       {
00140     this->clear();
00141     this->insert(__l);
00142     return *this;
00143       }
00144 
00145       ~unordered_set() noexcept
00146       {
00147         __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
00148                                      _Base::size());
00149         _M_profile_destruct();
00150       }
00151 
00152       void
00153       swap(unordered_set& __x)
00154       {
00155         _Base::swap(__x);
00156       }
00157 
00158       void
00159       clear() noexcept
00160       {
00161         __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
00162                                      _Base::size());
00163         _M_profile_destruct();
00164         _Base::clear();
00165       }
00166 
00167       template<typename... _Args>
00168     std::pair<iterator, bool>
00169     emplace(_Args&&... __args)
00170     {
00171       size_type __old_size = _Base::bucket_count();
00172       std::pair<iterator, bool> __res
00173         = _Base::emplace(std::forward<_Args>(__args)...);
00174       _M_profile_resize(__old_size);
00175       return __res;
00176     }
00177 
00178       template<typename... _Args>
00179     iterator
00180     emplace_hint(const_iterator __it, _Args&&... __args)
00181     {
00182       size_type __old_size = _Base::bucket_count();
00183       iterator __res
00184         = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
00185       _M_profile_resize(__old_size);
00186       return __res;
00187     }
00188 
00189       void
00190       insert(std::initializer_list<value_type> __l)
00191       { 
00192         size_type __old_size = _Base::bucket_count();
00193         _Base::insert(__l); 
00194         _M_profile_resize(__old_size); 
00195       }
00196 
00197       std::pair<iterator, bool>
00198       insert(const value_type& __obj)
00199       {
00200         size_type __old_size = _Base::bucket_count();
00201         std::pair<iterator, bool> __res = _Base::insert(__obj);
00202         _M_profile_resize(__old_size); 
00203         return __res;
00204       }
00205 
00206       iterator
00207       insert(const_iterator __iter, const value_type& __v)
00208       { 
00209         size_type __old_size = _Base::bucket_count(); 
00210         iterator __res = _Base::insert(__iter, __v);
00211         _M_profile_resize(__old_size); 
00212         return __res;
00213       }
00214 
00215       std::pair<iterator, bool>
00216       insert(value_type&& __obj)
00217       {
00218         size_type __old_size = _Base::bucket_count();
00219         std::pair<iterator, bool> __res = _Base::insert(std::move(__obj));
00220         _M_profile_resize(__old_size); 
00221         return __res;
00222       }
00223 
00224       iterator
00225       insert(const_iterator __iter, value_type&& __v)
00226       { 
00227         size_type __old_size = _Base::bucket_count();
00228         iterator __res = _Base::insert(__iter, std::move(__v));
00229         _M_profile_resize(__old_size); 
00230         return __res;
00231       }
00232 
00233       template<typename _InputIter>
00234         void
00235         insert(_InputIter __first, _InputIter __last)
00236         {
00237       size_type __old_size = _Base::bucket_count(); 
00238       _Base::insert(__first, __last);
00239       _M_profile_resize(__old_size); 
00240     }
00241 
00242       void
00243       insert(const value_type* __first, const value_type* __last)
00244       {
00245         size_type __old_size = _Base::bucket_count(); 
00246         _Base::insert(__first, __last);
00247         _M_profile_resize(__old_size); 
00248       }
00249      
00250       void rehash(size_type __n)
00251       {
00252         size_type __old_size = _Base::bucket_count();
00253         _Base::rehash(__n);
00254         _M_profile_resize(__old_size); 
00255       }
00256 
00257     private:
00258       void
00259       _M_profile_resize(size_type __old_size)
00260       {
00261     size_type __new_size = _Base::bucket_count();
00262     if (__old_size != __new_size)
00263       __profcxx_hashtable_resize(this, __old_size, __new_size);
00264       }
00265 
00266       void
00267       _M_profile_destruct()
00268       {
00269     size_type __hops = 0, __lc = 0, __chain = 0;
00270     iterator __it = this->begin();
00271     while (__it != this->end())
00272       {
00273         size_type __bkt = this->bucket(*__it);
00274         auto __lit = this->begin(__bkt);
00275         auto __lend = this->end(__bkt);
00276         for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
00277           ++__chain;
00278         if (__chain)
00279           {
00280         ++__chain;
00281         __lc = __lc > __chain ? __lc : __chain;
00282         __hops += __chain * (__chain - 1) / 2;
00283         __chain = 0;
00284           }
00285       }
00286         __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
00287       }
00288   };
00289 
00290   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00291     inline void
00292     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00293      unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00294     { __x.swap(__y); }
00295 
00296   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00297     inline bool
00298     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00299            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00300     { return __x._M_equal(__y); }
00301 
00302   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00303     inline bool
00304     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00305            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00306     { return !(__x == __y); }
00307 
00308 #undef _GLIBCXX_BASE
00309 #undef _GLIBCXX_STD_BASE
00310 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
00311 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
00312 
00313   /** @brief Unordered_multiset wrapper with performance instrumentation.  */
00314   template<typename _Value,
00315        typename _Hash  = std::hash<_Value>,
00316        typename _Pred = std::equal_to<_Value>,
00317        typename _Alloc =  std::allocator<_Value> >
00318     class unordered_multiset
00319     : public _GLIBCXX_STD_BASE
00320     {
00321       typedef typename _GLIBCXX_STD_BASE _Base;
00322 
00323     public:
00324       typedef typename _Base::size_type       size_type;
00325       typedef typename _Base::hasher          hasher;
00326       typedef typename _Base::key_equal       key_equal;
00327       typedef typename _Base::allocator_type  allocator_type;
00328       typedef typename _Base::key_type        key_type;
00329       typedef typename _Base::value_type      value_type;
00330       typedef typename _Base::difference_type difference_type;
00331       typedef typename _Base::reference       reference;
00332       typedef typename _Base::const_reference const_reference;
00333 
00334       typedef typename _Base::iterator iterator;
00335       typedef typename _Base::const_iterator const_iterator;
00336 
00337       explicit
00338       unordered_multiset(size_type __n = 10,
00339              const hasher& __hf = hasher(),
00340              const key_equal& __eql = key_equal(),
00341              const allocator_type& __a = allocator_type())
00342       : _Base(__n, __hf, __eql, __a)
00343       {
00344         __profcxx_hashtable_construct(this, _Base::bucket_count());
00345       }
00346 
00347       template<typename _InputIterator>
00348         unordered_multiset(_InputIterator __f, _InputIterator __l,
00349                size_type __n = 0,
00350                const hasher& __hf = hasher(),
00351                const key_equal& __eql = key_equal(),
00352                const allocator_type& __a = allocator_type())
00353       : _Base(__f, __l, __n, __hf, __eql, __a)
00354       {
00355         __profcxx_hashtable_construct(this, _Base::bucket_count());
00356       }
00357 
00358       unordered_multiset(const unordered_multiset& __x)
00359       : _Base(__x)
00360       {
00361         __profcxx_hashtable_construct(this, _Base::bucket_count());
00362       }
00363 
00364       unordered_multiset(const _Base& __x)
00365       : _Base(__x)
00366       {
00367         __profcxx_hashtable_construct(this, _Base::bucket_count());
00368       }
00369 
00370       unordered_multiset(unordered_multiset&& __x)
00371       : _Base(std::move(__x))
00372       {
00373         __profcxx_hashtable_construct(this, _Base::bucket_count());
00374       }
00375 
00376       unordered_multiset(initializer_list<value_type> __l,
00377              size_type __n = 0,
00378              const hasher& __hf = hasher(),
00379              const key_equal& __eql = key_equal(),
00380              const allocator_type& __a = allocator_type())
00381       : _Base(__l, __n, __hf, __eql, __a) { }
00382 
00383       unordered_multiset&
00384       operator=(const unordered_multiset& __x)
00385       {
00386     *static_cast<_Base*>(this) = __x;
00387     return *this;
00388       }
00389 
00390       unordered_multiset&
00391       operator=(unordered_multiset&& __x)
00392       {
00393     // NB: DR 1204.
00394     // NB: DR 675.
00395     this->clear();
00396     this->swap(__x);
00397     return *this;
00398       }
00399 
00400       unordered_multiset&
00401       operator=(initializer_list<value_type> __l)
00402       {
00403     this->clear();
00404     this->insert(__l);
00405     return *this;
00406       }
00407 
00408       ~unordered_multiset() noexcept
00409       {
00410         __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
00411                                      _Base::size());
00412         _M_profile_destruct();
00413       }
00414 
00415       void
00416       swap(unordered_multiset& __x)
00417       {
00418         _Base::swap(__x);
00419       }
00420 
00421       void
00422       clear() noexcept
00423       {
00424         __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
00425                                      _Base::size());
00426         _M_profile_destruct();
00427         _Base::clear();
00428       }
00429 
00430       template<typename... _Args>
00431     iterator
00432     emplace(_Args&&... __args)
00433     {
00434       size_type __old_size = _Base::bucket_count();
00435       iterator __res = _Base::emplace(std::forward<_Args>(__args)...);
00436       _M_profile_resize(__old_size);
00437       return __res;
00438     }
00439 
00440       template<typename... _Args>
00441     iterator
00442     emplace_hint(const_iterator __it, _Args&&... __args)
00443     {
00444       size_type __old_size = _Base::bucket_count();
00445       iterator __res
00446         = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
00447       _M_profile_resize(__old_size);
00448       return __res;
00449     }
00450 
00451       void
00452       insert(std::initializer_list<value_type> __l)
00453       { 
00454         size_type __old_size = _Base::bucket_count();
00455         _Base::insert(__l); 
00456         _M_profile_resize(__old_size); 
00457       }
00458 
00459       iterator
00460       insert(const value_type& __obj)
00461       {
00462         size_type __old_size = _Base::bucket_count();
00463         iterator __res = _Base::insert(__obj);
00464         _M_profile_resize(__old_size); 
00465         return __res;
00466       }
00467 
00468       iterator
00469       insert(const_iterator __iter, const value_type& __v)
00470       {
00471         size_type __old_size = _Base::bucket_count(); 
00472         iterator __res = _Base::insert(__iter, __v);
00473         _M_profile_resize(__old_size); 
00474         return __res;
00475       }
00476 
00477       iterator
00478       insert(value_type&& __obj)
00479       {
00480     size_type __old_size = _Base::bucket_count();
00481         iterator __res = _Base::insert(std::move(__obj));
00482         _M_profile_resize(__old_size); 
00483         return __res;
00484       }
00485 
00486       iterator
00487       insert(const_iterator __iter, value_type&& __v)
00488       {
00489         size_type __old_size = _Base::bucket_count(); 
00490         iterator __res = _Base::insert(__iter, std::move(__v));
00491         _M_profile_resize(__old_size); 
00492         return __res;
00493       }
00494 
00495       template<typename _InputIter>
00496         void
00497         insert(_InputIter __first, _InputIter __last)
00498         {
00499       size_type __old_size = _Base::bucket_count(); 
00500       _Base::insert(__first, __last);
00501       _M_profile_resize(__old_size); 
00502     }
00503 
00504       void
00505       insert(const value_type* __first, const value_type* __last)
00506       {
00507         size_type __old_size = _Base::bucket_count(); 
00508         _Base::insert(__first, __last);
00509         _M_profile_resize(__old_size); 
00510       }
00511      
00512       void rehash(size_type __n)
00513       {
00514         size_type __old_size = _Base::bucket_count();
00515         _Base::rehash(__n);
00516         _M_profile_resize(__old_size); 
00517       }
00518 
00519     private:
00520       void
00521       _M_profile_resize(size_type __old_size)
00522       {
00523     size_type __new_size = _Base::bucket_count();
00524         if (__old_size != __new_size)
00525           __profcxx_hashtable_resize(this, __old_size, __new_size);
00526       }
00527 
00528       void
00529       _M_profile_destruct()
00530       {
00531     size_type __hops = 0, __lc = 0, __chain = 0;
00532     iterator __it = this->begin();
00533     while (__it != this->end())
00534       {
00535         size_type __bkt = this->bucket(*__it);
00536         auto __lit = this->begin(__bkt);
00537         auto __lend = this->end(__bkt);
00538         for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
00539           ++__chain;
00540         if (__chain)
00541           {
00542         ++__chain;
00543         __lc = __lc > __chain ? __lc : __chain;
00544         __hops += __chain * (__chain - 1) / 2;
00545         __chain = 0;
00546           }
00547       }
00548         __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
00549       }
00550    };
00551 
00552   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00553     inline void
00554     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00555      unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00556     { __x.swap(__y); }
00557 
00558   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00559     inline bool
00560     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00561            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00562     { return __x._M_equal(__y); }
00563 
00564   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00565     inline bool
00566     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00567            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00568     { return !(__x == __y); }
00569 
00570 } // namespace __profile
00571 } // namespace std
00572 
00573 #undef _GLIBCXX_BASE
00574 #undef _GLIBCXX_STD_BASE
00575 
00576 #endif // __GXX_EXPERIMENTAL_CXX0X__
00577 
00578 #endif