libstdc++-v3/include/profile/map.h

   1 // Profiling map implementation -*- C++ -*-
   2
   3 // Copyright (C) 2009-2014 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/map.h
  25  *  This file is a GNU profile extension to the Standard C++ Library.
  26  */
  27
  28 #ifndef _GLIBCXX_PROFILE_MAP_H
  29 #define _GLIBCXX_PROFILE_MAP_H 1
  30
  31 #include <utility>
  32 #include <profile/base.h>
  33
  34 namespace std _GLIBCXX_VISIBILITY(default)
  35 {
  36 namespace __profile
  37 {
  38   /// Class std::map wrapper with performance instrumentation.
  39   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
  40            typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
  41     class map
  42     : public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>
  43     {
  44       typedef _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator> _Base;
  45
  46 #if __cplusplus >= 201103L
  47       typedef __gnu_cxx::__alloc_traits<_Allocator> _Alloc_traits;
  48 #endif
  49
  50     public:
  51       // types:
  52       typedef _Key                                  key_type;
  53       typedef _Tp                                   mapped_type;
  54       typedef std::pair<const _Key, _Tp>            value_type;
  55       typedef _Compare                              key_compare;
  56       typedef _Allocator                            allocator_type;
  57       typedef typename _Base::reference             reference;
  58       typedef typename _Base::const_reference       const_reference;
  59
  60       typedef typename _Base::iterator       iterator;
  61       typedef typename _Base::const_iterator       const_iterator;
  62       typedef typename _Base::size_type             size_type;
  63       typedef typename _Base::difference_type       difference_type;
  64       typedef typename _Base::pointer               pointer;
  65       typedef typename _Base::const_pointer         const_pointer;
  66       typedef std::reverse_iterator<iterator>       reverse_iterator;
  67       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  68
  69       // 23.3.1.1 construct/copy/destroy:
  70
  71       map()
  72       : _Base()
  73       { __profcxx_map_to_unordered_map_construct(this); }
  74
  75       explicit
  76       map(const _Compare& __comp,
  77           const _Allocator& __a = _Allocator())
  78       : _Base(__comp, __a)
  79       { __profcxx_map_to_unordered_map_construct(this); }
  80
  81 #if __cplusplus >= 201103L
  82       template<typename _InputIterator,
  83                typename = std::_RequireInputIter<_InputIterator>>
  84 #else
  85       template<typename _InputIterator>
  86 #endif
  87         map(_InputIterator __first, _InputIterator __last,
  88             const _Compare& __comp = _Compare(),
  89             const _Allocator& __a = _Allocator())
  90         : _Base(__first, __last, __comp, __a)
  91         { __profcxx_map_to_unordered_map_construct(this); }
  92
  93       map(const map& __x)
  94       : _Base(__x)
  95       { __profcxx_map_to_unordered_map_construct(this); }
  96
  97       map(const _Base& __x)
  98       : _Base(__x)
  99       { __profcxx_map_to_unordered_map_construct(this); }
 100
 101 #if __cplusplus >= 201103L
 102       map(map&& __x)
 103       noexcept(is_nothrow_copy_constructible<_Compare>::value)
 104       : _Base(std::move(__x))
 105       { __profcxx_map_to_unordered_map_construct(this); }
 106
 107       map(initializer_list<value_type> __l,
 108           const _Compare& __c = _Compare(),
 109           const allocator_type& __a = allocator_type())
 110       : _Base(__l, __c, __a)
 111       { __profcxx_map_to_unordered_map_construct(this); }
 112
 113       explicit
 114       map(const allocator_type& __a)
 115         : _Base(__a)
 116       { __profcxx_map_to_unordered_map_construct(this); }
 117
 118       map(const map& __x, const allocator_type& __a)
 119       : _Base(__x, __a)
 120       { __profcxx_map_to_unordered_map_construct(this); }
 121
 122       map(map&& __x, const allocator_type& __a)
 123       noexcept(is_nothrow_copy_constructible<_Compare>::value
 124                && _Alloc_traits::_S_always_equal())
 125       : _Base(std::move(__x), __a)
 126       { __profcxx_map_to_unordered_map_construct(this); }
 127
 128       map(initializer_list<value_type> __l, const allocator_type& __a)
 129       : _Base(__l, __a)
 130       { __profcxx_map_to_unordered_map_construct(this); }
 131
 132       template<typename _InputIterator>
 133         map(_InputIterator __first, _InputIterator __last,
 134             const allocator_type& __a)
 135           : _Base(__first, __last, __a)
 136       { __profcxx_map_to_unordered_map_construct(this); }
 137 #endif
 138
 139       ~map() _GLIBCXX_NOEXCEPT
 140       { __profcxx_map_to_unordered_map_destruct(this); }
 141
 142 #if __cplusplus < 201103L
 143       map&
 144       operator=(const map& __x)
 145       {
 146         _M_base() = __x;
 147         return *this;
 148       }
 149 #else
 150       map&
 151       operator=(const map&) = default;
 152
 153       map&
 154       operator=(map&&) = default;
 155
 156       map&
 157       operator=(initializer_list<value_type> __l)
 158       {
 159         _M_base() = __l;
 160         return *this;
 161       }
 162 #endif
 163
 164       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 165       // 133. map missing get_allocator()
 166       using _Base::get_allocator;
 167
 168       // iterators:
 169       iterator
 170       begin() _GLIBCXX_NOEXCEPT
 171       { return _Base::begin(); }
 172
 173       const_iterator
 174       begin() const _GLIBCXX_NOEXCEPT
 175       { return _Base::begin(); }
 176
 177       iterator
 178       end() _GLIBCXX_NOEXCEPT
 179       { return _Base::end(); }
 180
 181       const_iterator
 182       end() const _GLIBCXX_NOEXCEPT
 183       { return _Base::end(); }
 184
 185       reverse_iterator
 186       rbegin() _GLIBCXX_NOEXCEPT
 187       {
 188         __profcxx_map_to_unordered_map_invalidate(this);
 189         return reverse_iterator(end());
 190       }
 191
 192       const_reverse_iterator
 193       rbegin() const _GLIBCXX_NOEXCEPT
 194       {
 195         __profcxx_map_to_unordered_map_invalidate(this);
 196         return const_reverse_iterator(end());
 197       }
 198
 199       reverse_iterator
 200       rend() _GLIBCXX_NOEXCEPT
 201       {
 202         __profcxx_map_to_unordered_map_invalidate(this);
 203         return reverse_iterator(begin());
 204       }
 205
 206       const_reverse_iterator
 207       rend() const _GLIBCXX_NOEXCEPT
 208       {
 209         __profcxx_map_to_unordered_map_invalidate(this);
 210         return const_reverse_iterator(begin());
 211       }
 212
 213 #if __cplusplus >= 201103L
 214       const_iterator
 215       cbegin() const noexcept
 216       { return const_iterator(_Base::begin()); }
 217
 218       const_iterator
 219       cend() const noexcept
 220       { return const_iterator(_Base::end()); }
 221
 222       const_reverse_iterator
 223       crbegin() const noexcept
 224       {
 225         __profcxx_map_to_unordered_map_invalidate(this);
 226         return const_reverse_iterator(end());
 227       }
 228
 229       const_reverse_iterator
 230       crend() const noexcept
 231       {
 232         __profcxx_map_to_unordered_map_invalidate(this);
 233         return const_reverse_iterator(begin());
 234       }
 235 #endif
 236
 237       // capacity:
 238       using _Base::empty;
 239       using _Base::size;
 240       using _Base::max_size;
 241
 242       // 23.3.1.2 element access:
 243       mapped_type&
 244       operator[](const key_type& __k)
 245       {
 246         __profcxx_map_to_unordered_map_find(this, size());
 247         return _Base::operator[](__k);
 248       }
 249
 250 #if __cplusplus >= 201103L
 251       mapped_type&
 252       operator[](key_type&& __k)
 253       {
 254         __profcxx_map_to_unordered_map_find(this, size());
 255         return _Base::operator[](std::move(__k));
 256       }
 257 #endif
 258
 259       mapped_type&
 260       at(const key_type& __k)
 261       {
 262         __profcxx_map_to_unordered_map_find(this, size());
 263         return _Base::at(__k);
 264       }
 265
 266       const mapped_type&
 267       at(const key_type& __k) const
 268       {
 269         __profcxx_map_to_unordered_map_find(this, size());
 270         return _Base::at(__k);
 271       }
 272
 273       // modifiers:
 274 #if __cplusplus >= 201103L
 275       template<typename... _Args>
 276         std::pair<iterator, bool>
 277         emplace(_Args&&... __args)
 278         {
 279           __profcxx_map_to_unordered_map_insert(this, size(), 1);
 280           auto __res = _Base::emplace(std::forward<_Args>(__args)...);
 281           return std::pair<iterator, bool>(iterator(__res.first),
 282                                            __res.second);
 283         }
 284
 285       template<typename... _Args>
 286         iterator
 287         emplace_hint(const_iterator __pos, _Args&&... __args)
 288         {
 289           size_type size_before = size();
 290           auto __res = _Base::emplace_hint(__pos,
 291                                            std::forward<_Args>(__args)...);
 292           __profcxx_map_to_unordered_map_insert(this, size_before,
 293                                                 size() - size_before);
 294           return __res;
 295         }
 296 #endif
 297
 298       std::pair<iterator, bool>
 299       insert(const value_type& __x)
 300       {
 301         __profcxx_map_to_unordered_map_insert(this, size(), 1);
 302         typedef typename _Base::iterator _Base_iterator;
 303         std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
 304         return std::pair<iterator, bool>(iterator(__res.first),
 305                                          __res.second);
 306       }
 307
 308 #if __cplusplus >= 201103L
 309       template<typename _Pair, typename = typename
 310                std::enable_if<std::is_constructible<value_type,
 311                                                     _Pair&&>::value>::type>
 312         std::pair<iterator, bool>
 313         insert(_Pair&& __x)
 314         {
 315           __profcxx_map_to_unordered_map_insert(this, size(), 1);
 316           typedef typename _Base::iterator _Base_iterator;
 317           std::pair<_Base_iterator, bool> __res
 318             = _Base::insert(std::forward<_Pair>(__x));
 319           return std::pair<iterator, bool>(iterator(__res.first),
 320                                            __res.second);
 321         }
 322 #endif
 323
 324 #if __cplusplus >= 201103L
 325       void
 326       insert(std::initializer_list<value_type> __list)
 327       {
 328         size_type size_before = size();
 329         _Base::insert(__list);
 330         __profcxx_map_to_unordered_map_insert(this, size_before,
 331                                               size() - size_before);
 332       }
 333 #endif
 334
 335       iterator
 336 #if __cplusplus >= 201103L
 337       insert(const_iterator __position, const value_type& __x)
 338 #else
 339       insert(iterator __position, const value_type& __x)
 340 #endif
 341       {
 342         size_type size_before = size();
 343         iterator __i = iterator(_Base::insert(__position, __x));
 344         __profcxx_map_to_unordered_map_insert(this, size_before,
 345                                               size() - size_before);
 346         return __i;
 347       }
 348
 349 #if __cplusplus >= 201103L
 350       template<typename _Pair, typename = typename
 351                std::enable_if<std::is_constructible<value_type,
 352                                                     _Pair&&>::value>::type>
 353         iterator
 354         insert(const_iterator __position, _Pair&& __x)
 355         {
 356           size_type size_before = size();
 357           iterator __i
 358             = iterator(_Base::insert(__position, std::forward<_Pair>(__x)));
 359           __profcxx_map_to_unordered_map_insert(this, size_before,
 360                                                 size() - size_before);
 361           return __i;
 362       }
 363 #endif
 364
 365 #if __cplusplus >= 201103L
 366       template<typename _InputIterator,
 367                typename = std::_RequireInputIter<_InputIterator>>
 368 #else
 369       template<typename _InputIterator>
 370 #endif
 371         void
 372         insert(_InputIterator __first, _InputIterator __last)
 373         {
 374           size_type size_before = size();
 375           _Base::insert(__first, __last);
 376           __profcxx_map_to_unordered_map_insert(this, size_before,
 377                                                 size() - size_before);
 378         }
 379
 380 #if __cplusplus >= 201103L
 381       iterator
 382       erase(const_iterator __position)
 383       {
 384         iterator __i = _Base::erase(__position);
 385         __profcxx_map_to_unordered_map_erase(this, size(), 1);
 386         return __i;
 387       }
 388
 389       iterator
 390       erase(iterator __position)
 391       { return erase(const_iterator(__position)); }
 392 #else
 393       void
 394       erase(iterator __position)
 395       {
 396         _Base::erase(__position);
 397         __profcxx_map_to_unordered_map_erase(this, size(), 1);
 398       }
 399 #endif
 400
 401       size_type
 402       erase(const key_type& __x)
 403       {
 404         iterator __victim = find(__x);
 405         if (__victim == end())
 406           return 0;
 407         else
 408         {
 409           _Base::erase(__victim);
 410           return 1;
 411         }
 412       }
 413
 414 #if __cplusplus >= 201103L
 415       iterator
 416       erase(const_iterator __first, const_iterator __last)
 417       { return iterator(_Base::erase(__first, __last)); }
 418 #else
 419       void
 420       erase(iterator __first, iterator __last)
 421       { _Base::erase(__first, __last); }
 422 #endif
 423
 424       void
 425       swap(map& __x)
 426 #if __cplusplus >= 201103L
 427       noexcept(_Alloc_traits::_S_nothrow_swap())
 428 #endif
 429       { _Base::swap(__x); }
 430
 431       void
 432       clear() _GLIBCXX_NOEXCEPT
 433       { this->erase(begin(), end()); }
 434
 435       // observers:
 436       using _Base::key_comp;
 437       using _Base::value_comp;
 438
 439       // 23.3.1.3 map operations:
 440       iterator
 441       find(const key_type& __x)
 442       {
 443         __profcxx_map_to_unordered_map_find(this, size());
 444         return iterator(_Base::find(__x));
 445       }
 446
 447       const_iterator
 448       find(const key_type& __x) const
 449       {
 450         __profcxx_map_to_unordered_map_find(this, size());
 451         return const_iterator(_Base::find(__x));
 452       }
 453
 454       size_type
 455       count(const key_type& __x) const
 456       {
 457         __profcxx_map_to_unordered_map_find(this, size());
 458         return _Base::count(__x);
 459       }
 460
 461       iterator
 462       lower_bound(const key_type& __x)
 463       {
 464         __profcxx_map_to_unordered_map_invalidate(this);
 465         return iterator(_Base::lower_bound(__x));
 466       }
 467
 468       const_iterator
 469       lower_bound(const key_type& __x) const
 470       {
 471         __profcxx_map_to_unordered_map_invalidate(this);
 472         return const_iterator(_Base::lower_bound(__x));
 473       }
 474
 475       iterator
 476       upper_bound(const key_type& __x)
 477       {
 478         __profcxx_map_to_unordered_map_invalidate(this);
 479         return iterator(_Base::upper_bound(__x));
 480       }
 481
 482       const_iterator
 483       upper_bound(const key_type& __x) const
 484       {
 485         __profcxx_map_to_unordered_map_invalidate(this);
 486         return const_iterator(_Base::upper_bound(__x));
 487       }
 488
 489       std::pair<iterator,iterator>
 490       equal_range(const key_type& __x)
 491       {
 492         typedef typename _Base::iterator _Base_iterator;
 493         std::pair<_Base_iterator, _Base_iterator> __res =
 494         _Base::equal_range(__x);
 495         return std::make_pair(iterator(__res.first),
 496                               iterator(__res.second));
 497       }
 498
 499       std::pair<const_iterator,const_iterator>
 500       equal_range(const key_type& __x) const
 501       {
 502         __profcxx_map_to_unordered_map_find(this, size());
 503         typedef typename _Base::const_iterator _Base_const_iterator;
 504         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 505         _Base::equal_range(__x);
 506         return std::make_pair(const_iterator(__res.first),
 507                               const_iterator(__res.second));
 508       }
 509
 510       _Base&
 511       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
 512
 513       const _Base&
 514       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 515
 516     };
 517
 518   template<typename _Key, typename _Tp,
 519            typename _Compare, typename _Allocator>
 520     inline bool
 521     operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 522                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 523     {
 524       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 525       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 526       return __lhs._M_base() == __rhs._M_base();
 527     }
 528
 529   template<typename _Key, typename _Tp,
 530            typename _Compare, typename _Allocator>
 531     inline bool
 532     operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 533                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 534     {
 535       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 536       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 537       return __lhs._M_base() != __rhs._M_base();
 538     }
 539
 540   template<typename _Key, typename _Tp,
 541            typename _Compare, typename _Allocator>
 542     inline bool
 543     operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 544               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 545     {
 546       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 547       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 548       return __lhs._M_base() < __rhs._M_base();
 549     }
 550
 551   template<typename _Key, typename _Tp,
 552            typename _Compare, typename _Allocator>
 553     inline bool
 554     operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 555                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 556     {
 557       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 558       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 559       return __lhs._M_base() <= __rhs._M_base();
 560     }
 561
 562   template<typename _Key, typename _Tp,
 563            typename _Compare, typename _Allocator>
 564     inline bool
 565     operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 566                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 567     {
 568       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 569       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 570       return __lhs._M_base() >= __rhs._M_base();
 571     }
 572
 573   template<typename _Key, typename _Tp,
 574            typename _Compare, typename _Allocator>
 575     inline bool
 576     operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 577               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 578     {
 579       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 580       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 581       return __lhs._M_base() > __rhs._M_base();
 582     }
 583
 584   template<typename _Key, typename _Tp,
 585            typename _Compare, typename _Allocator>
 586     inline void
 587     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 588          map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 589     { __lhs.swap(__rhs); }
 590
 591 } // namespace __profile
 592 } // namespace std
 593
 594 #endif