libstdc++-v3/include/profile/unordered_map

   1 // Profiling unordered_map/unordered_multimap implementation -*- C++ -*-
   2
   3 // Copyright (C) 2009, 2010 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /** @file profile/unordered_map
  31  *  This file is a GNU profile extension to the Standard C++ Library.
  32  */
  33
  34 #ifndef _GLIBCXX_PROFILE_UNORDERED_MAP
  35 #define _GLIBCXX_PROFILE_UNORDERED_MAP 1
  36
  37 #ifndef __GXX_EXPERIMENTAL_CXX0X__
  38 # include <bits/c++0x_warning.h>
  39 #else
  40 # include <unordered_map>
  41
  42 #include <profile/base.h>
  43
  44 #define _GLIBCXX_BASE unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
  45 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE
  46
  47 namespace std
  48 {
  49 namespace __profile
  50 {
  51   /// Class std::unordered_map wrapper with performance instrumentation.
  52   template<typename _Key, typename _Tp,
  53            typename _Hash  = std::hash<_Key>,
  54            typename _Pred = std::equal_to<_Key>,
  55            typename _Alloc =  std::allocator<_Key> >
  56     class unordered_map
  57     : public _GLIBCXX_STD_BASE
  58     {
  59       typedef typename _GLIBCXX_STD_BASE _Base;
  60
  61     public:
  62       typedef typename _Base::size_type       size_type;
  63       typedef typename _Base::hasher          hasher;
  64       typedef typename _Base::key_equal       key_equal;
  65       typedef typename _Base::allocator_type  allocator_type;
  66       typedef typename _Base::key_type        key_type;
  67       typedef typename _Base::value_type      value_type;
  68       typedef typename _Base::difference_type difference_type;
  69       typedef typename _Base::reference       reference;
  70       typedef typename _Base::const_reference const_reference;
  71       typedef typename _Base::mapped_type      mapped_type;
  72
  73       typedef typename _Base::iterator iterator;
  74       typedef typename _Base::const_iterator const_iterator;
  75
  76       explicit
  77       unordered_map(size_type __n = 10,
  78                     const hasher& __hf = hasher(),
  79                     const key_equal& __eql = key_equal(),
  80                     const allocator_type& __a = allocator_type())
  81       : _Base(__n, __hf, __eql, __a)
  82       {
  83         __profcxx_hashtable_construct(this, _Base::bucket_count());
  84         __profcxx_hashtable_construct2(this);
  85       }
  86
  87       template<typename _InputIterator>
  88         unordered_map(_InputIterator __f, _InputIterator __l,
  89                       size_type __n = 0,
  90                       const hasher& __hf = hasher(),
  91                       const key_equal& __eql = key_equal(),
  92                       const allocator_type& __a = allocator_type())
  93       : _Base(__f, __l, __n, __hf, __eql, __a)
  94       {
  95         __profcxx_hashtable_construct(this, _Base::bucket_count());
  96         __profcxx_hashtable_construct2(this);
  97       }
  98
  99       unordered_map(const _Base& __x)
 100       : _Base(__x)
 101       {
 102         __profcxx_hashtable_construct(this, _Base::bucket_count());
 103         __profcxx_hashtable_construct2(this);
 104       }
 105
 106       unordered_map(unordered_map&& __x)
 107       : _Base(std::move(__x))
 108       {
 109         __profcxx_hashtable_construct(this, _Base::bucket_count());
 110         __profcxx_hashtable_construct2(this);
 111       }
 112
 113       unordered_map(initializer_list<value_type> __l,
 114                     size_type __n = 0,
 115                     const hasher& __hf = hasher(),
 116                     const key_equal& __eql = key_equal(),
 117                     const allocator_type& __a = allocator_type())
 118       : _Base(__l, __n, __hf, __eql, __a) { }
 119
 120       unordered_map&
 121       operator=(const unordered_map& __x)
 122       {
 123         *static_cast<_Base*>(this) = __x;
 124         return *this;
 125       }
 126
 127       unordered_map&
 128       operator=(unordered_map&& __x)
 129       {
 130         // NB: DR 1204.
 131         // NB: DR 675.
 132         this->clear();
 133         this->swap(__x);
 134         return *this;
 135       }
 136
 137       unordered_map&
 138       operator=(initializer_list<value_type> __l)
 139       {
 140         this->clear();
 141         this->insert(__l);
 142         return *this;
 143       }
 144
 145       ~unordered_map()
 146       {
 147         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 148                                      _Base::size());
 149         _M_profile_destruct();
 150       }
 151
 152       _Base&
 153       _M_base()       { return *this; }
 154
 155       const _Base&
 156       _M_base() const { return *this; }
 157
 158
 159       void
 160       clear()
 161       {
 162         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 163                                      _Base::size());
 164         _M_profile_destruct();
 165         _Base::clear();
 166       }
 167
 168       void
 169       insert(std::initializer_list<value_type> __l)
 170       {
 171         size_type __old_size = _Base::bucket_count();
 172         _Base::insert(__l);
 173         _M_profile_resize(__old_size, _Base::bucket_count());
 174       }
 175
 176       std::pair<iterator, bool>
 177       insert(const value_type& __obj)
 178       {
 179         size_type __old_size =  _Base::bucket_count();
 180         std::pair<iterator, bool> __res = _Base::insert(__obj);
 181         _M_profile_resize(__old_size, _Base::bucket_count());
 182         return __res;
 183       }
 184
 185       iterator
 186       insert(const_iterator __iter, const value_type& __v)
 187       {
 188         size_type __old_size = _Base::bucket_count();
 189         iterator __res = _Base::insert(__iter, __v);
 190         _M_profile_resize(__old_size, _Base::bucket_count());
 191         return __res;
 192       }
 193
 194       template<typename _InputIter>
 195         void
 196         insert(_InputIter __first, _InputIter __last)
 197         {
 198           size_type __old_size = _Base::bucket_count();
 199           _Base::insert(__first, __last);
 200           _M_profile_resize(__old_size, _Base::bucket_count());
 201         }
 202
 203       void
 204       insert(const value_type* __first, const value_type* __last)
 205       {
 206         size_type __old_size = _Base::bucket_count();
 207         _Base::insert(__first, __last);
 208         _M_profile_resize(__old_size, _Base::bucket_count());
 209       }
 210
 211       // operator []
 212       mapped_type&
 213       operator[](const _Key& _k)
 214       {
 215         size_type __old_size =  _Base::bucket_count();
 216         mapped_type& __res = _M_base()[_k];
 217         size_type __new_size =  _Base::bucket_count();
 218         _M_profile_resize(__old_size, _Base::bucket_count());
 219         return __res;
 220       }
 221
 222       void
 223       swap(unordered_map& __x)
 224       { _Base::swap(__x); }
 225
 226       void rehash(size_type __n)
 227       {
 228         size_type __old_size =  _Base::bucket_count();
 229         _Base::rehash(__n);
 230         _M_profile_resize(__old_size, _Base::bucket_count());
 231       }
 232
 233     private:
 234       void
 235       _M_profile_resize(size_type __old_size, size_type __new_size)
 236       {
 237         if (__old_size != __new_size)
 238           __profcxx_hashtable_resize(this, __old_size, __new_size);
 239       }
 240
 241       void
 242       _M_profile_destruct()
 243       {
 244         size_type __hops = 0, __lc = 0, __chain = 0;
 245         for (iterator __it = _M_base().begin(); __it != _M_base().end();
 246              ++__it)
 247           {
 248             while (__it._M_cur_node->_M_next)
 249               {
 250                 ++__chain;
 251                 ++__it;
 252               }
 253             if (__chain)
 254               {
 255                 ++__chain;
 256                 __lc = __lc > __chain ? __lc : __chain;
 257                 __hops += __chain * (__chain - 1) / 2;
 258                 __chain = 0;
 259               }
 260           }
 261         __profcxx_hashtable_destruct2(this, __lc,  _Base::size(), __hops);
 262       }
 263    };
 264
 265   template<typename _Key, typename _Tp, typename _Hash,
 266            typename _Pred, typename _Alloc>
 267     inline void
 268     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 269          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 270     { __x.swap(__y); }
 271
 272   template<typename _Key, typename _Tp, typename _Hash,
 273            typename _Pred, typename _Alloc>
 274     inline bool
 275     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 276                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 277     { return __x._M_equal(__y); }
 278
 279   template<typename _Key, typename _Tp, typename _Hash,
 280            typename _Pred, typename _Alloc>
 281     inline bool
 282     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 283                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 284     { return !(__x == __y); }
 285
 286 #undef _GLIBCXX_BASE
 287 #undef _GLIBCXX_STD_BASE
 288 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
 289 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE
 290
 291   /// Class std::unordered_multimap wrapper with performance instrumentation.
 292   template<typename _Key, typename _Tp,
 293            typename _Hash  = std::hash<_Key>,
 294            typename _Pred = std::equal_to<_Key>,
 295            typename _Alloc =  std::allocator<_Key> >
 296     class unordered_multimap
 297     : public _GLIBCXX_STD_BASE
 298     {
 299       typedef typename _GLIBCXX_STD_BASE _Base;
 300
 301     public:
 302       typedef typename _Base::size_type       size_type;
 303       typedef typename _Base::hasher          hasher;
 304       typedef typename _Base::key_equal       key_equal;
 305       typedef typename _Base::allocator_type  allocator_type;
 306       typedef typename _Base::key_type        key_type;
 307       typedef typename _Base::value_type      value_type;
 308       typedef typename _Base::difference_type difference_type;
 309       typedef typename _Base::reference       reference;
 310       typedef typename _Base::const_reference const_reference;
 311
 312       typedef typename _Base::iterator iterator;
 313       typedef typename _Base::const_iterator const_iterator;
 314
 315       explicit
 316       unordered_multimap(size_type __n = 10,
 317                          const hasher& __hf = hasher(),
 318                          const key_equal& __eql = key_equal(),
 319                          const allocator_type& __a = allocator_type())
 320       : _Base(__n, __hf, __eql, __a)
 321       {
 322         __profcxx_hashtable_construct(this, _Base::bucket_count());
 323       }
 324       template<typename _InputIterator>
 325         unordered_multimap(_InputIterator __f, _InputIterator __l,
 326                            size_type __n = 0,
 327                            const hasher& __hf = hasher(),
 328                            const key_equal& __eql = key_equal(),
 329                            const allocator_type& __a = allocator_type())
 330       : _Base(__f, __l, __n, __hf, __eql, __a)
 331       {
 332         __profcxx_hashtable_construct(this, _Base::bucket_count());
 333       }
 334
 335       unordered_multimap(const _Base& __x)
 336       : _Base(__x)
 337       {
 338         __profcxx_hashtable_construct(this, _Base::bucket_count());
 339       }
 340
 341       unordered_multimap(unordered_multimap&& __x)
 342       : _Base(std::move(__x))
 343       {
 344         __profcxx_hashtable_construct(this, _Base::bucket_count());
 345       }
 346
 347       unordered_multimap(initializer_list<value_type> __l,
 348                          size_type __n = 0,
 349                          const hasher& __hf = hasher(),
 350                          const key_equal& __eql = key_equal(),
 351                          const allocator_type& __a = allocator_type())
 352       : _Base(__l, __n, __hf, __eql, __a) { }
 353
 354       unordered_multimap&
 355       operator=(const unordered_multimap& __x)
 356       {
 357         *static_cast<_Base*>(this) = __x;
 358         return *this;
 359       }
 360
 361       unordered_multimap&
 362       operator=(unordered_multimap&& __x)
 363       {
 364         // NB: DR 1204.
 365         // NB: DR 675.
 366         this->clear();
 367         this->swap(__x);
 368         return *this;
 369       }
 370
 371       unordered_multimap&
 372       operator=(initializer_list<value_type> __l)
 373       {
 374         this->clear();
 375         this->insert(__l);
 376         return *this;
 377       }
 378
 379       ~unordered_multimap()
 380       {
 381         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 382                                      _Base::size());
 383         _M_profile_destruct();
 384       }
 385
 386       _Base&
 387       _M_base()       { return *this; }
 388
 389       const _Base&
 390       _M_base() const { return *this; }
 391
 392
 393       void
 394       clear()
 395       {
 396         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 397                                      _Base::size());
 398         _M_profile_destruct();
 399         _Base::clear();
 400       }
 401
 402       void
 403       insert(std::initializer_list<value_type> __l)
 404       {
 405         size_type __old_size =  _Base::bucket_count();
 406         _Base::insert(__l);
 407         _M_profile_resize(__old_size, _Base::bucket_count());
 408       }
 409
 410       iterator
 411       insert(const value_type& __obj)
 412       {
 413         size_type __old_size =  _Base::bucket_count();
 414         iterator __res = _Base::insert(__obj);
 415         _M_profile_resize(__old_size, _Base::bucket_count());
 416         return __res;
 417       }
 418
 419       iterator
 420       insert(const_iterator __iter, const value_type& __v)
 421       {
 422         size_type __old_size = _Base::bucket_count();
 423         iterator __res =_Base::insert(__iter, __v);
 424         _M_profile_resize(__old_size, _Base::bucket_count());
 425         return __res;
 426       }
 427
 428       template<typename _InputIter>
 429         void
 430         insert(_InputIter __first, _InputIter __last)
 431         {
 432           size_type __old_size = _Base::bucket_count();
 433           _Base::insert(__first, __last);
 434           _M_profile_resize(__old_size, _Base::bucket_count());
 435         }
 436
 437       void
 438       insert(const value_type* __first, const value_type* __last)
 439       {
 440         size_type __old_size = _Base::bucket_count();
 441         _Base::insert(__first, __last);
 442         _M_profile_resize(__old_size, _Base::bucket_count());
 443       }
 444
 445       void
 446       swap(unordered_multimap& __x)
 447       { _Base::swap(__x); }
 448
 449       void rehash(size_type __n)
 450       {
 451         size_type __old_size =  _Base::bucket_count();
 452         _Base::rehash(__n);
 453         _M_profile_resize(__old_size, _Base::bucket_count());
 454       }
 455
 456     private:
 457       void
 458       _M_profile_resize(size_type __old_size, size_type __new_size)
 459       {
 460         if (__old_size != __new_size)
 461           __profcxx_hashtable_resize(this, __old_size, __new_size);
 462       }
 463
 464       void
 465       _M_profile_destruct()
 466       {
 467         size_type __hops = 0, __lc = 0, __chain = 0;
 468         for (iterator __it = _M_base().begin(); __it != _M_base().end();
 469              ++__it)
 470           {
 471             while (__it._M_cur_node->_M_next)
 472               {
 473                 ++__chain;
 474                 ++__it;
 475               }
 476             if (__chain)
 477               {
 478                 ++__chain;
 479                 __lc = __lc > __chain ? __lc : __chain;
 480                 __hops += __chain * (__chain - 1) / 2;
 481                 __chain = 0;
 482               }
 483           }
 484         __profcxx_hashtable_destruct2(this, __lc,  _Base::size(), __hops);
 485       }
 486
 487     };
 488
 489   template<typename _Key, typename _Tp, typename _Hash,
 490            typename _Pred, typename _Alloc>
 491     inline void
 492     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 493          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 494     { __x.swap(__y); }
 495
 496   template<typename _Key, typename _Tp, typename _Hash,
 497            typename _Pred, typename _Alloc>
 498     inline bool
 499     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 500                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 501     { return __x._M_equal(__y); }
 502
 503   template<typename _Key, typename _Tp, typename _Hash,
 504            typename _Pred, typename _Alloc>
 505     inline bool
 506     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 507                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 508     { return !(__x == __y); }
 509
 510 } // namespace __profile
 511 } // namespace std
 512
 513 #undef _GLIBCXX_BASE
 514 #undef _GLIBCXX_STD_BASE
 515
 516 #endif // __GXX_EXPERIMENTAL_CXX0X__
 517
 518 #endif