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