Index: include/bits/stl_tree.h
===================================================================
--- include/bits/stl_tree.h (revision 211388)
+++ include/bits/stl_tree.h (working copy)
@@ -330,6 +330,111 @@
const _Rb_tree_const_iterator<_Val>& __y)
_GLIBCXX_NOEXCEPT
{ return __x._M_node != __y._M_node; }
+ // Functor recycling a pool of nodes and using allocation once the
pool is
+ // empty.
+ template<typename _RbTree>
+ struct _Rb_tree_reuse_or_alloc_node
+ {
Is there a reason to define this and _Rb_tree_alloc_node as
namespace-scope class templates, rather than non-template members of
_Rb_tree?
They wouldn't need to be friends if they were members, and you
wouldn't need a typedef for _Rb_tree_alloc_node<_Rb_tree> because it
would just be called _Rb_tree_alloc_node.
+ private:
+ typedef _RbTree __rb_tree;
This typedef doesn't seem useful, it's only used once and is more
characters than "_RbTree". If the class was a member of _Rb_tree it
could just use that name.
+ typedef _Rb_tree_node<typename _RbTree::value_type> __node_type;
If it was a member the value_type name would be in scope.
+ public:
+ _Rb_tree_reuse_or_alloc_node(const _Rb_tree_node_base& __header,
+ __rb_tree& __t)
+ : _M_root(__header._M_parent), _M_nodes(__header._M_right),
_M_t(__t)
+ {
+ if (_M_root)
+ _M_root->_M_parent = 0;
+ else
+ _M_nodes = 0;
+ }
+
+ ~_Rb_tree_reuse_or_alloc_node()
+ { _M_t._M_erase(static_cast<__node_type*>(_M_root)); }
This type needs to be non-copyable, or unintentional copies would
erase all the nodes and leave nothing to be reused (which might be
difficult to detect as it would only affect performance, not
correctness).
That means the members of this type don't need to be 'mutable'.
+ typedef _Rb_tree_node_base __node_base;
I'm not sure this typedef is useful either, it just means an extra
name to remember when reading the code, when _Rb_tree_node_base is
already in scope and probably understood by readers of the code.
+ mutable __node_base* _M_root;
+ mutable __node_base* _M_nodes;
These members should be of type _Rb_tree::_Base_ptr, not __node_base*,
because that's the type _Rb_tree::_M_right is declared as.
I have a work-in-progress patch to make _Rb_tree use
allocator_traits<_Node_allocator>::pointer for _Link_type, which
might not be the same type as _Rb_tree_node<Val>*, so it is important
to consistently use the _Base_ptr and _Link_type typedefs not the
underlying types they refer to (because those underlying types are
going to change soon).
+ _RbTree& _M_t;
+ };
+
+ // Functor similar to the previous one but without any pool of
node to recycle.
+ template<typename _RbTree>
+ struct _Rb_tree_alloc_node
Again, I think this should be a member of _Rb_tree.
+ {
+ private:
+ typedef _Rb_tree_node<typename _RbTree::value_type> __node_type;
This typedef should be removed.
+
+ public:
+ _Rb_tree_alloc_node(_RbTree& __t)
+ : _M_t(__t) { }
+
+ template<typename _Arg>
+ __node_type*
This function should return _Rb_tree::_Link_type because that's what
_M_create_node returns.
+#if __cplusplus < 201103L
+ operator()(const _Arg& __arg) const
+#else
+ operator()(_Arg&& __arg) const
+#endif
+ { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
@@ -349,6 +454,12 @@
rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
+ template<typename _RT>
+ friend struct _Rb_tree_alloc_node;
+ typedef _Rb_tree_alloc_node<_Rb_tree> __alloc_node_t;
+ template<typename _RT>
+ friend struct _Rb_tree_reuse_or_alloc_node;
+ typedef _Rb_tree_reuse_or_alloc_node<_Rb_tree>
__reuse_or_alloc_node_t;
These friend declarations and typedefs become unnecessary.
@@ -389,44 +500,55 @@
{ _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
#if __cplusplus < 201103L
- _Link_type
- _M_create_node(const value_type& __x)
+ void
+ _M_construct_node(_Link_type __node, const value_type& __x)
{
- _Link_type __tmp = _M_get_node();
__try
- { get_allocator().construct(__tmp->_M_valptr(), __x); }
+ { get_allocator().construct(__node->_M_valptr(), __x); }
__catch(...)
{
- _M_put_node(__tmp);
+ _M_put_node(__node);
__throw_exception_again;
}
+ }
+
+ _Link_type
+ _M_create_node(const value_type& __x)
+ {
+ _Link_type __tmp = _M_get_node();
+ _M_construct_node(__tmp, __x);
return __tmp;
}
void
_M_destroy_node(_Link_type __p)
- {
- get_allocator().destroy(__p->_M_valptr());
- _M_put_node(__p);
- }
+ { get_allocator().destroy(__p->_M_valptr()); }
#else
template<typename... _Args>
- _Link_type
- _M_create_node(_Args&&... __args)
+ void
+ _M_construct_node(_Link_type __node, _Args&&... __args)
{
- _Link_type __tmp = _M_get_node();
__try
{
- ::new(__tmp) _Rb_tree_node<_Val>;
+ ::new(__node) _Rb_tree_node<_Val>();
This should not be value-initialized.
In C++11 all that does is zero out the __aligned_buffer's
uninitialized storage, which is a waste of time as we're about to
overwrite it anyway in the construct(). If you have a large
value_type (e.g. std::map<int, std::array<double,1000>>) the redundant
initialization has a measurable cost and we've had bug reports for
similar code.
@@ -514,11 +651,11 @@
{ return this->_M_impl._M_header._M_right; }
_Link_type
- _M_begin() _GLIBCXX_NOEXCEPT
+ _M_begin() const _GLIBCXX_NOEXCEPT
{ return
static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
What's the purpose of this change?
Although it can be 'const' it is consistent with the usual
begin()/end() functions that the functions returning a mutable iterator
are non-const and the functions returning a constant iterator are const.
_Const_Link_type
- _M_begin() const _GLIBCXX_NOEXCEPT
+ _M_cbegin() const _GLIBCXX_NOEXCEPT
{
return static_cast<_Const_Link_type>
(this->_M_impl._M_header._M_parent);
@@ -529,7 +666,7 @@
{ return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); }
_Const_Link_type
- _M_end() const _GLIBCXX_NOEXCEPT
+ _M_cend() const _GLIBCXX_NOEXCEPT
{ return
reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); }
static const_reference
I'm not very comfortable with this renaming.
Having consistent _M_begin() functions allows using them in template
code that doesn't care if it's using the const or non-const version.