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).
+ template<typename _Arg>
+ __node_type*
+#if __cplusplus < 201103L
+ operator()(const _Arg& __arg) const
+#else
+ operator()(_Arg&& __arg) const
+#endif
Does this need to be const?
I don't think it does (if you change the function templates taking a
const _NodeGen& to take _NodeGen& instead).
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.
