l4/pkg/l4re-core/libstdc++-v3/contrib/libstdc++-v3-4.6/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 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       : _Base(std::move(__x))
  90       { }
  91
  92       map(initializer_list<value_type> __l,
  93           const _Compare& __c = _Compare(),
  94           const allocator_type& __a = allocator_type())
  95       : _Base(__l, __c, __a) { }
  96 #endif
  97
  98       ~map()
  99       { __profcxx_map_to_unordered_map_destruct(this); }
 100
 101       map&
 102       operator=(const map& __x)
 103       {
 104         *static_cast<_Base*>(this) = __x;
 105         return *this;
 106       }
 107
 108 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 109       map&
 110       operator=(map&& __x)
 111       {
 112         // NB: DR 1204.
 113         // NB: DR 675.
 114         this->clear();
 115         this->swap(__x);
 116         return *this;
 117       }
 118
 119       map&
 120       operator=(initializer_list<value_type> __l)
 121       {
 122         this->clear();
 123         this->insert(__l);
 124         return *this;
 125       }
 126 #endif
 127
 128       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 129       // 133. map missing get_allocator()
 130       using _Base::get_allocator;
 131
 132       // iterators:
 133       iterator
 134       begin()
 135       { return _Base::begin(); }
 136
 137       const_iterator
 138       begin() const
 139       { return _Base::begin(); }
 140
 141       iterator
 142       end()
 143       { return _Base::end(); }
 144
 145       const_iterator
 146       end() const
 147       { return _Base::end(); }
 148
 149       reverse_iterator
 150       rbegin()
 151       {
 152         __profcxx_map_to_unordered_map_invalidate(this);
 153         return reverse_iterator(end());
 154       }
 155
 156       const_reverse_iterator
 157       rbegin() const
 158       {
 159         __profcxx_map_to_unordered_map_invalidate(this);
 160         return const_reverse_iterator(end());
 161       }
 162
 163       reverse_iterator
 164       rend()
 165       {
 166         __profcxx_map_to_unordered_map_invalidate(this);
 167         return reverse_iterator(begin());
 168       }
 169
 170       const_reverse_iterator
 171       rend() const
 172       {
 173         __profcxx_map_to_unordered_map_invalidate(this);
 174         return const_reverse_iterator(begin());
 175       }
 176
 177 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 178       const_iterator
 179       cbegin() const
 180       { return const_iterator(_Base::begin()); }
 181
 182       const_iterator
 183       cend() const
 184       { return const_iterator(_Base::end()); }
 185
 186       const_reverse_iterator
 187       crbegin() const
 188       {
 189         __profcxx_map_to_unordered_map_invalidate(this);
 190         return const_reverse_iterator(end());
 191       }
 192
 193       const_reverse_iterator
 194       crend() const
 195       {
 196         __profcxx_map_to_unordered_map_invalidate(this);
 197         return const_reverse_iterator(begin());
 198       }
 199 #endif
 200
 201       // capacity:
 202       using _Base::empty;
 203       using _Base::size;
 204       using _Base::max_size;
 205
 206       // 23.3.1.2 element access:
 207       mapped_type&
 208       operator[](const key_type& __k)
 209       {
 210         __profcxx_map_to_unordered_map_find(this, size());
 211         return _Base::operator[](__k);
 212       }
 213
 214 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 215       mapped_type&
 216       operator[](key_type&& __k)
 217       {
 218         __profcxx_map_to_unordered_map_find(this, size());
 219         return _Base::operator[](std::move(__k));
 220       }
 221 #endif
 222
 223       mapped_type&
 224       at(const key_type& __k)
 225       {
 226         __profcxx_map_to_unordered_map_find(this, size());
 227         return _Base::at(__k);
 228       }
 229
 230       const mapped_type&
 231       at(const key_type& __k) const
 232       {
 233         __profcxx_map_to_unordered_map_find(this, size());
 234         return _Base::at(__k);
 235       }
 236
 237       // modifiers:
 238       std::pair<iterator, bool>
 239       insert(const value_type& __x)
 240       {
 241         __profcxx_map_to_unordered_map_insert(this, size(), 1);
 242         typedef typename _Base::iterator _Base_iterator;
 243         std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
 244         return std::pair<iterator, bool>(iterator(__res.first),
 245                                          __res.second);
 246       }
 247
 248 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 249       template<typename _Pair, typename = typename
 250                std::enable_if<std::is_convertible<_Pair,
 251                                                   value_type>::value>::type>
 252         std::pair<iterator, bool>
 253         insert(_Pair&& __x)
 254         {
 255           __profcxx_map_to_unordered_map_insert(this, size(), 1);
 256           typedef typename _Base::iterator _Base_iterator;
 257           std::pair<_Base_iterator, bool> __res
 258             = _Base::insert(std::forward<_Pair>(__x));
 259           return std::pair<iterator, bool>(iterator(__res.first),
 260                                            __res.second);
 261         }
 262 #endif
 263
 264 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 265       void
 266       insert(std::initializer_list<value_type> __list)
 267       {
 268         size_type size_before = size();
 269         _Base::insert(__list);
 270         __profcxx_map_to_unordered_map_insert(this, size_before,
 271                                               size() - size_before);
 272       }
 273 #endif
 274
 275       iterator
 276 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 277       insert(const_iterator __position, const value_type& __x)
 278 #else
 279       insert(iterator __position, const value_type& __x)
 280 #endif
 281       {
 282         size_type size_before = size();
 283         iterator __i = iterator(_Base::insert(__position, __x));
 284         __profcxx_map_to_unordered_map_insert(this, size_before,
 285                                               size() - size_before);
 286         return __i;
 287       }
 288
 289 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 290       template<typename _Pair, typename = typename
 291                std::enable_if<std::is_convertible<_Pair,
 292                                                   value_type>::value>::type>
 293         iterator
 294         insert(const_iterator __position, _Pair&& __x)
 295         {
 296           size_type size_before = size();
 297           iterator __i
 298             = iterator(_Base::insert(__position, std::forward<_Pair>(__x)));
 299           __profcxx_map_to_unordered_map_insert(this, size_before,
 300                                                 size() - size_before);
 301           return __i;
 302       }
 303 #endif
 304
 305       template<typename _InputIterator>
 306         void
 307         insert(_InputIterator __first, _InputIterator __last)
 308         {
 309           size_type size_before = size();
 310           _Base::insert(__first, __last);
 311           __profcxx_map_to_unordered_map_insert(this, size_before,
 312                                                 size() - size_before);
 313         }
 314
 315 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 316       iterator
 317       erase(const_iterator __position)
 318       {
 319         iterator __i = _Base::erase(__position);
 320         __profcxx_map_to_unordered_map_erase(this, size(), 1);
 321         return __i;
 322       }
 323
 324       iterator
 325       erase(iterator __position)
 326       { return erase(const_iterator(__position)); }
 327 #else
 328       void
 329       erase(iterator __position)
 330       {
 331         _Base::erase(__position);
 332         __profcxx_map_to_unordered_map_erase(this, size(), 1);
 333       }
 334 #endif
 335
 336       size_type
 337       erase(const key_type& __x)
 338       {
 339         iterator __victim = find(__x);
 340         if (__victim == end())
 341           return 0;
 342         else
 343         {
 344           _Base::erase(__victim);
 345           return 1;
 346         }
 347       }
 348
 349 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 350       iterator
 351       erase(const_iterator __first, const_iterator __last)
 352       { return iterator(_Base::erase(__first, __last)); }
 353 #else
 354       void
 355       erase(iterator __first, iterator __last)
 356       { _Base::erase(__first, __last); }
 357 #endif
 358
 359       void
 360
 361       swap(map& __x)
 362       { _Base::swap(__x); }
 363
 364       void
 365       clear()
 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() { return *this; }
 445
 446       const _Base&
 447       _M_base() const { 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