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

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