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