libstdc++-v3/include/profile/unordered_map

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