libstdc++
profile/unordered_map
Go to the documentation of this file.
00001 // Profiling unordered_map/unordered_multimap 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_map
00025  *  This file is a GNU profile extension to the Standard C++ Library.
00026  */
00027 
00028 #ifndef _GLIBCXX_PROFILE_UNORDERED_MAP
00029 #define _GLIBCXX_PROFILE_UNORDERED_MAP 1
00030 
00031 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00032 # include <bits/c++0x_warning.h>
00033 #else
00034 # include <unordered_map>
00035 
00036 #include <profile/base.h>
00037 
00038 #define _GLIBCXX_BASE unordered_map<_Key, _Tp, _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   /// Class std::unordered_map wrapper with performance instrumentation.
00046   template<typename _Key, typename _Tp,
00047        typename _Hash  = std::hash<_Key>,
00048        typename _Pred = std::equal_to<_Key>,
00049        typename _Alloc =  std::allocator<_Key> >
00050     class unordered_map
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       typedef typename _Base::mapped_type      mapped_type;
00066 
00067       typedef typename _Base::iterator iterator;
00068       typedef typename _Base::const_iterator const_iterator;
00069 
00070       explicit
00071       unordered_map(size_type __n = 10,
00072             const hasher& __hf = hasher(),
00073             const key_equal& __eql = key_equal(),
00074             const allocator_type& __a = allocator_type())
00075       : _Base(__n, __hf, __eql, __a)
00076       {
00077         __profcxx_hashtable_construct(this, _Base::bucket_count());
00078         __profcxx_hashtable_construct2(this);
00079       }
00080 
00081       template<typename _InputIterator>
00082         unordered_map(_InputIterator __f, _InputIterator __l,
00083               size_type __n = 0,
00084               const hasher& __hf = hasher(),
00085               const key_equal& __eql = key_equal(),
00086               const allocator_type& __a = allocator_type())
00087       : _Base(__f, __l, __n, __hf, __eql, __a)
00088       {
00089         __profcxx_hashtable_construct(this, _Base::bucket_count());
00090         __profcxx_hashtable_construct2(this);
00091       }
00092 
00093       unordered_map(const unordered_map& __x)
00094       : _Base(__x) 
00095       { 
00096         __profcxx_hashtable_construct(this, _Base::bucket_count());
00097         __profcxx_hashtable_construct2(this);
00098       }
00099 
00100       unordered_map(const _Base& __x)
00101       : _Base(__x) 
00102       { 
00103         __profcxx_hashtable_construct(this, _Base::bucket_count());
00104         __profcxx_hashtable_construct2(this);
00105       }
00106 
00107       unordered_map(unordered_map&& __x)
00108       : _Base(std::move(__x)) 
00109       {
00110         __profcxx_hashtable_construct(this, _Base::bucket_count());
00111         __profcxx_hashtable_construct2(this);
00112       }
00113 
00114       unordered_map(initializer_list<value_type> __l,
00115             size_type __n = 0,
00116             const hasher& __hf = hasher(),
00117             const key_equal& __eql = key_equal(),
00118             const allocator_type& __a = allocator_type())
00119       : _Base(__l, __n, __hf, __eql, __a) { }
00120 
00121       unordered_map&
00122       operator=(const unordered_map& __x)
00123       {
00124     *static_cast<_Base*>(this) = __x;
00125     return *this;
00126       }
00127 
00128       unordered_map&
00129       operator=(unordered_map&& __x)
00130       {
00131     // NB: DR 1204.
00132     // NB: DR 675.
00133     this->clear();
00134     this->swap(__x);
00135     return *this;
00136       }
00137 
00138       unordered_map&
00139       operator=(initializer_list<value_type> __l)
00140       {
00141     this->clear();
00142     this->insert(__l);
00143     return *this;
00144       }
00145 
00146       ~unordered_map() noexcept
00147       {
00148         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
00149                      _Base::size());
00150         _M_profile_destruct();
00151       }
00152 
00153       _Base&
00154       _M_base() noexcept       { return *this; }
00155 
00156       const _Base&
00157       _M_base() const noexcept { return *this; }
00158 
00159       void
00160       clear() noexcept
00161       {
00162         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
00163                      _Base::size());
00164         _M_profile_destruct();
00165         _Base::clear();
00166       }
00167 
00168       template<typename... _Args>
00169     std::pair<iterator, bool>
00170     emplace(_Args&&... __args)
00171     {
00172       size_type __old_size = _Base::bucket_count();
00173       std::pair<iterator, bool> __res
00174         = _Base::emplace(std::forward<_Args>(__args)...);
00175       _M_profile_resize(__old_size);
00176       return __res;
00177     }
00178 
00179       template<typename... _Args>
00180     iterator
00181     emplace_hint(const_iterator __it, _Args&&... __args)
00182     {
00183       size_type __old_size = _Base::bucket_count();
00184       iterator __res
00185         = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
00186       _M_profile_resize(__old_size);
00187       return __res;
00188     }
00189 
00190       void
00191       insert(std::initializer_list<value_type> __l)
00192       { 
00193         size_type __old_size = _Base::bucket_count(); 
00194         _Base::insert(__l);
00195         _M_profile_resize(__old_size); 
00196       }
00197 
00198       std::pair<iterator, bool>
00199       insert(const value_type& __obj)
00200       {
00201         size_type __old_size = _Base::bucket_count();
00202         std::pair<iterator, bool> __res = _Base::insert(__obj);
00203         _M_profile_resize(__old_size); 
00204         return __res;
00205       }
00206 
00207       iterator
00208       insert(const_iterator __iter, const value_type& __v)
00209       { 
00210         size_type __old_size = _Base::bucket_count(); 
00211         iterator __res = _Base::insert(__iter, __v);
00212         _M_profile_resize(__old_size); 
00213         return __res;
00214       }
00215 
00216       template<typename _Pair, typename = typename
00217            std::enable_if<std::is_convertible<_Pair,
00218                           value_type>::value>::type>
00219         std::pair<iterator, bool>
00220         insert(_Pair&& __obj)
00221         {
00222       size_type __old_size = _Base::bucket_count();
00223       std::pair<iterator, bool> __res
00224         = _Base::insert(std::forward<_Pair>(__obj));
00225       _M_profile_resize(__old_size); 
00226       return __res;
00227     }
00228 
00229       template<typename _Pair, typename = typename
00230            std::enable_if<std::is_convertible<_Pair,
00231                           value_type>::value>::type>
00232         iterator
00233         insert(const_iterator __iter, _Pair&& __v)
00234         { 
00235       size_type __old_size = _Base::bucket_count(); 
00236       iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
00237       _M_profile_resize(__old_size); 
00238       return __res;
00239     }
00240 
00241       template<typename _InputIter>
00242         void
00243         insert(_InputIter __first, _InputIter __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
00251       insert(const value_type* __first, const value_type* __last)
00252       {
00253         size_type __old_size = _Base::bucket_count(); 
00254         _Base::insert(__first, __last);
00255         _M_profile_resize(__old_size); 
00256       }
00257 
00258       // operator[]
00259       mapped_type&
00260       operator[](const _Key& __k)
00261       {
00262         size_type __old_size = _Base::bucket_count();
00263         mapped_type& __res = _M_base()[__k];
00264         _M_profile_resize(__old_size); 
00265         return __res;
00266       }
00267 
00268       mapped_type&
00269       operator[](_Key&& __k)
00270       {
00271         size_type __old_size = _Base::bucket_count();
00272         mapped_type& __res = _M_base()[std::move(__k)];
00273         _M_profile_resize(__old_size); 
00274         return __res;
00275       }
00276 
00277       void
00278       swap(unordered_map& __x)
00279       { _Base::swap(__x); }
00280 
00281       void rehash(size_type __n)
00282       {
00283     size_type __old_size = _Base::bucket_count();
00284     _Base::rehash(__n);
00285     _M_profile_resize(__old_size); 
00286       }
00287 
00288     private:
00289       void
00290       _M_profile_resize(size_type __old_size)
00291       {
00292     size_type __new_size = _Base::bucket_count();
00293     if (__old_size != __new_size)
00294       __profcxx_hashtable_resize(this, __old_size, __new_size);
00295       }
00296 
00297       void
00298       _M_profile_destruct()
00299       {
00300     size_type __hops = 0, __lc = 0, __chain = 0;
00301     iterator __it = this->begin();
00302     while (__it != this->end())
00303       {
00304         size_type __bkt = this->bucket(__it->first);
00305         auto __lit = this->begin(__bkt);
00306         auto __lend = this->end(__bkt);
00307         for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
00308           ++__chain;
00309         if (__chain)
00310           {
00311         ++__chain;
00312         __lc = __lc > __chain ? __lc : __chain;
00313         __hops += __chain * (__chain - 1) / 2;
00314         __chain = 0;
00315           }
00316       }
00317     __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
00318       }
00319   };
00320 
00321   template<typename _Key, typename _Tp, typename _Hash,
00322        typename _Pred, typename _Alloc>
00323     inline void
00324     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00325      unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00326     { __x.swap(__y); }
00327 
00328   template<typename _Key, typename _Tp, typename _Hash,
00329        typename _Pred, typename _Alloc>
00330     inline bool
00331     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00332            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00333     { return __x._M_equal(__y); }
00334 
00335   template<typename _Key, typename _Tp, typename _Hash,
00336        typename _Pred, typename _Alloc>
00337     inline bool
00338     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00339            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00340     { return !(__x == __y); }
00341 
00342 #undef _GLIBCXX_BASE
00343 #undef _GLIBCXX_STD_BASE
00344 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
00345 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
00346 
00347   /// Class std::unordered_multimap wrapper with performance instrumentation.
00348   template<typename _Key, typename _Tp,
00349        typename _Hash  = std::hash<_Key>,
00350        typename _Pred = std::equal_to<_Key>,
00351        typename _Alloc =  std::allocator<_Key> >
00352     class unordered_multimap
00353     : public _GLIBCXX_STD_BASE
00354     {      
00355       typedef typename _GLIBCXX_STD_BASE _Base;
00356 
00357     public:
00358       typedef typename _Base::size_type       size_type;
00359       typedef typename _Base::hasher          hasher;
00360       typedef typename _Base::key_equal       key_equal;
00361       typedef typename _Base::allocator_type  allocator_type;
00362       typedef typename _Base::key_type        key_type;
00363       typedef typename _Base::value_type      value_type;
00364       typedef typename _Base::difference_type difference_type;
00365       typedef typename _Base::reference       reference;
00366       typedef typename _Base::const_reference const_reference;
00367 
00368       typedef typename _Base::iterator iterator;
00369       typedef typename _Base::const_iterator const_iterator;
00370 
00371       explicit
00372       unordered_multimap(size_type __n = 10,
00373              const hasher& __hf = hasher(),
00374              const key_equal& __eql = key_equal(),
00375              const allocator_type& __a = allocator_type())
00376       : _Base(__n, __hf, __eql, __a)
00377       {
00378         __profcxx_hashtable_construct(this, _Base::bucket_count());
00379       }
00380       template<typename _InputIterator>
00381         unordered_multimap(_InputIterator __f, _InputIterator __l,
00382                size_type __n = 0,
00383                const hasher& __hf = hasher(),
00384                const key_equal& __eql = key_equal(),
00385                const allocator_type& __a = allocator_type())
00386       : _Base(__f, __l, __n, __hf, __eql, __a)
00387       {
00388         __profcxx_hashtable_construct(this, _Base::bucket_count());
00389       }
00390 
00391       unordered_multimap(const unordered_multimap& __x)
00392       : _Base(__x)
00393       {
00394         __profcxx_hashtable_construct(this, _Base::bucket_count());
00395       }
00396 
00397       unordered_multimap(const _Base& __x)
00398       : _Base(__x)
00399       {
00400         __profcxx_hashtable_construct(this, _Base::bucket_count());
00401       }
00402 
00403       unordered_multimap(unordered_multimap&& __x)
00404       : _Base(std::move(__x))
00405       {
00406         __profcxx_hashtable_construct(this, _Base::bucket_count());
00407       }
00408 
00409       unordered_multimap(initializer_list<value_type> __l,
00410              size_type __n = 0,
00411              const hasher& __hf = hasher(),
00412              const key_equal& __eql = key_equal(),
00413              const allocator_type& __a = allocator_type())
00414       : _Base(__l, __n, __hf, __eql, __a) { }
00415 
00416       unordered_multimap&
00417       operator=(const unordered_multimap& __x)
00418       {
00419     *static_cast<_Base*>(this) = __x;
00420     return *this;
00421       }
00422 
00423       unordered_multimap&
00424       operator=(unordered_multimap&& __x)
00425       {
00426     // NB: DR 1204.
00427     // NB: DR 675.
00428     this->clear();
00429     this->swap(__x);
00430     return *this;
00431       }
00432 
00433       unordered_multimap&
00434       operator=(initializer_list<value_type> __l)
00435       {
00436     this->clear();
00437     this->insert(__l);
00438     return *this;
00439       }
00440 
00441       ~unordered_multimap() noexcept
00442       {
00443         __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
00444                      _Base::size());
00445         _M_profile_destruct();
00446       }
00447 
00448       void
00449       clear() noexcept
00450       {
00451         __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
00452                      _Base::size());
00453         _M_profile_destruct();
00454         _Base::clear();
00455       }
00456 
00457       template<typename... _Args>
00458     iterator
00459     emplace(_Args&&... __args)
00460     {
00461       size_type __old_size = _Base::bucket_count();
00462       iterator __res
00463         = _Base::emplace(std::forward<_Args>(__args)...);
00464       _M_profile_resize(__old_size);
00465       return __res;
00466     }
00467 
00468       template<typename... _Args>
00469     iterator
00470     emplace_hint(const_iterator __it, _Args&&... __args)
00471     {
00472       size_type __old_size = _Base::bucket_count();
00473       iterator __res
00474         = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
00475       _M_profile_resize(__old_size);
00476       return __res;
00477     }
00478 
00479       void
00480       insert(std::initializer_list<value_type> __l)
00481       { 
00482         size_type __old_size = _Base::bucket_count();
00483         _Base::insert(__l);
00484         _M_profile_resize(__old_size);
00485       }
00486 
00487       iterator
00488       insert(const value_type& __obj)
00489       {
00490         size_type __old_size = _Base::bucket_count();
00491         iterator __res = _Base::insert(__obj);
00492         _M_profile_resize(__old_size); 
00493         return __res;
00494       }
00495 
00496       iterator
00497       insert(const_iterator __iter, const value_type& __v)
00498       { 
00499         size_type __old_size = _Base::bucket_count(); 
00500         iterator __res = _Base::insert(__iter, __v);
00501         _M_profile_resize(__old_size); 
00502         return __res;
00503       }
00504 
00505       template<typename _Pair, typename = typename
00506            std::enable_if<std::is_convertible<_Pair,
00507                           value_type>::value>::type>
00508         iterator
00509         insert(_Pair&& __obj)
00510         {
00511       size_type __old_size = _Base::bucket_count();
00512       iterator __res = _Base::insert(std::forward<_Pair>(__obj));
00513       _M_profile_resize(__old_size); 
00514       return __res;
00515     }
00516 
00517       template<typename _Pair, typename = typename
00518            std::enable_if<std::is_convertible<_Pair,
00519                           value_type>::value>::type>
00520         iterator
00521         insert(const_iterator __iter, _Pair&& __v)
00522         {
00523       size_type __old_size = _Base::bucket_count(); 
00524       iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
00525       _M_profile_resize(__old_size); 
00526       return __res;
00527     }
00528 
00529       template<typename _InputIter>
00530         void
00531         insert(_InputIter __first, _InputIter __last)
00532         {
00533       size_type __old_size = _Base::bucket_count(); 
00534       _Base::insert(__first, __last);
00535       _M_profile_resize(__old_size); 
00536     }
00537 
00538       void
00539       insert(const value_type* __first, const value_type* __last)
00540       {
00541         size_type __old_size = _Base::bucket_count(); 
00542         _Base::insert(__first, __last);
00543         _M_profile_resize(__old_size); 
00544       }
00545 
00546       void
00547       swap(unordered_multimap& __x)
00548       { _Base::swap(__x); }
00549 
00550       void rehash(size_type __n)
00551       {
00552         size_type __old_size = _Base::bucket_count();
00553         _Base::rehash(__n);
00554         _M_profile_resize(__old_size); 
00555       }
00556 
00557     private:
00558       void
00559       _M_profile_resize(size_type __old_size)
00560       {
00561     size_type __new_size = _Base::bucket_count();
00562         if (__old_size != __new_size)
00563           __profcxx_hashtable_resize(this, __old_size, __new_size);
00564       }
00565 
00566       void
00567       _M_profile_destruct()
00568       {
00569     size_type __hops = 0, __lc = 0, __chain = 0;
00570     iterator __it = this->begin();
00571     while (__it != this->end())
00572       {
00573         size_type __bkt = this->bucket(__it->first);
00574         auto __lit = this->begin(__bkt);
00575         auto __lend = this->end(__bkt);
00576         for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
00577           ++__chain;
00578         if (__chain)
00579           {
00580         ++__chain;
00581         __lc = __lc > __chain ? __lc : __chain;
00582         __hops += __chain * (__chain - 1) / 2;
00583         __chain = 0;
00584           }
00585       }
00586     __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
00587       }
00588   };
00589 
00590   template<typename _Key, typename _Tp, typename _Hash,
00591        typename _Pred, typename _Alloc>
00592     inline void
00593     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00594      unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00595     { __x.swap(__y); }
00596 
00597   template<typename _Key, typename _Tp, typename _Hash,
00598        typename _Pred, typename _Alloc>
00599     inline bool
00600     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00601            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00602     { return __x._M_equal(__y); }
00603 
00604   template<typename _Key, typename _Tp, typename _Hash,
00605        typename _Pred, typename _Alloc>
00606     inline bool
00607     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00608            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00609     { return !(__x == __y); }
00610 
00611 } // namespace __profile
00612 } // namespace std
00613 
00614 #undef _GLIBCXX_BASE
00615 #undef _GLIBCXX_STD_BASE
00616 
00617 #endif // __GXX_EXPERIMENTAL_CXX0X__
00618 
00619 #endif