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 __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_map(const unordered_map& __x)
  90       : _Base(__x), _Safe_base() { }
  91
  92       unordered_map(const _Base& __x)
  93       : _Base(__x), _Safe_base() { }
  94
  95       unordered_map(unordered_map&& __x)
  96       : _Base(std::forward<unordered_map>(__x)), _Safe_base() { }
  97
  98       unordered_map(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_map&
 106       operator=(const unordered_map& __x)
 107       {
 108         *static_cast<_Base*>(this) = __x;
 109         this->_M_invalidate_all();
 110         return *this;
 111       }
 112
 113       unordered_map&
 114       operator=(unordered_map&& __x)
 115       {
 116         // NB: DR 1204.
 117         // NB: DR 675.
 118         clear();
 119         swap(__x);
 120         return *this;
 121       }
 122
 123       unordered_map&
 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_map& __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 _Key, typename _Tp, typename _Hash,
 282            typename _Pred, typename _Alloc>
 283     inline void
 284     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 285          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 286     { __x.swap(__y); }
 287
 288   template<typename _Key, typename _Tp, typename _Hash,
 289            typename _Pred, typename _Alloc>
 290     inline bool
 291     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 292                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 293     { return __x._M_equal(__y); }
 294
 295   template<typename _Key, typename _Tp, typename _Hash,
 296            typename _Pred, typename _Alloc>
 297     inline bool
 298     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 299                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 300     { return !(__x == __y); }
 301
 302
 303   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
 304   template<typename _Key, typename _Tp,
 305            typename _Hash = std::hash<_Key>,
 306            typename _Pred = std::equal_to<_Key>,
 307            typename _Alloc = std::allocator<_Key> >
 308     class unordered_multimap
 309     : public _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash,
 310                                                 _Pred, _Alloc>,
 311       public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash,
 312                                                             _Pred, _Alloc> >
 313     {
 314       typedef _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash,
 315                                                  _Pred, _Alloc> _Base;
 316       typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base;
 317
 318     public:
 319       typedef typename _Base::size_type       size_type;
 320       typedef typename _Base::hasher          hasher;
 321       typedef typename _Base::key_equal       key_equal;
 322       typedef typename _Base::allocator_type  allocator_type;
 323
 324       typedef typename _Base::key_type        key_type;
 325       typedef typename _Base::value_type      value_type;
 326
 327       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
 328                                           unordered_multimap> iterator;
 329       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
 330                                           unordered_multimap> const_iterator;
 331
 332       explicit
 333       unordered_multimap(size_type __n = 10,
 334                          const hasher& __hf = hasher(),
 335                          const key_equal& __eql = key_equal(),
 336                          const allocator_type& __a = allocator_type())
 337       : _Base(__n, __hf, __eql, __a) { }
 338
 339       template<typename _InputIterator>
 340         unordered_multimap(_InputIterator __f, _InputIterator __l,
 341                            size_type __n = 10,
 342                            const hasher& __hf = hasher(),
 343                            const key_equal& __eql = key_equal(),
 344                            const allocator_type& __a = allocator_type())
 345         : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
 346                 __hf, __eql, __a), _Safe_base() { }
 347
 348       unordered_multimap(const unordered_multimap& __x)
 349       : _Base(__x), _Safe_base() { }
 350
 351       unordered_multimap(const _Base& __x)
 352       : _Base(__x), _Safe_base() { }
 353
 354       unordered_multimap(unordered_multimap&& __x)
 355       : _Base(std::forward<unordered_multimap>(__x)), _Safe_base() { }
 356
 357       unordered_multimap(initializer_list<value_type> __l,
 358                          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(__l, __n, __hf, __eql, __a), _Safe_base() { }
 363
 364       unordered_multimap&
 365       operator=(const unordered_multimap& __x)
 366       {
 367         *static_cast<_Base*>(this) = __x;
 368         this->_M_invalidate_all();
 369         return *this;
 370       }
 371
 372       unordered_multimap&
 373       operator=(unordered_multimap&& __x)
 374       {
 375         // NB: DR 1204.
 376         // NB: DR 675.
 377         clear();
 378         swap(__x);
 379         return *this;
 380       }
 381
 382       unordered_multimap&
 383       operator=(initializer_list<value_type> __l)
 384       {
 385         this->clear();
 386         this->insert(__l);
 387         return *this;
 388       }
 389
 390       void
 391       swap(unordered_multimap& __x)
 392       {
 393         _Base::swap(__x);
 394         _Safe_base::_M_swap(__x);
 395       }
 396
 397       void
 398       clear()
 399       {
 400         _Base::clear();
 401         this->_M_invalidate_all();
 402       }
 403
 404       iterator
 405       begin()
 406       { return iterator(_Base::begin(), this); }
 407
 408       const_iterator
 409       begin() const
 410       { return const_iterator(_Base::begin(), this); }
 411
 412       iterator
 413       end()
 414       { return iterator(_Base::end(), this); }
 415
 416       const_iterator
 417       end() const
 418       { return const_iterator(_Base::end(), this); }
 419
 420       const_iterator
 421       cbegin() const
 422       { return const_iterator(_Base::begin(), this); }
 423
 424       const_iterator
 425       cend() const
 426       { return const_iterator(_Base::end(), this); }
 427
 428       // local versions
 429       using _Base::begin;
 430       using _Base::end;
 431       using _Base::cbegin;
 432       using _Base::cend;
 433
 434       iterator
 435       insert(const value_type& __obj)
 436       { return iterator(_Base::insert(__obj), this); }
 437
 438       iterator
 439       insert(const_iterator, const value_type& __obj)
 440       { return iterator(_Base::insert(__obj), this); }
 441
 442       void
 443       insert(std::initializer_list<value_type> __l)
 444       { _Base::insert(__l); }
 445
 446       template<typename _InputIterator>
 447         void
 448         insert(_InputIterator __first, _InputIterator __last)
 449         {
 450           __glibcxx_check_valid_range(__first, __last);
 451           _Base::insert(__first, __last);
 452         }
 453
 454       iterator
 455       find(const key_type& __key)
 456       { return iterator(_Base::find(__key), this); }
 457
 458       const_iterator
 459       find(const key_type& __key) const
 460       { return const_iterator(_Base::find(__key), this); }
 461
 462       std::pair<iterator, iterator>
 463       equal_range(const key_type& __key)
 464       {
 465         typedef typename _Base::iterator _Base_iterator;
 466         typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
 467         __pair_type __res = _Base::equal_range(__key);
 468         return std::make_pair(iterator(__res.first, this),
 469                               iterator(__res.second, this));
 470       }
 471
 472       std::pair<const_iterator, const_iterator>
 473       equal_range(const key_type& __key) const
 474       {
 475         typedef typename _Base::const_iterator _Base_iterator;
 476         typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
 477         __pair_type __res = _Base::equal_range(__key);
 478         return std::make_pair(const_iterator(__res.first, this),
 479                               const_iterator(__res.second, this));
 480       }
 481
 482       size_type
 483       erase(const key_type& __key)
 484       {
 485         size_type __ret(0);
 486         iterator __victim(_Base::find(__key), this);
 487         if (__victim != end())
 488           {
 489             this->erase(__victim);
 490             __ret = 1;
 491           }
 492         return __ret;
 493       }
 494
 495       iterator
 496       erase(const_iterator __it)
 497       {
 498         __glibcxx_check_erase(__it);
 499         __it._M_invalidate();
 500         return iterator(_Base::erase(__it.base()), this);
 501       }
 502
 503       iterator
 504       erase(const_iterator __first, const_iterator __last)
 505       {
 506         __glibcxx_check_erase_range(__first, __last);
 507         for (const_iterator __tmp = __first; __tmp != __last;)
 508         {
 509           const_iterator __victim = __tmp++;
 510           __victim._M_invalidate();
 511         }
 512         return iterator(_Base::erase(__first.base(),
 513                                      __last.base()), this);
 514       }
 515
 516       _Base&
 517       _M_base() { return *this; }
 518
 519       const _Base&
 520       _M_base() const { return *this; }
 521
 522     private:
 523       void
 524       _M_invalidate_all()
 525       {
 526         typedef typename _Base::const_iterator _Base_const_iterator;
 527         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 528         this->_M_invalidate_if(_Not_equal(_M_base().end()));
 529       }
 530     };
 531
 532   template<typename _Key, typename _Tp, typename _Hash,
 533            typename _Pred, typename _Alloc>
 534     inline void
 535     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 536          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 537     { __x.swap(__y); }
 538
 539   template<typename _Key, typename _Tp, typename _Hash,
 540            typename _Pred, typename _Alloc>
 541     inline bool
 542     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 543                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 544     { return __x._M_equal(__y); }
 545
 546   template<typename _Key, typename _Tp, typename _Hash,
 547            typename _Pred, typename _Alloc>
 548     inline bool
 549     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 550                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 551     { return !(__x == __y); }
 552
 553 } // namespace __debug
 554 } // namespace std
 555
 556 #endif // __GXX_EXPERIMENTAL_CXX0X__
 557
 558 #endif