[patch] libstdc++/29988 Rb_Tree reuse allocated nodes
Jonathan Wakely
jwakely@redhat.com
Wed Jun 11 09:44:00 GMT 2014
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.
More information about the Gcc-patches
mailing list