libstdc++-v3/include/profile/unordered_map

   1 // Profiling unordered_map/unordered_multimap implementation -*- C++ -*-
   2
   3 // Copyright (C) 2009, 2010, 2011 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_C::_GLIBCXX_BASE
  46
  47 namespace std _GLIBCXX_VISIBILITY(default)
  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 unordered_map& __x)
 100       : _Base(__x)
 101       {
 102         __profcxx_hashtable_construct(this, _Base::bucket_count());
 103         __profcxx_hashtable_construct2(this);
 104       }
 105
 106       unordered_map(const _Base& __x)
 107       : _Base(__x)
 108       {
 109         __profcxx_hashtable_construct(this, _Base::bucket_count());
 110         __profcxx_hashtable_construct2(this);
 111       }
 112
 113       unordered_map(unordered_map&& __x)
 114       : _Base(std::move(__x))
 115       {
 116         __profcxx_hashtable_construct(this, _Base::bucket_count());
 117         __profcxx_hashtable_construct2(this);
 118       }
 119
 120       unordered_map(initializer_list<value_type> __l,
 121                     size_type __n = 0,
 122                     const hasher& __hf = hasher(),
 123                     const key_equal& __eql = key_equal(),
 124                     const allocator_type& __a = allocator_type())
 125       : _Base(__l, __n, __hf, __eql, __a) { }
 126
 127       unordered_map&
 128       operator=(const unordered_map& __x)
 129       {
 130         *static_cast<_Base*>(this) = __x;
 131         return *this;
 132       }
 133
 134       unordered_map&
 135       operator=(unordered_map&& __x)
 136       {
 137         // NB: DR 1204.
 138         // NB: DR 675.
 139         this->clear();
 140         this->swap(__x);
 141         return *this;
 142       }
 143
 144       unordered_map&
 145       operator=(initializer_list<value_type> __l)
 146       {
 147         this->clear();
 148         this->insert(__l);
 149         return *this;
 150       }
 151
 152       ~unordered_map() noexcept
 153       {
 154         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 155                                      _Base::size());
 156         _M_profile_destruct();
 157       }
 158
 159       _Base&
 160       _M_base() noexcept       { return *this; }
 161
 162       const _Base&
 163       _M_base() const noexcept { return *this; }
 164
 165       void
 166       clear() noexcept
 167       {
 168         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 169                                      _Base::size());
 170         _M_profile_destruct();
 171         _Base::clear();
 172       }
 173
 174       void
 175       insert(std::initializer_list<value_type> __l)
 176       {
 177         size_type __old_size = _Base::bucket_count();
 178         _Base::insert(__l);
 179         _M_profile_resize(__old_size);
 180       }
 181
 182       std::pair<iterator, bool>
 183       insert(const value_type& __obj)
 184       {
 185         size_type __old_size =  _Base::bucket_count();
 186         std::pair<iterator, bool> __res = _Base::insert(__obj);
 187         _M_profile_resize(__old_size);
 188         return __res;
 189       }
 190
 191       iterator
 192       insert(const_iterator __iter, const value_type& __v)
 193       {
 194         size_type __old_size = _Base::bucket_count();
 195         iterator __res = _Base::insert(__iter, __v);
 196         _M_profile_resize(__old_size);
 197         return __res;
 198       }
 199
 200       template<typename _Pair, typename = typename
 201                std::enable_if<std::is_convertible<_Pair,
 202                                                   value_type>::value>::type>
 203         std::pair<iterator, bool>
 204         insert(_Pair&& __obj)
 205         {
 206           size_type __old_size =  _Base::bucket_count();
 207           std::pair<iterator, bool> __res
 208             = _Base::insert(std::forward<_Pair>(__obj));
 209           _M_profile_resize(__old_size);
 210           return __res;
 211         }
 212
 213       template<typename _Pair, typename = typename
 214                std::enable_if<std::is_convertible<_Pair,
 215                                                   value_type>::value>::type>
 216         iterator
 217         insert(const_iterator __iter, _Pair&& __v)
 218         {
 219           size_type __old_size = _Base::bucket_count();
 220           iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
 221           _M_profile_resize(__old_size);
 222           return __res;
 223         }
 224
 225       template<typename _InputIter>
 226         void
 227         insert(_InputIter __first, _InputIter __last)
 228         {
 229           size_type __old_size = _Base::bucket_count();
 230           _Base::insert(__first, __last);
 231           _M_profile_resize(__old_size);
 232         }
 233
 234       void
 235       insert(const value_type* __first, const value_type* __last)
 236       {
 237         size_type __old_size = _Base::bucket_count();
 238         _Base::insert(__first, __last);
 239         _M_profile_resize(__old_size);
 240       }
 241
 242       // operator[]
 243       mapped_type&
 244       operator[](const _Key& __k)
 245       {
 246         size_type __old_size =  _Base::bucket_count();
 247         mapped_type& __res = _M_base()[__k];
 248         _M_profile_resize(__old_size);
 249         return __res;
 250       }
 251
 252       mapped_type&
 253       operator[](_Key&& __k)
 254       {
 255         size_type __old_size =  _Base::bucket_count();
 256         mapped_type& __res = _M_base()[std::move(__k)];
 257         _M_profile_resize(__old_size);
 258         return __res;
 259       }
 260
 261       void
 262       swap(unordered_map& __x)
 263       { _Base::swap(__x); }
 264
 265       void rehash(size_type __n)
 266       {
 267         size_type __old_size =  _Base::bucket_count();
 268         _Base::rehash(__n);
 269         _M_profile_resize(__old_size);
 270       }
 271
 272     private:
 273       void
 274       _M_profile_resize(size_type __old_size)
 275       {
 276         size_type __new_size = _Base::bucket_count();
 277         if (__old_size != __new_size)
 278           __profcxx_hashtable_resize(this, __old_size, __new_size);
 279       }
 280
 281       void
 282       _M_profile_destruct()
 283       {
 284         size_type __hops = 0, __lc = 0, __chain = 0;
 285         for (iterator __it = _M_base().begin(); __it != _M_base().end();
 286              ++__it)
 287           {
 288             while (__it._M_cur_node->_M_next)
 289               {
 290                 ++__chain;
 291                 ++__it;
 292               }
 293             if (__chain)
 294               {
 295                 ++__chain;
 296                 __lc = __lc > __chain ? __lc : __chain;
 297                 __hops += __chain * (__chain - 1) / 2;
 298                 __chain = 0;
 299               }
 300           }
 301         __profcxx_hashtable_destruct2(this, __lc,  _Base::size(), __hops);
 302       }
 303    };
 304
 305   template<typename _Key, typename _Tp, typename _Hash,
 306            typename _Pred, typename _Alloc>
 307     inline void
 308     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 309          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 310     { __x.swap(__y); }
 311
 312   template<typename _Key, typename _Tp, typename _Hash,
 313            typename _Pred, typename _Alloc>
 314     inline bool
 315     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 316                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 317     { return __x._M_equal(__y); }
 318
 319   template<typename _Key, typename _Tp, typename _Hash,
 320            typename _Pred, typename _Alloc>
 321     inline bool
 322     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 323                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 324     { return !(__x == __y); }
 325
 326 #undef _GLIBCXX_BASE
 327 #undef _GLIBCXX_STD_BASE
 328 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
 329 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
 330
 331   /// Class std::unordered_multimap wrapper with performance instrumentation.
 332   template<typename _Key, typename _Tp,
 333            typename _Hash  = std::hash<_Key>,
 334            typename _Pred = std::equal_to<_Key>,
 335            typename _Alloc =  std::allocator<_Key> >
 336     class unordered_multimap
 337     : public _GLIBCXX_STD_BASE
 338     {
 339       typedef typename _GLIBCXX_STD_BASE _Base;
 340
 341     public:
 342       typedef typename _Base::size_type       size_type;
 343       typedef typename _Base::hasher          hasher;
 344       typedef typename _Base::key_equal       key_equal;
 345       typedef typename _Base::allocator_type  allocator_type;
 346       typedef typename _Base::key_type        key_type;
 347       typedef typename _Base::value_type      value_type;
 348       typedef typename _Base::difference_type difference_type;
 349       typedef typename _Base::reference       reference;
 350       typedef typename _Base::const_reference const_reference;
 351
 352       typedef typename _Base::iterator iterator;
 353       typedef typename _Base::const_iterator const_iterator;
 354
 355       explicit
 356       unordered_multimap(size_type __n = 10,
 357                          const hasher& __hf = hasher(),
 358                          const key_equal& __eql = key_equal(),
 359                          const allocator_type& __a = allocator_type())
 360       : _Base(__n, __hf, __eql, __a)
 361       {
 362         __profcxx_hashtable_construct(this, _Base::bucket_count());
 363       }
 364       template<typename _InputIterator>
 365         unordered_multimap(_InputIterator __f, _InputIterator __l,
 366                            size_type __n = 0,
 367                            const hasher& __hf = hasher(),
 368                            const key_equal& __eql = key_equal(),
 369                            const allocator_type& __a = allocator_type())
 370       : _Base(__f, __l, __n, __hf, __eql, __a)
 371       {
 372         __profcxx_hashtable_construct(this, _Base::bucket_count());
 373       }
 374
 375       unordered_multimap(const unordered_multimap& __x)
 376       : _Base(__x)
 377       {
 378         __profcxx_hashtable_construct(this, _Base::bucket_count());
 379       }
 380
 381       unordered_multimap(const _Base& __x)
 382       : _Base(__x)
 383       {
 384         __profcxx_hashtable_construct(this, _Base::bucket_count());
 385       }
 386
 387       unordered_multimap(unordered_multimap&& __x)
 388       : _Base(std::move(__x))
 389       {
 390         __profcxx_hashtable_construct(this, _Base::bucket_count());
 391       }
 392
 393       unordered_multimap(initializer_list<value_type> __l,
 394                          size_type __n = 0,
 395                          const hasher& __hf = hasher(),
 396                          const key_equal& __eql = key_equal(),
 397                          const allocator_type& __a = allocator_type())
 398       : _Base(__l, __n, __hf, __eql, __a) { }
 399
 400       unordered_multimap&
 401       operator=(const unordered_multimap& __x)
 402       {
 403         *static_cast<_Base*>(this) = __x;
 404         return *this;
 405       }
 406
 407       unordered_multimap&
 408       operator=(unordered_multimap&& __x)
 409       {
 410         // NB: DR 1204.
 411         // NB: DR 675.
 412         this->clear();
 413         this->swap(__x);
 414         return *this;
 415       }
 416
 417       unordered_multimap&
 418       operator=(initializer_list<value_type> __l)
 419       {
 420         this->clear();
 421         this->insert(__l);
 422         return *this;
 423       }
 424
 425       ~unordered_multimap() noexcept
 426       {
 427         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 428                                      _Base::size());
 429         _M_profile_destruct();
 430       }
 431
 432       _Base&
 433       _M_base() noexcept       { return *this; }
 434
 435       const _Base&
 436       _M_base() const noexcept { return *this; }
 437
 438       void
 439       clear() noexcept
 440       {
 441         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 442                                      _Base::size());
 443         _M_profile_destruct();
 444         _Base::clear();
 445       }
 446
 447       void
 448       insert(std::initializer_list<value_type> __l)
 449       {
 450         size_type __old_size =  _Base::bucket_count();
 451         _Base::insert(__l);
 452         _M_profile_resize(__old_size, _Base::bucket_count());
 453       }
 454
 455       iterator
 456       insert(const value_type& __obj)
 457       {
 458         size_type __old_size =  _Base::bucket_count();
 459         iterator __res = _Base::insert(__obj);
 460         _M_profile_resize(__old_size, _Base::bucket_count());
 461         return __res;
 462       }
 463
 464       iterator
 465       insert(const_iterator __iter, const value_type& __v)
 466       {
 467         size_type __old_size = _Base::bucket_count();
 468         iterator __res = _Base::insert(__iter, __v);
 469         _M_profile_resize(__old_size, _Base::bucket_count());
 470         return __res;
 471       }
 472
 473       template<typename _Pair, typename = typename
 474                std::enable_if<std::is_convertible<_Pair,
 475                                                   value_type>::value>::type>
 476         iterator
 477         insert(_Pair&& __obj)
 478         {
 479           size_type __old_size =  _Base::bucket_count();
 480           iterator __res = _Base::insert(std::forward<_Pair>(__obj));
 481           _M_profile_resize(__old_size, _Base::bucket_count());
 482           return __res;
 483         }
 484
 485       template<typename _Pair, typename = typename
 486                std::enable_if<std::is_convertible<_Pair,
 487                                                   value_type>::value>::type>
 488         iterator
 489         insert(const_iterator __iter, _Pair&& __v)
 490         {
 491           size_type __old_size = _Base::bucket_count();
 492           iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
 493           _M_profile_resize(__old_size, _Base::bucket_count());
 494           return __res;
 495         }
 496
 497       template<typename _InputIter>
 498         void
 499         insert(_InputIter __first, _InputIter __last)
 500         {
 501           size_type __old_size = _Base::bucket_count();
 502           _Base::insert(__first, __last);
 503           _M_profile_resize(__old_size, _Base::bucket_count());
 504         }
 505
 506       void
 507       insert(const value_type* __first, const value_type* __last)
 508       {
 509         size_type __old_size = _Base::bucket_count();
 510         _Base::insert(__first, __last);
 511         _M_profile_resize(__old_size, _Base::bucket_count());
 512       }
 513
 514       void
 515       swap(unordered_multimap& __x)
 516       { _Base::swap(__x); }
 517
 518       void rehash(size_type __n)
 519       {
 520         size_type __old_size =  _Base::bucket_count();
 521         _Base::rehash(__n);
 522         _M_profile_resize(__old_size, _Base::bucket_count());
 523       }
 524
 525     private:
 526       void
 527       _M_profile_resize(size_type __old_size, size_type __new_size)
 528       {
 529         if (__old_size != __new_size)
 530           __profcxx_hashtable_resize(this, __old_size, __new_size);
 531       }
 532
 533       void
 534       _M_profile_destruct()
 535       {
 536         size_type __hops = 0, __lc = 0, __chain = 0;
 537         for (iterator __it = _M_base().begin(); __it != _M_base().end();
 538              ++__it)
 539           {
 540             while (__it._M_cur_node->_M_next)
 541               {
 542                 ++__chain;
 543                 ++__it;
 544               }
 545             if (__chain)
 546               {
 547                 ++__chain;
 548                 __lc = __lc > __chain ? __lc : __chain;
 549                 __hops += __chain * (__chain - 1) / 2;
 550                 __chain = 0;
 551               }
 552           }
 553         __profcxx_hashtable_destruct2(this, __lc,  _Base::size(), __hops);
 554       }
 555
 556     };
 557
 558   template<typename _Key, typename _Tp, typename _Hash,
 559            typename _Pred, typename _Alloc>
 560     inline void
 561     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 562          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 563     { __x.swap(__y); }
 564
 565   template<typename _Key, typename _Tp, typename _Hash,
 566            typename _Pred, typename _Alloc>
 567     inline bool
 568     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 569                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 570     { return __x._M_equal(__y); }
 571
 572   template<typename _Key, typename _Tp, typename _Hash,
 573            typename _Pred, typename _Alloc>
 574     inline bool
 575     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 576                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 577     { return !(__x == __y); }
 578
 579 } // namespace __profile
 580 } // namespace std
 581
 582 #undef _GLIBCXX_BASE
 583 #undef _GLIBCXX_STD_BASE
 584
 585 #endif // __GXX_EXPERIMENTAL_CXX0X__
 586
 587 #endif