vicente.botet escribió:
Hi,
I have recently found in the blog of Joaquin the following optimization consisting in embed a bit into the representation of a pointer. Please read it, it is not too long (http://bannalia.blogspot.com/2008/11/optimizing-red-black-tree-color-bits.ht...)
I was wondering if it would be interesting to provide some generic template classes making easier this kind of optimization.
Take a look at http://www.boost.org/boost/boost/intrusive/pointer_plus_bits.hpp for some helper classes used in Intrusive that might be useful: The method is being used to embed also N bits in offset_ptr and other smart pointers, see: http://www.boost.org/boost/intrusive/pointer_plus_bits.hpp http://www.boost.org/boost/interprocess/offset_ptr.hpp then the container select the correct node depending on the alignment of the generic pointer type: //Inherit from the detail::link_dispatch depending on the embedding capabilities template<class VoidPointer, bool OptimizeSize = false> struct rbtree_node_traits : public rbtree_node_traits_dispatch < VoidPointer , OptimizeSize && (max_pointer_plus_bits < VoidPointer , detail::alignment_of<compact_rbtree_node<VoidPointer>
::value >::value >= 1) > {};
the same happens with AVL trees but in this case we need 2 bits. Best, Ion