1// Debugging hash_set implementation -*- C++ -*-
2
3// Copyright (C) 2003, 2005, 2006
4// Free Software Foundation, Inc.
5//
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)
10// any later version.
11
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.
16
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,
20// USA.
21
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.
30
31/** @file debug/hash_set.h
32 *  This file is a GNU debug extension to the Standard C++ Library.
33 */
34
35#ifndef _GLIBCXX_DEBUG_HASH_SET_H
36#define _GLIBCXX_DEBUG_HASH_SET_H 1
37
38#include <debug/safe_sequence.h>
39#include <debug/safe_iterator.h>
40
41namespace __gnu_cxx
42{
43namespace __debug
44{
45  template<typename _Value,
46	   typename _HashFcn  = __gnu_cxx::hash<_Value>,
47	   typename _EqualKey = std::equal_to<_Value>,
48	   typename _Alloc =  std::allocator<_Value> >
49    class hash_set
50    : public _GLIBCXX_EXT::hash_set<_Value, _HashFcn, _EqualKey,_Alloc>,
51      public __gnu_debug::_Safe_sequence<hash_set<_Value, _HashFcn, _EqualKey,
52						  _Alloc> >
53    {
54      typedef _GLIBCXX_EXT::hash_set<_Value, _HashFcn, _EqualKey,_Alloc> _Base;
55      typedef __gnu_debug::_Safe_sequence<hash_set> _Safe_base;
56
57    public:
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;
68
69      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, hash_set>
70                                              iterator;
71      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
72					  hash_set>
73                                              const_iterator;
74
75      typedef typename _Base::allocator_type allocator_type;
76
77      using _Base::hash_funct;
78      using _Base::key_eq;
79      using _Base::get_allocator;
80
81      hash_set() { }
82
83      explicit hash_set(size_type __n) : _Base(__n) { }
84
85      hash_set(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
86
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) { }
90
91      template<typename _InputIterator>
92        hash_set(_InputIterator __f, _InputIterator __l)
93        : _Base(__gnu_debug::__check_valid_range(__f, __l), __l) { }
94
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) { }
98
99      template<typename _InputIterator>
100        hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
101		 const hasher& __hf)
102	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf) { }
103
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,
109		__eql, __a) { }
110
111      hash_set(const _Base& __x) : _Base(__x), _Safe_base() { }
112
113      using _Base::size;
114      using _Base::max_size;
115      using _Base::empty;
116
117      void
118      swap(hash_set& __x)
119      {
120	_Base::swap(__x);
121	this->_M_swap(__x);
122      }
123
124      iterator
125      begin() const { return iterator(_Base::begin(), this); }
126
127      iterator
128      end() const   { return iterator(_Base::end(),   this); }
129
130      std::pair<iterator, bool>
131      insert(const value_type& __obj)
132      {
133	std::pair<typename _Base::iterator, bool> __res =
134        _Base::insert(__obj);
135	return std::make_pair(iterator(__res.first, this), __res.second);
136      }
137
138      void
139      insert(const value_type* __first, const value_type* __last)
140      {
141	__glibcxx_check_valid_range(__first, __last);
142	_Base::insert(__first, __last);
143      }
144
145      template<typename _InputIterator>
146        void
147        insert(_InputIterator __first, _InputIterator __last)
148        {
149	  __glibcxx_check_valid_range(__first, __last);
150	  _Base::insert(__first.base(), __last.base());
151	}
152
153
154      std::pair<iterator, bool>
155      insert_noresize(const value_type& __obj)
156      {
157	std::pair<typename _Base::iterator, bool> __res =
158        _Base::insert_noresize(__obj);
159	return std::make_pair(iterator(__res.first, this), __res.second);
160      }
161
162      iterator
163      find(const key_type& __key) const
164      { return iterator(_Base::find(__key), this); }
165
166      using _Base::count;
167
168      std::pair<iterator, iterator>
169      equal_range(const key_type& __key) const
170      {
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));
176      }
177
178      size_type
179      erase(const key_type& __key)
180      {
181	iterator __victim(_Base::find(__key), this);
182	if (__victim != end())
183	  return this->erase(__victim), 1;
184	else
185	  return 0;
186      }
187
188      void
189      erase(iterator __it)
190      {
191	__glibcxx_check_erase(__it);
192	__it._M_invalidate();
193	_Base::erase(__it.base());
194      }
195
196      void
197      erase(iterator __first, iterator __last)
198      {
199	__glibcxx_check_erase_range(__first, __last);
200	for (iterator __tmp = __first; __tmp != __last;)
201	{
202	  iterator __victim = __tmp++;
203	  __victim._M_invalidate();
204	}
205	_Base::erase(__first.base(), __last.base());
206      }
207
208      void
209      clear()
210      {
211	_Base::clear();
212	this->_M_invalidate_all();
213      }
214
215      using _Base::resize;
216      using _Base::bucket_count;
217      using _Base::max_bucket_count;
218      using _Base::elems_in_bucket;
219
220      _Base&
221      _M_base()       { return *this; }
222
223      const _Base&
224      _M_base() const { return *this; }
225
226    private:
227      void
228      _M_invalidate_all()
229      {
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()));
233      }
234    };
235
236  template<typename _Value, typename _HashFcn, typename _EqualKey,
237	   typename _Alloc>
238    inline bool
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(); }
242
243  template<typename _Value, typename _HashFcn, typename _EqualKey,
244	   typename _Alloc>
245    inline bool
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(); }
249
250  template<typename _Value, typename _HashFcn, typename _EqualKey,
251	   typename _Alloc>
252    inline void
253    swap(hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __x,
254	 hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __y)
255    { __x.swap(__y); }
256} // namespace __debug
257} // namespace __gnu_cxx
258
259#endif
260