libstdc++-v3/include/debug/unordered_map

   1 // Debugging unordered_map/unordered_multimap 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_map
  27  *  This file is a GNU debug extension to the Standard C++ Library.
  28  */
  29
  30 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
  31 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1
  32
  33 #ifndef __GXX_EXPERIMENTAL_CXX0X__
  34 # include <bits/c++0x_warning.h>
  35 #else
  36 # include <unordered_map>
  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_map with safety/checking/debug instrumentation.
  46   template<typename _Key, typename _Tp,
  47            typename _Hash = std::hash<_Key>,
  48            typename _Pred = std::equal_to<_Key>,
  49            typename _Alloc = std::allocator<_Key> >
  50     class unordered_map
  51     : public _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
  52       public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash,
  53                                                        _Pred, _Alloc> >
  54     {
  55       typedef _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash,
  56                                             _Pred, _Alloc> _Base;
  57       typedef __gnu_debug::_Safe_sequence<unordered_map> _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_map> iterator;
  70       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
  71                                           unordered_map> const_iterator;
  72
  73       explicit
  74       unordered_map(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_map(_InputIterator __first, _InputIterator __last,
  82                       size_type __n = 0,
  83                       const hasher& __hf = hasher(),
  84                       const key_equal& __eql = key_equal(),
  85                       const allocator_type& __a = allocator_type())
  86         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
  87                                                                      __last)),
  88                 __gnu_debug::__base(__last), __n,
  89                 __hf, __eql, __a), _Safe_base() { }
  90
  91       unordered_map(const unordered_map& __x)
  92       : _Base(__x), _Safe_base() { }
  93
  94       unordered_map(const _Base& __x)
  95       : _Base(__x), _Safe_base() { }
  96
  97       unordered_map(unordered_map&& __x)
  98       : _Base(std::move(__x)), _Safe_base() { }
  99
 100       unordered_map(initializer_list<value_type> __l,
 101                     size_type __n = 0,
 102                     const hasher& __hf = hasher(),
 103                     const key_equal& __eql = key_equal(),
 104                     const allocator_type& __a = allocator_type())
 105       : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
 106
 107       unordered_map&
 108       operator=(const unordered_map& __x)
 109       {
 110         *static_cast<_Base*>(this) = __x;
 111         this->_M_invalidate_all();
 112         return *this;
 113       }
 114
 115       unordered_map&
 116       operator=(unordered_map&& __x)
 117       {
 118         // NB: DR 1204.
 119         // NB: DR 675.
 120         clear();
 121         swap(__x);
 122         return *this;
 123       }
 124
 125       unordered_map&
 126       operator=(initializer_list<value_type> __l)
 127       {
 128         this->clear();
 129         this->insert(__l);
 130         return *this;
 131       }
 132
 133       void
 134       swap(unordered_map& __x)
 135       {
 136         _Base::swap(__x);
 137         _Safe_base::_M_swap(__x);
 138       }
 139
 140       void
 141       clear()
 142       {
 143         _Base::clear();
 144         this->_M_invalidate_all();
 145       }
 146
 147       iterator
 148       begin()
 149       { return iterator(_Base::begin(), this); }
 150
 151       const_iterator
 152       begin() const
 153       { return const_iterator(_Base::begin(), this); }
 154
 155       iterator
 156       end()
 157       { return iterator(_Base::end(), this); }
 158
 159       const_iterator
 160       end() const
 161       { return const_iterator(_Base::end(), this); }
 162
 163       const_iterator
 164       cbegin() const
 165       { return const_iterator(_Base::begin(), this); }
 166
 167       const_iterator
 168       cend() const
 169       { return const_iterator(_Base::end(), this); }
 170
 171       // local versions
 172       using _Base::begin;
 173       using _Base::end;
 174       using _Base::cbegin;
 175       using _Base::cend;
 176
 177       std::pair<iterator, bool>
 178       insert(const value_type& __obj)
 179       {
 180         typedef std::pair<typename _Base::iterator, bool> __pair_type;
 181         __pair_type __res = _Base::insert(__obj);
 182         return std::make_pair(iterator(__res.first, this), __res.second);
 183       }
 184
 185       iterator
 186       insert(const_iterator, const value_type& __obj)
 187       {
 188         typedef std::pair<typename _Base::iterator, bool> __pair_type;
 189         __pair_type __res = _Base::insert(__obj);
 190         return iterator(__res.first, this);
 191       }
 192
 193       template<typename _Pair, typename = typename
 194                std::enable_if<std::is_convertible<_Pair,
 195                                                   value_type>::value>::type>
 196         std::pair<iterator, bool>
 197         insert(_Pair&& __obj)
 198         {
 199           typedef std::pair<typename _Base::iterator, bool> __pair_type;
 200           __pair_type __res = _Base::insert(std::forward<_Pair>(__obj));
 201           return std::make_pair(iterator(__res.first, this), __res.second);
 202         }
 203
 204       template<typename _Pair, typename = typename
 205                std::enable_if<std::is_convertible<_Pair,
 206                                                   value_type>::value>::type>
 207         iterator
 208         insert(const_iterator, _Pair&& __obj)
 209         {
 210           typedef std::pair<typename _Base::iterator, bool> __pair_type;
 211           __pair_type __res = _Base::insert(std::forward<_Pair>(__obj));
 212           return iterator(__res.first, this);
 213         }
 214
 215       void
 216       insert(std::initializer_list<value_type> __l)
 217       { _Base::insert(__l); }
 218
 219       template<typename _InputIterator>
 220         void
 221         insert(_InputIterator __first, _InputIterator __last)
 222         {
 223           __glibcxx_check_valid_range(__first, __last);
 224           _Base::insert(__gnu_debug::__base(__first),
 225                         __gnu_debug::__base(__last));
 226         }
 227
 228       iterator
 229       find(const key_type& __key)
 230       { return iterator(_Base::find(__key), this); }
 231
 232       const_iterator
 233       find(const key_type& __key) const
 234       { return const_iterator(_Base::find(__key), this); }
 235
 236       std::pair<iterator, iterator>
 237       equal_range(const key_type& __key)
 238       {
 239         typedef typename _Base::iterator _Base_iterator;
 240         typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
 241         __pair_type __res = _Base::equal_range(__key);
 242         return std::make_pair(iterator(__res.first, this),
 243                               iterator(__res.second, this));
 244       }
 245
 246       std::pair<const_iterator, const_iterator>
 247       equal_range(const key_type& __key) const
 248       {
 249         typedef typename _Base::const_iterator _Base_iterator;
 250         typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
 251         __pair_type __res = _Base::equal_range(__key);
 252         return std::make_pair(const_iterator(__res.first, this),
 253                               const_iterator(__res.second, this));
 254       }
 255
 256       size_type
 257       erase(const key_type& __key)
 258       {
 259         size_type __ret(0);
 260         iterator __victim(_Base::find(__key), this);
 261         if (__victim != end())
 262           {
 263             this->erase(__victim);
 264             __ret = 1;
 265           }
 266         return __ret;
 267       }
 268
 269       iterator
 270       erase(const_iterator __it)
 271       {
 272         __glibcxx_check_erase(__it);
 273         __it._M_invalidate();
 274         return iterator(_Base::erase(__it.base()), this);
 275       }
 276
 277       iterator
 278       erase(const_iterator __first, const_iterator __last)
 279       {
 280         __glibcxx_check_erase_range(__first, __last);
 281         for (const_iterator __tmp = __first; __tmp != __last;)
 282         {
 283           const_iterator __victim = __tmp++;
 284           __victim._M_invalidate();
 285         }
 286         return iterator(_Base::erase(__first.base(),
 287                                      __last.base()), this);
 288       }
 289
 290       _Base&
 291       _M_base() { return *this; }
 292
 293       const _Base&
 294       _M_base() const { return *this; }
 295
 296     private:
 297       void
 298       _M_invalidate_all()
 299       {
 300         typedef typename _Base::const_iterator _Base_const_iterator;
 301         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 302         this->_M_invalidate_if(_Not_equal(_M_base().end()));
 303       }
 304     };
 305
 306   template<typename _Key, typename _Tp, typename _Hash,
 307            typename _Pred, typename _Alloc>
 308     inline void
 309     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 310          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 311     { __x.swap(__y); }
 312
 313   template<typename _Key, typename _Tp, typename _Hash,
 314            typename _Pred, typename _Alloc>
 315     inline bool
 316     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 317                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 318     { return __x._M_equal(__y); }
 319
 320   template<typename _Key, typename _Tp, typename _Hash,
 321            typename _Pred, typename _Alloc>
 322     inline bool
 323     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 324                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 325     { return !(__x == __y); }
 326
 327
 328   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
 329   template<typename _Key, typename _Tp,
 330            typename _Hash = std::hash<_Key>,
 331            typename _Pred = std::equal_to<_Key>,
 332            typename _Alloc = std::allocator<_Key> >
 333     class unordered_multimap
 334     : public _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash,
 335                                                 _Pred, _Alloc>,
 336       public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash,
 337                                                             _Pred, _Alloc> >
 338     {
 339       typedef _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash,
 340                                                  _Pred, _Alloc> _Base;
 341       typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base;
 342
 343     public:
 344       typedef typename _Base::size_type       size_type;
 345       typedef typename _Base::hasher          hasher;
 346       typedef typename _Base::key_equal       key_equal;
 347       typedef typename _Base::allocator_type  allocator_type;
 348
 349       typedef typename _Base::key_type        key_type;
 350       typedef typename _Base::value_type      value_type;
 351
 352       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
 353                                           unordered_multimap> iterator;
 354       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
 355                                           unordered_multimap> const_iterator;
 356
 357       explicit
 358       unordered_multimap(size_type __n = 10,
 359                          const hasher& __hf = hasher(),
 360                          const key_equal& __eql = key_equal(),
 361                          const allocator_type& __a = allocator_type())
 362       : _Base(__n, __hf, __eql, __a) { }
 363
 364       template<typename _InputIterator>
 365         unordered_multimap(_InputIterator __first, _InputIterator __last,
 366                            size_type __n = 0,
 367                            const hasher& __hf = hasher(),
 368                            const key_equal& __eql = key_equal(),
 369                            const allocator_type& __a = allocator_type())
 370         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 371                                                                      __last)),
 372                 __gnu_debug::__base(__last), __n,
 373                 __hf, __eql, __a), _Safe_base() { }
 374
 375       unordered_multimap(const unordered_multimap& __x)
 376       : _Base(__x), _Safe_base() { }
 377
 378       unordered_multimap(const _Base& __x)
 379       : _Base(__x), _Safe_base() { }
 380
 381       unordered_multimap(unordered_multimap&& __x)
 382       : _Base(std::move(__x)), _Safe_base() { }
 383
 384       unordered_multimap(initializer_list<value_type> __l,
 385                          size_type __n = 0,
 386                          const hasher& __hf = hasher(),
 387                          const key_equal& __eql = key_equal(),
 388                          const allocator_type& __a = allocator_type())
 389       : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
 390
 391       unordered_multimap&
 392       operator=(const unordered_multimap& __x)
 393       {
 394         *static_cast<_Base*>(this) = __x;
 395         this->_M_invalidate_all();
 396         return *this;
 397       }
 398
 399       unordered_multimap&
 400       operator=(unordered_multimap&& __x)
 401       {
 402         // NB: DR 1204.
 403         // NB: DR 675.
 404         clear();
 405         swap(__x);
 406         return *this;
 407       }
 408
 409       unordered_multimap&
 410       operator=(initializer_list<value_type> __l)
 411       {
 412         this->clear();
 413         this->insert(__l);
 414         return *this;
 415       }
 416
 417       void
 418       swap(unordered_multimap& __x)
 419       {
 420         _Base::swap(__x);
 421         _Safe_base::_M_swap(__x);
 422       }
 423
 424       void
 425       clear()
 426       {
 427         _Base::clear();
 428         this->_M_invalidate_all();
 429       }
 430
 431       iterator
 432       begin()
 433       { return iterator(_Base::begin(), this); }
 434
 435       const_iterator
 436       begin() const
 437       { return const_iterator(_Base::begin(), this); }
 438
 439       iterator
 440       end()
 441       { return iterator(_Base::end(), this); }
 442
 443       const_iterator
 444       end() const
 445       { return const_iterator(_Base::end(), this); }
 446
 447       const_iterator
 448       cbegin() const
 449       { return const_iterator(_Base::begin(), this); }
 450
 451       const_iterator
 452       cend() const
 453       { return const_iterator(_Base::end(), this); }
 454
 455       // local versions
 456       using _Base::begin;
 457       using _Base::end;
 458       using _Base::cbegin;
 459       using _Base::cend;
 460
 461       iterator
 462       insert(const value_type& __obj)
 463       { return iterator(_Base::insert(__obj), this); }
 464
 465       iterator
 466       insert(const_iterator, const value_type& __obj)
 467       { return iterator(_Base::insert(__obj), this); }
 468
 469       template<typename _Pair, typename = typename
 470                std::enable_if<std::is_convertible<_Pair,
 471                                                   value_type>::value>::type>
 472         iterator
 473         insert(_Pair&& __obj)
 474         { return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); }
 475
 476       template<typename _Pair, typename = typename
 477                std::enable_if<std::is_convertible<_Pair,
 478                                                   value_type>::value>::type>
 479         iterator
 480         insert(const_iterator, _Pair&& __obj)
 481         { return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); }
 482
 483       void
 484       insert(std::initializer_list<value_type> __l)
 485       { _Base::insert(__l); }
 486
 487       template<typename _InputIterator>
 488         void
 489         insert(_InputIterator __first, _InputIterator __last)
 490         {
 491           __glibcxx_check_valid_range(__first, __last);
 492           _Base::insert(__gnu_debug::__base(__first),
 493                         __gnu_debug::__base(__last));
 494         }
 495
 496       iterator
 497       find(const key_type& __key)
 498       { return iterator(_Base::find(__key), this); }
 499
 500       const_iterator
 501       find(const key_type& __key) const
 502       { return const_iterator(_Base::find(__key), this); }
 503
 504       std::pair<iterator, iterator>
 505       equal_range(const key_type& __key)
 506       {
 507         typedef typename _Base::iterator _Base_iterator;
 508         typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
 509         __pair_type __res = _Base::equal_range(__key);
 510         return std::make_pair(iterator(__res.first, this),
 511                               iterator(__res.second, this));
 512       }
 513
 514       std::pair<const_iterator, const_iterator>
 515       equal_range(const key_type& __key) const
 516       {
 517         typedef typename _Base::const_iterator _Base_iterator;
 518         typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
 519         __pair_type __res = _Base::equal_range(__key);
 520         return std::make_pair(const_iterator(__res.first, this),
 521                               const_iterator(__res.second, this));
 522       }
 523
 524       size_type
 525       erase(const key_type& __key)
 526       {
 527         size_type __ret(0);
 528         iterator __victim(_Base::find(__key), this);
 529         if (__victim != end())
 530           {
 531             this->erase(__victim);
 532             __ret = 1;
 533           }
 534         return __ret;
 535       }
 536
 537       iterator
 538       erase(const_iterator __it)
 539       {
 540         __glibcxx_check_erase(__it);
 541         __it._M_invalidate();
 542         return iterator(_Base::erase(__it.base()), this);
 543       }
 544
 545       iterator
 546       erase(const_iterator __first, const_iterator __last)
 547       {
 548         __glibcxx_check_erase_range(__first, __last);
 549         for (const_iterator __tmp = __first; __tmp != __last;)
 550         {
 551           const_iterator __victim = __tmp++;
 552           __victim._M_invalidate();
 553         }
 554         return iterator(_Base::erase(__first.base(),
 555                                      __last.base()), this);
 556       }
 557
 558       _Base&
 559       _M_base() { return *this; }
 560
 561       const _Base&
 562       _M_base() const { return *this; }
 563
 564     private:
 565       void
 566       _M_invalidate_all()
 567       {
 568         typedef typename _Base::const_iterator _Base_const_iterator;
 569         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 570         this->_M_invalidate_if(_Not_equal(_M_base().end()));
 571       }
 572     };
 573
 574   template<typename _Key, typename _Tp, typename _Hash,
 575            typename _Pred, typename _Alloc>
 576     inline void
 577     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 578          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 579     { __x.swap(__y); }
 580
 581   template<typename _Key, typename _Tp, typename _Hash,
 582            typename _Pred, typename _Alloc>
 583     inline bool
 584     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 585                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 586     { return __x._M_equal(__y); }
 587
 588   template<typename _Key, typename _Tp, typename _Hash,
 589            typename _Pred, typename _Alloc>
 590     inline bool
 591     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 592                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 593     { return !(__x == __y); }
 594
 595 } // namespace __debug
 596 } // namespace std
 597
 598 #endif // __GXX_EXPERIMENTAL_CXX0X__
 599
 600 #endif