i686-linux-gnu-4.7/usr/include/c++/4.7/profile/unordered_map

   1 // Profiling unordered_map/unordered_multimap implementation -*- C++ -*-
   2
   3 // Copyright (C) 2009, 2010, 2011, 2012 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License along
  21 // with this library; see the file COPYING3.  If not see
  22 // <http://www.gnu.org/licenses/>.
  23
  24 /** @file profile/unordered_map
  25  *  This file is a GNU profile extension to the Standard C++ Library.
  26  */
  27
  28 #ifndef _GLIBCXX_PROFILE_UNORDERED_MAP
  29 #define _GLIBCXX_PROFILE_UNORDERED_MAP 1
  30
  31 #ifndef __GXX_EXPERIMENTAL_CXX0X__
  32 # include <bits/c++0x_warning.h>
  33 #else
  34 # include <unordered_map>
  35
  36 #include <profile/base.h>
  37
  38 #define _GLIBCXX_BASE unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
  39 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
  40
  41 namespace std _GLIBCXX_VISIBILITY(default)
  42 {
  43 namespace __profile
  44 {
  45   /// Class std::unordered_map wrapper with performance instrumentation.
  46   template<typename _Key, typename _Tp,
  47            typename _Hash  = std::hash<_Key>,
  48            typename _Pred = std::equal_to<_Key>,
  49            typename _Alloc =  std::allocator<_Key> >
  50     class unordered_map
  51     : public _GLIBCXX_STD_BASE
  52     {
  53       typedef typename _GLIBCXX_STD_BASE _Base;
  54
  55     public:
  56       typedef typename _Base::size_type       size_type;
  57       typedef typename _Base::hasher          hasher;
  58       typedef typename _Base::key_equal       key_equal;
  59       typedef typename _Base::allocator_type  allocator_type;
  60       typedef typename _Base::key_type        key_type;
  61       typedef typename _Base::value_type      value_type;
  62       typedef typename _Base::difference_type difference_type;
  63       typedef typename _Base::reference       reference;
  64       typedef typename _Base::const_reference const_reference;
  65       typedef typename _Base::mapped_type      mapped_type;
  66
  67       typedef typename _Base::iterator iterator;
  68       typedef typename _Base::const_iterator const_iterator;
  69
  70       explicit
  71       unordered_map(size_type __n = 10,
  72                     const hasher& __hf = hasher(),
  73                     const key_equal& __eql = key_equal(),
  74                     const allocator_type& __a = allocator_type())
  75       : _Base(__n, __hf, __eql, __a)
  76       {
  77         __profcxx_hashtable_construct(this, _Base::bucket_count());
  78         __profcxx_hashtable_construct2(this);
  79       }
  80
  81       template<typename _InputIterator>
  82         unordered_map(_InputIterator __f, _InputIterator __l,
  83                       size_type __n = 0,
  84                       const hasher& __hf = hasher(),
  85                       const key_equal& __eql = key_equal(),
  86                       const allocator_type& __a = allocator_type())
  87       : _Base(__f, __l, __n, __hf, __eql, __a)
  88       {
  89         __profcxx_hashtable_construct(this, _Base::bucket_count());
  90         __profcxx_hashtable_construct2(this);
  91       }
  92
  93       unordered_map(const unordered_map& __x)
  94       : _Base(__x)
  95       {
  96         __profcxx_hashtable_construct(this, _Base::bucket_count());
  97         __profcxx_hashtable_construct2(this);
  98       }
  99
 100       unordered_map(const _Base& __x)
 101       : _Base(__x)
 102       {
 103         __profcxx_hashtable_construct(this, _Base::bucket_count());
 104         __profcxx_hashtable_construct2(this);
 105       }
 106
 107       unordered_map(unordered_map&& __x)
 108       : _Base(std::move(__x))
 109       {
 110         __profcxx_hashtable_construct(this, _Base::bucket_count());
 111         __profcxx_hashtable_construct2(this);
 112       }
 113
 114       unordered_map(initializer_list<value_type> __l,
 115                     size_type __n = 0,
 116                     const hasher& __hf = hasher(),
 117                     const key_equal& __eql = key_equal(),
 118                     const allocator_type& __a = allocator_type())
 119       : _Base(__l, __n, __hf, __eql, __a) { }
 120
 121       unordered_map&
 122       operator=(const unordered_map& __x)
 123       {
 124         *static_cast<_Base*>(this) = __x;
 125         return *this;
 126       }
 127
 128       unordered_map&
 129       operator=(unordered_map&& __x)
 130       {
 131         // NB: DR 1204.
 132         // NB: DR 675.
 133         this->clear();
 134         this->swap(__x);
 135         return *this;
 136       }
 137
 138       unordered_map&
 139       operator=(initializer_list<value_type> __l)
 140       {
 141         this->clear();
 142         this->insert(__l);
 143         return *this;
 144       }
 145
 146       ~unordered_map() noexcept
 147       {
 148         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 149                                      _Base::size());
 150         _M_profile_destruct();
 151       }
 152
 153       _Base&
 154       _M_base() noexcept       { return *this; }
 155
 156       const _Base&
 157       _M_base() const noexcept { return *this; }
 158
 159       void
 160       clear() noexcept
 161       {
 162         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 163                                      _Base::size());
 164         _M_profile_destruct();
 165         _Base::clear();
 166       }
 167
 168       template<typename... _Args>
 169         std::pair<iterator, bool>
 170         emplace(_Args&&... __args)
 171         {
 172           size_type __old_size = _Base::bucket_count();
 173           std::pair<iterator, bool> __res
 174             = _Base::emplace(std::forward<_Args>(__args)...);
 175           _M_profile_resize(__old_size);
 176           return __res;
 177         }
 178
 179       template<typename... _Args>
 180         iterator
 181         emplace_hint(const_iterator __it, _Args&&... __args)
 182         {
 183           size_type __old_size = _Base::bucket_count();
 184           iterator __res
 185             = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
 186           _M_profile_resize(__old_size);
 187           return __res;
 188         }
 189
 190       void
 191       insert(std::initializer_list<value_type> __l)
 192       {
 193         size_type __old_size = _Base::bucket_count();
 194         _Base::insert(__l);
 195         _M_profile_resize(__old_size);
 196       }
 197
 198       std::pair<iterator, bool>
 199       insert(const value_type& __obj)
 200       {
 201         size_type __old_size = _Base::bucket_count();
 202         std::pair<iterator, bool> __res = _Base::insert(__obj);
 203         _M_profile_resize(__old_size);
 204         return __res;
 205       }
 206
 207       iterator
 208       insert(const_iterator __iter, const value_type& __v)
 209       {
 210         size_type __old_size = _Base::bucket_count();
 211         iterator __res = _Base::insert(__iter, __v);
 212         _M_profile_resize(__old_size);
 213         return __res;
 214       }
 215
 216       template<typename _Pair, typename = typename
 217                std::enable_if<std::is_constructible<value_type,
 218                                                     _Pair&&>::value>::type>
 219         std::pair<iterator, bool>
 220         insert(_Pair&& __obj)
 221         {
 222           size_type __old_size = _Base::bucket_count();
 223           std::pair<iterator, bool> __res
 224             = _Base::insert(std::forward<_Pair>(__obj));
 225           _M_profile_resize(__old_size);
 226           return __res;
 227         }
 228
 229       template<typename _Pair, typename = typename
 230                std::enable_if<std::is_constructible<value_type,
 231                                                     _Pair&&>::value>::type>
 232         iterator
 233         insert(const_iterator __iter, _Pair&& __v)
 234         {
 235           size_type __old_size = _Base::bucket_count();
 236           iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
 237           _M_profile_resize(__old_size);
 238           return __res;
 239         }
 240
 241       template<typename _InputIter>
 242         void
 243         insert(_InputIter __first, _InputIter __last)
 244         {
 245           size_type __old_size = _Base::bucket_count();
 246           _Base::insert(__first, __last);
 247           _M_profile_resize(__old_size);
 248         }
 249
 250       void
 251       insert(const value_type* __first, const value_type* __last)
 252       {
 253         size_type __old_size = _Base::bucket_count();
 254         _Base::insert(__first, __last);
 255         _M_profile_resize(__old_size);
 256       }
 257
 258       // operator[]
 259       mapped_type&
 260       operator[](const _Key& __k)
 261       {
 262         size_type __old_size = _Base::bucket_count();
 263         mapped_type& __res = _M_base()[__k];
 264         _M_profile_resize(__old_size);
 265         return __res;
 266       }
 267
 268       mapped_type&
 269       operator[](_Key&& __k)
 270       {
 271         size_type __old_size = _Base::bucket_count();
 272         mapped_type& __res = _M_base()[std::move(__k)];
 273         _M_profile_resize(__old_size);
 274         return __res;
 275       }
 276
 277       void
 278       swap(unordered_map& __x)
 279       { _Base::swap(__x); }
 280
 281       void rehash(size_type __n)
 282       {
 283         size_type __old_size = _Base::bucket_count();
 284         _Base::rehash(__n);
 285         _M_profile_resize(__old_size);
 286       }
 287
 288     private:
 289       void
 290       _M_profile_resize(size_type __old_size)
 291       {
 292         size_type __new_size = _Base::bucket_count();
 293         if (__old_size != __new_size)
 294           __profcxx_hashtable_resize(this, __old_size, __new_size);
 295       }
 296
 297       void
 298       _M_profile_destruct()
 299       {
 300         size_type __hops = 0, __lc = 0, __chain = 0;
 301         iterator __it = this->begin();
 302         while (__it != this->end())
 303           {
 304             size_type __bkt = this->bucket(__it->first);
 305             auto __lit = this->begin(__bkt);
 306             auto __lend = this->end(__bkt);
 307             for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
 308               ++__chain;
 309             if (__chain)
 310               {
 311                 ++__chain;
 312                 __lc = __lc > __chain ? __lc : __chain;
 313                 __hops += __chain * (__chain - 1) / 2;
 314                 __chain = 0;
 315               }
 316           }
 317         __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
 318       }
 319   };
 320
 321   template<typename _Key, typename _Tp, typename _Hash,
 322            typename _Pred, typename _Alloc>
 323     inline void
 324     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 325          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 326     { __x.swap(__y); }
 327
 328   template<typename _Key, typename _Tp, typename _Hash,
 329            typename _Pred, typename _Alloc>
 330     inline bool
 331     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 332                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 333     { return __x._M_equal(__y); }
 334
 335   template<typename _Key, typename _Tp, typename _Hash,
 336            typename _Pred, typename _Alloc>
 337     inline bool
 338     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 339                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 340     { return !(__x == __y); }
 341
 342 #undef _GLIBCXX_BASE
 343 #undef _GLIBCXX_STD_BASE
 344 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
 345 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
 346
 347   /// Class std::unordered_multimap wrapper with performance instrumentation.
 348   template<typename _Key, typename _Tp,
 349            typename _Hash  = std::hash<_Key>,
 350            typename _Pred = std::equal_to<_Key>,
 351            typename _Alloc =  std::allocator<_Key> >
 352     class unordered_multimap
 353     : public _GLIBCXX_STD_BASE
 354     {
 355       typedef typename _GLIBCXX_STD_BASE _Base;
 356
 357     public:
 358       typedef typename _Base::size_type       size_type;
 359       typedef typename _Base::hasher          hasher;
 360       typedef typename _Base::key_equal       key_equal;
 361       typedef typename _Base::allocator_type  allocator_type;
 362       typedef typename _Base::key_type        key_type;
 363       typedef typename _Base::value_type      value_type;
 364       typedef typename _Base::difference_type difference_type;
 365       typedef typename _Base::reference       reference;
 366       typedef typename _Base::const_reference const_reference;
 367
 368       typedef typename _Base::iterator iterator;
 369       typedef typename _Base::const_iterator const_iterator;
 370
 371       explicit
 372       unordered_multimap(size_type __n = 10,
 373                          const hasher& __hf = hasher(),
 374                          const key_equal& __eql = key_equal(),
 375                          const allocator_type& __a = allocator_type())
 376       : _Base(__n, __hf, __eql, __a)
 377       {
 378         __profcxx_hashtable_construct(this, _Base::bucket_count());
 379       }
 380       template<typename _InputIterator>
 381         unordered_multimap(_InputIterator __f, _InputIterator __l,
 382                            size_type __n = 0,
 383                            const hasher& __hf = hasher(),
 384                            const key_equal& __eql = key_equal(),
 385                            const allocator_type& __a = allocator_type())
 386       : _Base(__f, __l, __n, __hf, __eql, __a)
 387       {
 388         __profcxx_hashtable_construct(this, _Base::bucket_count());
 389       }
 390
 391       unordered_multimap(const unordered_multimap& __x)
 392       : _Base(__x)
 393       {
 394         __profcxx_hashtable_construct(this, _Base::bucket_count());
 395       }
 396
 397       unordered_multimap(const _Base& __x)
 398       : _Base(__x)
 399       {
 400         __profcxx_hashtable_construct(this, _Base::bucket_count());
 401       }
 402
 403       unordered_multimap(unordered_multimap&& __x)
 404       : _Base(std::move(__x))
 405       {
 406         __profcxx_hashtable_construct(this, _Base::bucket_count());
 407       }
 408
 409       unordered_multimap(initializer_list<value_type> __l,
 410                          size_type __n = 0,
 411                          const hasher& __hf = hasher(),
 412                          const key_equal& __eql = key_equal(),
 413                          const allocator_type& __a = allocator_type())
 414       : _Base(__l, __n, __hf, __eql, __a) { }
 415
 416       unordered_multimap&
 417       operator=(const unordered_multimap& __x)
 418       {
 419         *static_cast<_Base*>(this) = __x;
 420         return *this;
 421       }
 422
 423       unordered_multimap&
 424       operator=(unordered_multimap&& __x)
 425       {
 426         // NB: DR 1204.
 427         // NB: DR 675.
 428         this->clear();
 429         this->swap(__x);
 430         return *this;
 431       }
 432
 433       unordered_multimap&
 434       operator=(initializer_list<value_type> __l)
 435       {
 436         this->clear();
 437         this->insert(__l);
 438         return *this;
 439       }
 440
 441       ~unordered_multimap() noexcept
 442       {
 443         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 444                                      _Base::size());
 445         _M_profile_destruct();
 446       }
 447
 448       void
 449       clear() noexcept
 450       {
 451         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 452                                      _Base::size());
 453         _M_profile_destruct();
 454         _Base::clear();
 455       }
 456
 457       template<typename... _Args>
 458         iterator
 459         emplace(_Args&&... __args)
 460         {
 461           size_type __old_size = _Base::bucket_count();
 462           iterator __res
 463             = _Base::emplace(std::forward<_Args>(__args)...);
 464           _M_profile_resize(__old_size);
 465           return __res;
 466         }
 467
 468       template<typename... _Args>
 469         iterator
 470         emplace_hint(const_iterator __it, _Args&&... __args)
 471         {
 472           size_type __old_size = _Base::bucket_count();
 473           iterator __res
 474             = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
 475           _M_profile_resize(__old_size);
 476           return __res;
 477         }
 478
 479       void
 480       insert(std::initializer_list<value_type> __l)
 481       {
 482         size_type __old_size = _Base::bucket_count();
 483         _Base::insert(__l);
 484         _M_profile_resize(__old_size);
 485       }
 486
 487       iterator
 488       insert(const value_type& __obj)
 489       {
 490         size_type __old_size = _Base::bucket_count();
 491         iterator __res = _Base::insert(__obj);
 492         _M_profile_resize(__old_size);
 493         return __res;
 494       }
 495
 496       iterator
 497       insert(const_iterator __iter, const value_type& __v)
 498       {
 499         size_type __old_size = _Base::bucket_count();
 500         iterator __res = _Base::insert(__iter, __v);
 501         _M_profile_resize(__old_size);
 502         return __res;
 503       }
 504
 505       template<typename _Pair, typename = typename
 506                std::enable_if<std::is_constructible<value_type,
 507                                                     _Pair&&>::value>::type>
 508         iterator
 509         insert(_Pair&& __obj)
 510         {
 511           size_type __old_size = _Base::bucket_count();
 512           iterator __res = _Base::insert(std::forward<_Pair>(__obj));
 513           _M_profile_resize(__old_size);
 514           return __res;
 515         }
 516
 517       template<typename _Pair, typename = typename
 518                std::enable_if<std::is_constructible<value_type,
 519                                                     _Pair&&>::value>::type>
 520         iterator
 521         insert(const_iterator __iter, _Pair&& __v)
 522         {
 523           size_type __old_size = _Base::bucket_count();
 524           iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
 525           _M_profile_resize(__old_size);
 526           return __res;
 527         }
 528
 529       template<typename _InputIter>
 530         void
 531         insert(_InputIter __first, _InputIter __last)
 532         {
 533           size_type __old_size = _Base::bucket_count();
 534           _Base::insert(__first, __last);
 535           _M_profile_resize(__old_size);
 536         }
 537
 538       void
 539       insert(const value_type* __first, const value_type* __last)
 540       {
 541         size_type __old_size = _Base::bucket_count();
 542         _Base::insert(__first, __last);
 543         _M_profile_resize(__old_size);
 544       }
 545
 546       void
 547       swap(unordered_multimap& __x)
 548       { _Base::swap(__x); }
 549
 550       void rehash(size_type __n)
 551       {
 552         size_type __old_size = _Base::bucket_count();
 553         _Base::rehash(__n);
 554         _M_profile_resize(__old_size);
 555       }
 556
 557     private:
 558       void
 559       _M_profile_resize(size_type __old_size)
 560       {
 561         size_type __new_size = _Base::bucket_count();
 562         if (__old_size != __new_size)
 563           __profcxx_hashtable_resize(this, __old_size, __new_size);
 564       }
 565
 566       void
 567       _M_profile_destruct()
 568       {
 569         size_type __hops = 0, __lc = 0, __chain = 0;
 570         iterator __it = this->begin();
 571         while (__it != this->end())
 572           {
 573             size_type __bkt = this->bucket(__it->first);
 574             auto __lit = this->begin(__bkt);
 575             auto __lend = this->end(__bkt);
 576             for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
 577               ++__chain;
 578             if (__chain)
 579               {
 580                 ++__chain;
 581                 __lc = __lc > __chain ? __lc : __chain;
 582                 __hops += __chain * (__chain - 1) / 2;
 583                 __chain = 0;
 584               }
 585           }
 586         __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
 587       }
 588   };
 589
 590   template<typename _Key, typename _Tp, typename _Hash,
 591            typename _Pred, typename _Alloc>
 592     inline void
 593     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 594          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 595     { __x.swap(__y); }
 596
 597   template<typename _Key, typename _Tp, typename _Hash,
 598            typename _Pred, typename _Alloc>
 599     inline bool
 600     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 601                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 602     { return __x._M_equal(__y); }
 603
 604   template<typename _Key, typename _Tp, typename _Hash,
 605            typename _Pred, typename _Alloc>
 606     inline bool
 607     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 608                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 609     { return !(__x == __y); }
 610
 611 } // namespace __profile
 612 } // namespace std
 613
 614 #undef _GLIBCXX_BASE
 615 #undef _GLIBCXX_STD_BASE
 616
 617 #endif // __GXX_EXPERIMENTAL_CXX0X__
 618
 619 #endif