1 // Debugging hash_set implementation -*- C++ -*-
3 // Copyright (C) 2003, 2005, 2006
4 // Free Software Foundation, Inc.
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 2, or (at your option)
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.
17 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
31 /** @file debug/hash_set.h
32 * This file is a GNU debug extension to the Standard C++ Library.
35 #ifndef _GLIBCXX_DEBUG_HASH_SET_H
36 #define _GLIBCXX_DEBUG_HASH_SET_H 1
38 #include <debug/safe_sequence.h>
39 #include <debug/safe_iterator.h>
45 template<typename _Value,
46 typename _HashFcn = __gnu_cxx::hash<_Value>,
47 typename _EqualKey = std::equal_to<_Value>,
48 typename _Alloc = std::allocator<_Value> >
50 : public _GLIBCXX_EXT::hash_set<_Value, _HashFcn, _EqualKey,_Alloc>,
51 public __gnu_debug::_Safe_sequence<hash_set<_Value, _HashFcn, _EqualKey,
54 typedef _GLIBCXX_EXT::hash_set<_Value, _HashFcn, _EqualKey,_Alloc> _Base;
55 typedef __gnu_debug::_Safe_sequence<hash_set> _Safe_base;
58 typedef typename _Base::key_type key_type;
59 typedef typename _Base::value_type value_type;
60 typedef typename _Base::hasher hasher;
61 typedef typename _Base::key_equal key_equal;
62 typedef typename _Base::size_type size_type;
63 typedef typename _Base::difference_type difference_type;
64 typedef typename _Base::pointer pointer;
65 typedef typename _Base::const_pointer const_pointer;
66 typedef typename _Base::reference reference;
67 typedef typename _Base::const_reference const_reference;
69 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, hash_set>
71 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
75 typedef typename _Base::allocator_type allocator_type;
77 using _Base::hash_funct;
79 using _Base::get_allocator;
83 explicit hash_set(size_type __n) : _Base(__n) { }
85 hash_set(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
87 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
88 const allocator_type& __a = allocator_type())
89 : _Base(__n, __hf, __eql, __a) { }
91 template<typename _InputIterator>
92 hash_set(_InputIterator __f, _InputIterator __l)
93 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l) { }
95 template<typename _InputIterator>
96 hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
97 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n) { }
99 template<typename _InputIterator>
100 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
102 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf) { }
104 template<typename _InputIterator>
105 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
106 const hasher& __hf, const key_equal& __eql,
107 const allocator_type& __a = allocator_type())
108 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf,
111 hash_set(const _Base& __x) : _Base(__x), _Safe_base() { }
114 using _Base::max_size;
125 begin() const { return iterator(_Base::begin(), this); }
128 end() const { return iterator(_Base::end(), this); }
130 std::pair<iterator, bool>
131 insert(const value_type& __obj)
133 std::pair<typename _Base::iterator, bool> __res =
134 _Base::insert(__obj);
135 return std::make_pair(iterator(__res.first, this), __res.second);
139 insert(const value_type* __first, const value_type* __last)
141 __glibcxx_check_valid_range(__first, __last);
142 _Base::insert(__first, __last);
145 template<typename _InputIterator>
147 insert(_InputIterator __first, _InputIterator __last)
149 __glibcxx_check_valid_range(__first, __last);
150 _Base::insert(__first.base(), __last.base());
154 std::pair<iterator, bool>
155 insert_noresize(const value_type& __obj)
157 std::pair<typename _Base::iterator, bool> __res =
158 _Base::insert_noresize(__obj);
159 return std::make_pair(iterator(__res.first, this), __res.second);
163 find(const key_type& __key) const
164 { return iterator(_Base::find(__key), this); }
168 std::pair<iterator, iterator>
169 equal_range(const key_type& __key) const
171 typedef typename _Base::iterator _Base_iterator;
172 std::pair<_Base_iterator, _Base_iterator> __res =
173 _Base::equal_range(__key);
174 return std::make_pair(iterator(__res.first, this),
175 iterator(__res.second, this));
179 erase(const key_type& __key)
181 iterator __victim(_Base::find(__key), this);
182 if (__victim != end())
183 return this->erase(__victim), 1;
191 __glibcxx_check_erase(__it);
192 __it._M_invalidate();
193 _Base::erase(__it.base());
197 erase(iterator __first, iterator __last)
199 __glibcxx_check_erase_range(__first, __last);
200 for (iterator __tmp = __first; __tmp != __last;)
202 iterator __victim = __tmp++;
203 __victim._M_invalidate();
205 _Base::erase(__first.base(), __last.base());
212 this->_M_invalidate_all();
216 using _Base::bucket_count;
217 using _Base::max_bucket_count;
218 using _Base::elems_in_bucket;
221 _M_base() { return *this; }
224 _M_base() const { return *this; }
230 typedef typename _Base::const_iterator _Base_const_iterator;
231 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
232 this->_M_invalidate_if(_Not_equal(_M_base().end()));
236 template<typename _Value, typename _HashFcn, typename _EqualKey,
239 operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __x,
240 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __y)
241 { return __x._M_base() == __y._M_base(); }
243 template<typename _Value, typename _HashFcn, typename _EqualKey,
246 operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __x,
247 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __y)
248 { return __x._M_base() != __y._M_base(); }
250 template<typename _Value, typename _HashFcn, typename _EqualKey,
253 swap(hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __x,
254 hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __y)
256 } // namespace __debug
257 } // namespace __gnu_cxx