]>
Commit | Line | Data |
---|---|---|
e63637ea BK |
1 | // Debugging unordered_set/unordered_multiset implementation -*- C++ -*- |
2 | ||
6b592ab3 | 3 | // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 |
e63637ea BK |
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 | |
748086b7 | 9 | // Free Software Foundation; either version 3, or (at your option) |
e63637ea BK |
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 | ||
748086b7 JJ |
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/>. | |
e63637ea BK |
25 | |
26 | /** @file debug/unordered_set | |
27 | * This file is a GNU debug extension to the Standard C++ Library. | |
28 | */ | |
29 | ||
30 | #ifndef _GLIBCXX_DEBUG_UNORDERED_SET | |
31 | #define _GLIBCXX_DEBUG_UNORDERED_SET 1 | |
32 | ||
33 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ | |
34 | # include <unordered_set> | |
35 | #else | |
36 | # include <c++0x_warning.h> | |
37 | #endif | |
38 | ||
ced3cb9f | 39 | #include <debug/safe_sequence.h> |
e63637ea | 40 | #include <debug/safe_iterator.h> |
ced3cb9f | 41 | #include <initializer_list> |
e63637ea BK |
42 | |
43 | namespace std | |
44 | { | |
45 | namespace __debug | |
46 | { | |
1ceb9e06 | 47 | /// Class std::unordered_set with safety/checking/debug instrumentation. |
e63637ea | 48 | template<typename _Value, |
ced3cb9f | 49 | typename _Hash = std::hash<_Value>, |
e63637ea | 50 | typename _Pred = std::equal_to<_Value>, |
ced3cb9f | 51 | typename _Alloc = std::allocator<_Value> > |
e63637ea | 52 | class unordered_set |
ced3cb9f PC |
53 | : public _GLIBCXX_STD_D::unordered_set<_Value, _Hash, _Pred, _Alloc>, |
54 | public __gnu_debug::_Safe_sequence<unordered_set<_Value, _Hash, | |
55 | _Pred, _Alloc> > | |
e63637ea | 56 | { |
ced3cb9f PC |
57 | typedef _GLIBCXX_STD_D::unordered_set<_Value, _Hash, |
58 | _Pred, _Alloc> _Base; | |
e63637ea BK |
59 | typedef __gnu_debug::_Safe_sequence<unordered_set> _Safe_base; |
60 | ||
61 | public: | |
ced3cb9f PC |
62 | typedef typename _Base::size_type size_type; |
63 | typedef typename _Base::hasher hasher; | |
64 | typedef typename _Base::key_equal key_equal; | |
65 | typedef typename _Base::allocator_type allocator_type; | |
66 | ||
67 | typedef typename _Base::key_type key_type; | |
68 | typedef typename _Base::value_type value_type; | |
69 | ||
70 | typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, | |
71 | unordered_set> iterator; | |
72 | typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, | |
73 | unordered_set> const_iterator; | |
e63637ea BK |
74 | |
75 | explicit | |
76 | unordered_set(size_type __n = 10, | |
77 | const hasher& __hf = hasher(), | |
78 | const key_equal& __eql = key_equal(), | |
79 | const allocator_type& __a = allocator_type()) | |
ced3cb9f | 80 | : _Base(__n, __hf, __eql, __a) { } |
e63637ea BK |
81 | |
82 | template<typename _InputIterator> | |
83 | unordered_set(_InputIterator __f, _InputIterator __l, | |
84 | size_type __n = 10, | |
85 | const hasher& __hf = hasher(), | |
86 | const key_equal& __eql = key_equal(), | |
87 | const allocator_type& __a = allocator_type()) | |
ced3cb9f PC |
88 | : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, |
89 | __hf, __eql, __a), _Safe_base() { } | |
90 | ||
91 | unordered_set(const unordered_set& __x) | |
92 | : _Base(__x), _Safe_base() { } | |
93 | ||
94 | unordered_set(const _Base& __x) | |
95 | : _Base(__x), _Safe_base() { } | |
96 | ||
97 | unordered_set(unordered_set&& __x) | |
98 | : _Base(std::forward<unordered_set>(__x)), _Safe_base() { } | |
e63637ea | 99 | |
988499f4 JM |
100 | unordered_set(initializer_list<value_type> __l, |
101 | size_type __n = 10, | |
102 | const hasher& __hf = hasher(), | |
103 | const key_equal& __eql = key_equal(), | |
104 | const allocator_type& __a = allocator_type()) | |
ced3cb9f | 105 | : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { } |
e63637ea | 106 | |
ced3cb9f PC |
107 | unordered_set& |
108 | operator=(const unordered_set& __x) | |
109 | { | |
110 | *static_cast<_Base*>(this) = __x; | |
111 | this->_M_invalidate_all(); | |
112 | return *this; | |
113 | } | |
69b3331e PC |
114 | |
115 | unordered_set& | |
116 | operator=(unordered_set&& __x) | |
117 | { | |
0462fd5e PC |
118 | // NB: DR 1204. |
119 | // NB: DR 675. | |
120 | clear(); | |
121 | swap(__x); | |
69b3331e PC |
122 | return *this; |
123 | } | |
124 | ||
988499f4 JM |
125 | unordered_set& |
126 | operator=(initializer_list<value_type> __l) | |
127 | { | |
128 | this->clear(); | |
129 | this->insert(__l); | |
130 | return *this; | |
131 | } | |
132 | ||
e63637ea | 133 | void |
ff74fd13 | 134 | swap(unordered_set& __x) |
e63637ea | 135 | { |
ced3cb9f | 136 | _Base::swap(__x); |
e63637ea BK |
137 | _Safe_base::_M_swap(__x); |
138 | } | |
69b3331e PC |
139 | |
140 | void | |
141 | clear() | |
142 | { | |
143 | _Base::clear(); | |
144 | this->_M_invalidate_all(); | |
145 | } | |
146 | ||
ced3cb9f PC |
147 | iterator |
148 | begin() | |
149 | { return iterator(_Base::begin(), this); } | |
150 | ||
151 | const_iterator | |
152 | begin() const | |
153 | { return const_iterator(_Base::begin(), this); } | |
154 | ||
155 | iterator | |
156 | end() | |
157 | { return iterator(_Base::end(), this); } | |
158 | ||
159 | const_iterator | |
160 | end() const | |
161 | { return const_iterator(_Base::end(), this); } | |
162 | ||
163 | const_iterator | |
164 | cbegin() const | |
165 | { return const_iterator(_Base::begin(), this); } | |
166 | ||
167 | const_iterator | |
168 | cend() const | |
169 | { return const_iterator(_Base::end(), this); } | |
170 | ||
171 | // local versions | |
172 | using _Base::begin; | |
173 | using _Base::end; | |
174 | using _Base::cbegin; | |
175 | using _Base::cend; | |
176 | ||
177 | std::pair<iterator, bool> | |
178 | insert(const value_type& __obj) | |
179 | { | |
180 | typedef std::pair<typename _Base::iterator, bool> __pair_type; | |
181 | __pair_type __res = _Base::insert(__obj); | |
182 | return std::make_pair(iterator(__res.first, this), __res.second); | |
183 | } | |
184 | ||
185 | iterator | |
ced3cb9f PC |
186 | insert(const_iterator, const value_type& __obj) |
187 | { | |
188 | typedef std::pair<typename _Base::iterator, bool> __pair_type; | |
189 | __pair_type __res = _Base::insert(__obj); | |
3b2524b1 | 190 | return iterator(__res.first, this); |
ced3cb9f PC |
191 | } |
192 | ||
193 | void | |
194 | insert(std::initializer_list<value_type> __l) | |
195 | { _Base::insert(__l); } | |
196 | ||
197 | template<typename _InputIterator> | |
198 | void | |
199 | insert(_InputIterator __first, _InputIterator __last) | |
200 | { | |
201 | __glibcxx_check_valid_range(__first, __last); | |
202 | _Base::insert(__first, __last); | |
203 | } | |
204 | ||
205 | iterator | |
206 | find(const key_type& __key) | |
207 | { return iterator(_Base::find(__key), this); } | |
208 | ||
209 | const_iterator | |
210 | find(const key_type& __key) const | |
211 | { return const_iterator(_Base::find(__key), this); } | |
212 | ||
213 | std::pair<iterator, iterator> | |
214 | equal_range(const key_type& __key) | |
215 | { | |
216 | typedef typename _Base::iterator _Base_iterator; | |
217 | typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; | |
218 | __pair_type __res = _Base::equal_range(__key); | |
219 | return std::make_pair(iterator(__res.first, this), | |
220 | iterator(__res.second, this)); | |
221 | } | |
222 | ||
223 | std::pair<const_iterator, const_iterator> | |
224 | equal_range(const key_type& __key) const | |
225 | { | |
226 | typedef typename _Base::const_iterator _Base_iterator; | |
227 | typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; | |
228 | __pair_type __res = _Base::equal_range(__key); | |
229 | return std::make_pair(const_iterator(__res.first, this), | |
230 | const_iterator(__res.second, this)); | |
231 | } | |
232 | ||
233 | size_type | |
234 | erase(const key_type& __key) | |
235 | { | |
236 | size_type __ret(0); | |
237 | iterator __victim(_Base::find(__key), this); | |
238 | if (__victim != end()) | |
239 | { | |
240 | this->erase(__victim); | |
241 | __ret = 1; | |
242 | } | |
243 | return __ret; | |
244 | } | |
245 | ||
246 | iterator | |
ced3cb9f PC |
247 | erase(const_iterator __it) |
248 | { | |
249 | __glibcxx_check_erase(__it); | |
250 | __it._M_invalidate(); | |
3b2524b1 | 251 | return iterator(_Base::erase(__it.base()), this); |
ced3cb9f PC |
252 | } |
253 | ||
254 | iterator | |
ced3cb9f PC |
255 | erase(const_iterator __first, const_iterator __last) |
256 | { | |
257 | __glibcxx_check_erase_range(__first, __last); | |
258 | for (const_iterator __tmp = __first; __tmp != __last;) | |
259 | { | |
260 | const_iterator __victim = __tmp++; | |
261 | __victim._M_invalidate(); | |
262 | } | |
3b2524b1 PC |
263 | return iterator(_Base::erase(__first.base(), |
264 | __last.base()), this); | |
ced3cb9f PC |
265 | } |
266 | ||
267 | _Base& | |
268 | _M_base() { return *this; } | |
269 | ||
270 | const _Base& | |
271 | _M_base() const { return *this; } | |
272 | ||
69b3331e PC |
273 | private: |
274 | void | |
275 | _M_invalidate_all() | |
276 | { | |
277 | typedef typename _Base::const_iterator _Base_const_iterator; | |
278 | typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; | |
ced3cb9f | 279 | this->_M_invalidate_if(_Not_equal(_M_base().end())); |
69b3331e | 280 | } |
e63637ea BK |
281 | }; |
282 | ||
283 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> | |
69b3331e PC |
284 | inline void |
285 | swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, | |
286 | unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) | |
287 | { __x.swap(__y); } | |
e63637ea | 288 | |
e63637ea | 289 | |
1ceb9e06 | 290 | /// Class std::unordered_multiset with safety/checking/debug instrumentation. |
e63637ea | 291 | template<typename _Value, |
ced3cb9f | 292 | typename _Hash = std::hash<_Value>, |
e63637ea | 293 | typename _Pred = std::equal_to<_Value>, |
ced3cb9f | 294 | typename _Alloc = std::allocator<_Value> > |
e63637ea | 295 | class unordered_multiset |
ced3cb9f PC |
296 | : public _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, _Pred, _Alloc>, |
297 | public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash, | |
298 | _Pred, _Alloc> > | |
e63637ea | 299 | { |
ced3cb9f PC |
300 | typedef _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, |
301 | _Pred, _Alloc> _Base; | |
e63637ea BK |
302 | typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base; |
303 | ||
304 | public: | |
ced3cb9f PC |
305 | typedef typename _Base::size_type size_type; |
306 | typedef typename _Base::hasher hasher; | |
307 | typedef typename _Base::key_equal key_equal; | |
308 | typedef typename _Base::allocator_type allocator_type; | |
309 | ||
310 | typedef typename _Base::key_type key_type; | |
311 | typedef typename _Base::value_type value_type; | |
312 | ||
313 | typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, | |
314 | unordered_multiset> iterator; | |
315 | typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, | |
316 | unordered_multiset> const_iterator; | |
e63637ea BK |
317 | |
318 | explicit | |
319 | unordered_multiset(size_type __n = 10, | |
ced3cb9f PC |
320 | const hasher& __hf = hasher(), |
321 | const key_equal& __eql = key_equal(), | |
322 | const allocator_type& __a = allocator_type()) | |
323 | : _Base(__n, __hf, __eql, __a) { } | |
e63637ea BK |
324 | |
325 | template<typename _InputIterator> | |
326 | unordered_multiset(_InputIterator __f, _InputIterator __l, | |
ced3cb9f PC |
327 | size_type __n = 10, |
328 | const hasher& __hf = hasher(), | |
329 | const key_equal& __eql = key_equal(), | |
330 | const allocator_type& __a = allocator_type()) | |
331 | : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, | |
332 | __hf, __eql, __a), _Safe_base() { } | |
333 | ||
334 | unordered_multiset(const unordered_multiset& __x) | |
335 | : _Base(__x), _Safe_base() { } | |
336 | ||
337 | unordered_multiset(const _Base& __x) | |
338 | : _Base(__x), _Safe_base() { } | |
339 | ||
340 | unordered_multiset(unordered_multiset&& __x) | |
341 | : _Base(std::forward<unordered_multiset>(__x)), _Safe_base() { } | |
e63637ea | 342 | |
988499f4 JM |
343 | unordered_multiset(initializer_list<value_type> __l, |
344 | size_type __n = 10, | |
345 | const hasher& __hf = hasher(), | |
346 | const key_equal& __eql = key_equal(), | |
347 | const allocator_type& __a = allocator_type()) | |
ced3cb9f | 348 | : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { } |
e63637ea | 349 | |
ced3cb9f PC |
350 | unordered_multiset& |
351 | operator=(const unordered_multiset& __x) | |
352 | { | |
353 | *static_cast<_Base*>(this) = __x; | |
354 | this->_M_invalidate_all(); | |
355 | return *this; | |
356 | } | |
69b3331e PC |
357 | |
358 | unordered_multiset& | |
359 | operator=(unordered_multiset&& __x) | |
360 | { | |
0462fd5e | 361 | // NB: DR 1204. |
69b3331e PC |
362 | // NB: DR 675. |
363 | clear(); | |
364 | swap(__x); | |
365 | return *this; | |
366 | } | |
367 | ||
988499f4 JM |
368 | unordered_multiset& |
369 | operator=(initializer_list<value_type> __l) | |
370 | { | |
371 | this->clear(); | |
372 | this->insert(__l); | |
373 | return *this; | |
374 | } | |
375 | ||
e63637ea | 376 | void |
ff74fd13 | 377 | swap(unordered_multiset& __x) |
e63637ea | 378 | { |
ced3cb9f | 379 | _Base::swap(__x); |
e63637ea BK |
380 | _Safe_base::_M_swap(__x); |
381 | } | |
69b3331e | 382 | |
ced3cb9f | 383 | void |
69b3331e PC |
384 | clear() |
385 | { | |
386 | _Base::clear(); | |
387 | this->_M_invalidate_all(); | |
388 | } | |
389 | ||
ced3cb9f PC |
390 | iterator |
391 | begin() | |
392 | { return iterator(_Base::begin(), this); } | |
393 | ||
394 | const_iterator | |
395 | begin() const | |
396 | { return const_iterator(_Base::begin(), this); } | |
397 | ||
398 | iterator | |
399 | end() | |
400 | { return iterator(_Base::end(), this); } | |
401 | ||
402 | const_iterator | |
403 | end() const | |
404 | { return const_iterator(_Base::end(), this); } | |
405 | ||
406 | const_iterator | |
407 | cbegin() const | |
408 | { return const_iterator(_Base::begin(), this); } | |
409 | ||
410 | const_iterator | |
411 | cend() const | |
412 | { return const_iterator(_Base::end(), this); } | |
413 | ||
414 | // local versions | |
415 | using _Base::begin; | |
416 | using _Base::end; | |
417 | using _Base::cbegin; | |
418 | using _Base::cend; | |
419 | ||
420 | iterator | |
421 | insert(const value_type& __obj) | |
422 | { return iterator(_Base::insert(__obj), this); } | |
423 | ||
424 | iterator | |
ced3cb9f | 425 | insert(const_iterator, const value_type& __obj) |
3b2524b1 | 426 | { return iterator(_Base::insert(__obj), this); } |
ced3cb9f PC |
427 | |
428 | void | |
429 | insert(std::initializer_list<value_type> __l) | |
430 | { _Base::insert(__l); } | |
431 | ||
432 | template<typename _InputIterator> | |
433 | void | |
434 | insert(_InputIterator __first, _InputIterator __last) | |
435 | { | |
436 | __glibcxx_check_valid_range(__first, __last); | |
437 | _Base::insert(__first, __last); | |
438 | } | |
439 | ||
440 | iterator | |
441 | find(const key_type& __key) | |
442 | { return iterator(_Base::find(__key), this); } | |
443 | ||
444 | const_iterator | |
445 | find(const key_type& __key) const | |
446 | { return const_iterator(_Base::find(__key), this); } | |
447 | ||
448 | std::pair<iterator, iterator> | |
449 | equal_range(const key_type& __key) | |
450 | { | |
451 | typedef typename _Base::iterator _Base_iterator; | |
452 | typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; | |
453 | __pair_type __res = _Base::equal_range(__key); | |
454 | return std::make_pair(iterator(__res.first, this), | |
455 | iterator(__res.second, this)); | |
456 | } | |
457 | ||
458 | std::pair<const_iterator, const_iterator> | |
459 | equal_range(const key_type& __key) const | |
460 | { | |
461 | typedef typename _Base::const_iterator _Base_iterator; | |
462 | typedef std::pair<_Base_iterator, _Base_iterator> __pair_type; | |
463 | __pair_type __res = _Base::equal_range(__key); | |
464 | return std::make_pair(const_iterator(__res.first, this), | |
465 | const_iterator(__res.second, this)); | |
466 | } | |
467 | ||
468 | size_type | |
469 | erase(const key_type& __key) | |
470 | { | |
471 | size_type __ret(0); | |
472 | iterator __victim(_Base::find(__key), this); | |
473 | if (__victim != end()) | |
474 | { | |
475 | this->erase(__victim); | |
476 | __ret = 1; | |
477 | } | |
478 | return __ret; | |
479 | } | |
480 | ||
481 | iterator | |
ced3cb9f PC |
482 | erase(const_iterator __it) |
483 | { | |
484 | __glibcxx_check_erase(__it); | |
485 | __it._M_invalidate(); | |
3b2524b1 | 486 | return iterator(_Base::erase(__it.base()), this); |
ced3cb9f PC |
487 | } |
488 | ||
489 | iterator | |
ced3cb9f PC |
490 | erase(const_iterator __first, const_iterator __last) |
491 | { | |
492 | __glibcxx_check_erase_range(__first, __last); | |
493 | for (const_iterator __tmp = __first; __tmp != __last;) | |
494 | { | |
495 | const_iterator __victim = __tmp++; | |
496 | __victim._M_invalidate(); | |
497 | } | |
3b2524b1 PC |
498 | return iterator(_Base::erase(__first.base(), |
499 | __last.base()), this); | |
ced3cb9f PC |
500 | } |
501 | ||
502 | _Base& | |
503 | _M_base() { return *this; } | |
504 | ||
505 | const _Base& | |
506 | _M_base() const { return *this; } | |
507 | ||
69b3331e PC |
508 | private: |
509 | void | |
510 | _M_invalidate_all() | |
511 | { | |
512 | typedef typename _Base::const_iterator _Base_const_iterator; | |
513 | typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; | |
ced3cb9f | 514 | this->_M_invalidate_if(_Not_equal(_M_base().end())); |
69b3331e | 515 | } |
e63637ea BK |
516 | }; |
517 | ||
518 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> | |
69b3331e PC |
519 | inline void |
520 | swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, | |
521 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) | |
522 | { __x.swap(__y); } | |
e63637ea | 523 | |
e63637ea BK |
524 | } // namespace __debug |
525 | } // namespace std | |
526 | ||
e63637ea | 527 | #endif |