|
111
|
1 // { dg-do compile }
|
|
|
2 // { dg-options "-fgnu-tm -O0"}
|
|
|
3
|
|
|
4 namespace std __attribute__ ((__visibility__ ("default"))) {
|
|
|
5 template<class _T1, class _T2>
|
|
|
6 struct pair
|
|
|
7 {
|
|
|
8 typedef _T1 first_type;
|
|
|
9 typedef _T2 second_type;
|
|
|
10 _T1 first;
|
|
|
11 _T2 second;
|
|
|
12 pair()
|
|
|
13 : first(), second() { }
|
|
|
14 pair(const _T1& __a, const _T2& __b)
|
|
|
15 : first(__a), second(__b) { }
|
|
|
16 };
|
|
|
17 }
|
|
|
18
|
|
|
19
|
|
|
20 typedef long int ptrdiff_t;
|
|
|
21 typedef __SIZE_TYPE__ size_t;
|
|
|
22 namespace std __attribute__ ((__visibility__ ("default"))) {
|
|
|
23 using ::ptrdiff_t;
|
|
|
24 using ::size_t;
|
|
|
25 }
|
|
|
26 namespace std __attribute__ ((__visibility__ ("default"))) {
|
|
|
27 struct input_iterator_tag { };
|
|
|
28 struct output_iterator_tag { };
|
|
|
29 struct forward_iterator_tag : public input_iterator_tag { };
|
|
|
30 struct bidirectional_iterator_tag : public forward_iterator_tag { };
|
|
|
31 struct random_access_iterator_tag : public bidirectional_iterator_tag { };
|
|
|
32 template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
|
|
|
33 typename _Pointer = _Tp*, typename _Reference = _Tp&>
|
|
|
34 struct iterator
|
|
|
35 {
|
|
|
36 typedef _Category iterator_category;
|
|
|
37 typedef _Tp value_type;
|
|
|
38 typedef _Distance difference_type;
|
|
|
39 typedef _Pointer pointer;
|
|
|
40 typedef _Reference reference;
|
|
|
41 };
|
|
|
42 template<typename _Iterator>
|
|
|
43 struct iterator_traits
|
|
|
44 {
|
|
|
45 typedef typename _Iterator::iterator_category iterator_category;
|
|
|
46 typedef typename _Iterator::value_type value_type;
|
|
|
47 typedef typename _Iterator::difference_type difference_type;
|
|
|
48 typedef typename _Iterator::pointer pointer;
|
|
|
49 typedef typename _Iterator::reference reference;
|
|
|
50 };
|
|
|
51 template<typename _Tp>
|
|
|
52 struct iterator_traits<_Tp*>
|
|
|
53 {
|
|
|
54 typedef random_access_iterator_tag iterator_category;
|
|
|
55 typedef _Tp value_type;
|
|
|
56 typedef ptrdiff_t difference_type;
|
|
|
57 typedef _Tp* pointer;
|
|
|
58 typedef _Tp& reference;
|
|
|
59 };
|
|
|
60 template<typename _Tp>
|
|
|
61 struct iterator_traits<const _Tp*>
|
|
|
62 {
|
|
|
63 typedef random_access_iterator_tag iterator_category;
|
|
|
64 typedef _Tp value_type;
|
|
|
65 typedef ptrdiff_t difference_type;
|
|
|
66 typedef const _Tp* pointer;
|
|
|
67 typedef const _Tp& reference;
|
|
|
68 };
|
|
|
69 template<typename _Iter>
|
|
|
70 inline typename iterator_traits<_Iter>::iterator_category
|
|
|
71 __iterator_category(const _Iter&)
|
|
|
72 { return typename iterator_traits<_Iter>::iterator_category(); }
|
|
|
73 }
|
|
|
74 namespace std __attribute__ ((__visibility__ ("default"))) {
|
|
|
75 template<typename _Iterator>
|
|
|
76 class reverse_iterator
|
|
|
77 : public iterator<typename iterator_traits<_Iterator>::iterator_category,
|
|
|
78 typename iterator_traits<_Iterator>::value_type,
|
|
|
79 typename iterator_traits<_Iterator>::difference_type,
|
|
|
80 typename iterator_traits<_Iterator>::pointer,
|
|
|
81 typename iterator_traits<_Iterator>::reference>
|
|
|
82 {
|
|
|
83 protected:
|
|
|
84 _Iterator current;
|
|
|
85 typedef iterator_traits<_Iterator> __traits_type;
|
|
|
86 public:
|
|
|
87 typedef _Iterator iterator_type;
|
|
|
88 typedef typename __traits_type::difference_type difference_type;
|
|
|
89 typedef typename __traits_type::pointer pointer;
|
|
|
90 typedef typename __traits_type::reference reference;
|
|
|
91 reverse_iterator() : current() { }
|
|
|
92 explicit
|
|
|
93 reverse_iterator(iterator_type __x) : current(__x) { }
|
|
|
94 reverse_iterator(const reverse_iterator& __x)
|
|
|
95 : current(__x.current) { }
|
|
|
96 template<typename _Iter>
|
|
|
97 reverse_iterator(const reverse_iterator<_Iter>& __x)
|
|
|
98 : current(__x.base()) { }
|
|
|
99 iterator_type
|
|
|
100 base() const
|
|
|
101 { return current; }
|
|
|
102 reference
|
|
|
103 operator*() const
|
|
|
104 {
|
|
|
105 _Iterator __tmp = current;
|
|
|
106 return *--__tmp;
|
|
|
107 }
|
|
|
108 pointer
|
|
|
109 operator->() const
|
|
|
110 { return &(operator*()); }
|
|
|
111 reverse_iterator&
|
|
|
112 operator++()
|
|
|
113 {
|
|
|
114 --current;
|
|
|
115 return *this;
|
|
|
116 }
|
|
|
117 reverse_iterator
|
|
|
118 operator++(int)
|
|
|
119 {
|
|
|
120 reverse_iterator __tmp = *this;
|
|
|
121 --current;
|
|
|
122 return __tmp;
|
|
|
123 }
|
|
|
124 reverse_iterator&
|
|
|
125 operator--()
|
|
|
126 {
|
|
|
127 ++current;
|
|
|
128 return *this;
|
|
|
129 }
|
|
|
130 reverse_iterator
|
|
|
131 operator--(int)
|
|
|
132 {
|
|
|
133 reverse_iterator __tmp = *this;
|
|
|
134 ++current;
|
|
|
135 return __tmp;
|
|
|
136 }
|
|
|
137 reverse_iterator
|
|
|
138 operator+(difference_type __n) const
|
|
|
139 { return reverse_iterator(current - __n); }
|
|
|
140 reverse_iterator&
|
|
|
141 operator+=(difference_type __n)
|
|
|
142 {
|
|
|
143 current -= __n;
|
|
|
144 return *this;
|
|
|
145 }
|
|
|
146 reverse_iterator
|
|
|
147 operator-(difference_type __n) const
|
|
|
148 { return reverse_iterator(current + __n); }
|
|
|
149 reverse_iterator&
|
|
|
150 operator-=(difference_type __n)
|
|
|
151 {
|
|
|
152 current += __n;
|
|
|
153 return *this;
|
|
|
154 }
|
|
|
155 reference
|
|
|
156 operator[](difference_type __n) const
|
|
|
157 { return *(*this + __n); }
|
|
|
158 };
|
|
|
159 }
|
|
|
160
|
|
|
161
|
|
|
162
|
|
|
163 extern "C++" {
|
|
|
164 namespace std
|
|
|
165 {
|
|
|
166 class exception
|
|
|
167 {
|
|
|
168 public:
|
|
|
169 exception() throw() { }
|
|
|
170 virtual ~exception() throw();
|
|
|
171 virtual const char* what() const throw();
|
|
|
172 };
|
|
|
173 class bad_exception : public exception
|
|
|
174 {
|
|
|
175 public:
|
|
|
176 bad_exception() throw() { }
|
|
|
177 virtual ~bad_exception() throw();
|
|
|
178 virtual const char* what() const throw();
|
|
|
179 };
|
|
|
180 typedef void (*terminate_handler) ();
|
|
|
181 typedef void (*unexpected_handler) ();
|
|
|
182 terminate_handler set_terminate(terminate_handler) throw();
|
|
|
183 void terminate() throw() __attribute__ ((__noreturn__));
|
|
|
184 unexpected_handler set_unexpected(unexpected_handler) throw();
|
|
|
185 void unexpected() __attribute__ ((__noreturn__));
|
|
|
186 bool uncaught_exception() throw() __attribute__ ((__pure__));
|
|
|
187 }
|
|
|
188 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
|
|
|
189 void __verbose_terminate_handler();
|
|
|
190 }
|
|
|
191 }
|
|
|
192 extern "C++" {
|
|
|
193 namespace std
|
|
|
194 {
|
|
|
195 class bad_alloc : public exception
|
|
|
196 {
|
|
|
197 public:
|
|
|
198 bad_alloc() throw() { }
|
|
|
199 virtual ~bad_alloc() throw();
|
|
|
200 virtual const char* what() const throw();
|
|
|
201 };
|
|
|
202 struct nothrow_t { };
|
|
|
203 extern const nothrow_t nothrow;
|
|
|
204 typedef void (*new_handler)();
|
|
|
205 new_handler set_new_handler(new_handler) throw();
|
|
|
206 }
|
|
|
207
|
|
|
208 void* operator new(std::size_t, const std::nothrow_t&) throw();
|
|
|
209 void* operator new[](std::size_t, const std::nothrow_t&) throw();
|
|
|
210 void operator delete(void*, const std::nothrow_t&) throw();
|
|
|
211 void operator delete[](void*, const std::nothrow_t&) throw();
|
|
|
212 inline void* operator new(std::size_t, void* __p) throw() { return __p; }
|
|
|
213 inline void* operator new[](std::size_t, void* __p) throw() { return __p; }
|
|
|
214 inline void operator delete (void*, void*) throw() { }
|
|
|
215 inline void operator delete[](void*, void*) throw() { }
|
|
|
216 }
|
|
|
217 namespace std __attribute__ ((__visibility__ ("default"))) {
|
|
|
218 void
|
|
|
219 __throw_bad_exception(void) __attribute__((__noreturn__));
|
|
|
220 __attribute__((transaction_safe))
|
|
|
221 void
|
|
|
222 __throw_bad_alloc(void) __attribute__((__noreturn__));
|
|
|
223 void
|
|
|
224 __throw_bad_cast(void) __attribute__((__noreturn__));
|
|
|
225 void
|
|
|
226 __throw_bad_typeid(void) __attribute__((__noreturn__));
|
|
|
227 void
|
|
|
228 __throw_logic_error(const char*) __attribute__((__noreturn__));
|
|
|
229 void
|
|
|
230 __throw_domain_error(const char*) __attribute__((__noreturn__));
|
|
|
231 void
|
|
|
232 __throw_invalid_argument(const char*) __attribute__((__noreturn__));
|
|
|
233 void
|
|
|
234 __throw_length_error(const char*) __attribute__((__noreturn__));
|
|
|
235 void
|
|
|
236 __throw_out_of_range(const char*) __attribute__((__noreturn__));
|
|
|
237 void
|
|
|
238 __throw_runtime_error(const char*) __attribute__((__noreturn__));
|
|
|
239 void
|
|
|
240 __throw_range_error(const char*) __attribute__((__noreturn__));
|
|
|
241 void
|
|
|
242 __throw_overflow_error(const char*) __attribute__((__noreturn__));
|
|
|
243 void
|
|
|
244 __throw_underflow_error(const char*) __attribute__((__noreturn__));
|
|
|
245 void
|
|
|
246 __throw_ios_failure(const char*) __attribute__((__noreturn__));
|
|
|
247 void
|
|
|
248 __throw_system_error(int) __attribute__((__noreturn__));
|
|
|
249 void
|
|
|
250 __throw_future_error(int) __attribute__((__noreturn__));
|
|
|
251 void
|
|
|
252 __throw_bad_function_call() __attribute__((__noreturn__));
|
|
|
253 }
|
|
|
254
|
|
|
255
|
|
|
256 namespace std __attribute__ ((__visibility__ ("default"))) {
|
|
|
257 template<typename _Tp>
|
|
|
258 inline void
|
|
|
259 swap(_Tp& __a, _Tp& __b)
|
|
|
260 {
|
|
|
261
|
|
|
262 _Tp __tmp = (__a);
|
|
|
263 __a = (__b);
|
|
|
264 __b = (__tmp);
|
|
|
265 }
|
|
|
266 template<typename _Tp, size_t _Nm>
|
|
|
267 inline void
|
|
|
268 swap(_Tp (&__a)[_Nm], _Tp (&__b)[_Nm])
|
|
|
269 {
|
|
|
270 for (size_t __n = 0; __n < _Nm; ++__n)
|
|
|
271 swap(__a[__n], __b[__n]);
|
|
|
272 }
|
|
|
273 }
|
|
|
274 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
|
|
|
275 using std::size_t;
|
|
|
276 using std::ptrdiff_t;
|
|
|
277 template<typename _Tp>
|
|
|
278 class new_allocator
|
|
|
279 {
|
|
|
280 public:
|
|
|
281 typedef size_t size_type;
|
|
|
282 typedef ptrdiff_t difference_type;
|
|
|
283 typedef _Tp* pointer;
|
|
|
284 typedef const _Tp* const_pointer;
|
|
|
285 typedef _Tp& reference;
|
|
|
286 typedef const _Tp& const_reference;
|
|
|
287 typedef _Tp value_type;
|
|
|
288 template<typename _Tp1>
|
|
|
289 struct rebind
|
|
|
290 { typedef new_allocator<_Tp1> other; };
|
|
|
291 new_allocator() throw() { }
|
|
|
292 new_allocator(const new_allocator&) throw() { }
|
|
|
293 template<typename _Tp1>
|
|
|
294 new_allocator(const new_allocator<_Tp1>&) throw() { }
|
|
|
295 ~new_allocator() throw() { }
|
|
|
296 pointer
|
|
|
297 address(reference __x) const { return &__x; }
|
|
|
298 const_pointer
|
|
|
299 address(const_reference __x) const { return &__x; }
|
|
|
300 __attribute__((transaction_safe))
|
|
|
301 pointer
|
|
|
302 allocate(size_type __n, const void* = 0)
|
|
|
303 {
|
|
|
304 if (__n > this->max_size())
|
|
|
305 std::__throw_bad_alloc();
|
|
|
306 return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
|
|
|
307 }
|
|
|
308 __attribute__((transaction_safe))
|
|
|
309 void
|
|
|
310 deallocate(pointer __p, size_type)
|
|
|
311 { ::operator delete(__p); }
|
|
|
312 size_type
|
|
|
313 max_size() const throw()
|
|
|
314 { return size_t(-1) / sizeof(_Tp); }
|
|
|
315 void
|
|
|
316 construct(pointer __p, const _Tp& __val)
|
|
|
317 { ::new((void *)__p) _Tp(__val); }
|
|
|
318 void
|
|
|
319 destroy(pointer __p) { __p->~_Tp(); }
|
|
|
320 };
|
|
|
321 template<typename _Tp>
|
|
|
322 inline bool
|
|
|
323 operator==(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
|
|
|
324 { return true; }
|
|
|
325 template<typename _Tp>
|
|
|
326 inline bool
|
|
|
327 operator!=(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
|
|
|
328 { return false; }
|
|
|
329 }
|
|
|
330 namespace std __attribute__ ((__visibility__ ("default"))) {
|
|
|
331 template<typename _Tp>
|
|
|
332 class allocator;
|
|
|
333 template<>
|
|
|
334 class allocator<void>
|
|
|
335 {
|
|
|
336 public:
|
|
|
337 typedef size_t size_type;
|
|
|
338 typedef ptrdiff_t difference_type;
|
|
|
339 typedef void* pointer;
|
|
|
340 typedef const void* const_pointer;
|
|
|
341 typedef void value_type;
|
|
|
342 template<typename _Tp1>
|
|
|
343 struct rebind
|
|
|
344 { typedef allocator<_Tp1> other; };
|
|
|
345 };
|
|
|
346 template<typename _Tp>
|
|
|
347 class allocator: public __gnu_cxx::new_allocator<_Tp>
|
|
|
348 {
|
|
|
349 public:
|
|
|
350 typedef size_t size_type;
|
|
|
351 typedef ptrdiff_t difference_type;
|
|
|
352 typedef _Tp* pointer;
|
|
|
353 typedef const _Tp* const_pointer;
|
|
|
354 typedef _Tp& reference;
|
|
|
355 typedef const _Tp& const_reference;
|
|
|
356 typedef _Tp value_type;
|
|
|
357 template<typename _Tp1>
|
|
|
358 struct rebind
|
|
|
359 { typedef allocator<_Tp1> other; };
|
|
|
360 allocator() throw() { }
|
|
|
361 allocator(const allocator& __a) throw()
|
|
|
362 : __gnu_cxx::new_allocator<_Tp>(__a) { }
|
|
|
363 template<typename _Tp1>
|
|
|
364 allocator(const allocator<_Tp1>&) throw() { }
|
|
|
365 ~allocator() throw() { }
|
|
|
366 };
|
|
|
367 template<typename _T1, typename _T2>
|
|
|
368 inline bool
|
|
|
369 operator==(const allocator<_T1>&, const allocator<_T2>&)
|
|
|
370 { return true; }
|
|
|
371 template<typename _Tp>
|
|
|
372 inline bool
|
|
|
373 operator==(const allocator<_Tp>&, const allocator<_Tp>&)
|
|
|
374 { return true; }
|
|
|
375 template<typename _T1, typename _T2>
|
|
|
376 inline bool
|
|
|
377 operator!=(const allocator<_T1>&, const allocator<_T2>&)
|
|
|
378 { return false; }
|
|
|
379 template<typename _Tp>
|
|
|
380 inline bool
|
|
|
381 operator!=(const allocator<_Tp>&, const allocator<_Tp>&)
|
|
|
382 { return false; }
|
|
|
383 //extern template class allocator<char>;
|
|
|
384 // extern template class allocator<wchar_t>;
|
|
|
385 template<typename _Alloc, bool = __is_empty(_Alloc)>
|
|
|
386 struct __alloc_swap
|
|
|
387 { static void _S_do_it(_Alloc&, _Alloc&) { } };
|
|
|
388 template<typename _Alloc>
|
|
|
389 struct __alloc_swap<_Alloc, false>
|
|
|
390 {
|
|
|
391 static void
|
|
|
392 _S_do_it(_Alloc& __one, _Alloc& __two)
|
|
|
393 {
|
|
|
394 if (__one != __two)
|
|
|
395 swap(__one, __two);
|
|
|
396 }
|
|
|
397 };
|
|
|
398 template<typename _Alloc, bool = __is_empty(_Alloc)>
|
|
|
399 struct __alloc_neq
|
|
|
400 {
|
|
|
401 static bool
|
|
|
402 _S_do_it(const _Alloc&, const _Alloc&)
|
|
|
403 { return false; }
|
|
|
404 };
|
|
|
405 template<typename _Alloc>
|
|
|
406 struct __alloc_neq<_Alloc, false>
|
|
|
407 {
|
|
|
408 static bool
|
|
|
409 _S_do_it(const _Alloc& __one, const _Alloc& __two)
|
|
|
410 { return __one != __two; }
|
|
|
411 };
|
|
|
412 }
|
|
|
413 namespace std __attribute__ ((__visibility__ ("default"))) {
|
|
|
414 template<typename _Arg, typename _Result>
|
|
|
415 struct unary_function
|
|
|
416 {
|
|
|
417 typedef _Arg argument_type;
|
|
|
418 typedef _Result result_type;
|
|
|
419 };
|
|
|
420 template<typename _Arg1, typename _Arg2, typename _Result>
|
|
|
421 struct binary_function
|
|
|
422 {
|
|
|
423 typedef _Arg1 first_argument_type;
|
|
|
424 typedef _Arg2 second_argument_type;
|
|
|
425 typedef _Result result_type;
|
|
|
426 };
|
|
|
427 template<typename _Tp>
|
|
|
428 struct equal_to : public binary_function<_Tp, _Tp, bool>
|
|
|
429 {
|
|
|
430 bool
|
|
|
431 operator()(const _Tp& __x, const _Tp& __y) const
|
|
|
432 { return __x == __y; }
|
|
|
433 };
|
|
|
434 template<typename _Tp>
|
|
|
435 struct not_equal_to : public binary_function<_Tp, _Tp, bool>
|
|
|
436 {
|
|
|
437 bool
|
|
|
438 operator()(const _Tp& __x, const _Tp& __y) const
|
|
|
439 { return __x != __y; }
|
|
|
440 };
|
|
|
441 template<typename _Tp>
|
|
|
442 struct greater : public binary_function<_Tp, _Tp, bool>
|
|
|
443 {
|
|
|
444 bool
|
|
|
445 operator()(const _Tp& __x, const _Tp& __y) const
|
|
|
446 { return __x > __y; }
|
|
|
447 };
|
|
|
448 template<typename _Tp>
|
|
|
449 struct less : public binary_function<_Tp, _Tp, bool>
|
|
|
450 {
|
|
|
451 bool
|
|
|
452 operator()(const _Tp& __x, const _Tp& __y) const
|
|
|
453 { return __x < __y; }
|
|
|
454 };
|
|
|
455 template<typename _Tp>
|
|
|
456 struct _Identity : public unary_function<_Tp,_Tp>
|
|
|
457 {
|
|
|
458 _Tp&
|
|
|
459 operator()(_Tp& __x) const
|
|
|
460 { return __x; }
|
|
|
461 const _Tp&
|
|
|
462 operator()(const _Tp& __x) const
|
|
|
463 { return __x; }
|
|
|
464 };
|
|
|
465 }
|
|
|
466 namespace std __attribute__ ((__visibility__ ("default"))) {
|
|
|
467 enum _Rb_tree_color { _S_red = false, _S_black = true };
|
|
|
468 struct _Rb_tree_node_base
|
|
|
469 {
|
|
|
470 typedef _Rb_tree_node_base* _Base_ptr;
|
|
|
471 typedef const _Rb_tree_node_base* _Const_Base_ptr;
|
|
|
472 _Rb_tree_color _M_color;
|
|
|
473 _Base_ptr _M_parent;
|
|
|
474 _Base_ptr _M_left;
|
|
|
475 _Base_ptr _M_right;
|
|
|
476 static _Base_ptr
|
|
|
477 _S_minimum(_Base_ptr __x)
|
|
|
478 {
|
|
|
479 while (__x->_M_left != 0) __x = __x->_M_left;
|
|
|
480 return __x;
|
|
|
481 }
|
|
|
482 static _Const_Base_ptr
|
|
|
483 _S_minimum(_Const_Base_ptr __x)
|
|
|
484 {
|
|
|
485 while (__x->_M_left != 0) __x = __x->_M_left;
|
|
|
486 return __x;
|
|
|
487 }
|
|
|
488 static _Base_ptr
|
|
|
489 _S_maximum(_Base_ptr __x)
|
|
|
490 {
|
|
|
491 while (__x->_M_right != 0) __x = __x->_M_right;
|
|
|
492 return __x;
|
|
|
493 }
|
|
|
494 static _Const_Base_ptr
|
|
|
495 _S_maximum(_Const_Base_ptr __x)
|
|
|
496 {
|
|
|
497 while (__x->_M_right != 0) __x = __x->_M_right;
|
|
|
498 return __x;
|
|
|
499 }
|
|
|
500 };
|
|
|
501 template<typename _Val>
|
|
|
502 struct _Rb_tree_node : public _Rb_tree_node_base
|
|
|
503 {
|
|
|
504 typedef _Rb_tree_node<_Val>* _Link_type;
|
|
|
505 _Val _M_value_field;
|
|
|
506 };
|
|
|
507 __attribute__ ((__pure__)) _Rb_tree_node_base*
|
|
|
508 _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
|
|
|
509 __attribute__ ((__pure__)) const _Rb_tree_node_base*
|
|
|
510 _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
|
|
|
511 __attribute__ ((__pure__)) _Rb_tree_node_base*
|
|
|
512 _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
|
|
|
513 __attribute__ ((__pure__)) const _Rb_tree_node_base*
|
|
|
514 _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
|
|
|
515 template<typename _Tp>
|
|
|
516 struct _Rb_tree_iterator
|
|
|
517 {
|
|
|
518 typedef _Tp value_type;
|
|
|
519 typedef _Tp& reference;
|
|
|
520 typedef _Tp* pointer;
|
|
|
521 typedef bidirectional_iterator_tag iterator_category;
|
|
|
522 typedef ptrdiff_t difference_type;
|
|
|
523 typedef _Rb_tree_iterator<_Tp> _Self;
|
|
|
524 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
|
|
|
525 typedef _Rb_tree_node<_Tp>* _Link_type;
|
|
|
526 _Rb_tree_iterator()
|
|
|
527 : _M_node() { }
|
|
|
528 explicit
|
|
|
529 _Rb_tree_iterator(_Link_type __x)
|
|
|
530 : _M_node(__x) { }
|
|
|
531 reference
|
|
|
532 operator*() const
|
|
|
533 { return static_cast<_Link_type>(_M_node)->_M_value_field; }
|
|
|
534 pointer
|
|
|
535 operator->() const
|
|
|
536 { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
|
|
|
537 _Self&
|
|
|
538 operator++()
|
|
|
539 {
|
|
|
540 _M_node = _Rb_tree_increment(_M_node);
|
|
|
541 return *this;
|
|
|
542 }
|
|
|
543 _Self
|
|
|
544 operator++(int)
|
|
|
545 {
|
|
|
546 _Self __tmp = *this;
|
|
|
547 _M_node = _Rb_tree_increment(_M_node);
|
|
|
548 return __tmp;
|
|
|
549 }
|
|
|
550 _Self&
|
|
|
551 operator--()
|
|
|
552 {
|
|
|
553 _M_node = _Rb_tree_decrement(_M_node);
|
|
|
554 return *this;
|
|
|
555 }
|
|
|
556 _Self
|
|
|
557 operator--(int)
|
|
|
558 {
|
|
|
559 _Self __tmp = *this;
|
|
|
560 _M_node = _Rb_tree_decrement(_M_node);
|
|
|
561 return __tmp;
|
|
|
562 }
|
|
|
563 bool
|
|
|
564 operator==(const _Self& __x) const
|
|
|
565 { return _M_node == __x._M_node; }
|
|
|
566 bool
|
|
|
567 operator!=(const _Self& __x) const
|
|
|
568 { return _M_node != __x._M_node; }
|
|
|
569 _Base_ptr _M_node;
|
|
|
570 };
|
|
|
571 template<typename _Tp>
|
|
|
572 struct _Rb_tree_const_iterator
|
|
|
573 {
|
|
|
574 typedef _Tp value_type;
|
|
|
575 typedef const _Tp& reference;
|
|
|
576 typedef const _Tp* pointer;
|
|
|
577 typedef _Rb_tree_iterator<_Tp> iterator;
|
|
|
578 typedef bidirectional_iterator_tag iterator_category;
|
|
|
579 typedef ptrdiff_t difference_type;
|
|
|
580 typedef _Rb_tree_const_iterator<_Tp> _Self;
|
|
|
581 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
|
|
|
582 typedef const _Rb_tree_node<_Tp>* _Link_type;
|
|
|
583 _Rb_tree_const_iterator()
|
|
|
584 : _M_node() { }
|
|
|
585 explicit
|
|
|
586 _Rb_tree_const_iterator(_Link_type __x)
|
|
|
587 : _M_node(__x) { }
|
|
|
588 _Rb_tree_const_iterator(const iterator& __it)
|
|
|
589 : _M_node(__it._M_node) { }
|
|
|
590 reference
|
|
|
591 operator*() const
|
|
|
592 { return static_cast<_Link_type>(_M_node)->_M_value_field; }
|
|
|
593 pointer
|
|
|
594 operator->() const
|
|
|
595 { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
|
|
|
596 _Self&
|
|
|
597 operator++()
|
|
|
598 {
|
|
|
599 _M_node = _Rb_tree_increment(_M_node);
|
|
|
600 return *this;
|
|
|
601 }
|
|
|
602 _Self
|
|
|
603 operator++(int)
|
|
|
604 {
|
|
|
605 _Self __tmp = *this;
|
|
|
606 _M_node = _Rb_tree_increment(_M_node);
|
|
|
607 return __tmp;
|
|
|
608 }
|
|
|
609 _Self&
|
|
|
610 operator--()
|
|
|
611 {
|
|
|
612 _M_node = _Rb_tree_decrement(_M_node);
|
|
|
613 return *this;
|
|
|
614 }
|
|
|
615 _Self
|
|
|
616 operator--(int)
|
|
|
617 {
|
|
|
618 _Self __tmp = *this;
|
|
|
619 _M_node = _Rb_tree_decrement(_M_node);
|
|
|
620 return __tmp;
|
|
|
621 }
|
|
|
622 bool
|
|
|
623 operator==(const _Self& __x) const
|
|
|
624 { return _M_node == __x._M_node; }
|
|
|
625 bool
|
|
|
626 operator!=(const _Self& __x) const
|
|
|
627 { return _M_node != __x._M_node; }
|
|
|
628 _Base_ptr _M_node;
|
|
|
629 };
|
|
|
630 void
|
|
|
631 _Rb_tree_insert_and_rebalance(const bool __insert_left,
|
|
|
632 _Rb_tree_node_base* __x,
|
|
|
633 _Rb_tree_node_base* __p,
|
|
|
634 _Rb_tree_node_base& __header) throw ();
|
|
|
635 _Rb_tree_node_base*
|
|
|
636 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
|
|
|
637 _Rb_tree_node_base& __header) throw ();
|
|
|
638 template<typename _Key, typename _Val, typename _KeyOfValue,
|
|
|
639 typename _Compare, typename _Alloc = allocator<_Val> >
|
|
|
640 class _Rb_tree
|
|
|
641 {
|
|
|
642 typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
|
|
|
643 _Node_allocator;
|
|
|
644 protected:
|
|
|
645 typedef _Rb_tree_node_base* _Base_ptr;
|
|
|
646 typedef const _Rb_tree_node_base* _Const_Base_ptr;
|
|
|
647 public:
|
|
|
648 typedef _Key key_type;
|
|
|
649 typedef _Val value_type;
|
|
|
650 typedef value_type* pointer;
|
|
|
651 typedef const value_type* const_pointer;
|
|
|
652 typedef value_type& reference;
|
|
|
653 typedef const value_type& const_reference;
|
|
|
654 typedef _Rb_tree_node<_Val>* _Link_type;
|
|
|
655 typedef const _Rb_tree_node<_Val>* _Const_Link_type;
|
|
|
656 typedef size_t size_type;
|
|
|
657 typedef ptrdiff_t difference_type;
|
|
|
658 typedef _Alloc allocator_type;
|
|
|
659 _Node_allocator&
|
|
|
660 _M_get_Node_allocator()
|
|
|
661 { return *static_cast<_Node_allocator*>(&this->_M_impl); }
|
|
|
662 const _Node_allocator&
|
|
|
663 _M_get_Node_allocator() const
|
|
|
664 { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
|
|
|
665 allocator_type
|
|
|
666 get_allocator() const
|
|
|
667 { return allocator_type(_M_get_Node_allocator()); }
|
|
|
668 protected:
|
|
|
669 _Link_type
|
|
|
670 _M_get_node()
|
|
|
671 { return _M_impl._Node_allocator::allocate(1); }
|
|
|
672 __attribute__((transaction_safe))
|
|
|
673 void
|
|
|
674 _M_put_node(_Link_type __p)
|
|
|
675 { _M_impl._Node_allocator::deallocate(__p, 1); }
|
|
|
676 __attribute__((transaction_safe))
|
|
|
677 _Link_type
|
|
|
678 _M_create_node(const value_type& __x)
|
|
|
679 {
|
|
|
680 _Link_type __tmp = _M_get_node();
|
|
|
681 try
|
|
|
682 { get_allocator().construct(&__tmp->_M_value_field, __x); }
|
|
|
683 catch(...)
|
|
|
684 {
|
|
|
685 _M_put_node(__tmp);
|
|
|
686 throw;
|
|
|
687 }
|
|
|
688 return __tmp;
|
|
|
689 }
|
|
|
690 void
|
|
|
691 _M_destroy_node(_Link_type __p)
|
|
|
692 {
|
|
|
693 get_allocator().destroy(&__p->_M_value_field);
|
|
|
694 _M_put_node(__p);
|
|
|
695 }
|
|
|
696 protected:
|
|
|
697 template<typename _Key_compare,
|
|
|
698 bool _Is_pod_comparator = __is_pod(_Key_compare)>
|
|
|
699 struct _Rb_tree_impl : public _Node_allocator
|
|
|
700 {
|
|
|
701 _Key_compare _M_key_compare;
|
|
|
702 _Rb_tree_node_base _M_header;
|
|
|
703 size_type _M_node_count;
|
|
|
704 _Rb_tree_impl()
|
|
|
705 : _Node_allocator(), _M_key_compare(), _M_header(),
|
|
|
706 _M_node_count(0)
|
|
|
707 { _M_initialize(); }
|
|
|
708 _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
|
|
|
709 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
|
|
|
710 _M_node_count(0)
|
|
|
711 { _M_initialize(); }
|
|
|
712 private:
|
|
|
713 void
|
|
|
714 _M_initialize()
|
|
|
715 {
|
|
|
716 this->_M_header._M_color = _S_red;
|
|
|
717 this->_M_header._M_parent = 0;
|
|
|
718 this->_M_header._M_left = &this->_M_header;
|
|
|
719 this->_M_header._M_right = &this->_M_header;
|
|
|
720 }
|
|
|
721 };
|
|
|
722 _Rb_tree_impl<_Compare> _M_impl;
|
|
|
723 protected:
|
|
|
724 _Base_ptr&
|
|
|
725 _M_root()
|
|
|
726 { return this->_M_impl._M_header._M_parent; }
|
|
|
727 _Const_Base_ptr
|
|
|
728 _M_root() const
|
|
|
729 { return this->_M_impl._M_header._M_parent; }
|
|
|
730 _Base_ptr&
|
|
|
731 _M_leftmost()
|
|
|
732 { return this->_M_impl._M_header._M_left; }
|
|
|
733 _Const_Base_ptr
|
|
|
734 _M_leftmost() const
|
|
|
735 { return this->_M_impl._M_header._M_left; }
|
|
|
736 _Base_ptr&
|
|
|
737 _M_rightmost()
|
|
|
738 { return this->_M_impl._M_header._M_right; }
|
|
|
739 _Const_Base_ptr
|
|
|
740 _M_rightmost() const
|
|
|
741 { return this->_M_impl._M_header._M_right; }
|
|
|
742 _Link_type
|
|
|
743 _M_begin()
|
|
|
744 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
|
|
|
745 _Const_Link_type
|
|
|
746 _M_begin() const
|
|
|
747 {
|
|
|
748 return static_cast<_Const_Link_type>
|
|
|
749 (this->_M_impl._M_header._M_parent);
|
|
|
750 }
|
|
|
751 _Link_type
|
|
|
752 _M_end()
|
|
|
753 { return static_cast<_Link_type>(&this->_M_impl._M_header); }
|
|
|
754 _Const_Link_type
|
|
|
755 _M_end() const
|
|
|
756 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
|
|
|
757 static const_reference
|
|
|
758 _S_value(_Const_Link_type __x)
|
|
|
759 { return __x->_M_value_field; }
|
|
|
760 static const _Key&
|
|
|
761 _S_key(_Const_Link_type __x)
|
|
|
762 { return _KeyOfValue()(_S_value(__x)); }
|
|
|
763 static _Link_type
|
|
|
764 _S_left(_Base_ptr __x)
|
|
|
765 { return static_cast<_Link_type>(__x->_M_left); }
|
|
|
766 static _Const_Link_type
|
|
|
767 _S_left(_Const_Base_ptr __x)
|
|
|
768 { return static_cast<_Const_Link_type>(__x->_M_left); }
|
|
|
769 static _Link_type
|
|
|
770 _S_right(_Base_ptr __x)
|
|
|
771 { return static_cast<_Link_type>(__x->_M_right); }
|
|
|
772 static _Const_Link_type
|
|
|
773 _S_right(_Const_Base_ptr __x)
|
|
|
774 { return static_cast<_Const_Link_type>(__x->_M_right); }
|
|
|
775 static const_reference
|
|
|
776 _S_value(_Const_Base_ptr __x)
|
|
|
777 { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
|
|
|
778 static const _Key&
|
|
|
779 _S_key(_Const_Base_ptr __x)
|
|
|
780 { return _KeyOfValue()(_S_value(__x)); }
|
|
|
781 public:
|
|
|
782 typedef _Rb_tree_iterator<value_type> iterator;
|
|
|
783 typedef _Rb_tree_const_iterator<value_type> const_iterator;
|
|
|
784 typedef std::reverse_iterator<iterator> reverse_iterator;
|
|
|
785 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
|
|
|
786 private:
|
|
|
787 iterator
|
|
|
788 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
|
|
|
789 const value_type& __v);
|
|
|
790 public:
|
|
|
791 _Rb_tree() { }
|
|
|
792 iterator
|
|
|
793 begin()
|
|
|
794 {
|
|
|
795 return iterator(static_cast<_Link_type>
|
|
|
796 (this->_M_impl._M_header._M_left));
|
|
|
797 }
|
|
|
798 const_iterator
|
|
|
799 begin() const
|
|
|
800 {
|
|
|
801 return const_iterator(static_cast<_Const_Link_type>
|
|
|
802 (this->_M_impl._M_header._M_left));
|
|
|
803 }
|
|
|
804 iterator
|
|
|
805 end()
|
|
|
806 { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
|
|
|
807 const_iterator
|
|
|
808 end() const
|
|
|
809 {
|
|
|
810 return const_iterator(static_cast<_Const_Link_type>
|
|
|
811 (&this->_M_impl._M_header));
|
|
|
812 }
|
|
|
813 pair<iterator, bool>
|
|
|
814 _M_insert_unique(const value_type& __x);
|
|
|
815 };
|
|
|
816 template<typename _Key, typename _Val, typename _KeyOfValue,
|
|
|
817 typename _Compare, typename _Alloc>
|
|
|
818 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
|
|
|
819 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
|
|
|
820 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
|
|
|
821 {
|
|
|
822 _Link_type __z = _M_create_node(__v);
|
|
|
823 return iterator(__z);
|
|
|
824 }
|
|
|
825 template<typename _Key, typename _Val, typename _KeyOfValue,
|
|
|
826 typename _Compare, typename _Alloc>
|
|
|
827 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
|
|
|
828 _Compare, _Alloc>::iterator, bool>
|
|
|
829 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
|
|
|
830 _M_insert_unique(const _Val& __v)
|
|
|
831 {
|
|
|
832 _Link_type __x = _M_begin();
|
|
|
833 _Link_type __y = _M_end();
|
|
|
834 iterator __j = iterator(__y);
|
|
|
835 return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
|
|
|
836 }
|
|
|
837 }
|
|
|
838 namespace std __attribute__ ((__visibility__ ("default"))) {
|
|
|
839 template<typename _Key, typename _Compare = std::less<_Key>,
|
|
|
840 typename _Alloc = std::allocator<_Key> >
|
|
|
841 class set
|
|
|
842 {
|
|
|
843 public:
|
|
|
844 typedef _Key key_type;
|
|
|
845 typedef _Key value_type;
|
|
|
846 typedef _Compare key_compare;
|
|
|
847 typedef _Compare value_compare;
|
|
|
848 typedef _Alloc allocator_type;
|
|
|
849 private:
|
|
|
850 typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;
|
|
|
851 typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
|
|
|
852 key_compare, _Key_alloc_type> _Rep_type;
|
|
|
853 _Rep_type _M_t;
|
|
|
854 public:
|
|
|
855 typedef typename _Key_alloc_type::pointer pointer;
|
|
|
856 typedef typename _Key_alloc_type::const_pointer const_pointer;
|
|
|
857 typedef typename _Key_alloc_type::reference reference;
|
|
|
858 typedef typename _Key_alloc_type::const_reference const_reference;
|
|
|
859 typedef typename _Rep_type::const_iterator iterator;
|
|
|
860 typedef typename _Rep_type::const_iterator const_iterator;
|
|
|
861 typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
|
|
|
862 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
|
|
|
863 typedef typename _Rep_type::size_type size_type;
|
|
|
864 typedef typename _Rep_type::difference_type difference_type;
|
|
|
865 std::pair<iterator, bool>
|
|
|
866 insert(const value_type& __x)
|
|
|
867 {
|
|
|
868 _M_t._M_insert_unique(__x);
|
|
|
869 }
|
|
|
870 };
|
|
|
871 }
|
|
|
872 __attribute__((transaction_pure))
|
|
|
873 void* operator new(size_t);
|
|
|
874 __attribute__((transaction_pure))
|
|
|
875 void operator delete(void*);
|
|
|
876 class Widget
|
|
|
877 {
|
|
|
878 private:
|
|
|
879 };
|
|
|
880 class Screen
|
|
|
881 {
|
|
|
882 protected:
|
|
|
883 std::set<Widget *> widgets;
|
|
|
884 public:
|
|
|
885 void addWidget(Widget* widget);
|
|
|
886 };
|
|
|
887 void Screen::addWidget(Widget* widget)
|
|
|
888 {
|
|
|
889 widgets.insert(widget);
|
|
|
890 }
|
