From patchwork Tue Jul 27 16:34:38 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 60012 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 2A140B6F11 for ; Wed, 28 Jul 2010 02:35:22 +1000 (EST) Received: (qmail 25433 invoked by alias); 27 Jul 2010 16:35:19 -0000 Received: (qmail 25110 invoked by uid 22791); 27 Jul 2010 16:35:06 -0000 X-SWARE-Spam-Status: No, hits=-6.2 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_HI, SPF_HELO_PASS, TW_CX, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 27 Jul 2010 16:34:51 +0000 Received: from int-mx08.intmail.prod.int.phx2.redhat.com (int-mx08.intmail.prod.int.phx2.redhat.com [10.5.11.21]) by mx1.redhat.com (8.13.8/8.13.8) with ESMTP id o6RGYngT002240 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Tue, 27 Jul 2010 12:34:49 -0400 Received: from redhat.com (vpn-10-138.rdu.redhat.com [10.11.10.138]) by int-mx08.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id o6RGYcn2025579 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Tue, 27 Jul 2010 12:34:40 -0400 Date: Tue, 27 Jul 2010 12:34:38 -0400 From: Aldy Hernandez To: Patrick Marlier Cc: Richard Henderson , FELBER Pascal , gcc-patches@gcc.gnu.org Subject: Re: [trans-mem] error with transaction_callable in gimplify.c Message-ID: <20100727163435.GA9974@redhat.com> References: <4C3F6829.40300@unine.ch> <20100716113816.GB2158@redhat.com> <4C4045BB.2040608@unine.ch> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <4C4045BB.2040608@unine.ch> User-Agent: Mutt/1.5.20 (2009-08-17) Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org There is no need to instrument a function call that has a return slot optimization, since the callee should've performed any instrumentation necessary. Oh yeah, the comment was wrong, this is a store not a load. Fixed. OK for branch? p.s. Sorry, but I'm too dumb to properly reduce a C++ testcase. I tried. Index: trans-mem.c =================================================================== --- trans-mem.c (revision 161318) +++ trans-mem.c (working copy) @@ -2143,8 +2143,13 @@ expand_call_tm (struct tm_region *region return true; } - /* Instrument the LHS load if needed. */ - if (lhs && requires_barrier (region->entry_block, lhs, stmt)) + /* Instrument the store if needed. + + If the assignment happens inside the function call (return slot + optimization), there is no instrumentation to be done, since + the callee should have done the right thing. */ + if (lhs && requires_barrier (region->entry_block, lhs, stmt) + && !gimple_call_return_slot_opt_p (stmt)) { tree tmp = make_rename_temp (TREE_TYPE (lhs), NULL); location_t loc = gimple_location (stmt); Index: testsuite/g++.dg/tm/20100727.C =================================================================== --- testsuite/g++.dg/tm/20100727.C (revision 0) +++ testsuite/g++.dg/tm/20100727.C (revision 0) @@ -0,0 +1,2129 @@ +typedef long int ptrdiff_t; +typedef long unsigned int size_t; +namespace std __attribute__ ((__visibility__ ("default"))) { + using ::ptrdiff_t; + using ::size_t; +} + +namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) { + template + class __normal_iterator; +} +namespace std __attribute__ ((__visibility__ ("default"))) { + struct __true_type { }; + struct __false_type { }; + template + struct __truth_type + { typedef __false_type __type; }; + template<> + struct __truth_type + { typedef __true_type __type; }; + template + struct __traitor + { + enum { __value = bool(_Sp::__value) || bool(_Tp::__value) }; + typedef typename __truth_type<__value>::__type __type; + }; + template + struct __are_same + { + enum { __value = 0 }; + typedef __false_type __type; + }; + template + struct __are_same<_Tp, _Tp> + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template + struct __is_void + { + enum { __value = 0 }; + typedef __false_type __type; + }; + template<> + struct __is_void + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template + struct __is_integer + { + enum { __value = 0 }; + typedef __false_type __type; + }; + template<> + struct __is_integer + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_integer + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_integer + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_integer + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_integer + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_integer + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_integer + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_integer + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_integer + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_integer + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_integer + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_integer + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_integer + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template + struct __is_floating + { + enum { __value = 0 }; + typedef __false_type __type; + }; + template<> + struct __is_floating + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_floating + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_floating + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template + struct __is_pointer + { + enum { __value = 0 }; + typedef __false_type __type; + }; + template + struct __is_pointer<_Tp*> + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template + struct __is_normal_iterator + { + enum { __value = 0 }; + typedef __false_type __type; + }; + template + struct __is_normal_iterator< __gnu_cxx::__normal_iterator<_Iterator, + _Container> > + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template + struct __is_arithmetic + : public __traitor<__is_integer<_Tp>, __is_floating<_Tp> > + { }; + template + struct __is_fundamental + : public __traitor<__is_void<_Tp>, __is_arithmetic<_Tp> > + { }; + template + struct __is_scalar + : public __traitor<__is_arithmetic<_Tp>, __is_pointer<_Tp> > + { }; + template + struct __is_char + { + enum { __value = 0 }; + typedef __false_type __type; + }; + template<> + struct __is_char + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_char + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template + struct __is_byte + { + enum { __value = 0 }; + typedef __false_type __type; + }; + template<> + struct __is_byte + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_byte + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template<> + struct __is_byte + { + enum { __value = 1 }; + typedef __true_type __type; + }; + template + struct __is_move_iterator + { + enum { __value = 0 }; + typedef __false_type __type; + }; +} + +namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) { + template + struct __enable_if + { }; + template + struct __enable_if + { typedef _Tp __type; }; + template + struct __conditional_type + { typedef _Iftrue __type; }; + template + struct __conditional_type + { typedef _Iffalse __type; }; + template + struct __add_unsigned + { + private: + typedef __enable_if::__value, _Tp> __if_type; + public: + typedef typename __if_type::__type __type; + }; + template<> + struct __add_unsigned + { typedef unsigned char __type; }; + template<> + struct __add_unsigned + { typedef unsigned char __type; }; + template<> + struct __add_unsigned + { typedef unsigned short __type; }; + template<> + struct __add_unsigned + { typedef unsigned int __type; }; + template<> + struct __add_unsigned + { typedef unsigned long __type; }; + template<> + struct __add_unsigned + { typedef unsigned long long __type; }; + template<> + struct __add_unsigned; + template<> + struct __add_unsigned; + template + struct __remove_unsigned + { + private: + typedef __enable_if::__value, _Tp> __if_type; + public: + typedef typename __if_type::__type __type; + }; + template<> + struct __remove_unsigned + { typedef signed char __type; }; + template<> + struct __remove_unsigned + { typedef signed char __type; }; + template<> + struct __remove_unsigned + { typedef short __type; }; + template<> + struct __remove_unsigned + { typedef int __type; }; + template<> + struct __remove_unsigned + { typedef long __type; }; + template<> + struct __remove_unsigned + { typedef long long __type; }; + template<> + struct __remove_unsigned; + template<> + struct __remove_unsigned; + template + inline bool + __is_null_pointer(_Type* __ptr) + { return __ptr == 0; } + template + inline bool + __is_null_pointer(_Type) + { return false; } + template::__value> + struct __promote + { typedef double __type; }; + template + struct __promote<_Tp, false> + { typedef _Tp __type; }; + template + struct __promote_2 + { + private: + typedef typename __promote<_Tp>::__type __type1; + typedef typename __promote<_Up>::__type __type2; + public: + typedef __typeof__(__type1() + __type2()) __type; + }; + template + struct __promote_3 + { + private: + typedef typename __promote<_Tp>::__type __type1; + typedef typename __promote<_Up>::__type __type2; + typedef typename __promote<_Vp>::__type __type3; + public: + typedef __typeof__(__type1() + __type2() + __type3()) __type; + }; + template + struct __promote_4 + { + private: + typedef typename __promote<_Tp>::__type __type1; + typedef typename __promote<_Up>::__type __type2; + typedef typename __promote<_Vp>::__type __type3; + typedef typename __promote<_Wp>::__type __type4; + public: + typedef __typeof__(__type1() + __type2() + __type3() + __type4()) __type; + }; +} + +namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) { + template + struct __numeric_traits_integer + { + static const _Value __min = (((_Value)(-1) < 0) ? (_Value)1 << (sizeof(_Value) * 8 - ((_Value)(-1) < 0)) : (_Value)0); + static const _Value __max = (((_Value)(-1) < 0) ? (((((_Value)1 << ((sizeof(_Value) * 8 - ((_Value)(-1) < 0)) - 1)) - 1) << 1) + 1) : ~(_Value)0); + static const bool __is_signed = ((_Value)(-1) < 0); + static const int __digits = (sizeof(_Value) * 8 - ((_Value)(-1) < 0)); + }; + template + const _Value __numeric_traits_integer<_Value>::__min; + template + const _Value __numeric_traits_integer<_Value>::__max; + template + const bool __numeric_traits_integer<_Value>::__is_signed; + template + const int __numeric_traits_integer<_Value>::__digits; + template + struct __numeric_traits_floating + { + static const int __max_digits10 = (2 + (std::__are_same<_Value, float>::__value ? 24 : std::__are_same<_Value, double>::__value ? 53 : 64) * 3010 / 10000); + static const bool __is_signed = true; + static const int __digits10 = (std::__are_same<_Value, float>::__value ? 6 : std::__are_same<_Value, double>::__value ? 15 : 18); + static const int __max_exponent10 = (std::__are_same<_Value, float>::__value ? 38 : std::__are_same<_Value, double>::__value ? 308 : 4932); + }; + template + const int __numeric_traits_floating<_Value>::__max_digits10; + template + const bool __numeric_traits_floating<_Value>::__is_signed; + template + const int __numeric_traits_floating<_Value>::__digits10; + template + const int __numeric_traits_floating<_Value>::__max_exponent10; + template + struct __numeric_traits + : public __conditional_type::__value, + __numeric_traits_integer<_Value>, + __numeric_traits_floating<_Value> >::__type + { }; +} + + +namespace std __attribute__ ((__visibility__ ("default"))) { + template + inline void + swap(_Tp& __a, _Tp& __b) + { + + _Tp __tmp = (__a); + __a = (__b); + __b = (__tmp); + } + template + inline void + swap(_Tp (&__a)[_Nm], _Tp (&__b)[_Nm]) + { + for (size_t __n = 0; __n < _Nm; ++__n) + swap(__a[__n], __b[__n]); + } +} +namespace std __attribute__ ((__visibility__ ("default"))) { + template + struct pair + { + typedef _T1 first_type; + typedef _T2 second_type; + _T1 first; + _T2 second; + pair() + : first(), second() { } + pair(const _T1& __a, const _T2& __b) + : first(__a), second(__b) { } + template + pair(const pair<_U1, _U2>& __p) + : first(__p.first), + second(__p.second) { } + }; + template + inline bool + operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) + { return __x.first == __y.first && __x.second == __y.second; } + template + inline bool + operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) + { return __x.first < __y.first + || (!(__y.first < __x.first) && __x.second < __y.second); } + template + inline bool + operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) + { return !(__x == __y); } + template + inline bool + operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) + { return __y < __x; } + template + inline bool + operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) + { return !(__y < __x); } + template + inline bool + operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) + { return !(__x < __y); } + template + inline pair<_T1, _T2> + make_pair(_T1 __x, _T2 __y) + { return pair<_T1, _T2>(__x, __y); } +} + + +namespace std __attribute__ ((__visibility__ ("default"))) { + struct input_iterator_tag { }; + struct output_iterator_tag { }; + struct forward_iterator_tag : public input_iterator_tag { }; + struct bidirectional_iterator_tag : public forward_iterator_tag { }; + struct random_access_iterator_tag : public bidirectional_iterator_tag { }; + template + struct iterator + { + typedef _Category iterator_category; + typedef _Tp value_type; + typedef _Distance difference_type; + typedef _Pointer pointer; + typedef _Reference reference; + }; + template + struct iterator_traits + { + typedef typename _Iterator::iterator_category iterator_category; + typedef typename _Iterator::value_type value_type; + typedef typename _Iterator::difference_type difference_type; + typedef typename _Iterator::pointer pointer; + typedef typename _Iterator::reference reference; + }; + template + struct iterator_traits<_Tp*> + { + typedef random_access_iterator_tag iterator_category; + typedef _Tp value_type; + typedef ptrdiff_t difference_type; + typedef _Tp* pointer; + typedef _Tp& reference; + }; + template + struct iterator_traits + { + typedef random_access_iterator_tag iterator_category; + typedef _Tp value_type; + typedef ptrdiff_t difference_type; + typedef const _Tp* pointer; + typedef const _Tp& reference; + }; + template + inline typename iterator_traits<_Iter>::iterator_category + __iterator_category(const _Iter&) + { return typename iterator_traits<_Iter>::iterator_category(); } +} + +namespace std __attribute__ ((__visibility__ ("default"))) { + template + inline typename iterator_traits<_InputIterator>::difference_type + __distance(_InputIterator __first, _InputIterator __last, + input_iterator_tag) + { + + typename iterator_traits<_InputIterator>::difference_type __n = 0; + while (__first != __last) + { + ++__first; + ++__n; + } + return __n; + } + template + inline typename iterator_traits<_RandomAccessIterator>::difference_type + __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, + random_access_iterator_tag) + { + + return __last - __first; + } + template + inline typename iterator_traits<_InputIterator>::difference_type + distance(_InputIterator __first, _InputIterator __last) + { + return std::__distance(__first, __last, + std::__iterator_category(__first)); + } + template + inline void + __advance(_InputIterator& __i, _Distance __n, input_iterator_tag) + { + + while (__n--) + ++__i; + } + template + inline void + __advance(_BidirectionalIterator& __i, _Distance __n, + bidirectional_iterator_tag) + { + + if (__n > 0) + while (__n--) + ++__i; + else + while (__n++) + --__i; + } + template + inline void + __advance(_RandomAccessIterator& __i, _Distance __n, + random_access_iterator_tag) + { + + __i += __n; + } + template + inline void + advance(_InputIterator& __i, _Distance __n) + { + typename iterator_traits<_InputIterator>::difference_type __d = __n; + std::__advance(__i, __d, std::__iterator_category(__i)); + } +} +namespace std __attribute__ ((__visibility__ ("default"))) { + template + class reverse_iterator + : public iterator::iterator_category, + typename iterator_traits<_Iterator>::value_type, + typename iterator_traits<_Iterator>::difference_type, + typename iterator_traits<_Iterator>::pointer, + typename iterator_traits<_Iterator>::reference> + { + protected: + _Iterator current; + typedef iterator_traits<_Iterator> __traits_type; + public: + typedef _Iterator iterator_type; + typedef typename __traits_type::difference_type difference_type; + typedef typename __traits_type::pointer pointer; + typedef typename __traits_type::reference reference; + reverse_iterator() : current() { } + explicit + reverse_iterator(iterator_type __x) : current(__x) { } + reverse_iterator(const reverse_iterator& __x) + : current(__x.current) { } + template + reverse_iterator(const reverse_iterator<_Iter>& __x) + : current(__x.base()) { } + iterator_type + base() const + { return current; } + reference + operator*() const + { + _Iterator __tmp = current; + return *--__tmp; + } + pointer + operator->() const + { return &(operator*()); } + reverse_iterator& + operator++() + { + --current; + return *this; + } + reverse_iterator + operator++(int) + { + reverse_iterator __tmp = *this; + --current; + return __tmp; + } + reverse_iterator& + operator--() + { + ++current; + return *this; + } + reverse_iterator + operator--(int) + { + reverse_iterator __tmp = *this; + ++current; + return __tmp; + } + reverse_iterator + operator+(difference_type __n) const + { return reverse_iterator(current - __n); } + reverse_iterator& + operator+=(difference_type __n) + { + current -= __n; + return *this; + } + reverse_iterator + operator-(difference_type __n) const + { return reverse_iterator(current + __n); } + reverse_iterator& + operator-=(difference_type __n) + { + current += __n; + return *this; + } + reference + operator[](difference_type __n) const + { return *(*this + __n); } + }; + template + inline bool + operator==(const reverse_iterator<_Iterator>& __x, + const reverse_iterator<_Iterator>& __y) + { return __x.base() == __y.base(); } + template + inline bool + operator<(const reverse_iterator<_Iterator>& __x, + const reverse_iterator<_Iterator>& __y) + { return __y.base() < __x.base(); } + template + inline bool + operator!=(const reverse_iterator<_Iterator>& __x, + const reverse_iterator<_Iterator>& __y) + { return !(__x == __y); } + template + inline bool + operator>(const reverse_iterator<_Iterator>& __x, + const reverse_iterator<_Iterator>& __y) + { return __y < __x; } + template + inline bool + operator<=(const reverse_iterator<_Iterator>& __x, + const reverse_iterator<_Iterator>& __y) + { return !(__y < __x); } + template + inline bool + operator>=(const reverse_iterator<_Iterator>& __x, + const reverse_iterator<_Iterator>& __y) + { return !(__x < __y); } + template + inline typename reverse_iterator<_Iterator>::difference_type + operator-(const reverse_iterator<_Iterator>& __x, + const reverse_iterator<_Iterator>& __y) + { return __y.base() - __x.base(); } + template + inline reverse_iterator<_Iterator> + operator+(typename reverse_iterator<_Iterator>::difference_type __n, + const reverse_iterator<_Iterator>& __x) + { return reverse_iterator<_Iterator>(__x.base() - __n); } + template + inline bool + operator==(const reverse_iterator<_IteratorL>& __x, + const reverse_iterator<_IteratorR>& __y) + { return __x.base() == __y.base(); } + template + inline bool + operator<(const reverse_iterator<_IteratorL>& __x, + const reverse_iterator<_IteratorR>& __y) + { return __y.base() < __x.base(); } + template + inline bool + operator!=(const reverse_iterator<_IteratorL>& __x, + const reverse_iterator<_IteratorR>& __y) + { return !(__x == __y); } + template + inline bool + operator>(const reverse_iterator<_IteratorL>& __x, + const reverse_iterator<_IteratorR>& __y) + { return __y < __x; } + template + inline bool + operator<=(const reverse_iterator<_IteratorL>& __x, + const reverse_iterator<_IteratorR>& __y) + { return !(__y < __x); } + template + inline bool + operator>=(const reverse_iterator<_IteratorL>& __x, + const reverse_iterator<_IteratorR>& __y) + { return !(__x < __y); } + template + inline typename reverse_iterator<_IteratorL>::difference_type + operator-(const reverse_iterator<_IteratorL>& __x, + const reverse_iterator<_IteratorR>& __y) + { return __y.base() - __x.base(); } + template + class back_insert_iterator + : public iterator + { + protected: + _Container* container; + public: + typedef _Container container_type; + explicit + back_insert_iterator(_Container& __x) : container(&__x) { } + back_insert_iterator& + operator=(typename _Container::const_reference __value) + { + container->push_back(__value); + return *this; + } + back_insert_iterator& + operator*() + { return *this; } + back_insert_iterator& + operator++() + { return *this; } + back_insert_iterator + operator++(int) + { return *this; } + }; + template + inline back_insert_iterator<_Container> + back_inserter(_Container& __x) + { return back_insert_iterator<_Container>(__x); } + template + class front_insert_iterator + : public iterator + { + protected: + _Container* container; + public: + typedef _Container container_type; + explicit front_insert_iterator(_Container& __x) : container(&__x) { } + front_insert_iterator& + operator=(typename _Container::const_reference __value) + { + container->push_front(__value); + return *this; + } + front_insert_iterator& + operator*() + { return *this; } + front_insert_iterator& + operator++() + { return *this; } + front_insert_iterator + operator++(int) + { return *this; } + }; + template + inline front_insert_iterator<_Container> + front_inserter(_Container& __x) + { return front_insert_iterator<_Container>(__x); } + template + class insert_iterator + : public iterator + { + protected: + _Container* container; + typename _Container::iterator iter; + public: + typedef _Container container_type; + insert_iterator(_Container& __x, typename _Container::iterator __i) + : container(&__x), iter(__i) {} + insert_iterator& + operator=(typename _Container::const_reference __value) + { + iter = container->insert(iter, __value); + ++iter; + return *this; + } + insert_iterator& + operator*() + { return *this; } + insert_iterator& + operator++() + { return *this; } + insert_iterator& + operator++(int) + { return *this; } + }; + template + inline insert_iterator<_Container> + inserter(_Container& __x, _Iterator __i) + { + return insert_iterator<_Container>(__x, + typename _Container::iterator(__i)); + } +} +namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) { + using std::iterator_traits; + using std::iterator; + template + class __normal_iterator + { + protected: + _Iterator _M_current; + typedef iterator_traits<_Iterator> __traits_type; + public: + typedef _Iterator iterator_type; + typedef typename __traits_type::iterator_category iterator_category; + typedef typename __traits_type::value_type value_type; + typedef typename __traits_type::difference_type difference_type; + typedef typename __traits_type::reference reference; + typedef typename __traits_type::pointer pointer; + __normal_iterator() : _M_current(_Iterator()) { } + explicit + __normal_iterator(const _Iterator& __i) : _M_current(__i) { } + template + __normal_iterator(const __normal_iterator<_Iter, + typename __enable_if< + (std::__are_same<_Iter, typename _Container::pointer>::__value), + _Container>::__type>& __i) + : _M_current(__i.base()) { } + reference + operator*() const + { return *_M_current; } + pointer + operator->() const + { return _M_current; } + __normal_iterator& + operator++() + { + ++_M_current; + return *this; + } + __normal_iterator + operator++(int) + { return __normal_iterator(_M_current++); } + __normal_iterator& + operator--() + { + --_M_current; + return *this; + } + __normal_iterator + operator--(int) + { return __normal_iterator(_M_current--); } + reference + operator[](const difference_type& __n) const + { return _M_current[__n]; } + __normal_iterator& + operator+=(const difference_type& __n) + { _M_current += __n; return *this; } + __normal_iterator + operator+(const difference_type& __n) const + { return __normal_iterator(_M_current + __n); } + __normal_iterator& + operator-=(const difference_type& __n) + { _M_current -= __n; return *this; } + __normal_iterator + operator-(const difference_type& __n) const + { return __normal_iterator(_M_current - __n); } + const _Iterator& + base() const + { return _M_current; } + }; + template + inline bool + operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, + const __normal_iterator<_IteratorR, _Container>& __rhs) + { return __lhs.base() == __rhs.base(); } + template + inline bool + operator==(const __normal_iterator<_Iterator, _Container>& __lhs, + const __normal_iterator<_Iterator, _Container>& __rhs) + { return __lhs.base() == __rhs.base(); } + template + inline bool + operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, + const __normal_iterator<_IteratorR, _Container>& __rhs) + { return __lhs.base() != __rhs.base(); } + template + inline bool + operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, + const __normal_iterator<_Iterator, _Container>& __rhs) + { return __lhs.base() != __rhs.base(); } + template + inline bool + operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, + const __normal_iterator<_IteratorR, _Container>& __rhs) + { return __lhs.base() < __rhs.base(); } + template + inline bool + operator<(const __normal_iterator<_Iterator, _Container>& __lhs, + const __normal_iterator<_Iterator, _Container>& __rhs) + { return __lhs.base() < __rhs.base(); } + template + inline bool + operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, + const __normal_iterator<_IteratorR, _Container>& __rhs) + { return __lhs.base() > __rhs.base(); } + template + inline bool + operator>(const __normal_iterator<_Iterator, _Container>& __lhs, + const __normal_iterator<_Iterator, _Container>& __rhs) + { return __lhs.base() > __rhs.base(); } + template + inline bool + operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, + const __normal_iterator<_IteratorR, _Container>& __rhs) + { return __lhs.base() <= __rhs.base(); } + template + inline bool + operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, + const __normal_iterator<_Iterator, _Container>& __rhs) + { return __lhs.base() <= __rhs.base(); } + template + inline bool + operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, + const __normal_iterator<_IteratorR, _Container>& __rhs) + { return __lhs.base() >= __rhs.base(); } + template + inline bool + operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, + const __normal_iterator<_Iterator, _Container>& __rhs) + { return __lhs.base() >= __rhs.base(); } + template + inline typename __normal_iterator<_IteratorL, _Container>::difference_type + operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, + const __normal_iterator<_IteratorR, _Container>& __rhs) + { return __lhs.base() - __rhs.base(); } + template + inline typename __normal_iterator<_Iterator, _Container>::difference_type + operator-(const __normal_iterator<_Iterator, _Container>& __lhs, + const __normal_iterator<_Iterator, _Container>& __rhs) + { return __lhs.base() - __rhs.base(); } + template + inline __normal_iterator<_Iterator, _Container> + operator+(typename __normal_iterator<_Iterator, _Container>::difference_type + __n, const __normal_iterator<_Iterator, _Container>& __i) + { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } +} +namespace std +{ + namespace __debug { } +} +namespace __gnu_debug +{ + using namespace std::__debug; +} +namespace std __attribute__ ((__visibility__ ("default"))) { + template + struct __iter_swap + { + template + static void + iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) + { + typedef typename iterator_traits<_ForwardIterator1>::value_type + _ValueType1; + _ValueType1 __tmp = (*__a); + *__a = (*__b); + *__b = (__tmp); + } + }; + template<> + struct __iter_swap + { + template + static void + iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) + { + swap(*__a, *__b); + } + }; + template + inline void + iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) + { + typedef typename iterator_traits<_ForwardIterator1>::value_type + _ValueType1; + typedef typename iterator_traits<_ForwardIterator2>::value_type + _ValueType2; + + + + + typedef typename iterator_traits<_ForwardIterator1>::reference + _ReferenceType1; + typedef typename iterator_traits<_ForwardIterator2>::reference + _ReferenceType2; + std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value + && __are_same<_ValueType1&, _ReferenceType1>::__value + && __are_same<_ValueType2&, _ReferenceType2>::__value>:: + iter_swap(__a, __b); + } + template + _ForwardIterator2 + swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2) + { + + + ; + for (; __first1 != __last1; ++__first1, ++__first2) + std::iter_swap(__first1, __first2); + return __first2; + } + template + inline const _Tp& + min(const _Tp& __a, const _Tp& __b) + { + + if (__b < __a) + return __b; + return __a; + } + template + inline const _Tp& + max(const _Tp& __a, const _Tp& __b) + { + + if (__a < __b) + return __b; + return __a; + } + template + inline const _Tp& + min(const _Tp& __a, const _Tp& __b, _Compare __comp) + { + if (__comp(__b, __a)) + return __b; + return __a; + } + template + inline const _Tp& + max(const _Tp& __a, const _Tp& __b, _Compare __comp) + { + if (__comp(__a, __b)) + return __b; + return __a; + } + template + struct _Iter_base + { + typedef _Iterator iterator_type; + static iterator_type + _S_base(_Iterator __it) + { return __it; } + }; + template + struct _Iter_base<_Iterator, true> + { + typedef typename _Iterator::iterator_type iterator_type; + static iterator_type + _S_base(_Iterator __it) + { return __it.base(); } + }; + template + struct _Niter_base + : _Iter_base<_Iterator, __is_normal_iterator<_Iterator>::__value> + { }; + template + inline typename _Niter_base<_Iterator>::iterator_type + __niter_base(_Iterator __it) + { return std::_Niter_base<_Iterator>::_S_base(__it); } + template + struct _Miter_base + : _Iter_base<_Iterator, __is_move_iterator<_Iterator>::__value> + { }; + template + inline typename _Miter_base<_Iterator>::iterator_type + __miter_base(_Iterator __it) + { return std::_Miter_base<_Iterator>::_S_base(__it); } + template + struct __copy_move + { + template + static _OI + __copy_m(_II __first, _II __last, _OI __result) + { + for (; __first != __last; ++__result, ++__first) + *__result = *__first; + return __result; + } + }; + template<> + struct __copy_move + { + template + static _OI + __copy_m(_II __first, _II __last, _OI __result) + { + typedef typename iterator_traits<_II>::difference_type _Distance; + for(_Distance __n = __last - __first; __n > 0; --__n) + { + *__result = *__first; + ++__first; + ++__result; + } + return __result; + } + }; + template + struct __copy_move<_IsMove, true, random_access_iterator_tag> + { + template + static _Tp* + __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result) + { + const ptrdiff_t _Num = __last - __first; + if (_Num) + __builtin_memmove(__result, __first, sizeof(_Tp) * _Num); + return __result + _Num; + } + }; + template + inline _OI + __copy_move_a(_II __first, _II __last, _OI __result) + { + typedef typename iterator_traits<_II>::value_type _ValueTypeI; + typedef typename iterator_traits<_OI>::value_type _ValueTypeO; + typedef typename iterator_traits<_II>::iterator_category _Category; + const bool __simple = (__is_pod(_ValueTypeI) + && __is_pointer<_II>::__value + && __is_pointer<_OI>::__value + && __are_same<_ValueTypeI, _ValueTypeO>::__value); + return std::__copy_move<_IsMove, __simple, + _Category>::__copy_m(__first, __last, __result); + } + template + struct char_traits; + template + class istreambuf_iterator; + template + class ostreambuf_iterator; + template + typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, + ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type + __copy_move_a2(_CharT*, _CharT*, + ostreambuf_iterator<_CharT, char_traits<_CharT> >); + template + typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, + ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type + __copy_move_a2(const _CharT*, const _CharT*, + ostreambuf_iterator<_CharT, char_traits<_CharT> >); + template + typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, + _CharT*>::__type + __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >, + istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*); + template + inline _OI + __copy_move_a2(_II __first, _II __last, _OI __result) + { + return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first), + std::__niter_base(__last), + std::__niter_base(__result))); + } + template + inline _OI + copy(_II __first, _II __last, _OI __result) + { + + + ; + return (std::__copy_move_a2<__is_move_iterator<_II>::__value> + (std::__miter_base(__first), std::__miter_base(__last), + __result)); + } + template + struct __copy_move_backward + { + template + static _BI2 + __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) + { + while (__first != __last) + *--__result = *--__last; + return __result; + } + }; + template<> + struct __copy_move_backward + { + template + static _BI2 + __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) + { + typename iterator_traits<_BI1>::difference_type __n; + for (__n = __last - __first; __n > 0; --__n) + *--__result = *--__last; + return __result; + } + }; + template + struct __copy_move_backward<_IsMove, true, random_access_iterator_tag> + { + template + static _Tp* + __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result) + { + const ptrdiff_t _Num = __last - __first; + if (_Num) + __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num); + return __result - _Num; + } + }; + template + inline _BI2 + __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result) + { + typedef typename iterator_traits<_BI1>::value_type _ValueType1; + typedef typename iterator_traits<_BI2>::value_type _ValueType2; + typedef typename iterator_traits<_BI1>::iterator_category _Category; + const bool __simple = (__is_pod(_ValueType1) + && __is_pointer<_BI1>::__value + && __is_pointer<_BI2>::__value + && __are_same<_ValueType1, _ValueType2>::__value); + return std::__copy_move_backward<_IsMove, __simple, + _Category>::__copy_move_b(__first, + __last, + __result); + } + template + inline _BI2 + __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result) + { + return _BI2(std::__copy_move_backward_a<_IsMove> + (std::__niter_base(__first), std::__niter_base(__last), + std::__niter_base(__result))); + } + template + inline _BI2 + copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) + { + + + + ; + return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value> + (std::__miter_base(__first), std::__miter_base(__last), + __result)); + } + template + inline typename + __gnu_cxx::__enable_if::__value, void>::__type + __fill_a(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __value) + { + for (; __first != __last; ++__first) + *__first = __value; + } + template + inline typename + __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type + __fill_a(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __value) + { + const _Tp __tmp = __value; + for (; __first != __last; ++__first) + *__first = __tmp; + } + template + inline typename + __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type + __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c) + { + const _Tp __tmp = __c; + __builtin_memset(__first, static_cast(__tmp), + __last - __first); + } + template + inline void + fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) + { + + ; + std::__fill_a(std::__niter_base(__first), std::__niter_base(__last), + __value); + } + template + inline typename + __gnu_cxx::__enable_if::__value, _OutputIterator>::__type + __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value) + { + for (; __n > 0; --__n, ++__first) + *__first = __value; + return __first; + } + template + inline typename + __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type + __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value) + { + const _Tp __tmp = __value; + for (; __n > 0; --__n, ++__first) + *__first = __tmp; + return __first; + } + template + inline typename + __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type + __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c) + { + std::__fill_a(__first, __first + __n, __c); + return __first + __n; + } + template + inline _OI + fill_n(_OI __first, _Size __n, const _Tp& __value) + { + + return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value)); + } + template + struct __equal + { + template + static bool + equal(_II1 __first1, _II1 __last1, _II2 __first2) + { + for (; __first1 != __last1; ++__first1, ++__first2) + if (!(*__first1 == *__first2)) + return false; + return true; + } + }; + template<> + struct __equal + { + template + static bool + equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2) + { + return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) + * (__last1 - __first1)); + } + }; + template + inline bool + __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2) + { + typedef typename iterator_traits<_II1>::value_type _ValueType1; + typedef typename iterator_traits<_II2>::value_type _ValueType2; + const bool __simple = (__is_integer<_ValueType1>::__value + && __is_pointer<_II1>::__value + && __is_pointer<_II2>::__value + && __are_same<_ValueType1, _ValueType2>::__value); + return std::__equal<__simple>::equal(__first1, __last1, __first2); + } + template + struct __lc_rai + { + template + static _II1 + __newlast1(_II1, _II1 __last1, _II2, _II2) + { return __last1; } + template + static bool + __cnd2(_II __first, _II __last) + { return __first != __last; } + }; + template<> + struct __lc_rai + { + template + static _RAI1 + __newlast1(_RAI1 __first1, _RAI1 __last1, + _RAI2 __first2, _RAI2 __last2) + { + const typename iterator_traits<_RAI1>::difference_type + __diff1 = __last1 - __first1; + const typename iterator_traits<_RAI2>::difference_type + __diff2 = __last2 - __first2; + return __diff2 < __diff1 ? __first1 + __diff2 : __last1; + } + template + static bool + __cnd2(_RAI, _RAI) + { return true; } + }; + template + struct __lexicographical_compare + { + template + static bool __lc(_II1, _II1, _II2, _II2); + }; + template + template + bool + __lexicographical_compare<_BoolType>:: + __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) + { + typedef typename iterator_traits<_II1>::iterator_category _Category1; + typedef typename iterator_traits<_II2>::iterator_category _Category2; + typedef std::__lc_rai<_Category1, _Category2> __rai_type; + __last1 = __rai_type::__newlast1(__first1, __last1, + __first2, __last2); + for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2); + ++__first1, ++__first2) + { + if (*__first1 < *__first2) + return true; + if (*__first2 < *__first1) + return false; + } + return __first1 == __last1 && __first2 != __last2; + } + template<> + struct __lexicographical_compare + { + template + static bool + __lc(const _Tp* __first1, const _Tp* __last1, + const _Up* __first2, const _Up* __last2) + { + const size_t __len1 = __last1 - __first1; + const size_t __len2 = __last2 - __first2; + const int __result = __builtin_memcmp(__first1, __first2, + std::min(__len1, __len2)); + return __result != 0 ? __result < 0 : __len1 < __len2; + } + }; + template + inline bool + __lexicographical_compare_aux(_II1 __first1, _II1 __last1, + _II2 __first2, _II2 __last2) + { + typedef typename iterator_traits<_II1>::value_type _ValueType1; + typedef typename iterator_traits<_II2>::value_type _ValueType2; + const bool __simple = + (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value + && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed + && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed + && __is_pointer<_II1>::__value + && __is_pointer<_II2>::__value); + return std::__lexicographical_compare<__simple>::__lc(__first1, __last1, + __first2, __last2); + } + template + _ForwardIterator + lower_bound(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __val) + { + typedef typename iterator_traits<_ForwardIterator>::value_type + _ValueType; + typedef typename iterator_traits<_ForwardIterator>::difference_type + _DistanceType; + + + ; + _DistanceType __len = std::distance(__first, __last); + _DistanceType __half; + _ForwardIterator __middle; + while (__len > 0) + { + __half = __len >> 1; + __middle = __first; + std::advance(__middle, __half); + if (*__middle < __val) + { + __first = __middle; + ++__first; + __len = __len - __half - 1; + } + else + __len = __half; + } + return __first; + } + template + inline _Size + __lg(_Size __n) + { + _Size __k; + for (__k = 0; __n != 0; __n >>= 1) + ++__k; + return __k - 1; + } + inline int + __lg(int __n) + { return sizeof(int) * 8 - 1 - __builtin_clz(__n); } + inline long + __lg(long __n) + { return sizeof(long) * 8 - 1 - __builtin_clzl(__n); } + inline long long + __lg(long long __n) + { return sizeof(long long) * 8 - 1 - __builtin_clzll(__n); } +} +namespace std __attribute__ ((__visibility__ ("default"))) { + template + inline bool + equal(_II1 __first1, _II1 __last1, _II2 __first2) + { + + + + ; + return std::__equal_aux(std::__niter_base(__first1), + std::__niter_base(__last1), + std::__niter_base(__first2)); + } + template + inline bool + equal(_IIter1 __first1, _IIter1 __last1, + _IIter2 __first2, _BinaryPredicate __binary_pred) + { + + + ; + for (; __first1 != __last1; ++__first1, ++__first2) + if (!bool(__binary_pred(*__first1, *__first2))) + return false; + return true; + } + template + inline bool + lexicographical_compare(_II1 __first1, _II1 __last1, + _II2 __first2, _II2 __last2) + { + typedef typename iterator_traits<_II1>::value_type _ValueType1; + typedef typename iterator_traits<_II2>::value_type _ValueType2; + + + + + ; + ; + return std::__lexicographical_compare_aux(std::__niter_base(__first1), + std::__niter_base(__last1), + std::__niter_base(__first2), + std::__niter_base(__last2)); + } + template + bool + lexicographical_compare(_II1 __first1, _II1 __last1, + _II2 __first2, _II2 __last2, _Compare __comp) + { + typedef typename iterator_traits<_II1>::iterator_category _Category1; + typedef typename iterator_traits<_II2>::iterator_category _Category2; + typedef std::__lc_rai<_Category1, _Category2> __rai_type; + + + ; + ; + __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2); + for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2); + ++__first1, ++__first2) + { + if (__comp(*__first1, *__first2)) + return true; + if (__comp(*__first2, *__first1)) + return false; + } + return __first1 == __last1 && __first2 != __last2; + } + template + pair<_InputIterator1, _InputIterator2> + mismatch(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2) + { + + + + ; + while (__first1 != __last1 && *__first1 == *__first2) + { + ++__first1; + ++__first2; + } + return pair<_InputIterator1, _InputIterator2>(__first1, __first2); + } + template + pair<_InputIterator1, _InputIterator2> + mismatch(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _BinaryPredicate __binary_pred) + { + + + ; + while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2))) + { + ++__first1; + ++__first2; + } + return pair<_InputIterator1, _InputIterator2>(__first1, __first2); + } +} + + + +extern "C++" { +namespace std +{ + class exception + { + public: + exception() throw() { } + virtual ~exception() throw(); + virtual const char* what() const throw(); + }; + class bad_exception : public exception + { + public: + bad_exception() throw() { } + virtual ~bad_exception() throw(); + virtual const char* what() const throw(); + }; + typedef void (*terminate_handler) (); + typedef void (*unexpected_handler) (); + terminate_handler set_terminate(terminate_handler) throw(); + void terminate() throw() __attribute__ ((__noreturn__)); + unexpected_handler set_unexpected(unexpected_handler) throw(); + void unexpected() __attribute__ ((__noreturn__)); + bool uncaught_exception() throw() __attribute__ ((__pure__)); +} +namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) { + void __verbose_terminate_handler(); +} +} +extern "C++" { +namespace std +{ + class bad_alloc : public exception + { + public: + bad_alloc() throw() { } + virtual ~bad_alloc() throw(); + virtual const char* what() const throw(); + }; + struct nothrow_t { }; + extern const nothrow_t nothrow; + typedef void (*new_handler)(); + new_handler set_new_handler(new_handler) throw(); +} +void* operator new(std::size_t) throw (std::bad_alloc); +void* operator new[](std::size_t) throw (std::bad_alloc); +void operator delete(void*) throw(); +void operator delete[](void*) throw(); +void* operator new(std::size_t, const std::nothrow_t&) throw(); +void* operator new[](std::size_t, const std::nothrow_t&) throw(); +void operator delete(void*, const std::nothrow_t&) throw(); +void operator delete[](void*, const std::nothrow_t&) throw(); +inline void* operator new(std::size_t, void* __p) throw() { return __p; } +inline void* operator new[](std::size_t, void* __p) throw() { return __p; } +inline void operator delete (void*, void*) throw() { } +inline void operator delete[](void*, void*) throw() { } +} +namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) { + using std::size_t; + using std::ptrdiff_t; + template + class new_allocator + { + public: + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef _Tp* pointer; + typedef const _Tp* const_pointer; + typedef _Tp& reference; + typedef const _Tp& const_reference; + typedef _Tp value_type; + template + struct rebind + { typedef new_allocator<_Tp1> other; }; + new_allocator() throw() { } + new_allocator(const new_allocator&) throw() { } + template + new_allocator(const new_allocator<_Tp1>&) throw() { } + ~new_allocator() throw() { } + pointer + address(reference __x) const { return &__x; } + const_pointer + address(const_reference __x) const { return &__x; } + pointer + allocate(size_type __n, const void* = 0) + { + return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp))); + } + void + deallocate(pointer __p, size_type) + { ::operator delete(__p); } + size_type + max_size() const throw() + { return size_t(-1) / sizeof(_Tp); } + void + construct(pointer __p, const _Tp& __val) + { ::new((void *)__p) _Tp(__val); } + void + destroy(pointer __p) { __p->~_Tp(); } + }; + template + inline bool + operator==(const new_allocator<_Tp>&, const new_allocator<_Tp>&) + { return true; } + template + inline bool + operator!=(const new_allocator<_Tp>&, const new_allocator<_Tp>&) + { return false; } +} +namespace std __attribute__ ((__visibility__ ("default"))) { + template + class allocator; + template<> + class allocator + { + public: + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef void* pointer; + typedef const void* const_pointer; + typedef void value_type; + template + struct rebind + { typedef allocator<_Tp1> other; }; + }; + template + class allocator: public __gnu_cxx::new_allocator<_Tp> + { + public: + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef _Tp* pointer; + typedef const _Tp* const_pointer; + typedef _Tp& reference; + typedef const _Tp& const_reference; + typedef _Tp value_type; + template + struct rebind + { typedef allocator<_Tp1> other; }; + allocator() throw() { } + allocator(const allocator& __a) throw() + : __gnu_cxx::new_allocator<_Tp>(__a) { } + template + allocator(const allocator<_Tp1>&) throw() { } + ~allocator() throw() { } + }; + template + inline bool + operator==(const allocator<_T1>&, const allocator<_T2>&) + { return true; } + template + inline bool + operator==(const allocator<_Tp>&, const allocator<_Tp>&) + { return true; } + template + inline bool + operator!=(const allocator<_T1>&, const allocator<_T2>&) + { return false; } + template + inline bool + operator!=(const allocator<_Tp>&, const allocator<_Tp>&) + { return false; } + template + struct __alloc_swap + { static void _S_do_it(_Alloc&, _Alloc&) { } }; + template + struct __alloc_swap<_Alloc, false> + { + static void + _S_do_it(_Alloc& __one, _Alloc& __two) + { + if (__one != __two) + swap(__one, __two); + } + }; + template + struct __alloc_neq + { + static bool + _S_do_it(const _Alloc&, const _Alloc&) + { return false; } + }; + template + struct __alloc_neq<_Alloc, false> + { + static bool + _S_do_it(const _Alloc& __one, const _Alloc& __two) + { return __one != __two; } + }; +} + +namespace std __attribute__ ((__visibility__ ("default"))) { + struct _List_node_base + { + _List_node_base* _M_next; + _List_node_base* _M_prev; + static void + swap(_List_node_base& __x, _List_node_base& __y) throw (); + void + _M_transfer(_List_node_base * const __first, + _List_node_base * const __last) throw (); + void + _M_reverse() throw (); + void + _M_hook(_List_node_base * const __position) throw (); + void + _M_unhook() throw (); + }; + template + struct _List_node : public _List_node_base + { + _Tp _M_data; + }; + template + struct _List_iterator + { + typedef _List_iterator<_Tp> _Self; + typedef _List_node<_Tp> _Node; + typedef ptrdiff_t difference_type; + typedef std::bidirectional_iterator_tag iterator_category; + typedef _Tp value_type; + typedef _Tp* pointer; + typedef _Tp& reference; + _List_iterator() + : _M_node() { } + explicit + _List_iterator(_List_node_base* __x) + : _M_node(__x) { } + reference + operator*() const + { return static_cast<_Node*>(_M_node)->_M_data; } + pointer + operator->() const + { return &static_cast<_Node*>(_M_node)->_M_data; } + _Self& + operator++() + { + _M_node = _M_node->_M_next; + return *this; + } + _Self + operator++(int) + { + _Self __tmp = *this; + _M_node = _M_node->_M_next; + return __tmp; + } + _Self& + operator--() + { + _M_node = _M_node->_M_prev; + return *this; + } + _Self + operator--(int) + { + _Self __tmp = *this; + _M_node = _M_node->_M_prev; + return __tmp; + } + bool + operator==(const _Self& __x) const + { return _M_node == __x._M_node; } + bool + operator!=(const _Self& __x) const + { return _M_node != __x._M_node; } + _List_node_base* _M_node; + }; + template + struct _List_const_iterator + { + typedef _List_const_iterator<_Tp> _Self; + typedef const _List_node<_Tp> _Node; + typedef _List_iterator<_Tp> iterator; + typedef ptrdiff_t difference_type; + typedef std::bidirectional_iterator_tag iterator_category; + typedef _Tp value_type; + typedef const _Tp* pointer; + typedef const _Tp& reference; + _List_const_iterator() + : _M_node() { } + explicit + _List_const_iterator(const _List_node_base* __x) + : _M_node(__x) { } + _List_const_iterator(const iterator& __x) + : _M_node(__x._M_node) { } + reference + operator*() const + { return static_cast<_Node*>(_M_node)->_M_data; } + pointer + operator->() const + { return &static_cast<_Node*>(_M_node)->_M_data; } + _Self& + operator++() + { + _M_node = _M_node->_M_next; + return *this; + } + _Self + operator++(int) + { + _Self __tmp = *this; + _M_node = _M_node->_M_next; + return __tmp; + } + _Self& + operator--() + { + _M_node = _M_node->_M_prev; + return *this; + } + _Self + operator--(int) + { + _Self __tmp = *this; + _M_node = _M_node->_M_prev; + return __tmp; + } + bool + operator==(const _Self& __x) const + { return _M_node == __x._M_node; } + bool + operator!=(const _Self& __x) const + { return _M_node != __x._M_node; } + const _List_node_base* _M_node; + }; + template + class _List_base + { + protected: + typedef typename _Alloc::template rebind<_List_node<_Tp> >::other + _Node_alloc_type; + typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; + struct _List_impl + : public _Node_alloc_type + { + _List_node_base _M_node; + _List_impl() + : _Node_alloc_type(), _M_node() + { } + _List_impl(const _Node_alloc_type& __a) + : _Node_alloc_type(__a), _M_node() + { } + }; + _List_impl _M_impl; + _List_node<_Tp>* + _M_get_node() + { return _M_impl._Node_alloc_type::allocate(1); } + void + _M_put_node(_List_node<_Tp>* __p) + { _M_impl._Node_alloc_type::deallocate(__p, 1); } + public: + typedef _Alloc allocator_type; + _Node_alloc_type& + _M_get_Node_allocator() + { return *static_cast<_Node_alloc_type*>(&this->_M_impl); } + const _Node_alloc_type& + _M_get_Node_allocator() const + { return *static_cast(&this->_M_impl); } + _Tp_alloc_type + _M_get_Tp_allocator() const + { return _Tp_alloc_type(_M_get_Node_allocator()); } + allocator_type + get_allocator() const + { return allocator_type(_M_get_Node_allocator()); } + _List_base() + : _M_impl() + { _M_init(); } + _List_base(const allocator_type& __a) + : _M_impl(__a) + { _M_init(); } + ~_List_base() + { _M_clear(); } + void + _M_clear(); + void + _M_init() + { + this->_M_impl._M_node._M_next = &this->_M_impl._M_node; + this->_M_impl._M_node._M_prev = &this->_M_impl._M_node; + } + }; + template > + class list : protected _List_base<_Tp, _Alloc> + { + typedef typename _Alloc::value_type _Alloc_value_type; + + + typedef _List_base<_Tp, _Alloc> _Base; + typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; + public: + typedef _Tp value_type; + typedef typename _Tp_alloc_type::pointer pointer; + typedef typename _Tp_alloc_type::const_pointer const_pointer; + typedef typename _Tp_alloc_type::reference reference; + typedef typename _Tp_alloc_type::const_reference const_reference; + typedef _List_iterator<_Tp> iterator; + typedef _List_const_iterator<_Tp> const_iterator; + typedef std::reverse_iterator const_reverse_iterator; + typedef std::reverse_iterator reverse_iterator; + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef _Alloc allocator_type; + protected: + typedef _List_node<_Tp> _Node; + using _Base::_M_impl; + using _Base::_M_put_node; + using _Base::_M_get_node; + using _Base::_M_get_Tp_allocator; + using _Base::_M_get_Node_allocator; + + public: + + + iterator + begin() + { return iterator(this->_M_impl._M_node._M_next); } + const_iterator + begin() const + { return const_iterator(this->_M_impl._M_node._M_next); } + iterator + end() + { return iterator(&this->_M_impl._M_node); } + + void + remove(const _Tp& __value); + template + void + remove_if(_Predicate); + + void + _M_erase(iterator __position) + { + __position._M_node->_M_unhook(); + _Node* __n = static_cast<_Node*>(__position._M_node); + _M_get_Tp_allocator().destroy(&__n->_M_data); + _M_put_node(__n); + } + void + _M_check_equal_allocators(list& __x) + { + if (std::__alloc_neq:: + _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator())) + ; + } + }; + + +} +namespace std __attribute__ ((__visibility__ ("default"))) { + template + void + list<_Tp, _Alloc>:: + remove(const value_type& __value) + { + iterator __first = begin(); + iterator __last = end(); + iterator __extra = __last; + while (__first != __last) + { + iterator __next = __first; + ++__next; + if (*__first == __value) + { + if (&*__first != &__value) + _M_erase(__first); + else + __extra = __first; + } + __first = __next; + } + if (__extra != __last) + _M_erase(__extra); + } +} +class Unit { +public: + int dummy; +}; +class Building +{ +public: + __attribute__((transaction_callable)) void removeUnitFromInside(Unit* unit); + std::list unitsInside; +}; + +void Building::removeUnitFromInside(Unit* unit) +{ + unitsInside.remove(unit); +}