hash_set.h

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

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