Re: [patch] libstdc++/29988 Rb_Tree reuse allocated nodes

[Jonathan Wakely <jwakely at redhat dot com>]

On 11/06/14 09:17 +0200, François Dumont wrote:
> Hi
>
>    Here is the patch to reuse allocated nodes in the _Rb_tree 
> implementation like it is done in the _Hashtable. I have associated it 
> to bugzilla 29988 even if my patch also cover the new C++11 move 
> assign operator and assignment from initialization list. I took a look 
> to the code proposed in 29988 and it is more or less what I have done 
> even if I benefit from C++11 lambdas to reuse more code.
>
>    I have changed propagating_allocator so that we can combine it 
> with any other allocator. I combined it with the tracker_allocator so 
> that I can control propagation of the allocator and at the same time 
> track allocations.

Here are some comments on the testsuite changes, I'm still reviewing
the rest.



> Property changes on: testsuite/23_containers/map/allocator/init-list.cc
> ___________________________________________________________________
> Added: svn:executable
> ## -0,0 +1 ##
> +*
> \ No newline at end of property

Several files are executable, please correct that.


> Index: testsuite/util/testsuite_allocator.h
> ===================================================================
> --- testsuite/util/testsuite_allocator.h	(revision 211388)
> +++ testsuite/util/testsuite_allocator.h	(working copy)
> @@ -244,26 +244,30 @@
>     }
>   };
>
> -  template<typename Tp>
> +  template<typename Tp, typename _Alloc = std::allocator<Tp> >
>     class uneq_allocator
> -    : private uneq_allocator_base
> +    : private uneq_allocator_base,
> +      public _Alloc
>     {
>     public:
> -      typedef std::size_t                         size_type;
> -      typedef std::ptrdiff_t                      difference_type;
> -      typedef Tp*                                 pointer;
> -      typedef const Tp*                           const_pointer;
> -      typedef Tp&                                 reference;
> -      typedef const Tp&                           const_reference;
> -      typedef Tp                                  value_type;
> +      typedef typename _Alloc::size_type	size_type;
> +      typedef typename _Alloc::difference_type	difference_type;
> +      typedef typename _Alloc::pointer		pointer;
> +      typedef typename _Alloc::const_pointer	const_pointer;
> +      typedef typename _Alloc::reference	reference;
> +      typedef typename _Alloc::const_reference	const_reference;
> +      typedef typename _Alloc::value_type	value_type;

For a C++11 allocator is no guarantee any of these members is present
except value_type.

Use __gnu_cxx::__alloc_traits to access those members in a way that
works for both C++03 and C++11 allocators.

Please try using uneq_allocator<int, SimpleAllocator<int>> and fix
everything that fails.

You can use the __gnu_test::SimpleAlloc to verify you do not depend on
anything that is not mandatory for allocators. It might be useful to
have a function in testsuite_allocator.h that checks the minimal
allocator requirements, and maybe call it from the constructor of the
various test allocators to ensure our test allocators are valid.


> #if __cplusplus >= 201103L
> -      typedef std::true_type                      propagate_on_container_swap;
> +      typedef std::true_type			propagate_on_container_swap;
> #endif
>
>       template<typename Tp1>
> -        struct rebind
> -	{ typedef uneq_allocator<Tp1> other; };
> +	struct rebind
> +	{
> +	  typedef uneq_allocator<Tp1,
> +			typename _Alloc::template rebind<Tp1>::other> other;
> +	};
>
>       uneq_allocator() _GLIBCXX_USE_NOEXCEPT
>       : personality(0) { }
> @@ -272,7 +276,9 @@
>       : personality(person) { }
>       
>       template<typename Tp1>
> -        uneq_allocator(const uneq_allocator<Tp1>& b) _GLIBCXX_USE_NOEXCEPT
> +	uneq_allocator(const uneq_allocator<Tp1,
> +		       typename _Alloc::template rebind<Tp1>::other>& b)
> +	_GLIBCXX_USE_NOEXCEPT
> 	: personality(b.get_personality()) { }
>
>       ~uneq_allocator() _GLIBCXX_USE_NOEXCEPT

This is an invalid use of rebind.

You cannot rely on the presence of a nested rebind member, you need to
use __gnu_cxx::__alloc_traits::rebind instead.


> @@ -281,20 +287,9 @@
>       int get_personality() const { return personality; }
>       
>       pointer
> -      address(reference x) const _GLIBCXX_NOEXCEPT
> -      { return std::__addressof(x); }
> -    
> -      const_pointer
> -      address(const_reference x) const _GLIBCXX_NOEXCEPT
> -      { return std::__addressof(x); }
> -
> -      pointer
> -      allocate(size_type n, const void* = 0)
> +      allocate(size_type n, const void* hint = 0)
>       { 
> -	if (__builtin_expect(n > this->max_size(), false))
> -	  std::__throw_bad_alloc();
> -	
> -	pointer p = static_cast<Tp*>(::operator new(n * sizeof(Tp)));
> +	pointer p = _Alloc::allocate(n, hint);
> 	try
> 	  {
> 	    get_map().insert(map_type::value_type(reinterpret_cast<void*>(p),

> @@ -364,15 +339,14 @@
>       swap(uneq_allocator& a, uneq_allocator& b)
>       { std::swap(a.personality, b.personality); } 
>       
> -      template<typename Tp1>
> -        friend inline bool
> -        operator==(const uneq_allocator& a, const uneq_allocator<Tp1>& b)
> -        { return a.personality == b.personality; }
> +      friend inline bool
> +      operator==(const uneq_allocator& a,
> +		 const uneq_allocator& b)
> +      { return a.personality == b.personality; }
>
> -      template<typename Tp1>
> -        friend inline bool
> -        operator!=(const uneq_allocator& a, const uneq_allocator<Tp1>& b)
> -        { return !(a == b); }
> +      friend inline bool
> +      operator!=(const uneq_allocator& a, const uneq_allocator& b)
> +      { return !(a == b); }
>       
>       int personality;
>     };

This looks wrong, unless I'm mistaken this would no longer work:

   uneq_allocator<A> a;
   uneq_allocator<B> b;
   a == b;

That is required by the Allocator requirements.



> @@ -393,7 +367,11 @@
>       // default allocator_traits::rebind_alloc would select
>       // uneq_allocator::rebind so we must define rebind here
>       template<typename Up>
> -	struct rebind { typedef propagating_allocator<Up, Propagate> other; };
> +	struct rebind
> +	{
> +	  typedef propagating_allocator<Up, Propagate,
> +		typename _Alloc::template rebind<Up>::other> other;
> +	};
>
>       propagating_allocator(int i) noexcept
>       : base_alloc(i)
> @@ -400,8 +378,9 @@
>       { }
>
>       template<typename Up>
> -	propagating_allocator(const propagating_allocator<Up, Propagate>& a)
> -       	noexcept
> +	propagating_allocator(const propagating_allocator<Up, Propagate,
> +			      typename _Alloc::template rebind<Up>::other>& a)
> +	noexcept
> 	: base_alloc(a)
> 	{ }

Invalid use of rebind.


> Property changes on: testsuite/23_containers/set/allocator/init-list.cc
> ___________________________________________________________________
> Added: svn:executable
> ## -0,0 +1 ##
> +*
> \ No newline at end of property


> Property changes on: testsuite/23_containers/multimap/allocator/init-list.cc
> ___________________________________________________________________
> Added: svn:executable
> ## -0,0 +1 ##
> +*
> \ No newline at end of property


> Property changes on: testsuite/23_containers/multiset/allocator/init-list.cc
> ___________________________________________________________________
> Added: svn:executable
> ## -0,0 +1 ##
> +*
> \ No newline at end of property

More executable files.