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 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 _Base& __x)
00093       : _Base(__x) 
00094       { 
00095         __profcxx_hashtable_construct(this, _Base::bucket_count());
00096         __profcxx_hashtable_construct2(this);
00097       }
00098 
00099       unordered_set(unordered_set&& __x)
00100       : _Base(std::move(__x)) 
00101       { 
00102         __profcxx_hashtable_construct(this, _Base::bucket_count());
00103         __profcxx_hashtable_construct2(this);
00104       }
00105 
00106       unordered_set(initializer_list<value_type> __l,
00107             size_type __n = 0,
00108             const hasher& __hf = hasher(),
00109             const key_equal& __eql = key_equal(),
00110             const allocator_type& __a = allocator_type())
00111       : _Base(__l, __n, __hf, __eql, __a) { }
00112 
00113       unordered_set&
00114       operator=(const unordered_set& __x)
00115       {
00116     *static_cast<_Base*>(this) = __x;
00117     return *this;
00118       }
00119 
00120       unordered_set&
00121       operator=(unordered_set&& __x)
00122       {
00123     // NB: DR 1204.
00124     // NB: DR 675.
00125     this->clear();
00126     this->swap(__x);
00127     return *this;
00128       }
00129 
00130       unordered_set&
00131       operator=(initializer_list<value_type> __l)
00132       {
00133     this->clear();
00134     this->insert(__l);
00135     return *this;
00136       }
00137 
00138       ~unordered_set()
00139       {
00140         __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
00141                                      _Base::size());
00142         _M_profile_destruct();
00143       }
00144 
00145       void
00146       swap(unordered_set& __x)
00147       {
00148         _Base::swap(__x);
00149       }
00150 
00151       void
00152       clear()
00153       {
00154         __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
00155                                      _Base::size());
00156         _M_profile_destruct();
00157         _Base::clear();
00158       }
00159 
00160       void
00161       insert(std::initializer_list<value_type> __l)
00162       { 
00163         size_type __old_size =  _Base::bucket_count();
00164         _Base::insert(__l); 
00165         _M_profile_resize(__old_size,  _Base::bucket_count()); 
00166       }
00167 
00168       std::pair<iterator, bool>
00169       insert(const value_type& __obj)
00170       {
00171         size_type __old_size = _Base::bucket_count();
00172         std::pair<iterator, bool> __res = _Base::insert(__obj);
00173         _M_profile_resize(__old_size,  _Base::bucket_count()); 
00174         return __res;
00175       }
00176 
00177       iterator
00178       insert(const_iterator __iter, const value_type& __v)
00179       { 
00180         size_type __old_size = _Base::bucket_count(); 
00181         iterator __res = _Base::insert(__iter, __v);
00182         _M_profile_resize(__old_size, _Base::bucket_count()); 
00183         return __res;
00184       }
00185 
00186       std::pair<iterator, bool>
00187       insert(value_type&& __obj)
00188       {
00189         size_type __old_size = _Base::bucket_count();
00190         std::pair<iterator, bool> __res = _Base::insert(std::move(__obj));
00191         _M_profile_resize(__old_size,  _Base::bucket_count()); 
00192         return __res;
00193       }
00194 
00195       iterator
00196       insert(const_iterator __iter, value_type&& __v)
00197       { 
00198         size_type __old_size = _Base::bucket_count();
00199         iterator __res = _Base::insert(__iter, std::move(__v));
00200         _M_profile_resize(__old_size, _Base::bucket_count()); 
00201         return __res;
00202       }
00203 
00204       template<typename _InputIter>
00205         void
00206         insert(_InputIter __first, _InputIter __last)
00207         {
00208       size_type __old_size = _Base::bucket_count(); 
00209       _Base::insert(__first, __last);
00210       _M_profile_resize(__old_size,  _Base::bucket_count()); 
00211     }
00212 
00213       void
00214       insert(const value_type* __first, const value_type* __last)
00215       {
00216         size_type __old_size = _Base::bucket_count(); 
00217         _Base::insert(__first, __last);
00218         _M_profile_resize(__old_size,  _Base::bucket_count()); 
00219       }
00220      
00221       void rehash(size_type __n)
00222       {
00223         size_type __old_size =  _Base::bucket_count();
00224         _Base::rehash(__n);
00225         _M_profile_resize(__old_size,  _Base::bucket_count()); 
00226       }
00227 
00228     private:
00229       _Base&
00230       _M_base()       { return *this; }
00231 
00232       const _Base&
00233       _M_base() const { return *this; }
00234 
00235       void
00236       _M_profile_resize(size_type __old_size, size_type __new_size)
00237       {
00238         if (__old_size != __new_size)
00239       __profcxx_hashtable_resize(this, __old_size, __new_size);
00240       }
00241 
00242       void
00243       _M_profile_destruct()
00244       {
00245         size_type __hops = 0, __lc = 0, __chain = 0;
00246         for (iterator __it = _M_base().begin(); __it != _M_base().end();
00247          ++__it)
00248         {
00249           while (__it._M_cur_node->_M_next)
00250         {
00251           ++__chain;
00252           ++__it;
00253         }
00254 
00255           if (__chain)
00256         {
00257           ++__chain;
00258           __lc = __lc > __chain ? __lc : __chain;
00259           __hops += __chain * (__chain - 1) / 2;
00260           __chain = 0;
00261         }
00262         }
00263         __profcxx_hashtable_destruct2(this, __lc,  _Base::size(), __hops);
00264       }
00265 
00266    };
00267 
00268   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00269     inline void
00270     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00271      unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00272     { __x.swap(__y); }
00273 
00274   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00275     inline bool
00276     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00277            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00278     { return __x._M_equal(__y); }
00279 
00280   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00281     inline bool
00282     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00283            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00284     { return !(__x == __y); }
00285 
00286 #undef _GLIBCXX_BASE
00287 #undef _GLIBCXX_STD_BASE
00288 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
00289 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
00290 
00291   /** @brief Unordered_multiset wrapper with performance instrumentation.  */
00292   template<typename _Value,
00293        typename _Hash  = std::hash<_Value>,
00294        typename _Pred = std::equal_to<_Value>,
00295        typename _Alloc =  std::allocator<_Value> >
00296     class unordered_multiset
00297     : public _GLIBCXX_STD_BASE
00298     {
00299       typedef typename _GLIBCXX_STD_BASE _Base;
00300 
00301     public:
00302       typedef typename _Base::size_type       size_type;
00303       typedef typename _Base::hasher          hasher;
00304       typedef typename _Base::key_equal       key_equal;
00305       typedef typename _Base::allocator_type  allocator_type;
00306       typedef typename _Base::key_type        key_type;
00307       typedef typename _Base::value_type      value_type;
00308       typedef typename _Base::difference_type difference_type;
00309       typedef typename _Base::reference       reference;
00310       typedef typename _Base::const_reference const_reference;
00311 
00312       typedef typename _Base::iterator iterator;
00313       typedef typename _Base::const_iterator const_iterator;
00314 
00315       explicit
00316       unordered_multiset(size_type __n = 10,
00317              const hasher& __hf = hasher(),
00318              const key_equal& __eql = key_equal(),
00319              const allocator_type& __a = allocator_type())
00320       : _Base(__n, __hf, __eql, __a)
00321       {
00322         __profcxx_hashtable_construct(this, _Base::bucket_count());
00323       }
00324 
00325       template<typename _InputIterator>
00326         unordered_multiset(_InputIterator __f, _InputIterator __l,
00327                size_type __n = 0,
00328                const hasher& __hf = hasher(),
00329                const key_equal& __eql = key_equal(),
00330                const allocator_type& __a = allocator_type())
00331       : _Base(__f, __l, __n, __hf, __eql, __a)
00332       {
00333         __profcxx_hashtable_construct(this, _Base::bucket_count());
00334       }
00335 
00336       unordered_multiset(const _Base& __x)
00337       : _Base(__x)
00338       {
00339         __profcxx_hashtable_construct(this, _Base::bucket_count());
00340       }
00341 
00342       unordered_multiset(unordered_multiset&& __x)
00343       : _Base(std::move(__x))
00344       {
00345         __profcxx_hashtable_construct(this, _Base::bucket_count());
00346       }
00347 
00348       unordered_multiset(initializer_list<value_type> __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(__l, __n, __hf, __eql, __a) { }
00354 
00355       unordered_multiset&
00356       operator=(const unordered_multiset& __x)
00357       {
00358     *static_cast<_Base*>(this) = __x;
00359     return *this;
00360       }
00361 
00362       unordered_multiset&
00363       operator=(unordered_multiset&& __x)
00364       {
00365     // NB: DR 1204.
00366     // NB: DR 675.
00367     this->clear();
00368     this->swap(__x);
00369     return *this;
00370       }
00371 
00372       unordered_multiset&
00373       operator=(initializer_list<value_type> __l)
00374       {
00375     this->clear();
00376     this->insert(__l);
00377     return *this;
00378       }
00379 
00380       ~unordered_multiset()
00381       {
00382         __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
00383                                      _Base::size());
00384         _M_profile_destruct();
00385       }
00386 
00387       void
00388       swap(unordered_multiset& __x)
00389       {
00390         _Base::swap(__x);
00391       }
00392 
00393       void
00394       clear()
00395       {
00396         __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
00397                                      _Base::size());
00398         _M_profile_destruct();
00399         _Base::clear();
00400       }
00401 
00402       void
00403       insert(std::initializer_list<value_type> __l)
00404       { 
00405         size_type __old_size =  _Base::bucket_count();
00406         _Base::insert(__l); 
00407         _M_profile_resize(__old_size,  _Base::bucket_count()); 
00408       }
00409 
00410       iterator
00411       insert(const value_type& __obj)
00412       {
00413         size_type __old_size =  _Base::bucket_count();
00414         iterator __res = _Base::insert(__obj);
00415         _M_profile_resize(__old_size,  _Base::bucket_count()); 
00416         return __res;
00417       }
00418 
00419       iterator
00420       insert(const_iterator __iter, const value_type& __v)
00421       {
00422         size_type __old_size = _Base::bucket_count(); 
00423         iterator __res = _Base::insert(__iter, __v);
00424         _M_profile_resize(__old_size, _Base::bucket_count()); 
00425         return __res;
00426       }
00427 
00428       iterator
00429       insert(value_type&& __obj)
00430       {
00431     size_type __old_size =  _Base::bucket_count();
00432         iterator __res = _Base::insert(std::move(__obj));
00433         _M_profile_resize(__old_size,  _Base::bucket_count()); 
00434         return __res;
00435       }
00436 
00437       iterator
00438       insert(const_iterator __iter, value_type&& __v)
00439       {
00440         size_type __old_size = _Base::bucket_count(); 
00441         iterator __res = _Base::insert(__iter, std::move(__v));
00442         _M_profile_resize(__old_size, _Base::bucket_count()); 
00443         return __res;
00444       }
00445 
00446       template<typename _InputIter>
00447         void
00448         insert(_InputIter __first, _InputIter __last)
00449         {
00450       size_type __old_size = _Base::bucket_count(); 
00451       _Base::insert(__first, __last);
00452       _M_profile_resize(__old_size,  _Base::bucket_count()); 
00453     }
00454 
00455       void
00456       insert(const value_type* __first, const value_type* __last)
00457       {
00458         size_type __old_size = _Base::bucket_count(); 
00459         _Base::insert(__first, __last);
00460         _M_profile_resize(__old_size,  _Base::bucket_count()); 
00461       }
00462      
00463       void rehash(size_type __n)
00464       {
00465         size_type __old_size =  _Base::bucket_count();
00466         _Base::rehash(__n);
00467         _M_profile_resize(__old_size,  _Base::bucket_count()); 
00468       }
00469 
00470     private:
00471       _Base&
00472       _M_base()       { return *this; }
00473 
00474       const _Base&
00475       _M_base() const { return *this; }
00476 
00477       void
00478       _M_profile_resize(size_type __old_size, size_type __new_size)
00479       {
00480         if (__old_size != __new_size)
00481           __profcxx_hashtable_resize(this, __old_size, __new_size);
00482       }
00483 
00484       void
00485       _M_profile_destruct()
00486       {
00487         size_type __hops = 0, __lc = 0, __chain = 0;
00488         for (iterator __it = _M_base().begin(); __it != _M_base().end();
00489          ++__it)
00490         {
00491           while (__it._M_cur_node->_M_next)
00492         {
00493              ++__chain;
00494              ++__it;
00495         }
00496 
00497           if (__chain)
00498         {
00499           ++__chain;
00500           __lc = __lc > __chain ? __lc : __chain;
00501           __hops += __chain * (__chain - 1) / 2;
00502           __chain = 0;
00503         }
00504         }
00505         __profcxx_hashtable_destruct2(this, __lc,  _Base::size(), __hops);
00506       }
00507 
00508    };
00509 
00510   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00511     inline void
00512     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00513      unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00514     { __x.swap(__y); }
00515 
00516   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00517     inline bool
00518     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00519            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00520     { return __x._M_equal(__y); }
00521 
00522   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00523     inline bool
00524     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00525            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00526     { return !(__x == __y); }
00527 
00528 } // namespace __profile
00529 } // namespace std
00530 
00531 #undef _GLIBCXX_BASE
00532 #undef _GLIBCXX_STD_BASE
00533 
00534 #endif // __GXX_EXPERIMENTAL_CXX0X__
00535 
00536 #endif