[boost] Re: change to linked_ptr release

From: Mark Borgerding (markab_at_[hidden])
Date: 2000-02-07 10:21:34

"gavin collings" <gcolling-_at_[hidden]> wrote: 
original article:http://www.egroups.com/group/boost/?start=2117
> > ***  release()
> > I added a release() function that allows the user to delete a
pointer
> > instead of the chain of linked_ptrs.  The "released" message is
> > passed on to the "left" neighbor when a node leaves the list. This
> > maintains the O(1) complexity.
> 
> Well, technically, it's still O(N), but it just doesn't happen all at
> once; if everything is going to work, the message has to pass around
> the entire list (otherwise one of the nodes will delete it in its
> destructor.
> 
> "If everything is going to work" Hmmm.  Everything has to work, so the
> message must be passed to all nodes.  Not doing it on the initial call
> to release is dangerous as you point out.  In fact, leaving things as
> they are means that linked_ptr clients would need to have detailed
> knowledge of the implementation of linked_ptr in order to use
release()
> at all, since they would have to set up the list so that nodes are
> destroyed in order, right to left, as it were.  I'm sure this could be
> arranged for nested block usage, but it won't be true generally with
> temporaries, function calls and returns...

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).

Scenario:
N linked_ptrs ( 1,2,...,N ) which  all point to the same object.
1 is left of 2, 2 is left of 3, .... , N is left of 1.

Note: the choice of node #1 is arbitrary since it is a circular list.

linked_ptr #1 has its release() called.
   1  #1's released bool is set to true
   2  #1's leave_list is called
   3 if the released flag is set (which it is), then the left node's
(#N) released flag is set true.
   4 ptr is set to null
   5 release returns the original ptr

So now, there are N-1 linked_ptrs, and one of them knows not to delete
the ptr.

There are three cases.
a) The one that knows the message is reset.
      In this case, the "released" message is passed left.

b) The one to the right of the one that knows is reset
      It has no message to pass along, so it does not ovewrite the left
neighbor's message.  If by some chance, both had the message, then the
assignment would be redundant and have no effect.

c) Some other node is reset
      This has no effect on the node that has the message.

Take one down. Pass it around. N-1 linked_ptr<beer> on the wall. 

> > This functionality required adding a bool to the base class. This
may
> > increase the sizeof(linked_ptr), an exception is the case where
> > struct alignment is 64 bits and a pointer is 32, as is MSVC's
> > default.  I imagine this is a fairly common condition.  I don't have
> > access to my linux box right now, or I would see what gcc defaults
> > to.
> 
> I've just checked this with MSVC and gcc.  It tells me that a
> linked_ptr (without flag) is 12 bytes (3 ptrs), so adding the flag is
> not for free - in fact it will add 4 bytes to the struct size.

Do you have struct alignment settings leftover from some previous
project?  MSVC's default is 8 byte alignment.