xref: /netbsd-src/external/gpl3/gcc.old/dist/libstdc++-v3/include/debug/set.h (revision b7b7574d3bf8eeb51a1fa3977b59142ec6434a55)
1 // Debugging set implementation -*- C++ -*-
2 
3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /** @file debug/set.h
27  *  This file is a GNU debug extension to the Standard C++ Library.
28  */
29 
30 #ifndef _GLIBCXX_DEBUG_SET_H
31 #define _GLIBCXX_DEBUG_SET_H 1
32 
33 #include <debug/safe_sequence.h>
34 #include <debug/safe_iterator.h>
35 #include <utility>
36 
37 namespace std
38 {
39 namespace __debug
40 {
41   /// Class std::set with safety/checking/debug instrumentation.
42   template<typename _Key, typename _Compare = std::less<_Key>,
43 	   typename _Allocator = std::allocator<_Key> >
44     class set
45     : public _GLIBCXX_STD_D::set<_Key,_Compare,_Allocator>,
46       public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
47     {
48       typedef _GLIBCXX_STD_D::set<_Key, _Compare, _Allocator> _Base;
49       typedef __gnu_debug::_Safe_sequence<set> _Safe_base;
50 
51     public:
52       // types:
53       typedef _Key				    key_type;
54       typedef _Key				    value_type;
55       typedef _Compare				    key_compare;
56       typedef _Compare				    value_compare;
57       typedef _Allocator			    allocator_type;
58       typedef typename _Base::reference             reference;
59       typedef typename _Base::const_reference       const_reference;
60 
61       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, set>
62                                                     iterator;
63       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, set>
64                                                     const_iterator;
65 
66       typedef typename _Base::size_type             size_type;
67       typedef typename _Base::difference_type       difference_type;
68       typedef typename _Base::pointer               pointer;
69       typedef typename _Base::const_pointer         const_pointer;
70       typedef std::reverse_iterator<iterator>       reverse_iterator;
71       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
72 
73       // 23.3.3.1 construct/copy/destroy:
74       explicit set(const _Compare& __comp = _Compare(),
75 		   const _Allocator& __a = _Allocator())
76       : _Base(__comp, __a) { }
77 
78       template<typename _InputIterator>
79         set(_InputIterator __first, _InputIterator __last,
80 	    const _Compare& __comp = _Compare(),
81 	    const _Allocator& __a = _Allocator())
82 	: _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
83 		__comp, __a) { }
84 
85       set(const set& __x)
86       : _Base(__x), _Safe_base() { }
87 
88       set(const _Base& __x)
89       : _Base(__x), _Safe_base() { }
90 
91 #ifdef __GXX_EXPERIMENTAL_CXX0X__
92       set(set&& __x)
93       : _Base(std::forward<set>(__x)), _Safe_base()
94       { this->_M_swap(__x); }
95 
96       set(initializer_list<value_type> __l,
97 	  const _Compare& __comp = _Compare(),
98 	  const allocator_type& __a = allocator_type())
99       : _Base(__l, __comp, __a), _Safe_base() { }
100 #endif
101 
102       ~set() { }
103 
104       set&
105       operator=(const set& __x)
106       {
107 	*static_cast<_Base*>(this) = __x;
108 	this->_M_invalidate_all();
109 	return *this;
110       }
111 
112 #ifdef __GXX_EXPERIMENTAL_CXX0X__
113       set&
114       operator=(set&& __x)
115       {
116 	// NB: DR 1204.
117 	// NB: DR 675.
118 	clear();
119 	swap(__x);
120 	return *this;
121       }
122 
123       set&
124       operator=(initializer_list<value_type> __l)
125       {
126 	this->clear();
127 	this->insert(__l);
128 	return *this;
129       }
130 #endif
131 
132       using _Base::get_allocator;
133 
134       // iterators:
135       iterator
136       begin()
137       { return iterator(_Base::begin(), this); }
138 
139       const_iterator
140       begin() const
141       { return const_iterator(_Base::begin(), this); }
142 
143       iterator
144       end()
145       { return iterator(_Base::end(), this); }
146 
147       const_iterator
148       end() const
149       { return const_iterator(_Base::end(), this); }
150 
151       reverse_iterator
152       rbegin()
153       { return reverse_iterator(end()); }
154 
155       const_reverse_iterator
156       rbegin() const
157       { return const_reverse_iterator(end()); }
158 
159       reverse_iterator
160       rend()
161       { return reverse_iterator(begin()); }
162 
163       const_reverse_iterator
164       rend() const
165       { return const_reverse_iterator(begin()); }
166 
167 #ifdef __GXX_EXPERIMENTAL_CXX0X__
168       const_iterator
169       cbegin() const
170       { return const_iterator(_Base::begin(), this); }
171 
172       const_iterator
173       cend() const
174       { return const_iterator(_Base::end(), this); }
175 
176       const_reverse_iterator
177       crbegin() const
178       { return const_reverse_iterator(end()); }
179 
180       const_reverse_iterator
181       crend() const
182       { return const_reverse_iterator(begin()); }
183 #endif
184 
185       // capacity:
186       using _Base::empty;
187       using _Base::size;
188       using _Base::max_size;
189 
190       // modifiers:
191       std::pair<iterator, bool>
192       insert(const value_type& __x)
193       {
194 	typedef typename _Base::iterator _Base_iterator;
195 	std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
196 	return std::pair<iterator, bool>(iterator(__res.first, this),
197 					 __res.second);
198       }
199 
200       iterator
201       insert(iterator __position, const value_type& __x)
202       {
203 	__glibcxx_check_insert(__position);
204 	return iterator(_Base::insert(__position.base(), __x), this);
205       }
206 
207       template <typename _InputIterator>
208         void
209         insert(_InputIterator __first, _InputIterator __last)
210         {
211 	  __glibcxx_check_valid_range(__first, __last);
212 	  _Base::insert(__first, __last);
213 	}
214 
215 #ifdef __GXX_EXPERIMENTAL_CXX0X__
216       void
217       insert(initializer_list<value_type> __l)
218       { _Base::insert(__l); }
219 #endif
220 
221 #ifdef __GXX_EXPERIMENTAL_CXX0X__
222       iterator
223       erase(iterator __position)
224       {
225 	__glibcxx_check_erase(__position);
226 	__position._M_invalidate();
227 	return iterator(_Base::erase(__position.base()), this);
228       }
229 #else
230       void
231       erase(iterator __position)
232       {
233 	__glibcxx_check_erase(__position);
234 	__position._M_invalidate();
235 	_Base::erase(__position.base());
236       }
237 #endif
238 
239       size_type
240       erase(const key_type& __x)
241       {
242 	iterator __victim = find(__x);
243 	if (__victim == end())
244           return 0;
245 	else
246         {
247 	  __victim._M_invalidate();
248 	  _Base::erase(__victim.base());
249 	  return 1;
250         }
251       }
252 
253 #ifdef __GXX_EXPERIMENTAL_CXX0X__
254       iterator
255       erase(iterator __first, iterator __last)
256       {
257 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
258 	// 151. can't currently clear() empty container
259 	__glibcxx_check_erase_range(__first, __last);
260 	while (__first != __last)
261 	  this->erase(__first++);
262 	return __last;
263       }
264 #else
265       void
266       erase(iterator __first, iterator __last)
267       {
268 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
269 	// 151. can't currently clear() empty container
270 	__glibcxx_check_erase_range(__first, __last);
271 	while (__first != __last)
272 	  this->erase(__first++);
273       }
274 #endif
275 
276       void
277       swap(set& __x)
278       {
279 	_Base::swap(__x);
280 	this->_M_swap(__x);
281       }
282 
283       void
284       clear()
285       { this->erase(begin(), end()); }
286 
287       // observers:
288       using _Base::key_comp;
289       using _Base::value_comp;
290 
291       // set operations:
292       iterator
293       find(const key_type& __x)
294       { return iterator(_Base::find(__x), this); }
295 
296       // _GLIBCXX_RESOLVE_LIB_DEFECTS
297       // 214. set::find() missing const overload
298       const_iterator
299       find(const key_type& __x) const
300       { return const_iterator(_Base::find(__x), this); }
301 
302       using _Base::count;
303 
304       iterator
305       lower_bound(const key_type& __x)
306       { return iterator(_Base::lower_bound(__x), this); }
307 
308       // _GLIBCXX_RESOLVE_LIB_DEFECTS
309       // 214. set::find() missing const overload
310       const_iterator
311       lower_bound(const key_type& __x) const
312       { return const_iterator(_Base::lower_bound(__x), this); }
313 
314       iterator
315       upper_bound(const key_type& __x)
316       { return iterator(_Base::upper_bound(__x), this); }
317 
318       // _GLIBCXX_RESOLVE_LIB_DEFECTS
319       // 214. set::find() missing const overload
320       const_iterator
321       upper_bound(const key_type& __x) const
322       { return const_iterator(_Base::upper_bound(__x), this); }
323 
324       std::pair<iterator,iterator>
325       equal_range(const key_type& __x)
326       {
327 	typedef typename _Base::iterator _Base_iterator;
328 	std::pair<_Base_iterator, _Base_iterator> __res =
329         _Base::equal_range(__x);
330 	return std::make_pair(iterator(__res.first, this),
331 			      iterator(__res.second, this));
332       }
333 
334       // _GLIBCXX_RESOLVE_LIB_DEFECTS
335       // 214. set::find() missing const overload
336       std::pair<const_iterator,const_iterator>
337       equal_range(const key_type& __x) const
338       {
339 	typedef typename _Base::const_iterator _Base_iterator;
340 	std::pair<_Base_iterator, _Base_iterator> __res =
341         _Base::equal_range(__x);
342 	return std::make_pair(const_iterator(__res.first, this),
343 			      const_iterator(__res.second, this));
344       }
345 
346       _Base&
347       _M_base() { return *this; }
348 
349       const _Base&
350       _M_base() const { return *this; }
351 
352     private:
353       void
354       _M_invalidate_all()
355       {
356 	typedef typename _Base::const_iterator _Base_const_iterator;
357 	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
358 	this->_M_invalidate_if(_Not_equal(_M_base().end()));
359       }
360     };
361 
362   template<typename _Key, typename _Compare, typename _Allocator>
363     inline bool
364     operator==(const set<_Key, _Compare, _Allocator>& __lhs,
365 	       const set<_Key, _Compare, _Allocator>& __rhs)
366     { return __lhs._M_base() == __rhs._M_base(); }
367 
368   template<typename _Key, typename _Compare, typename _Allocator>
369     inline bool
370     operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
371 	       const set<_Key, _Compare, _Allocator>& __rhs)
372     { return __lhs._M_base() != __rhs._M_base(); }
373 
374   template<typename _Key, typename _Compare, typename _Allocator>
375     inline bool
376     operator<(const set<_Key, _Compare, _Allocator>& __lhs,
377 	      const set<_Key, _Compare, _Allocator>& __rhs)
378     { return __lhs._M_base() < __rhs._M_base(); }
379 
380   template<typename _Key, typename _Compare, typename _Allocator>
381     inline bool
382     operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
383 	       const set<_Key, _Compare, _Allocator>& __rhs)
384     { return __lhs._M_base() <= __rhs._M_base(); }
385 
386   template<typename _Key, typename _Compare, typename _Allocator>
387     inline bool
388     operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
389 	       const set<_Key, _Compare, _Allocator>& __rhs)
390     { return __lhs._M_base() >= __rhs._M_base(); }
391 
392   template<typename _Key, typename _Compare, typename _Allocator>
393     inline bool
394     operator>(const set<_Key, _Compare, _Allocator>& __lhs,
395 	      const set<_Key, _Compare, _Allocator>& __rhs)
396     { return __lhs._M_base() > __rhs._M_base(); }
397 
398   template<typename _Key, typename _Compare, typename _Allocator>
399     void
400     swap(set<_Key, _Compare, _Allocator>& __x,
401 	 set<_Key, _Compare, _Allocator>& __y)
402     { return __x.swap(__y); }
403 
404 } // namespace __debug
405 } // namespace std
406 
407 #endif
408