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