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

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