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

[Jonathan Wakely]

>>-  template<typename Tp>
>>+  template<typename Tp, typename _Alloc = std::allocator<Tp> >

Also, there's no need to uglify the name "Alloc" in our testsuite
code, it doesn't have to use the implementation namespace.

>>    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;

Also, you should check here that is_same<Tp, _Alloc::value_type>.

That check should work for C++03 too (so can't use is_same or
static_assert) so maybe:

  template<typename T, typename Alloc,
           typename T2 = typename Alloc::value_type>
  struct check_value_type;

  template<typename T, typename Alloc>
  struct check_value_type<T, Alloc, T>
  {
    typedef T value_type;
  };

Then use 

  typedef typename check_value_type<Tp, Alloc>::value_type value_type;

Alternatively, you could redefine the uneq_allocator and
propagating_allocator to take an allocator as their first parameter:

  template<typename Alloc>
    class uneq_allocator : public Alloc
    {
      typedef Alloc inner_allocator;
      typedef __gnu_cxx::__alloc_traits<Alloc> inner_traits;

    public:
      template<typename U>
        struct rebind
        {
          typedef typename inner_traits::template rebind<U>::other
            other_inner;
          typedef uneq_allocator<other_inner> other;
        }

      ...
    };

But that would require a lot of changes to the testsuite, so I think
having the value_type and an allocator as template parameters is
better (as long as there's a check that the types agree).