# hash_multimap.h

    00001 // Debugging hash_multimap implementation -*- C++ -*-
    00002
    00003 // Copyright (C) 2003
    00004 // Free Software Foundation, Inc.
    00005 //
    00006 // This file is part of the GNU ISO C++ Library.  This library is free
    00007 // software; you can redistribute it and/or modify it under the
    00008 // terms of the GNU General Public License as published by the
    00009 // Free Software Foundation; either version 2, or (at your option)
    00010 // any later version.
    00011
    00012 // This library is distributed in the hope that it will be useful,
    00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    00015 // GNU General Public License for more details.
    00016
    00017 // You should have received a copy of the GNU General Public License along
    00018 // with this library; see the file COPYING.  If not, write to the Free
    00019 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
    00020 // USA.
    00021
    00022 // As a special exception, you may use this file as part of a free software
    00023 // library without restriction.  Specifically, if other files instantiate
    00024 // templates or use macros or inline functions from this file, or you compile
    00025 // this file and link it with other files to produce an executable, this
    00026 // file does not by itself cause the resulting executable to be covered by
    00027 // the GNU General Public License.  This exception does not however
    00028 // invalidate any other reasons why the executable file might be covered by
    00029 // the GNU General Public License.
    00030
    00031 #ifndef _GLIBCXX_DEBUG_HASH_MULTIMAP_H
    00032 #define _GLIBCXX_DEBUG_HASH_MULTIMAP_H 1
    00033
    00034 #include <debug/safe_sequence.h>
    00035 #include <debug/safe_iterator.h>
    00036
    00037 namespace __gnu_debug_def
    00038 {
    00039   template<typename _Value, typename _Tp,
    00040        typename _HashFcn  = __gnu_cxx::hash<_Value>,
    00041        typename _EqualKey = std::equal_to<_Value>,
    00042        typename _Alloc =  std::allocator<_Value> >
    00043     class hash_multimap
    00044     : public __gnu_cxx::hash_multimap<_Value,_Tp,_HashFcn, _EqualKey,_Alloc>,
    00045       public __gnu_debug::_Safe_sequence<hash_multimap<_Value, _Tp, _HashFcn,
    00046                                _EqualKey, _Alloc> >
    00047     {
    00048       typedef __gnu_cxx::hash_multimap<_Value,_Tp,_HashFcn, _EqualKey,_Alloc>
    00049                             _Base;
    00050       typedef __gnu_debug::_Safe_sequence<hash_multimap> _Safe_base;
    00051
    00052   public:
    00053       typedef typename _Base::key_type          key_type;
    00054       typedef typename _Base::data_type         data_type;
    00055       typedef typename _Base::mapped_type       mapped_type;
    00056       typedef typename _Base::value_type        value_type;
    00057       typedef typename _Base::hasher            hasher;
    00058       typedef typename _Base::key_equal         key_equal;
    00059       typedef typename _Base::size_type         size_type;
    00060       typedef typename _Base::difference_type       difference_type;
    00061       typedef typename _Base::pointer           pointer;
    00062       typedef typename _Base::const_pointer     const_pointer;
    00063       typedef typename _Base::reference         reference;
    00064       typedef typename _Base::const_reference       const_reference;
    00065
    00066       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
    00067                       hash_multimap> iterator;
    00068       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
    00069                       hash_multimap> const_iterator;
    00070
    00071       typedef typename _Base::allocator_type              allocator_type;
    00072
    00073       using _Base::hash_funct;
    00074       using _Base::key_eq;
    00075       using _Base::get_allocator;
    00076
    00077       hash_multimap() { }
    00078
    00079       explicit hash_multimap(size_type __n) : _Base(__n) { }
    00080
    00081       hash_multimap(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
    00082
    00083       hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
    00084             const allocator_type& __a = allocator_type())
    00085       : _Base(__n, __hf, __eql, __a) { }
    00086
    00087       template<typename _InputIterator>
    00088         hash_multimap(_InputIterator __f, _InputIterator __l)
    00089     : _Base(__gnu_debug::__check_valid_range(__f, __l), __l) { }
    00090
    00091       template<typename _InputIterator>
    00092         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
    00093         : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n) { }
    00094
    00095       template<typename _InputIterator>
    00096         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
    00097               const hasher& __hf)
    00098     : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf) { }
    00099
    00100       template<typename _InputIterator>
    00101         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
    00102               const hasher& __hf, const key_equal& __eql,
    00103               const allocator_type& __a = allocator_type())
    00104     : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf,
    00105         __eql, __a) { }
    00106
    00107       using _Base::size;
    00108       using _Base::max_size;
    00109       using _Base::empty;
    00110
    00111       void
    00112       swap(hash_multimap& __x)
    00113       {
    00114     _Base::swap(__x);
    00115     this->_M_swap(__x);
    00116       }
    00117
    00118       iterator
    00119       begin() { return iterator(_Base::begin(), this); }
    00120
    00121       iterator
    00122       end()   { return iterator(_Base::end(),   this); }
    00123
    00124       const_iterator
    00125       begin() const
    00126       { return const_iterator(_Base::begin(), this); }
    00127
    00128       const_iterator
    00129       end() const
    00130       { return const_iterator(_Base::end(),   this); }
    00131
    00132       iterator
    00133       insert(const value_type& __obj)
    00134       { return iterator(_Base::insert(__obj), this); }
    00135
    00136       template <typename _InputIterator>
    00137         void
    00138         insert(_InputIterator __first, _InputIterator __last)
    00139         {
    00140       __glibcxx_check_valid_range(__first, __last);
    00141       _Base::insert(__first.base(), __last.base());
    00142     }
    00143
    00144       iterator
    00145       insert_noresize(const value_type& __obj)
    00146       { return iterator(_Base::insert_noresize(__obj), this); }
    00147
    00148       iterator
    00149       find(const key_type& __key)
    00150       { return iterator(_Base::find(__key), this); }
    00151
    00152       const_iterator
    00153       find(const key_type& __key) const
    00154       { return const_iterator(_Base::find(__key), this); }
    00155
    00156       using _Base::count;
    00157
    00158       std::pair<iterator, iterator>
    00159       equal_range(const key_type& __key)
    00160       {
    00161     typedef typename _Base::iterator _Base_iterator;
    00162     std::pair<_Base_iterator, _Base_iterator> __res =
    00163                                                  _Base::equal_range(__key);
    00164     return std::make_pair(iterator(__res.first, this),
    00165                   iterator(__res.second, this));
    00166       }
    00167
    00168       std::pair<const_iterator, const_iterator>
    00169       equal_range(const key_type& __key) const
    00170       {
    00171     typedef typename _Base::const_iterator _Base_iterator;
    00172     std::pair<_Base_iterator, _Base_iterator> __res =
    00173         _Base::equal_range(__key);
    00174     return std::make_pair(const_iterator(__res.first, this),
    00175                   const_iterator(__res.second, this));
    00176       }
    00177
    00178       size_type
    00179       erase(const key_type& __key)
    00180       {
    00181     std::pair<iterator, iterator> __victims = this->equal_range(__key);
    00182     size_t __num_victims = 0;
    00183     while (__victims.first != __victims.second)
    00184     {
    00185       this->erase(__victims.first++);
    00186       ++__num_victims;
    00187     }
    00188     return __num_victims;
    00189       }
    00190
    00191       void
    00192       erase(iterator __it)
    00193       {
    00194     __glibcxx_check_erase(__it);
    00195     __it._M_invalidate();
    00196     _Base::erase(__it.base());
    00197       }
    00198
    00199       void
    00200       erase(iterator __first, iterator __last)
    00201       {
    00202     __glibcxx_check_erase_range(__first, __last);
    00203     for (iterator __tmp = __first; __tmp != __last;)
    00204     {
    00205       iterator __victim = __tmp++;
    00206       __victim._M_invalidate();
    00207     }
    00208     _Base::erase(__first.base(), __last.base());
    00209       }
    00210
    00211       void
    00212       clear()
    00213       {
    00214     _Base::clear();
    00215     this->_M_invalidate_all();
    00216       }
    00217
    00218       using _Base::resize;
    00219       using _Base::bucket_count;
    00220       using _Base::max_bucket_count;
    00221       using _Base::elems_in_bucket;
    00222
    00223       _Base&
    00224       _M_base()       { return *this; }
    00225
    00226       const _Base&
    00227       _M_base() const { return *this; }
    00228
    00229     private:
    00230       void
    00231       _M_invalidate_all()
    00232       {
    00233     typedef typename _Base::const_iterator _Base_const_iterator;
    00234     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
    00235     this->_M_invalidate_if(_Not_equal(_M_base().end()));
    00236       }
    00237     };
    00238
    00239   template<typename _Value, typename _Tp, typename _HashFcn,
    00240        typename _EqualKey, typename _Alloc>
    00241     inline bool
    00242     operator==(const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __x,
    00243            const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __y)
    00244     { return __x._M_base() == __y._M_base(); }
    00245
    00246   template<typename _Value, typename _Tp, typename _HashFcn,
    00247        typename _EqualKey, typename _Alloc>
    00248     inline bool
    00249     operator!=(const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __x,
    00250            const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __y)
    00251     { return __x._M_base() != __y._M_base(); }
    00252
    00253   template<typename _Value, typename _Tp, typename _HashFcn,
    00254        typename _EqualKey, typename _Alloc>
    00255     inline void
    00256     swap(hash_multimap<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
    00257      hash_multimap<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
    00258     { __x.swap(__y); }
    00259 } // namespace __gnu_debug_def
    00260
    00261 #endif