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
37namespace std _GLIBCXX_VISIBILITY(default)
38{
39namespace __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_C::set<_Key,_Compare,_Allocator>,
46      public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
47    {
48      typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base;
49      typedef __gnu_debug::_Safe_sequence<set> _Safe_base;
50
51      typedef typename _Base::const_iterator _Base_const_iterator;
52      typedef typename _Base::iterator _Base_iterator;
53      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
54    public:
55      // types:
56      typedef _Key				    key_type;
57      typedef _Key				    value_type;
58      typedef _Compare				    key_compare;
59      typedef _Compare				    value_compare;
60      typedef _Allocator			    allocator_type;
61      typedef typename _Base::reference             reference;
62      typedef typename _Base::const_reference       const_reference;
63
64      typedef __gnu_debug::_Safe_iterator<_Base_iterator, set>
65                                                    iterator;
66      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set>
67                                                    const_iterator;
68
69      typedef typename _Base::size_type             size_type;
70      typedef typename _Base::difference_type       difference_type;
71      typedef typename _Base::pointer               pointer;
72      typedef typename _Base::const_pointer         const_pointer;
73      typedef std::reverse_iterator<iterator>       reverse_iterator;
74      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
75
76      // 23.3.3.1 construct/copy/destroy:
77      explicit set(const _Compare& __comp = _Compare(),
78		   const _Allocator& __a = _Allocator())
79      : _Base(__comp, __a) { }
80
81      template<typename _InputIterator>
82        set(_InputIterator __first, _InputIterator __last,
83	    const _Compare& __comp = _Compare(),
84	    const _Allocator& __a = _Allocator())
85	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
86								     __last)),
87		__gnu_debug::__base(__last),
88		__comp, __a) { }
89
90      set(const set& __x)
91      : _Base(__x), _Safe_base() { }
92
93      set(const _Base& __x)
94      : _Base(__x), _Safe_base() { }
95
96#ifdef __GXX_EXPERIMENTAL_CXX0X__
97      set(set&& __x)
98      : _Base(std::move(__x)), _Safe_base()
99      { this->_M_swap(__x); }
100
101      set(initializer_list<value_type> __l,
102	  const _Compare& __comp = _Compare(),
103	  const allocator_type& __a = allocator_type())
104      : _Base(__l, __comp, __a), _Safe_base() { }
105#endif
106
107      ~set() { }
108
109      set&
110      operator=(const set& __x)
111      {
112	*static_cast<_Base*>(this) = __x;
113	this->_M_invalidate_all();
114	return *this;
115      }
116
117#ifdef __GXX_EXPERIMENTAL_CXX0X__
118      set&
119      operator=(set&& __x)
120      {
121	// NB: DR 1204.
122	// NB: DR 675.
123	clear();
124	swap(__x);
125	return *this;
126      }
127
128      set&
129      operator=(initializer_list<value_type> __l)
130      {
131	this->clear();
132	this->insert(__l);
133	return *this;
134      }
135#endif
136
137      using _Base::get_allocator;
138
139      // iterators:
140      iterator
141      begin()
142      { return iterator(_Base::begin(), this); }
143
144      const_iterator
145      begin() const
146      { return const_iterator(_Base::begin(), this); }
147
148      iterator
149      end()
150      { return iterator(_Base::end(), this); }
151
152      const_iterator
153      end() const
154      { return const_iterator(_Base::end(), this); }
155
156      reverse_iterator
157      rbegin()
158      { return reverse_iterator(end()); }
159
160      const_reverse_iterator
161      rbegin() const
162      { return const_reverse_iterator(end()); }
163
164      reverse_iterator
165      rend()
166      { return reverse_iterator(begin()); }
167
168      const_reverse_iterator
169      rend() const
170      { return const_reverse_iterator(begin()); }
171
172#ifdef __GXX_EXPERIMENTAL_CXX0X__
173      const_iterator
174      cbegin() const
175      { return const_iterator(_Base::begin(), this); }
176
177      const_iterator
178      cend() const
179      { return const_iterator(_Base::end(), this); }
180
181      const_reverse_iterator
182      crbegin() const
183      { return const_reverse_iterator(end()); }
184
185      const_reverse_iterator
186      crend() const
187      { return const_reverse_iterator(begin()); }
188#endif
189
190      // capacity:
191      using _Base::empty;
192      using _Base::size;
193      using _Base::max_size;
194
195      // modifiers:
196      std::pair<iterator, bool>
197      insert(const value_type& __x)
198      {
199	std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
200	return std::pair<iterator, bool>(iterator(__res.first, this),
201					 __res.second);
202      }
203
204#ifdef __GXX_EXPERIMENTAL_CXX0X__
205      std::pair<iterator, bool>
206      insert(value_type&& __x)
207      {
208	typedef typename _Base::iterator _Base_iterator;
209	std::pair<_Base_iterator, bool> __res
210	  = _Base::insert(std::move(__x));
211	return std::pair<iterator, bool>(iterator(__res.first, this),
212					 __res.second);
213      }
214#endif
215
216      iterator
217      insert(const_iterator __position, const value_type& __x)
218      {
219	__glibcxx_check_insert(__position);
220	return iterator(_Base::insert(__position.base(), __x), this);
221      }
222
223#ifdef __GXX_EXPERIMENTAL_CXX0X__
224      iterator
225      insert(const_iterator __position, value_type&& __x)
226      {
227	__glibcxx_check_insert(__position);
228	return iterator(_Base::insert(__position.base(), std::move(__x)),
229			this);
230      }
231#endif
232
233      template <typename _InputIterator>
234        void
235        insert(_InputIterator __first, _InputIterator __last)
236        {
237	  __glibcxx_check_valid_range(__first, __last);
238	  _Base::insert(__gnu_debug::__base(__first),
239			__gnu_debug::__base(__last));
240	}
241
242#ifdef __GXX_EXPERIMENTAL_CXX0X__
243      void
244      insert(initializer_list<value_type> __l)
245      { _Base::insert(__l); }
246#endif
247
248#ifdef __GXX_EXPERIMENTAL_CXX0X__
249      iterator
250      erase(const_iterator __position)
251      {
252	__glibcxx_check_erase(__position);
253	this->_M_invalidate_if(_Equal(__position.base()));
254	return iterator(_Base::erase(__position.base()), this);
255      }
256#else
257      void
258      erase(iterator __position)
259      {
260	__glibcxx_check_erase(__position);
261	this->_M_invalidate_if(_Equal(__position.base()));
262	_Base::erase(__position.base());
263      }
264#endif
265
266      size_type
267      erase(const key_type& __x)
268      {
269	_Base_iterator __victim = _Base::find(__x);
270	if (__victim == _Base::end())
271          return 0;
272	else
273	  {
274	    this->_M_invalidate_if(_Equal(__victim));
275	    _Base::erase(__victim);
276	    return 1;
277	  }
278      }
279
280#ifdef __GXX_EXPERIMENTAL_CXX0X__
281      iterator
282      erase(const_iterator __first, const_iterator __last)
283      {
284	// _GLIBCXX_RESOLVE_LIB_DEFECTS
285	// 151. can't currently clear() empty container
286	__glibcxx_check_erase_range(__first, __last);
287	for (_Base_const_iterator __victim = __first.base();
288	     __victim != __last.base(); ++__victim)
289	  {
290	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
291				  _M_message(__gnu_debug::__msg_valid_range)
292				  ._M_iterator(__first, "first")
293				  ._M_iterator(__last, "last"));
294	    this->_M_invalidate_if(_Equal(__victim));
295	  }
296	return iterator(_Base::erase(__first.base(), __last.base()), this);
297      }
298#else
299      void
300      erase(iterator __first, iterator __last)
301      {
302	// _GLIBCXX_RESOLVE_LIB_DEFECTS
303	// 151. can't currently clear() empty container
304	__glibcxx_check_erase_range(__first, __last);
305	for (_Base_iterator __victim = __first.base();
306	     __victim != __last.base(); ++__victim)
307	  {
308	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
309				  _M_message(__gnu_debug::__msg_valid_range)
310				  ._M_iterator(__first, "first")
311				  ._M_iterator(__last, "last"));
312	    this->_M_invalidate_if(_Equal(__victim));
313	  }
314	_Base::erase(__first.base(), __last.base());
315      }
316#endif
317
318      void
319      swap(set& __x)
320      {
321	_Base::swap(__x);
322	this->_M_swap(__x);
323      }
324
325      void
326      clear()
327      {
328	this->_M_invalidate_all();
329	_Base::clear();
330      }
331
332      // observers:
333      using _Base::key_comp;
334      using _Base::value_comp;
335
336      // set operations:
337      iterator
338      find(const key_type& __x)
339      { return iterator(_Base::find(__x), this); }
340
341      // _GLIBCXX_RESOLVE_LIB_DEFECTS
342      // 214. set::find() missing const overload
343      const_iterator
344      find(const key_type& __x) const
345      { return const_iterator(_Base::find(__x), this); }
346
347      using _Base::count;
348
349      iterator
350      lower_bound(const key_type& __x)
351      { return iterator(_Base::lower_bound(__x), this); }
352
353      // _GLIBCXX_RESOLVE_LIB_DEFECTS
354      // 214. set::find() missing const overload
355      const_iterator
356      lower_bound(const key_type& __x) const
357      { return const_iterator(_Base::lower_bound(__x), this); }
358
359      iterator
360      upper_bound(const key_type& __x)
361      { return iterator(_Base::upper_bound(__x), this); }
362
363      // _GLIBCXX_RESOLVE_LIB_DEFECTS
364      // 214. set::find() missing const overload
365      const_iterator
366      upper_bound(const key_type& __x) const
367      { return const_iterator(_Base::upper_bound(__x), this); }
368
369      std::pair<iterator,iterator>
370      equal_range(const key_type& __x)
371      {
372	std::pair<_Base_iterator, _Base_iterator> __res =
373        _Base::equal_range(__x);
374	return std::make_pair(iterator(__res.first, this),
375			      iterator(__res.second, this));
376      }
377
378      // _GLIBCXX_RESOLVE_LIB_DEFECTS
379      // 214. set::find() missing const overload
380      std::pair<const_iterator,const_iterator>
381      equal_range(const key_type& __x) const
382      {
383	std::pair<_Base_iterator, _Base_iterator> __res =
384        _Base::equal_range(__x);
385	return std::make_pair(const_iterator(__res.first, this),
386			      const_iterator(__res.second, this));
387      }
388
389      _Base&
390      _M_base() { return *this; }
391
392      const _Base&
393      _M_base() const { return *this; }
394
395    private:
396      void
397      _M_invalidate_all()
398      {
399	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
400	this->_M_invalidate_if(_Not_equal(_M_base().end()));
401      }
402    };
403
404  template<typename _Key, typename _Compare, typename _Allocator>
405    inline bool
406    operator==(const set<_Key, _Compare, _Allocator>& __lhs,
407	       const set<_Key, _Compare, _Allocator>& __rhs)
408    { return __lhs._M_base() == __rhs._M_base(); }
409
410  template<typename _Key, typename _Compare, typename _Allocator>
411    inline bool
412    operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
413	       const set<_Key, _Compare, _Allocator>& __rhs)
414    { return __lhs._M_base() != __rhs._M_base(); }
415
416  template<typename _Key, typename _Compare, typename _Allocator>
417    inline bool
418    operator<(const set<_Key, _Compare, _Allocator>& __lhs,
419	      const set<_Key, _Compare, _Allocator>& __rhs)
420    { return __lhs._M_base() < __rhs._M_base(); }
421
422  template<typename _Key, typename _Compare, typename _Allocator>
423    inline bool
424    operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
425	       const set<_Key, _Compare, _Allocator>& __rhs)
426    { return __lhs._M_base() <= __rhs._M_base(); }
427
428  template<typename _Key, typename _Compare, typename _Allocator>
429    inline bool
430    operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
431	       const set<_Key, _Compare, _Allocator>& __rhs)
432    { return __lhs._M_base() >= __rhs._M_base(); }
433
434  template<typename _Key, typename _Compare, typename _Allocator>
435    inline bool
436    operator>(const set<_Key, _Compare, _Allocator>& __lhs,
437	      const set<_Key, _Compare, _Allocator>& __rhs)
438    { return __lhs._M_base() > __rhs._M_base(); }
439
440  template<typename _Key, typename _Compare, typename _Allocator>
441    void
442    swap(set<_Key, _Compare, _Allocator>& __x,
443	 set<_Key, _Compare, _Allocator>& __y)
444    { return __x.swap(__y); }
445
446} // namespace __debug
447} // namespace std
448
449#endif
450