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