Boost logo

Boost :

From: Gavin Collings (gcollings_at_[hidden])
Date: 2000-02-07 06:11:55

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

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

Having made that assertion, the need for a flag disappears, the pointer
value could just be nulled for all nodes. The following code should do

      void release_pointer() throw() { ptr = 0; }

      void release() throw()
         linked_ptr * current = this;

            current = static_cast<linked_ptr *>
                         ( const_cast<linked_ptr_base *>( current->left
) );
         while ( current != this );

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


Boost list run by bdawes at, gregod at, cpdaniel at, john at