Re: [boost] Re: shared_ptr doubts

From: Beman Dawes (bdawes_at_[hidden])
Date: 2005-02-17 20:45:23

At 11:11 AM 2/15/2005, Howard Hinnant wrote:

 >On Feb 15, 2005, at 9:49 AM, David Abrahams wrote:
 >
 >>> Absolutely, all designs have certain irreducible overhead - I didn't
 >>> mean to imply otherwise. In the case of std::map, one should expect
 >>> an instance to be on the large-ish side. Also, one should expect the
 >>> per node overhead to be two pointers and probably another word for
 >>> the tree balancing algorithm.
 >>
 >> You don't need any storage for rebalancing.  Typical map nodes have 3
 >> pointers: parent, left child, and right child.
 >
 >If it is a red-black tree, you need to store the color of each node.
 >This information requires 1 bit, which can easily be padded to a word.
 >If it is a AVL tree, each node needs to store its tilt.  This
 >information requires 2 bits.
 >
 >Or is there a new technique I'm about to learn about? :-)

I don't know of any 100% portable technique, but on many platforms pointers 
to heap allocated memory within a node never have one or more of the 
low-order bits on. This opens those bits up to be used as color or similar 
flags, at the cost of having to "and" them off before dereferencing the 
pointer. If the pointer is wrapped in a class, and can only be accessed by 
member functions, then there is no chance of inadvertently forgetting the 
"and", and an assert can be done on construction to verify the low-order 
bits involved are actually zero. A bit ugly and I'd hate to see it used in 
portable Boost code, but if you are writing library code for a specific 
platform, why not?

--Beman