hash_map.h

Go to the documentation of this file.
00001 // Debugging hash_map implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2005, 2006
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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
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 /** @file debug/hash_map.h
00032  *  This file is a GNU debug extension to the Standard C++ Library.
00033  */
00034 
00035 #ifndef _GLIBCXX_DEBUG_HASH_MAP_H
00036 #define _GLIBCXX_DEBUG_HASH_MAP_H 1
00037 
00038 #include <debug/safe_sequence.h>
00039 #include <debug/safe_iterator.h>
00040 
00041 namespace __gnu_cxx
00042 {
00043 namespace __debug
00044 {
00045   template<typename _Value, typename _Tp,
00046        typename _HashFcn  = __gnu_cxx::hash<_Value>,
00047        typename _EqualKey = std::equal_to<_Value>,
00048        typename _Alloc = std::allocator<_Value> >
00049     class hash_map
00050     : public _GLIBCXX_EXT::hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>,
00051       public __gnu_debug::_Safe_sequence<hash_map<_Value, _Tp, _HashFcn,
00052                          _EqualKey, _Alloc> >
00053     {
00054       typedef _GLIBCXX_EXT::hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>
00055                                 _Base;
00056       typedef __gnu_debug::_Safe_sequence<hash_map>     _Safe_base;
00057 
00058     public:
00059       typedef typename _Base::key_type        key_type;
00060       typedef typename _Base::data_type       data_type;
00061       typedef typename _Base::mapped_type     mapped_type;
00062       typedef typename _Base::value_type      value_type;
00063       typedef typename _Base::hasher          hasher;
00064       typedef typename _Base::key_equal       key_equal;
00065       typedef typename _Base::size_type       size_type;
00066       typedef typename _Base::difference_type difference_type;
00067       typedef typename _Base::pointer         pointer;
00068       typedef typename _Base::const_pointer   const_pointer;
00069       typedef typename _Base::reference       reference;
00070       typedef typename _Base::const_reference const_reference;
00071 
00072       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, hash_map>
00073                           iterator;
00074       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
00075                       hash_map>
00076                           const_iterator;
00077 
00078       typedef typename _Base::allocator_type  allocator_type;
00079 
00080       using _Base::hash_funct;
00081       using _Base::key_eq;
00082       using _Base::get_allocator;
00083 
00084       hash_map() { }
00085 
00086       explicit hash_map(size_type __n) : _Base(__n) { }
00087 
00088       hash_map(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
00089 
00090       hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
00091            const allocator_type& __a = allocator_type())
00092       : _Base(__n, __hf, __eql, __a) { }
00093 
00094       template<typename _InputIterator>
00095         hash_map(_InputIterator __f, _InputIterator __l)
00096         : _Base(__gnu_debug::__check_valid_range(__f, __l), __l) { }
00097 
00098       template<typename _InputIterator>
00099         hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
00100     : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n) { }
00101 
00102       template<typename _InputIterator>
00103         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
00104          const hasher& __hf)
00105         : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf) { }
00106 
00107       template<typename _InputIterator>
00108         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
00109          const hasher& __hf, const key_equal& __eql,
00110          const allocator_type& __a = allocator_type())
00111     : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf,
00112         __eql, __a) { }
00113 
00114       hash_map(const _Base& __x) : _Base(__x), _Safe_base() { }
00115 
00116       using _Base::size;
00117       using _Base::max_size;
00118       using _Base::empty;
00119 
00120       void
00121       swap(hash_map& __x)
00122       {
00123     _Base::swap(__x);
00124     this->_M_swap(__x);
00125       }
00126 
00127       iterator
00128       begin() { return iterator(_Base::begin(), this); }
00129 
00130       iterator
00131       end() { return iterator(_Base::end(),   this); }
00132 
00133       const_iterator
00134       begin() const
00135       { return const_iterator(_Base::begin(), this); }
00136 
00137       const_iterator
00138       end() const
00139       { return const_iterator(_Base::end(),   this); }
00140 
00141       std::pair<iterator, bool>
00142       insert(const value_type& __obj)
00143       {
00144     std::pair<typename _Base::iterator, bool> __res = _Base::insert(__obj);
00145     return std::make_pair(iterator(__res.first, this), __res.second);
00146       }
00147 
00148       void
00149       insert(const value_type* __first, const value_type* __last)
00150       {
00151     __glibcxx_check_valid_range(__first, __last);
00152     _Base::insert(__first, __last);
00153       }
00154 
00155      template<typename _InputIterator>
00156         void
00157         insert(_InputIterator __first, _InputIterator __last)
00158         {
00159       __glibcxx_check_valid_range(__first, __last);
00160       _Base::insert(__first.base(), __last.base());
00161     }
00162 
00163 
00164       std::pair<iterator, bool>
00165       insert_noresize(const value_type& __obj)
00166       {
00167     std::pair<typename _Base::iterator, bool> __res =
00168                                             _Base::insert_noresize(__obj);
00169     return std::make_pair(iterator(__res.first, this), __res.second);
00170       }
00171 
00172       iterator
00173       find(const key_type& __key)
00174       { return iterator(_Base::find(__key), this); }
00175 
00176       const_iterator
00177       find(const key_type& __key) const
00178       { return const_iterator(_Base::find(__key), this); }
00179 
00180       using _Base::operator[];
00181       using _Base::count;
00182 
00183       std::pair<iterator, iterator>
00184       equal_range(const key_type& __key)
00185       {
00186     typedef typename _Base::iterator _Base_iterator;
00187     std::pair<_Base_iterator, _Base_iterator> __res =
00188                       _Base::equal_range(__key);
00189     return std::make_pair(iterator(__res.first, this),
00190                   iterator(__res.second, this));
00191       }
00192 
00193       std::pair<const_iterator, const_iterator>
00194       equal_range(const key_type& __key) const
00195       {
00196     typedef typename _Base::const_iterator _Base_iterator;
00197     std::pair<_Base_iterator, _Base_iterator> __res =
00198     _Base::equal_range(__key);
00199     return std::make_pair(const_iterator(__res.first, this),
00200                   const_iterator(__res.second, this));
00201       }
00202 
00203       size_type
00204       erase(const key_type& __key)
00205       {
00206     iterator __victim(_Base::find(__key), this);
00207     if (__victim != end())
00208       return this->erase(__victim), 1;
00209     else
00210       return 0;
00211       }
00212 
00213       void
00214       erase(iterator __it)
00215       {
00216     __glibcxx_check_erase(__it);
00217     __it._M_invalidate();
00218     _Base::erase(__it.base());
00219       }
00220 
00221       void
00222       erase(iterator __first, iterator __last)
00223       {
00224     __glibcxx_check_erase_range(__first, __last);
00225     for (iterator __tmp = __first; __tmp != __last;)
00226     {
00227       iterator __victim = __tmp++;
00228       __victim._M_invalidate();
00229     }
00230     _Base::erase(__first.base(), __last.base());
00231       }
00232 
00233       void
00234       clear()
00235       {
00236     _Base::clear();
00237     this->_M_invalidate_all();
00238       }
00239 
00240       using _Base::resize;
00241       using _Base::bucket_count;
00242       using _Base::max_bucket_count;
00243       using _Base::elems_in_bucket;
00244 
00245       _Base&
00246       _M_base()       { return *this; }
00247 
00248       const _Base&
00249       _M_base() const { return *this; }
00250 
00251     private:
00252       void
00253       _M_invalidate_all()
00254       {
00255     typedef typename _Base::const_iterator _Base_const_iterator;
00256     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00257     this->_M_invalidate_if(_Not_equal(_M_base().end()));
00258       }
00259     };
00260 
00261   template<typename _Value, typename _Tp, typename _HashFcn,
00262        typename _EqualKey, typename _Alloc>
00263     inline bool
00264     operator==(const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
00265            const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
00266     { return __x._M_base() == __y._M_base(); }
00267 
00268   template<typename _Value, typename _Tp, typename _HashFcn,
00269        typename _EqualKey, typename _Alloc>
00270     inline bool
00271     operator!=(const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
00272            const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
00273     { return __x._M_base() != __y._M_base(); }
00274 
00275   template<typename _Value, typename _Tp, typename _HashFcn,
00276        typename _EqualKey, typename _Alloc>
00277     inline void
00278     swap(hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
00279      hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
00280     { __x.swap(__y); }
00281 } // namespace __debug
00282 } // namespace __gnu_cxx
00283 
00284 #endif

Generated on Thu Nov 1 13:11:38 2007 for libstdc++ by  doxygen 1.5.1