l4/pkg/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 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()
 141       { return _Base::begin(); }
 142
 143       const_iterator
 144       begin() const
 145       { return _Base::begin(); }
 146
 147       iterator
 148       end()
 149       { return _Base::end(); }
 150
 151       const_iterator
 152       end() const
 153       { return _Base::end(); }
 154
 155       reverse_iterator
 156       rbegin()
 157       {
 158         __profcxx_map_to_unordered_map_invalidate(this);
 159         return reverse_iterator(end());
 160       }
 161
 162       const_reverse_iterator
 163       rbegin() const
 164       {
 165         __profcxx_map_to_unordered_map_invalidate(this);
 166         return const_reverse_iterator(end());
 167       }
 168
 169       reverse_iterator
 170       rend()
 171       {
 172         __profcxx_map_to_unordered_map_invalidate(this);
 173         return reverse_iterator(begin());
 174       }
 175
 176       const_reverse_iterator
 177       rend() const
 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
 186       { return const_iterator(_Base::begin()); }
 187
 188       const_iterator
 189       cend() const
 190       { return const_iterator(_Base::end()); }
 191
 192       const_reverse_iterator
 193       crbegin() const
 194       {
 195         __profcxx_map_to_unordered_map_invalidate(this);
 196         return const_reverse_iterator(end());
 197       }
 198
 199       const_reverse_iterator
 200       crend() const
 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
 363       swap(map& __x)
 364       { _Base::swap(__x); }
 365
 366       void
 367       clear()
 368       { this->erase(begin(), end()); }
 369
 370       // observers:
 371       using _Base::key_comp;
 372       using _Base::value_comp;
 373
 374       // 23.3.1.3 map operations:
 375       iterator
 376       find(const key_type& __x)
 377       {
 378         __profcxx_map_to_unordered_map_find(this, size());
 379         return iterator(_Base::find(__x));
 380       }
 381
 382       const_iterator
 383       find(const key_type& __x) const
 384       {
 385         __profcxx_map_to_unordered_map_find(this, size());
 386         return const_iterator(_Base::find(__x));
 387       }
 388
 389       size_type
 390       count(const key_type& __x) const
 391       {
 392         __profcxx_map_to_unordered_map_find(this, size());
 393         return _Base::count(__x);
 394       }
 395
 396       iterator
 397       lower_bound(const key_type& __x)
 398       {
 399         __profcxx_map_to_unordered_map_invalidate(this);
 400         return iterator(_Base::lower_bound(__x));
 401       }
 402
 403       const_iterator
 404       lower_bound(const key_type& __x) const
 405       {
 406         __profcxx_map_to_unordered_map_invalidate(this);
 407         return const_iterator(_Base::lower_bound(__x));
 408       }
 409
 410       iterator
 411       upper_bound(const key_type& __x)
 412       {
 413         __profcxx_map_to_unordered_map_invalidate(this);
 414         return iterator(_Base::upper_bound(__x));
 415       }
 416
 417       const_iterator
 418       upper_bound(const key_type& __x) const
 419       {
 420         __profcxx_map_to_unordered_map_invalidate(this);
 421         return const_iterator(_Base::upper_bound(__x));
 422       }
 423
 424       std::pair<iterator,iterator>
 425       equal_range(const key_type& __x)
 426       {
 427         typedef typename _Base::iterator _Base_iterator;
 428         std::pair<_Base_iterator, _Base_iterator> __res =
 429         _Base::equal_range(__x);
 430         return std::make_pair(iterator(__res.first),
 431                               iterator(__res.second));
 432       }
 433
 434       std::pair<const_iterator,const_iterator>
 435       equal_range(const key_type& __x) const
 436       {
 437         __profcxx_map_to_unordered_map_find(this, size());
 438         typedef typename _Base::const_iterator _Base_const_iterator;
 439         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 440         _Base::equal_range(__x);
 441         return std::make_pair(const_iterator(__res.first),
 442                               const_iterator(__res.second));
 443       }
 444
 445       _Base&
 446       _M_base() { return *this; }
 447
 448       const _Base&
 449       _M_base() const { return *this; }
 450
 451     };
 452
 453   template<typename _Key, typename _Tp,
 454            typename _Compare, typename _Allocator>
 455     inline bool
 456     operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 457                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 458     {
 459       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 460       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 461       return __lhs._M_base() == __rhs._M_base();
 462     }
 463
 464   template<typename _Key, typename _Tp,
 465            typename _Compare, typename _Allocator>
 466     inline bool
 467     operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 468                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 469     {
 470       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 471       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 472       return __lhs._M_base() != __rhs._M_base();
 473     }
 474
 475   template<typename _Key, typename _Tp,
 476            typename _Compare, typename _Allocator>
 477     inline bool
 478     operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 479               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 480     {
 481       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 482       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 483       return __lhs._M_base() < __rhs._M_base();
 484     }
 485
 486   template<typename _Key, typename _Tp,
 487            typename _Compare, typename _Allocator>
 488     inline bool
 489     operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 490                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 491     {
 492       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 493       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 494       return __lhs._M_base() <= __rhs._M_base();
 495     }
 496
 497   template<typename _Key, typename _Tp,
 498            typename _Compare, typename _Allocator>
 499     inline bool
 500     operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 501                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 502     {
 503       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 504       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 505       return __lhs._M_base() >= __rhs._M_base();
 506     }
 507
 508   template<typename _Key, typename _Tp,
 509            typename _Compare, typename _Allocator>
 510     inline bool
 511     operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 512               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 513     {
 514       __profcxx_map_to_unordered_map_invalidate(&__lhs);
 515       __profcxx_map_to_unordered_map_invalidate(&__rhs);
 516       return __lhs._M_base() > __rhs._M_base();
 517     }
 518
 519   template<typename _Key, typename _Tp,
 520            typename _Compare, typename _Allocator>
 521     inline void
 522     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 523          map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 524     { __lhs.swap(__rhs); }
 525
 526 } // namespace __profile
 527 } // namespace std
 528
 529 #endif