# hash_map.h

    00001 // Debugging hash_map 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_MAP_H
    00032 #define _GLIBCXX_DEBUG_HASH_MAP_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_map
    00044     : public __gnu_cxx::hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>,
    00045       public __gnu_debug::_Safe_sequence<hash_map<_Value, _Tp, _HashFcn,
    00046                          _EqualKey, _Alloc> >
    00047     {
    00048       typedef __gnu_cxx::hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>
    00049                                 _Base;
    00050       typedef __gnu_debug::_Safe_sequence<hash_map>     _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, hash_map>
    00067                           iterator;
    00068       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
    00069                       hash_map>
    00070                           const_iterator;
    00071
    00072       typedef typename _Base::allocator_type  allocator_type;
    00073
    00074       using _Base::hash_funct;
    00075       using _Base::key_eq;
    00076       using _Base::get_allocator;
    00077
    00078       hash_map() { }
    00079
    00080       explicit hash_map(size_type __n) : _Base(__n) { }
    00081
    00082       hash_map(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
    00083
    00084       hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
    00085            const allocator_type& __a = allocator_type())
    00086       : _Base(__n, __hf, __eql, __a) { }
    00087
    00088       template<typename _InputIterator>
    00089         hash_map(_InputIterator __f, _InputIterator __l)
    00090         : _Base(__gnu_debug::__check_valid_range(__f, __l), __l) { }
    00091
    00092       template<typename _InputIterator>
    00093         hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
    00094     : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n) { }
    00095
    00096       template<typename _InputIterator>
    00097         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
    00098          const hasher& __hf)
    00099         : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf) { }
    00100
    00101       template<typename _InputIterator>
    00102         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
    00103          const hasher& __hf, const key_equal& __eql,
    00104          const allocator_type& __a = allocator_type())
    00105     : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf,
    00106         __eql, __a) { }
    00107
    00108       hash_map(const _Base& __x) : _Base(__x), _Safe_base() { }
    00109
    00110       using _Base::size;
    00111       using _Base::max_size;
    00112       using _Base::empty;
    00113
    00114       void
    00115       swap(hash_map& __x)
    00116       {
    00117     _Base::swap(__x);
    00118     this->_M_swap(__x);
    00119       }
    00120
    00121       iterator
    00122       begin() { return iterator(_Base::begin(), this); }
    00123
    00124       iterator
    00125       end() { return iterator(_Base::end(),   this); }
    00126
    00127       const_iterator
    00128       begin() const
    00129       { return const_iterator(_Base::begin(), this); }
    00130
    00131       const_iterator
    00132       end() const
    00133       { return const_iterator(_Base::end(),   this); }
    00134
    00135       std::pair<iterator, bool>
    00136       insert(const value_type& __obj)
    00137       {
    00138     std::pair<typename _Base::iterator, bool> __res = _Base::insert(__obj);
    00139     return std::make_pair(iterator(__res.first, this), __res.second);
    00140       }
    00141
    00142       template <typename _InputIterator>
    00143         void
    00144         insert(_InputIterator __first, _InputIterator __last)
    00145         {
    00146       __glibcxx_check_valid_range(__first, __last);
    00147       _Base::insert(__first.base(), __last.base());
    00148     }
    00149
    00150
    00151       std::pair<iterator, bool>
    00152       insert_noresize(const value_type& __obj)
    00153       {
    00154     std::pair<typename _Base::iterator, bool> __res =
    00155                                             _Base::insert_noresize(__obj);
    00156     return std::make_pair(iterator(__res.first, this), __res.second);
    00157       }
    00158
    00159       iterator
    00160       find(const key_type& __key)
    00161       { return iterator(_Base::find(__key), this); }
    00162
    00163       const_iterator
    00164       find(const key_type& __key) const
    00165       { return const_iterator(_Base::find(__key), this); }
    00166
    00167       using _Base::operator[];
    00168       using _Base::count;
    00169
    00170       std::pair<iterator, iterator>
    00171       equal_range(const key_type& __key)
    00172       {
    00173     typedef typename _Base::iterator _Base_iterator;
    00174     std::pair<_Base_iterator, _Base_iterator> __res =
    00175                       _Base::equal_range(__key);
    00176     return std::make_pair(iterator(__res.first, this),
    00177                   iterator(__res.second, this));
    00178       }
    00179
    00180       std::pair<const_iterator, const_iterator>
    00181       equal_range(const key_type& __key) const
    00182       {
    00183     typedef typename _Base::const_iterator _Base_iterator;
    00184     std::pair<_Base_iterator, _Base_iterator> __res =
    00185     _Base::equal_range(__key);
    00186     return std::make_pair(const_iterator(__res.first, this),
    00187                   const_iterator(__res.second, this));
    00188       }
    00189
    00190       size_type
    00191       erase(const key_type& __key)
    00192       {
    00193     iterator __victim(_Base::find(__key), this);
    00194     if (__victim != end())
    00195       return this->erase(__victim), 1;
    00196     else
    00197       return 0;
    00198       }
    00199
    00200       void
    00201       erase(iterator __it)
    00202       {
    00203     __glibcxx_check_erase(__it);
    00204     __it._M_invalidate();
    00205     _Base::erase(__it.base());
    00206       }
    00207
    00208       void
    00209       erase(iterator __first, iterator __last)
    00210       {
    00211     __glibcxx_check_erase_range(__first, __last);
    00212     for (iterator __tmp = __first; __tmp != __last;)
    00213     {
    00214       iterator __victim = __tmp++;
    00215       __victim._M_invalidate();
    00216     }
    00217     _Base::erase(__first.base(), __last.base());
    00218       }
    00219
    00220       void
    00221       clear()
    00222       {
    00223     _Base::clear();
    00224     this->_M_invalidate_all();
    00225       }
    00226
    00227       using _Base::resize;
    00228       using _Base::bucket_count;
    00229       using _Base::max_bucket_count;
    00230       using _Base::elems_in_bucket;
    00231
    00232       _Base&
    00233       _M_base()       { return *this; }
    00234
    00235       const _Base&
    00236       _M_base() const { return *this; }
    00237
    00238     private:
    00239       void
    00240       _M_invalidate_all()
    00241       {
    00242     typedef typename _Base::const_iterator _Base_const_iterator;
    00243     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
    00244     this->_M_invalidate_if(_Not_equal(_M_base().end()));
    00245       }
    00246     };
    00247
    00248   template<typename _Value, typename _Tp, typename _HashFcn,
    00249        typename _EqualKey, typename _Alloc>
    00250     inline bool
    00251     operator==(const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
    00252            const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
    00253     { return __x._M_base() == __y._M_base(); }
    00254
    00255   template<typename _Value, typename _Tp, typename _HashFcn,
    00256        typename _EqualKey, typename _Alloc>
    00257     inline bool
    00258     operator!=(const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
    00259            const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
    00260     { return __x._M_base() != __y._M_base(); }
    00261
    00262   template<typename _Value, typename _Tp, typename _HashFcn,
    00263        typename _EqualKey, typename _Alloc>
    00264     inline void
    00265     swap(hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
    00266      hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
    00267     { __x.swap(__y); }
    00268 } // namespace __gnu_debug_def
    00269
    00270 #endif