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

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