contrib/gcc-4.7/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       std::pair<iterator, bool>
 240       insert(const value_type& __x)
 241       {
 242         __profcxx_map_to_unordered_map_insert(this, size(), 1);
 243         typedef typename _Base::iterator _Base_iterator;
 244         std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
 245         return std::pair<iterator, bool>(iterator(__res.first),
 246                                          __res.second);
 247       }
 248
 249 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 250       template<typename _Pair, typename = typename
 251                std::enable_if<std::is_constructible<value_type,
 252                                                     _Pair&&>::value>::type>
 253         std::pair<iterator, bool>
 254         insert(_Pair&& __x)
 255         {
 256           __profcxx_map_to_unordered_map_insert(this, size(), 1);
 257           typedef typename _Base::iterator _Base_iterator;
 258           std::pair<_Base_iterator, bool> __res
 259             = _Base::insert(std::forward<_Pair>(__x));
 260           return std::pair<iterator, bool>(iterator(__res.first),
 261                                            __res.second);
 262         }
 263 #endif
 264
 265 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 266       void
 267       insert(std::initializer_list<value_type> __list)
 268       {
 269         size_type size_before = size();
 270         _Base::insert(__list);
 271         __profcxx_map_to_unordered_map_insert(this, size_before,
 272                                               size() - size_before);
 273       }
 274 #endif
 275
 276       iterator
 277 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 278       insert(const_iterator __position, const value_type& __x)
 279 #else
 280       insert(iterator __position, const value_type& __x)
 281 #endif
 282       {
 283         size_type size_before = size();
 284         iterator __i = iterator(_Base::insert(__position, __x));
 285         __profcxx_map_to_unordered_map_insert(this, size_before,
 286                                               size() - size_before);
 287         return __i;
 288       }
 289
 290 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 291       template<typename _Pair, typename = typename
 292                std::enable_if<std::is_constructible<value_type,
 293                                                     _Pair&&>::value>::type>
 294         iterator
 295         insert(const_iterator __position, _Pair&& __x)
 296         {
 297           size_type size_before = size();
 298           iterator __i
 299             = iterator(_Base::insert(__position, std::forward<_Pair>(__x)));
 300           __profcxx_map_to_unordered_map_insert(this, size_before,
 301                                                 size() - size_before);
 302           return __i;
 303       }
 304 #endif
 305
 306       template<typename _InputIterator>
 307         void
 308         insert(_InputIterator __first, _InputIterator __last)
 309         {
 310           size_type size_before = size();
 311           _Base::insert(__first, __last);
 312           __profcxx_map_to_unordered_map_insert(this, size_before,
 313                                                 size() - size_before);
 314         }
 315
 316 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 317       iterator
 318       erase(const_iterator __position)
 319       {
 320         iterator __i = _Base::erase(__position);
 321         __profcxx_map_to_unordered_map_erase(this, size(), 1);
 322         return __i;
 323       }
 324
 325       iterator
 326       erase(iterator __position)
 327       { return erase(const_iterator(__position)); }
 328 #else
 329       void
 330       erase(iterator __position)
 331       {
 332         _Base::erase(__position);
 333         __profcxx_map_to_unordered_map_erase(this, size(), 1);
 334       }
 335 #endif
 336
 337       size_type
 338       erase(const key_type& __x)
 339       {
 340         iterator __victim = find(__x);
 341         if (__victim == end())
 342           return 0;
 343         else
 344         {
 345           _Base::erase(__victim);
 346           return 1;
 347         }
 348       }
 349
 350 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 351       iterator
 352       erase(const_iterator __first, const_iterator __last)
 353       { return iterator(_Base::erase(__first, __last)); }
 354 #else
 355       void
 356       erase(iterator __first, iterator __last)
 357       { _Base::erase(__first, __last); }
 358 #endif
 359
 360       void
 361       swap(map& __x)
 362       { _Base::swap(__x); }
 363
 364       void
 365       clear() _GLIBCXX_NOEXCEPT
 366       { this->erase(begin(), end()); }
 367
 368       // observers:
 369       using _Base::key_comp;
 370       using _Base::value_comp;
 371
 372       // 23.3.1.3 map operations:
 373       iterator
 374       find(const key_type& __x)
 375       {
 376         __profcxx_map_to_unordered_map_find(this, size());
 377         return iterator(_Base::find(__x));
 378       }
 379
 380       const_iterator
 381       find(const key_type& __x) const
 382       {
 383         __profcxx_map_to_unordered_map_find(this, size());
 384         return const_iterator(_Base::find(__x));
 385       }
 386
 387       size_type
 388       count(const key_type& __x) const
 389       {
 390         __profcxx_map_to_unordered_map_find(this, size());
 391         return _Base::count(__x);
 392       }
 393
 394       iterator
 395       lower_bound(const key_type& __x)
 396       {
 397         __profcxx_map_to_unordered_map_invalidate(this);
 398         return iterator(_Base::lower_bound(__x));
 399       }
 400
 401       const_iterator
 402       lower_bound(const key_type& __x) const
 403       {
 404         __profcxx_map_to_unordered_map_invalidate(this);
 405         return const_iterator(_Base::lower_bound(__x));
 406       }
 407
 408       iterator
 409       upper_bound(const key_type& __x)
 410       {
 411         __profcxx_map_to_unordered_map_invalidate(this);
 412         return iterator(_Base::upper_bound(__x));
 413       }
 414
 415       const_iterator
 416       upper_bound(const key_type& __x) const
 417       {
 418         __profcxx_map_to_unordered_map_invalidate(this);
 419         return const_iterator(_Base::upper_bound(__x));
 420       }
 421
 422       std::pair<iterator,iterator>
 423       equal_range(const key_type& __x)
 424       {
 425         typedef typename _Base::iterator _Base_iterator;
 426         std::pair<_Base_iterator, _Base_iterator> __res =
 427         _Base::equal_range(__x);
 428         return std::make_pair(iterator(__res.first),
 429                               iterator(__res.second));
 430       }
 431
 432       std::pair<const_iterator,const_iterator>
 433       equal_range(const key_type& __x) const
 434       {
 435         __profcxx_map_to_unordered_map_find(this, size());
 436         typedef typename _Base::const_iterator _Base_const_iterator;
 437         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 438         _Base::equal_range(__x);
 439         return std::make_pair(const_iterator(__res.first),
 440                               const_iterator(__res.second));
 441       }
 442
 443       _Base&
 444       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
 445
 446       const _Base&
 447       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 448
 449     };
 450
 451   template<typename _Key, typename _Tp,
 452            typename _Compare, typename _Allocator>
 453     inline bool
 454     operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 455                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 456     {
 457       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 458       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 459       return __lhs._M_base() == __rhs._M_base();
 460     }
 461
 462   template<typename _Key, typename _Tp,
 463            typename _Compare, typename _Allocator>
 464     inline bool
 465     operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 466                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 467     {
 468       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 469       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 470       return __lhs._M_base() != __rhs._M_base();
 471     }
 472
 473   template<typename _Key, typename _Tp,
 474            typename _Compare, typename _Allocator>
 475     inline bool
 476     operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 477               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 478     {
 479       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 480       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 481       return __lhs._M_base() < __rhs._M_base();
 482     }
 483
 484   template<typename _Key, typename _Tp,
 485            typename _Compare, typename _Allocator>
 486     inline bool
 487     operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 488                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 489     {
 490       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 491       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 492       return __lhs._M_base() <= __rhs._M_base();
 493     }
 494
 495   template<typename _Key, typename _Tp,
 496            typename _Compare, typename _Allocator>
 497     inline bool
 498     operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 499                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 500     {
 501       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 502       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 503       return __lhs._M_base() >= __rhs._M_base();
 504     }
 505
 506   template<typename _Key, typename _Tp,
 507            typename _Compare, typename _Allocator>
 508     inline bool
 509     operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 510               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 511     {
 512       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 513       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 514       return __lhs._M_base() > __rhs._M_base();
 515     }
 516
 517   template<typename _Key, typename _Tp,
 518            typename _Compare, typename _Allocator>
 519     inline void
 520     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 521          map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 522     { __lhs.swap(__rhs); }
 523
 524 } // namespace __profile
 525 } // namespace std
 526
 527 #endif