[boost] Re: change to linked_ptr release

From: Mark Borgerding (markab_at_[hidden])
Date: 2000-02-07 13:22:56

"gavin collings" <gcolling-_at_[hidden]> wrote: 
original article:http://www.egroups.com/group/boost/?start=2121
> > No specific destruction order is necessary to pass around the
> message. 
> > The message itself is not used until there is only one node on the
> > list.  So the actual node that carries it is unimportant (the
circular
> > list helps here).  Along as one node knows the message, it is not
> lost.
> >  If a node is leaving the list and has the message, it passes it on
to
> > its neighbor.  The direction is irrelevant.  It is true that in some
> > circumstances, the message might need to be passed to evey node on
the
> > list, but each of these operations would be constant time.  This
lazy
> > evaluation allows all operations to be limited to O(1).
> 
> Ah yes, quite neat.  I haven't properly explored using the list as a
> notification mechanism, this looks like a good application of it,
> though.  Shall we split the difference and say N/2 on average then ;)
> I'm still a little hesitant about leaving all those potentially
> dangling references around, though.

All the operations of linked_ptr are O(1).

The time required to make a call to release() is constant, it does not
matter if there are 2 nodes or 2 million nodes in the linked_ptr list.

It is true that because of a call to release, each node in the list
might have to do a tiny bit of work at some later time, this still does
not account into the efficiency of the individual operation.  Each of
the subsequent operations is also O(1).

An analogy is the ios_base::flags(fmtflags) operation.  A call to this
can affect the time required for subsequent operations.
A call to ios_base::flags(boolalpha) will cause every bool inserted to
the stream to take longer. 4 or 5 chars will be inserted instead of 1.
But the complexity of ios_base::flags(fmtflags) is still O(1).

> 
> The largest alignment requirement of any member is 4 bytes (pointer). 
> The 8 bytes you're talking of is the maximum amount of padding that
> will be inserted to bring about this alignment (/Zp option).  That is
> set to 8 bytes in my VC project, I still get a 12 byte linked_ptr
> though - apparently no padding is necessary.
> 

You are right.  Either I am dreaming things or I did something wrong
the first time around.  I remember comparing the releasable vs.
non-releasable linked_ptrs and saw that they were both 16 bytes long. 
But now when I try taking out the bool, the size shrinks back down to
12 bytes as you said.  

So adding the bool expands linked_ptr by 4 bytes unless packing
alignment of 1 byte is specified, in which case the size becomes 13.
(or 2 --> 14)