release/src-rt-6.x.4708/toolchains/hndtools-arm-linux-2.6.36-uclibc-4.5.3/arm-brcm-linux-uclibcgnueabi/include/c++/4.5.3/debug/unordered_set

   1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
   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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /** @file debug/unordered_set
  27  *  This file is a GNU debug extension to the Standard C++ Library.
  28  */
  29
  30 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET
  31 #define _GLIBCXX_DEBUG_UNORDERED_SET 1
  32
  33 #ifndef __GXX_EXPERIMENTAL_CXX0X__
  34 # include <bits/c++0x_warning.h>
  35 #else
  36 # include <unordered_set>
  37
  38 #include <debug/safe_sequence.h>
  39 #include <debug/safe_iterator.h>
  40
  41 namespace std
  42 {
  43 namespace __debug
  44 {
  45   /// Class std::unordered_set with safety/checking/debug instrumentation.
  46   template<typename _Value,
  47            typename _Hash = std::hash<_Value>,
  48            typename _Pred = std::equal_to<_Value>,
  49            typename _Alloc = std::allocator<_Value> >
  50     class unordered_set
  51     : public _GLIBCXX_STD_D::unordered_set<_Value, _Hash, _Pred, _Alloc>,
  52       public __gnu_debug::_Safe_sequence<unordered_set<_Value, _Hash,
  53                                                        _Pred, _Alloc> >
  54     {
  55       typedef _GLIBCXX_STD_D::unordered_set<_Value, _Hash,
  56                                             _Pred, _Alloc> _Base;
  57       typedef __gnu_debug::_Safe_sequence<unordered_set> _Safe_base;
  58
  59     public:
  60       typedef typename _Base::size_type       size_type;
  61       typedef typename _Base::hasher          hasher;
  62       typedef typename _Base::key_equal       key_equal;
  63       typedef typename _Base::allocator_type  allocator_type;
  64
  65       typedef typename _Base::key_type        key_type;
  66       typedef typename _Base::value_type      value_type;
  67
  68       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
  69                                           unordered_set> iterator;
  70       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
  71                                           unordered_set> const_iterator;
  72
  73       explicit
  74       unordered_set(size_type __n = 10,
  75                     const hasher& __hf = hasher(),
  76                     const key_equal& __eql = key_equal(),
  77                     const allocator_type& __a = allocator_type())
  78       : _Base(__n, __hf, __eql, __a) { }
  79
  80       template<typename _InputIterator>
  81         unordered_set(_InputIterator __f, _InputIterator __l,
  82                       size_type __n = 10,
  83                       const hasher& __hf = hasher(),
  84                       const key_equal& __eql = key_equal(),
  85                       const allocator_type& __a = allocator_type())
  86         : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
  87                 __hf, __eql, __a), _Safe_base() { }
  88
  89       unordered_set(const unordered_set& __x)
  90       : _Base(__x), _Safe_base() { }
  91
  92       unordered_set(const _Base& __x)
  93       : _Base(__x), _Safe_base() { }
  94
  95       unordered_set(unordered_set&& __x)
  96       : _Base(std::forward<unordered_set>(__x)), _Safe_base() { }
  97
  98       unordered_set(initializer_list<value_type> __l,
  99                     size_type __n = 10,
 100                     const hasher& __hf = hasher(),
 101                     const key_equal& __eql = key_equal(),
 102                     const allocator_type& __a = allocator_type())
 103       : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
 104
 105       unordered_set&
 106       operator=(const unordered_set& __x)
 107       {
 108         *static_cast<_Base*>(this) = __x;
 109         this->_M_invalidate_all();
 110         return *this;
 111       }
 112
 113       unordered_set&
 114       operator=(unordered_set&& __x)
 115       {
 116         // NB: DR 1204.
 117         // NB: DR 675.
 118         clear();
 119         swap(__x);
 120         return *this;
 121       }
 122
 123       unordered_set&
 124       operator=(initializer_list<value_type> __l)
 125       {
 126         this->clear();
 127         this->insert(__l);
 128         return *this;
 129       }
 130
 131       void
 132       swap(unordered_set& __x)
 133       {
 134         _Base::swap(__x);
 135         _Safe_base::_M_swap(__x);
 136       }
 137
 138       void
 139       clear()
 140       {
 141         _Base::clear();
 142         this->_M_invalidate_all();
 143       }
 144
 145       iterator
 146       begin()
 147       { return iterator(_Base::begin(), this); }
 148
 149       const_iterator
 150       begin() const
 151       { return const_iterator(_Base::begin(), this); }
 152
 153       iterator
 154       end()
 155       { return iterator(_Base::end(), this); }
 156
 157       const_iterator
 158       end() const
 159       { return const_iterator(_Base::end(), this); }
 160
 161       const_iterator
 162       cbegin() const
 163       { return const_iterator(_Base::begin(), this); }
 164
 165       const_iterator
 166       cend() const
 167       { return const_iterator(_Base::end(), this); }
 168
 169       // local versions
 170       using _Base::begin;
 171       using _Base::end;
 172       using _Base::cbegin;
 173       using _Base::cend;
 174
 175       std::pair<iterator, bool>
 176       insert(const value_type& __obj)
 177       {
 178         typedef std::pair<typename _Base::iterator, bool> __pair_type;
 179         __pair_type __res = _Base::insert(__obj);
 180         return std::make_pair(iterator(__res.first, this), __res.second);
 181       }
 182
 183       iterator
 184       insert(const_iterator, const value_type& __obj)
 185       {
 186         typedef std::pair<typename _Base::iterator, bool> __pair_type;
 187         __pair_type __res = _Base::insert(__obj);
 188         return iterator(__res.first, this);
 189       }
 190
 191       void
 192       insert(std::initializer_list<value_type> __l)
 193       { _Base::insert(__l); }
 194
 195       template<typename _InputIterator>
 196         void
 197         insert(_InputIterator __first, _InputIterator __last)
 198         {
 199           __glibcxx_check_valid_range(__first, __last);
 200           _Base::insert(__first, __last);
 201         }
 202
 203       iterator
 204       find(const key_type& __key)
 205       { return iterator(_Base::find(__key), this); }
 206
 207       const_iterator
 208       find(const key_type& __key) const
 209       { return const_iterator(_Base::find(__key), this); }
 210
 211       std::pair<iterator, iterator>
 212       equal_range(const key_type& __key)
 213       {
 214         typedef typename _Base::iterator _Base_iterator;
 215         typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
 216         __pair_type __res = _Base::equal_range(__key);
 217         return std::make_pair(iterator(__res.first, this),
 218                               iterator(__res.second, this));
 219       }
 220
 221       std::pair<const_iterator, const_iterator>
 222       equal_range(const key_type& __key) const
 223       {
 224         typedef typename _Base::const_iterator _Base_iterator;
 225         typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
 226         __pair_type __res = _Base::equal_range(__key);
 227         return std::make_pair(const_iterator(__res.first, this),
 228                               const_iterator(__res.second, this));
 229       }
 230
 231       size_type
 232       erase(const key_type& __key)
 233       {
 234         size_type __ret(0);
 235         iterator __victim(_Base::find(__key), this);
 236         if (__victim != end())
 237           {
 238             this->erase(__victim);
 239             __ret = 1;
 240           }
 241         return __ret;
 242       }
 243
 244       iterator
 245       erase(const_iterator __it)
 246       {
 247         __glibcxx_check_erase(__it);
 248         __it._M_invalidate();
 249         return iterator(_Base::erase(__it.base()), this);
 250       }
 251
 252       iterator
 253       erase(const_iterator __first, const_iterator __last)
 254       {
 255         __glibcxx_check_erase_range(__first, __last);
 256         for (const_iterator __tmp = __first; __tmp != __last;)
 257         {
 258           const_iterator __victim = __tmp++;
 259           __victim._M_invalidate();
 260         }
 261         return iterator(_Base::erase(__first.base(),
 262                                      __last.base()), this);
 263       }
 264
 265       _Base&
 266       _M_base() { return *this; }
 267
 268       const _Base&
 269       _M_base() const { return *this; }
 270
 271     private:
 272       void
 273       _M_invalidate_all()
 274       {
 275         typedef typename _Base::const_iterator _Base_const_iterator;
 276         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 277         this->_M_invalidate_if(_Not_equal(_M_base().end()));
 278       }
 279     };
 280
 281   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 282     inline void
 283     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 284          unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 285     { __x.swap(__y); }
 286
 287   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 288     inline bool
 289     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 290                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 291     { return __x._M_equal(__y); }
 292
 293   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 294     inline bool
 295     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 296                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 297     { return !(__x == __y); }
 298
 299
 300   /// Class std::unordered_multiset with safety/checking/debug instrumentation.
 301   template<typename _Value,
 302            typename _Hash = std::hash<_Value>,
 303            typename _Pred = std::equal_to<_Value>,
 304            typename _Alloc = std::allocator<_Value> >
 305     class unordered_multiset
 306     : public _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
 307       public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash,
 308                                                             _Pred, _Alloc> >
 309     {
 310       typedef _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash,
 311                                                  _Pred, _Alloc> _Base;
 312       typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base;
 313
 314     public:
 315       typedef typename _Base::size_type       size_type;
 316       typedef typename _Base::hasher          hasher;
 317       typedef typename _Base::key_equal       key_equal;
 318       typedef typename _Base::allocator_type  allocator_type;
 319
 320       typedef typename _Base::key_type        key_type;
 321       typedef typename _Base::value_type      value_type;
 322
 323       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
 324                                           unordered_multiset> iterator;
 325       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
 326                                           unordered_multiset> const_iterator;
 327
 328       explicit
 329       unordered_multiset(size_type __n = 10,
 330                          const hasher& __hf = hasher(),
 331                          const key_equal& __eql = key_equal(),
 332                          const allocator_type& __a = allocator_type())
 333       : _Base(__n, __hf, __eql, __a) { }
 334
 335       template<typename _InputIterator>
 336         unordered_multiset(_InputIterator __f, _InputIterator __l,
 337                            size_type __n = 10,
 338                            const hasher& __hf = hasher(),
 339                            const key_equal& __eql = key_equal(),
 340                            const allocator_type& __a = allocator_type())
 341         : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
 342                 __hf, __eql, __a), _Safe_base() { }
 343
 344       unordered_multiset(const unordered_multiset& __x)
 345       : _Base(__x), _Safe_base() { }
 346
 347       unordered_multiset(const _Base& __x)
 348       : _Base(__x), _Safe_base() { }
 349
 350       unordered_multiset(unordered_multiset&& __x)
 351       : _Base(std::forward<unordered_multiset>(__x)), _Safe_base() { }
 352
 353       unordered_multiset(initializer_list<value_type> __l,
 354                          size_type __n = 10,
 355                          const hasher& __hf = hasher(),
 356                          const key_equal& __eql = key_equal(),
 357                          const allocator_type& __a = allocator_type())
 358       : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
 359
 360       unordered_multiset&
 361       operator=(const unordered_multiset& __x)
 362       {
 363         *static_cast<_Base*>(this) = __x;
 364         this->_M_invalidate_all();
 365         return *this;
 366       }
 367
 368       unordered_multiset&
 369       operator=(unordered_multiset&& __x)
 370       {
 371         // NB: DR 1204.
 372         // NB: DR 675.
 373         clear();
 374         swap(__x);
 375         return *this;
 376       }
 377
 378       unordered_multiset&
 379       operator=(initializer_list<value_type> __l)
 380       {
 381         this->clear();
 382         this->insert(__l);
 383         return *this;
 384       }
 385
 386       void
 387       swap(unordered_multiset& __x)
 388       {
 389         _Base::swap(__x);
 390         _Safe_base::_M_swap(__x);
 391       }
 392
 393       void
 394       clear()
 395       {
 396         _Base::clear();
 397         this->_M_invalidate_all();
 398       }
 399
 400       iterator
 401       begin()
 402       { return iterator(_Base::begin(), this); }
 403
 404       const_iterator
 405       begin() const
 406       { return const_iterator(_Base::begin(), this); }
 407
 408       iterator
 409       end()
 410       { return iterator(_Base::end(), this); }
 411
 412       const_iterator
 413       end() const
 414       { return const_iterator(_Base::end(), this); }
 415
 416       const_iterator
 417       cbegin() const
 418       { return const_iterator(_Base::begin(), this); }
 419
 420       const_iterator
 421       cend() const
 422       { return const_iterator(_Base::end(), this); }
 423
 424       // local versions
 425       using _Base::begin;
 426       using _Base::end;
 427       using _Base::cbegin;
 428       using _Base::cend;
 429
 430       iterator
 431       insert(const value_type& __obj)
 432       { return iterator(_Base::insert(__obj), this); }
 433
 434       iterator
 435       insert(const_iterator, const value_type& __obj)
 436       { return iterator(_Base::insert(__obj), this); }
 437
 438       void
 439       insert(std::initializer_list<value_type> __l)
 440       { _Base::insert(__l); }
 441
 442       template<typename _InputIterator>
 443         void
 444         insert(_InputIterator __first, _InputIterator __last)
 445         {
 446           __glibcxx_check_valid_range(__first, __last);
 447           _Base::insert(__first, __last);
 448         }
 449
 450       iterator
 451       find(const key_type& __key)
 452       { return iterator(_Base::find(__key), this); }
 453
 454       const_iterator
 455       find(const key_type& __key) const
 456       { return const_iterator(_Base::find(__key), this); }
 457
 458       std::pair<iterator, iterator>
 459       equal_range(const key_type& __key)
 460       {
 461         typedef typename _Base::iterator _Base_iterator;
 462         typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
 463         __pair_type __res = _Base::equal_range(__key);
 464         return std::make_pair(iterator(__res.first, this),
 465                               iterator(__res.second, this));
 466       }
 467
 468       std::pair<const_iterator, const_iterator>
 469       equal_range(const key_type& __key) const
 470       {
 471         typedef typename _Base::const_iterator _Base_iterator;
 472         typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
 473         __pair_type __res = _Base::equal_range(__key);
 474         return std::make_pair(const_iterator(__res.first, this),
 475                               const_iterator(__res.second, this));
 476       }
 477
 478       size_type
 479       erase(const key_type& __key)
 480       {
 481         size_type __ret(0);
 482         iterator __victim(_Base::find(__key), this);
 483         if (__victim != end())
 484           {
 485             this->erase(__victim);
 486             __ret = 1;
 487           }
 488         return __ret;
 489       }
 490
 491       iterator
 492       erase(const_iterator __it)
 493       {
 494         __glibcxx_check_erase(__it);
 495         __it._M_invalidate();
 496         return iterator(_Base::erase(__it.base()), this);
 497       }
 498
 499       iterator
 500       erase(const_iterator __first, const_iterator __last)
 501       {
 502         __glibcxx_check_erase_range(__first, __last);
 503         for (const_iterator __tmp = __first; __tmp != __last;)
 504         {
 505           const_iterator __victim = __tmp++;
 506           __victim._M_invalidate();
 507         }
 508         return iterator(_Base::erase(__first.base(),
 509                                      __last.base()), this);
 510       }
 511
 512       _Base&
 513       _M_base() { return *this; }
 514
 515       const _Base&
 516       _M_base() const { return *this; }
 517
 518     private:
 519       void
 520       _M_invalidate_all()
 521       {
 522         typedef typename _Base::const_iterator _Base_const_iterator;
 523         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 524         this->_M_invalidate_if(_Not_equal(_M_base().end()));
 525       }
 526     };
 527
 528   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 529     inline void
 530     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 531          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 532     { __x.swap(__y); }
 533
 534   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 535     inline bool
 536     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 537                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 538     { return __x._M_equal(__y); }
 539
 540   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 541     inline bool
 542     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 543                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 544     { return !(__x == __y); }
 545
 546 } // namespace __debug
 547 } // namespace std
 548
 549 #endif // __GXX_EXPERIMENTAL_CXX0X__
 550
 551 #endif