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

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