libstdc++: Add fancy pointer support to std::map and std::set [PR57272]

libstdc++: Add fancy pointer support to std::map and std::set [PR57272]

The fancy allocator pointer type support is added to std::map,
std::multimap, std::multiset and std::set through the underlying
std::_Rb_tree class.

To respect ABI a new parralel hierarchy of node types has been added.
This change introduces new class template parameterized on the
allocator's void_pointer type, __rb_tree::_Node_base, and new class
templates parameterized on the allocator's pointer type, __rb_tree::_Node,
__rb_tree::_Iterator. The iterator class template is used for both
iterator and const_iterator. Whether std::_Rb_tree<K, V, KoV, C, A>
should use the old _Rb_tree_node<V> or new __rb_tree::_Node<A::pointer>
type family internally is controlled by a new __rb_tree::_Node_traits
traits template.

Because std::pointer_traits and std::__to_address are not defined for
C++98, there is no way to support fancy pointers in C++98. For C++98 the
_Node_traits traits always choose the old _Rb_tree_node family.

In case anybody is currently using std::_Rb_tree with an allocator that
has a fancy pointer, this change would be an ABI break, because their
std::_Rb_tree instantiations would start to (correctly) use the fancy
pointer type. If the fancy pointer just contains a single pointer and so
has the same size, layout, and object representation as a raw pointer,
the code might still work (despite being an ODR violation). But if their
fancy pointer has a different representation, they would need to
recompile all their code using that allocator with std::_Rb_tree. Because
std::_Rb_tree will never use fancy pointers in C++98 mode, recompiling
everything to use fancy pointers isn't even possible if mixing C++98 and
C++11 code that uses std::_Rb_tree. To alleviate this problem, compiling
with -D_GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE=0 will force std::_Rb_tree to
have the old, non-conforming behaviour and use raw pointers internally.
For testing purposes, compiling with -D_GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE=9001
will force std::_Rb_tree to always use the new node types. This macro is
currently undocumented, which needs to be fixed.

As _Rb_tree is using _Base_ptr to represent the tree this change also
simplifies the implementation by removing all the const pointer types
and associated methods.

libstdc++-v3/ChangeLog:

	PR libstdc++/57272
	* include/bits/stl_tree.h
	[_GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE]: New macro to control usage of the
	code required to support fancy allocator pointer type.
	(_Rb_tree_node_base::_Const_Base_ptr): Remove.
	(_Rb_tree_node_base::_S_minimum, _Rb_tree_node_base::_S_maximum): Remove
	overloads for _Const_Base_ptr.
	(_Rb_tree_node_base::_M_base_ptr()): New.
	(_Rb_tree_node::_Link_type): Remove.
	(_Rb_tree_node::_M_node_ptr()): New.
	(__rb_tree::_Node_base<>): New.
	(__rb_tree::_Header<>): New.
	(__rb_tree::_Node<>): New.
	(_Rb_tree_increment(const _Rb_tree_node_base*)): Remove declaration.
	(_Rb_tree_decrement(const _Rb_tree_node_base*)): Remove declaration.
	(_Rb_tree_iterator<>::_Self): Remove.
	(_Rb_tree_iterator<>::_Link_type): Rename into...
	(_Rb_tree_iterator<>::_Node_ptr): ...this.
	(_Rb_tree_const_iterator<>::_Link_type): Rename into...
	(_Rb_tree_const_iterator<>::_Node_ptr): ...this.
	(_Rb_tree_const_iterator<>::_M_const_cast): Remove.
	(_Rb_tree_const_iterator<>::_M_node): Change type into _Base_ptr.
	(__rb_tree::_Iterator<>): New.
	(__rb_tree::_Node_traits<>): New.
	(_Rb_tree<>::_Node_base, _Rb_tree::_Node): New.
	(_Rb_tree<>::_Link_type): Rename into...
	(_Rb_tree<>::_Node_ptr): ...this.
	(_Rb_tree<>::_Const_Base_ptr, _Rb_tree<>::_Const_Node_ptr): Remove.
	(_Rb_tree<>::_M_mbegin): Remove.
	(_Rb_tree<>::_M_begin_node()): New.
	(_S_key(const _Node&)): New.
	(_S_key(_Base_ptr)): New, call latter.
	(_S_key(_Node_ptr)): Likewise.
	(_Rb_tree<>::_S_left(_Const_Base_ptr)): Remove.
	(_Rb_tree<>::_S_right(_Const_Base_ptr)): Remove.
	(_Rb_tree<>::_S_maximum(_Const_Base_ptr)): Remove.
	(_Rb_tree<>::_S_minimum(_Const_Base_ptr)): Remove.
	* testsuite/23_containers/map/allocator/ext_ptr.cc: New test case.
	* testsuite/23_containers/multimap/allocator/ext_ptr.cc: New test case.
	* testsuite/23_containers/multiset/allocator/ext_ptr.cc: New test case.
	* testsuite/23_containers/set/allocator/ext_ptr.cc: New test case.
	* testsuite/23_containers/set/requirements/explicit_instantiation/alloc_ptr.cc:
	New test case.
	* testsuite/23_containers/set/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
	New test case.