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       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()
 145       {
 146         _Base::clear();
 147         this->_M_invalidate_all();
 148       }
 149
 150       iterator
 151       begin()
 152       { return iterator(_Base::begin(), this); }
 153
 154       const_iterator
 155       begin() const
 156       { return const_iterator(_Base::begin(), this); }
 157
 158       iterator
 159       end()
 160       { return iterator(_Base::end(), this); }
 161
 162       const_iterator
 163       end() const
 164       { return const_iterator(_Base::end(), this); }
 165
 166       const_iterator
 167       cbegin() const
 168       { return const_iterator(_Base::begin(), this); }
 169
 170       const_iterator
 171       cend() const
 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, const value_type& __obj)
 189       {
 190         return iterator(_Base::insert(__obj).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           std::pair<_Base_iterator, bool> __res =
 200             _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           return iterator(_Base::insert(std::forward<_Pair>(__obj)).first,
 211                           this);
 212         }
 213
 214       void
 215       insert(std::initializer_list<value_type> __l)
 216       { _Base::insert(__l); }
 217
 218       template<typename _InputIterator>
 219         void
 220         insert(_InputIterator __first, _InputIterator __last)
 221         {
 222           __glibcxx_check_valid_range(__first, __last);
 223           _Base::insert(__gnu_debug::__base(__first),
 224                         __gnu_debug::__base(__last));
 225         }
 226
 227       iterator
 228       find(const key_type& __key)
 229       { return iterator(_Base::find(__key), this); }
 230
 231       const_iterator
 232       find(const key_type& __key) const
 233       { return const_iterator(_Base::find(__key), this); }
 234
 235       std::pair<iterator, iterator>
 236       equal_range(const key_type& __key)
 237       {
 238         std::pair<_Base_iterator, _Base_iterator> __res =
 239           _Base::equal_range(__key);
 240         return std::make_pair(iterator(__res.first, this),
 241                               iterator(__res.second, this));
 242       }
 243
 244       std::pair<const_iterator, const_iterator>
 245       equal_range(const key_type& __key) const
 246       {
 247         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 248           _Base::equal_range(__key);
 249         return std::make_pair(const_iterator(__res.first, this),
 250                               const_iterator(__res.second, this));
 251       }
 252
 253       size_type
 254       erase(const key_type& __key)
 255       {
 256         size_type __ret(0);
 257         _Base_iterator __victim(_Base::find(__key));
 258         if (__victim != _Base::end())
 259           {
 260             this->_M_invalidate_if(_Equal(__victim));
 261             _Base::erase(__victim);
 262             __ret = 1;
 263           }
 264         return __ret;
 265       }
 266
 267       iterator
 268       erase(const_iterator __it)
 269       {
 270         __glibcxx_check_erase(__it);
 271         this->_M_invalidate_if(_Equal(__it.base()));
 272         return iterator(_Base::erase(__it.base()), this);
 273       }
 274
 275       iterator
 276       erase(const_iterator __first, const_iterator __last)
 277       {
 278         __glibcxx_check_erase_range(__first, __last);
 279         for (_Base_const_iterator __tmp = __first.base();
 280              __tmp != __last.base(); ++__tmp)
 281           {
 282             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 283                                   _M_message(__gnu_debug::__msg_valid_range)
 284                                   ._M_iterator(__first, "first")
 285                                   ._M_iterator(__last, "last"));
 286             this->_M_invalidate_if(_Equal(__tmp));
 287           }
 288         return iterator(_Base::erase(__first.base(),
 289                                      __last.base()), this);
 290       }
 291
 292       _Base&
 293       _M_base() { return *this; }
 294
 295       const _Base&
 296       _M_base() const { return *this; }
 297
 298     private:
 299       void
 300       _M_invalidate_all()
 301       {
 302         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 303         this->_M_invalidate_if(_Not_equal(_Base::end()));
 304       }
 305     };
 306
 307   template<typename _Key, typename _Tp, typename _Hash,
 308            typename _Pred, typename _Alloc>
 309     inline void
 310     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 311          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 312     { __x.swap(__y); }
 313
 314   template<typename _Key, typename _Tp, typename _Hash,
 315            typename _Pred, typename _Alloc>
 316     inline bool
 317     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 318                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 319     { return __x._M_equal(__y); }
 320
 321   template<typename _Key, typename _Tp, typename _Hash,
 322            typename _Pred, typename _Alloc>
 323     inline bool
 324     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 325                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 326     { return !(__x == __y); }
 327
 328
 329   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
 330   template<typename _Key, typename _Tp,
 331            typename _Hash = std::hash<_Key>,
 332            typename _Pred = std::equal_to<_Key>,
 333            typename _Alloc = std::allocator<_Key> >
 334     class unordered_multimap
 335     : public _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash,
 336                                                 _Pred, _Alloc>,
 337       public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash,
 338                                                             _Pred, _Alloc> >
 339     {
 340       typedef _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash,
 341                                                  _Pred, _Alloc> _Base;
 342       typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base;
 343       typedef typename _Base::const_iterator _Base_const_iterator;
 344       typedef typename _Base::iterator _Base_iterator;
 345       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 346
 347     public:
 348       typedef typename _Base::size_type       size_type;
 349       typedef typename _Base::hasher          hasher;
 350       typedef typename _Base::key_equal       key_equal;
 351       typedef typename _Base::allocator_type  allocator_type;
 352
 353       typedef typename _Base::key_type        key_type;
 354       typedef typename _Base::value_type      value_type;
 355
 356       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
 357                                           unordered_multimap> iterator;
 358       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
 359                                           unordered_multimap> const_iterator;
 360
 361       explicit
 362       unordered_multimap(size_type __n = 10,
 363                          const hasher& __hf = hasher(),
 364                          const key_equal& __eql = key_equal(),
 365                          const allocator_type& __a = allocator_type())
 366       : _Base(__n, __hf, __eql, __a) { }
 367
 368       template<typename _InputIterator>
 369         unordered_multimap(_InputIterator __first, _InputIterator __last,
 370                            size_type __n = 0,
 371                            const hasher& __hf = hasher(),
 372                            const key_equal& __eql = key_equal(),
 373                            const allocator_type& __a = allocator_type())
 374         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 375                                                                      __last)),
 376                 __gnu_debug::__base(__last), __n,
 377                 __hf, __eql, __a), _Safe_base() { }
 378
 379       unordered_multimap(const unordered_multimap& __x)
 380       : _Base(__x), _Safe_base() { }
 381
 382       unordered_multimap(const _Base& __x)
 383       : _Base(__x), _Safe_base() { }
 384
 385       unordered_multimap(unordered_multimap&& __x)
 386       : _Base(std::move(__x)), _Safe_base() { }
 387
 388       unordered_multimap(initializer_list<value_type> __l,
 389                          size_type __n = 0,
 390                          const hasher& __hf = hasher(),
 391                          const key_equal& __eql = key_equal(),
 392                          const allocator_type& __a = allocator_type())
 393       : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
 394
 395       unordered_multimap&
 396       operator=(const unordered_multimap& __x)
 397       {
 398         *static_cast<_Base*>(this) = __x;
 399         this->_M_invalidate_all();
 400         return *this;
 401       }
 402
 403       unordered_multimap&
 404       operator=(unordered_multimap&& __x)
 405       {
 406         // NB: DR 1204.
 407         // NB: DR 675.
 408         clear();
 409         swap(__x);
 410         return *this;
 411       }
 412
 413       unordered_multimap&
 414       operator=(initializer_list<value_type> __l)
 415       {
 416         this->clear();
 417         this->insert(__l);
 418         return *this;
 419       }
 420
 421       void
 422       swap(unordered_multimap& __x)
 423       {
 424         _Base::swap(__x);
 425         _Safe_base::_M_swap(__x);
 426       }
 427
 428       void
 429       clear()
 430       {
 431         _Base::clear();
 432         this->_M_invalidate_all();
 433       }
 434
 435       iterator
 436       begin()
 437       { return iterator(_Base::begin(), this); }
 438
 439       const_iterator
 440       begin() const
 441       { return const_iterator(_Base::begin(), this); }
 442
 443       iterator
 444       end()
 445       { return iterator(_Base::end(), this); }
 446
 447       const_iterator
 448       end() const
 449       { return const_iterator(_Base::end(), this); }
 450
 451       const_iterator
 452       cbegin() const
 453       { return const_iterator(_Base::begin(), this); }
 454
 455       const_iterator
 456       cend() const
 457       { return const_iterator(_Base::end(), this); }
 458
 459       // local versions
 460       using _Base::begin;
 461       using _Base::end;
 462       using _Base::cbegin;
 463       using _Base::cend;
 464
 465       iterator
 466       insert(const value_type& __obj)
 467       { return iterator(_Base::insert(__obj), this); }
 468
 469       iterator
 470       insert(const_iterator, const value_type& __obj)
 471       { return iterator(_Base::insert(__obj), this); }
 472
 473       template<typename _Pair, typename = typename
 474                std::enable_if<std::is_convertible<_Pair,
 475                                                   value_type>::value>::type>
 476         iterator
 477         insert(_Pair&& __obj)
 478         { return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); }
 479
 480       template<typename _Pair, typename = typename
 481                std::enable_if<std::is_convertible<_Pair,
 482                                                   value_type>::value>::type>
 483         iterator
 484         insert(const_iterator, _Pair&& __obj)
 485         { return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); }
 486
 487       void
 488       insert(std::initializer_list<value_type> __l)
 489       { _Base::insert(__l); }
 490
 491       template<typename _InputIterator>
 492         void
 493         insert(_InputIterator __first, _InputIterator __last)
 494         {
 495           __glibcxx_check_valid_range(__first, __last);
 496           _Base::insert(__gnu_debug::__base(__first),
 497                         __gnu_debug::__base(__last));
 498         }
 499
 500       iterator
 501       find(const key_type& __key)
 502       { return iterator(_Base::find(__key), this); }
 503
 504       const_iterator
 505       find(const key_type& __key) const
 506       { return const_iterator(_Base::find(__key), this); }
 507
 508       std::pair<iterator, iterator>
 509       equal_range(const key_type& __key)
 510       {
 511         std::pair<_Base_iterator, _Base_iterator> __res =
 512           _Base::equal_range(__key);
 513         return std::make_pair(iterator(__res.first, this),
 514                               iterator(__res.second, this));
 515       }
 516
 517       std::pair<const_iterator, const_iterator>
 518       equal_range(const key_type& __key) const
 519       {
 520         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 521           _Base::equal_range(__key);
 522         return std::make_pair(const_iterator(__res.first, this),
 523                               const_iterator(__res.second, this));
 524       }
 525
 526       size_type
 527       erase(const key_type& __key)
 528       {
 529         size_type __ret(0);
 530         _Base_iterator __victim(_Base::find(__key));
 531         if (__victim != _Base::end())
 532           {
 533             this->_M_invalidate_if(_Equal(__victim));
 534             _Base::erase(__victim);
 535             __ret = 1;
 536           }
 537         return __ret;
 538       }
 539
 540       iterator
 541       erase(const_iterator __it)
 542       {
 543         __glibcxx_check_erase(__it);
 544         this->_M_invalidate_if(_Equal(__it.base()));
 545         return iterator(_Base::erase(__it.base()), this);
 546       }
 547
 548       iterator
 549       erase(const_iterator __first, const_iterator __last)
 550       {
 551         __glibcxx_check_erase_range(__first, __last);
 552         for (_Base_const_iterator __tmp = __first.base();
 553              __tmp != __last.base(); ++__tmp)
 554           {
 555             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 556                                   _M_message(__gnu_debug::__msg_valid_range)
 557                                   ._M_iterator(__first, "first")
 558                                   ._M_iterator(__last, "last"));
 559             this->_M_invalidate_if(_Equal(__tmp));
 560           }
 561         return iterator(_Base::erase(__first.base(),
 562                                      __last.base()), this);
 563       }
 564
 565       _Base&
 566       _M_base() { return *this; }
 567
 568       const _Base&
 569       _M_base() const { return *this; }
 570
 571     private:
 572       void
 573       _M_invalidate_all()
 574       {
 575         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 576         this->_M_invalidate_if(_Not_equal(_Base::end()));
 577       }
 578     };
 579
 580   template<typename _Key, typename _Tp, typename _Hash,
 581            typename _Pred, typename _Alloc>
 582     inline void
 583     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 584          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 585     { __x.swap(__y); }
 586
 587   template<typename _Key, typename _Tp, typename _Hash,
 588            typename _Pred, typename _Alloc>
 589     inline bool
 590     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 591                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 592     { return __x._M_equal(__y); }
 593
 594   template<typename _Key, typename _Tp, typename _Hash,
 595            typename _Pred, typename _Alloc>
 596     inline bool
 597     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 598                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 599     { return !(__x == __y); }
 600
 601 } // namespace __debug
 602 } // namespace std
 603
 604 #endif // __GXX_EXPERIMENTAL_CXX0X__
 605
 606 #endif