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