l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.3.3/include/debug/map.h

   1 // Debugging map implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003, 2004, 2005, 2006, 2007
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 2, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // You should have received a copy of the GNU General Public License along
  18 // with this library; see the file COPYING.  If not, write to the Free
  19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  20 // USA.
  21
  22 // As a special exception, you may use this file as part of a free software
  23 // library without restriction.  Specifically, if other files instantiate
  24 // templates or use macros or inline functions from this file, or you compile
  25 // this file and link it with other files to produce an executable, this
  26 // file does not by itself cause the resulting executable to be covered by
  27 // the GNU General Public License.  This exception does not however
  28 // invalidate any other reasons why the executable file might be covered by
  29 // the GNU General Public License.
  30
  31 /** @file debug/map.h
  32  *  This file is a GNU debug extension to the Standard C++ Library.
  33  */
  34
  35 #ifndef _GLIBCXX_DEBUG_MAP_H
  36 #define _GLIBCXX_DEBUG_MAP_H 1
  37
  38 #include <debug/safe_sequence.h>
  39 #include <debug/safe_iterator.h>
  40 #include <utility>
  41
  42 namespace std
  43 {
  44 namespace __debug
  45 {
  46   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
  47            typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
  48     class map
  49     : public _GLIBCXX_STD_D::map<_Key, _Tp, _Compare, _Allocator>,
  50       public __gnu_debug::_Safe_sequence<map<_Key, _Tp, _Compare, _Allocator> >
  51     {
  52       typedef _GLIBCXX_STD_D::map<_Key, _Tp, _Compare, _Allocator> _Base;
  53       typedef __gnu_debug::_Safe_sequence<map> _Safe_base;
  54
  55     public:
  56       // types:
  57       typedef _Key                                  key_type;
  58       typedef _Tp                                   mapped_type;
  59       typedef std::pair<const _Key, _Tp>            value_type;
  60       typedef _Compare                              key_compare;
  61       typedef _Allocator                            allocator_type;
  62       typedef typename _Base::reference             reference;
  63       typedef typename _Base::const_reference       const_reference;
  64
  65       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, map>
  66                                                     iterator;
  67       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, map>
  68                                                     const_iterator;
  69
  70       typedef typename _Base::size_type             size_type;
  71       typedef typename _Base::difference_type       difference_type;
  72       typedef typename _Base::pointer               pointer;
  73       typedef typename _Base::const_pointer         const_pointer;
  74       typedef std::reverse_iterator<iterator>       reverse_iterator;
  75       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  76
  77       using _Base::value_compare;
  78
  79       // 23.3.1.1 construct/copy/destroy:
  80       explicit map(const _Compare& __comp = _Compare(),
  81                    const _Allocator& __a = _Allocator())
  82       : _Base(__comp, __a) { }
  83
  84       template<typename _InputIterator>
  85         map(_InputIterator __first, _InputIterator __last,
  86             const _Compare& __comp = _Compare(),
  87             const _Allocator& __a = _Allocator())
  88         : _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
  89                 __comp, __a), _Safe_base() { }
  90
  91       map(const map& __x)
  92       : _Base(__x), _Safe_base() { }
  93
  94       map(const _Base& __x)
  95       : _Base(__x), _Safe_base() { }
  96
  97 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  98       map(map&& __x)
  99       : _Base(std::forward<map>(__x)), _Safe_base()
 100       { this->_M_swap(__x); }
 101 #endif
 102
 103       ~map() { }
 104
 105       map&
 106       operator=(const map& __x)
 107       {
 108         *static_cast<_Base*>(this) = __x;
 109         this->_M_invalidate_all();
 110         return *this;
 111       }
 112
 113 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 114       map&
 115       operator=(map&& __x)
 116       {
 117         // NB: DR 675.
 118         clear();
 119         swap(__x);
 120         return *this;
 121       }
 122 #endif
 123
 124       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 125       // 133. map missing get_allocator()
 126       using _Base::get_allocator;
 127
 128       // iterators:
 129       iterator
 130       begin()
 131       { return iterator(_Base::begin(), this); }
 132
 133       const_iterator
 134       begin() const
 135       { return const_iterator(_Base::begin(), this); }
 136
 137       iterator
 138       end()
 139       { return iterator(_Base::end(), this); }
 140
 141       const_iterator
 142       end() const
 143       { return const_iterator(_Base::end(), this); }
 144
 145       reverse_iterator
 146       rbegin()
 147       { return reverse_iterator(end()); }
 148
 149       const_reverse_iterator
 150       rbegin() const
 151       { return const_reverse_iterator(end()); }
 152
 153       reverse_iterator
 154       rend()
 155       { return reverse_iterator(begin()); }
 156
 157       const_reverse_iterator
 158       rend() const
 159       { return const_reverse_iterator(begin()); }
 160
 161 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 162       const_iterator
 163       cbegin() const
 164       { return const_iterator(_Base::begin(), this); }
 165
 166       const_iterator
 167       cend() const
 168       { return const_iterator(_Base::end(), this); }
 169
 170       const_reverse_iterator
 171       crbegin() const
 172       { return const_reverse_iterator(end()); }
 173
 174       const_reverse_iterator
 175       crend() const
 176       { return const_reverse_iterator(begin()); }
 177 #endif
 178
 179       // capacity:
 180       using _Base::empty;
 181       using _Base::size;
 182       using _Base::max_size;
 183
 184       // 23.3.1.2 element access:
 185       using _Base::operator[];
 186
 187       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 188       // DR 464. Suggestion for new member functions in standard containers.
 189       using _Base::at;
 190
 191       // modifiers:
 192       std::pair<iterator, bool>
 193       insert(const value_type& __x)
 194       {
 195         typedef typename _Base::iterator _Base_iterator;
 196         std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
 197         return std::pair<iterator, bool>(iterator(__res.first, this),
 198                                          __res.second);
 199       }
 200
 201       iterator
 202       insert(iterator __position, const value_type& __x)
 203       {
 204         __glibcxx_check_insert(__position);
 205         return iterator(_Base::insert(__position.base(), __x), this);
 206       }
 207
 208       template<typename _InputIterator>
 209         void
 210         insert(_InputIterator __first, _InputIterator __last)
 211         {
 212           __glibcxx_check_valid_range(__first, __last);
 213           _Base::insert(__first, __last);
 214         }
 215
 216       void
 217       erase(iterator __position)
 218       {
 219         __glibcxx_check_erase(__position);
 220         __position._M_invalidate();
 221         _Base::erase(__position.base());
 222       }
 223
 224       size_type
 225       erase(const key_type& __x)
 226       {
 227         iterator __victim = find(__x);
 228         if (__victim == end())
 229           return 0;
 230         else
 231         {
 232           __victim._M_invalidate();
 233           _Base::erase(__victim.base());
 234           return 1;
 235         }
 236       }
 237
 238       void
 239       erase(iterator __first, iterator __last)
 240       {
 241         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 242         // 151. can't currently clear() empty container
 243         __glibcxx_check_erase_range(__first, __last);
 244         while (__first != __last)
 245           this->erase(__first++);
 246       }
 247
 248       void
 249 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 250       swap(map&& __x)
 251 #else
 252       swap(map& __x)
 253 #endif
 254       {
 255         _Base::swap(__x);
 256         this->_M_swap(__x);
 257       }
 258
 259       void
 260       clear()
 261       { this->erase(begin(), end()); }
 262
 263       // observers:
 264       using _Base::key_comp;
 265       using _Base::value_comp;
 266
 267       // 23.3.1.3 map operations:
 268       iterator
 269       find(const key_type& __x)
 270       { return iterator(_Base::find(__x), this); }
 271
 272       const_iterator
 273       find(const key_type& __x) const
 274       { return const_iterator(_Base::find(__x), this); }
 275
 276       using _Base::count;
 277
 278       iterator
 279       lower_bound(const key_type& __x)
 280       { return iterator(_Base::lower_bound(__x), this); }
 281
 282       const_iterator
 283       lower_bound(const key_type& __x) const
 284       { return const_iterator(_Base::lower_bound(__x), this); }
 285
 286       iterator
 287       upper_bound(const key_type& __x)
 288       { return iterator(_Base::upper_bound(__x), this); }
 289
 290       const_iterator
 291       upper_bound(const key_type& __x) const
 292       { return const_iterator(_Base::upper_bound(__x), this); }
 293
 294       std::pair<iterator,iterator>
 295       equal_range(const key_type& __x)
 296       {
 297         typedef typename _Base::iterator _Base_iterator;
 298         std::pair<_Base_iterator, _Base_iterator> __res =
 299         _Base::equal_range(__x);
 300         return std::make_pair(iterator(__res.first, this),
 301                               iterator(__res.second, this));
 302       }
 303
 304       std::pair<const_iterator,const_iterator>
 305       equal_range(const key_type& __x) const
 306       {
 307         typedef typename _Base::const_iterator _Base_const_iterator;
 308         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 309         _Base::equal_range(__x);
 310         return std::make_pair(const_iterator(__res.first, this),
 311                               const_iterator(__res.second, this));
 312       }
 313
 314       _Base&
 315       _M_base() { return *this; }
 316
 317       const _Base&
 318       _M_base() const { return *this; }
 319
 320     private:
 321       void
 322       _M_invalidate_all()
 323       {
 324         typedef typename _Base::const_iterator _Base_const_iterator;
 325         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 326         this->_M_invalidate_if(_Not_equal(_M_base().end()));
 327       }
 328     };
 329
 330   template<typename _Key, typename _Tp,
 331            typename _Compare, typename _Allocator>
 332     inline bool
 333     operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 334                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 335     { return __lhs._M_base() == __rhs._M_base(); }
 336
 337   template<typename _Key, typename _Tp,
 338            typename _Compare, typename _Allocator>
 339     inline bool
 340     operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 341                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 342     { return __lhs._M_base() != __rhs._M_base(); }
 343
 344   template<typename _Key, typename _Tp,
 345            typename _Compare, typename _Allocator>
 346     inline bool
 347     operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 348               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 349     { return __lhs._M_base() < __rhs._M_base(); }
 350
 351   template<typename _Key, typename _Tp,
 352            typename _Compare, typename _Allocator>
 353     inline bool
 354     operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 355                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 356     { return __lhs._M_base() <= __rhs._M_base(); }
 357
 358   template<typename _Key, typename _Tp,
 359            typename _Compare, typename _Allocator>
 360     inline bool
 361     operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 362                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 363     { return __lhs._M_base() >= __rhs._M_base(); }
 364
 365   template<typename _Key, typename _Tp,
 366            typename _Compare, typename _Allocator>
 367     inline bool
 368     operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 369               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 370     { return __lhs._M_base() > __rhs._M_base(); }
 371
 372   template<typename _Key, typename _Tp,
 373            typename _Compare, typename _Allocator>
 374     inline void
 375     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 376          map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 377     { __lhs.swap(__rhs); }
 378
 379 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 380   template<typename _Key, typename _Tp,
 381            typename _Compare, typename _Allocator>
 382     inline void
 383     swap(map<_Key, _Tp, _Compare, _Allocator>&& __lhs,
 384          map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 385     { __lhs.swap(__rhs); }
 386
 387   template<typename _Key, typename _Tp,
 388            typename _Compare, typename _Allocator>
 389     inline void
 390     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 391          map<_Key, _Tp, _Compare, _Allocator>&& __rhs)
 392     { __lhs.swap(__rhs); }
 393 #endif
 394
 395 } // namespace __debug
 396 } // namespace std
 397
 398 #endif