[boost] Re: shared_ptr doubts

From: David Abrahams (dave_at_[hidden])
Date: 2005-02-21 10:43:51

Beman Dawes <bdawes_at_[hidden]> writes:

> 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?

It's fine to use it conditionally in portable code, providing you have
a (non-portable, obviously) way to find out if the low bit of the
pointer is needed.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com