Perhaps I need a How-to guide for this, but I just cannot get it to
work. Assuming a node based container using a sentinel node, how are
you supposed to re-establish the sentinel in an exception safe manner
after replacing the allocator?

I tried with this code:

_RedBlackTree& operator=(const _RedBlackTree& _Other)
{
    if (this != &_Other)
    {
       clear();

       if (__node_allocator_traits::
           propagate_on_container_copy_assignment::value)
       {
          _DropSentinel();
          _MyAllocator = _Other._MyAllocator;
          _CreateSentinel();
       }

       insert(_Other.cbegin(), _Other.cend());
    }

    return *this;
}


Before replacing the allocator, I obviously must deallocate everything
through the old allocator, including the sentinel node.

Now, if _CreateSentinel() throws a bad_alloc because the new allocator
is fresh out of resources, I cannot re-establish my invariant that the
container always has a sentinel node! I'm toast!!

Then what??


Bo Persson



--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Bo Persson wrote:
> Perhaps I need a How-to guide for this, but I just cannot get it to
> work. Assuming a node based container using a sentinel node, how are
> you supposed to re-establish the sentinel in an exception safe
> manner after replacing the allocator?
>
> I tried with this code:
>
> _RedBlackTree& operator=(const _RedBlackTree& _Other)
> {
>    if (this != &_Other)
>    {
>       clear();
>
>       if (__node_allocator_traits::
>           propagate_on_container_copy_assignment::value)
>       {
>          _DropSentinel();
>          _MyAllocator = _Other._MyAllocator;
>          _CreateSentinel();
>       }
>
>       insert(_Other.cbegin(), _Other.cend());
>    }
>
>    return *this;
> }
>
>
> Before replacing the allocator, I obviously must deallocate
> everything through the old allocator, including the sentinel node.
>
> Now, if _CreateSentinel() throws a bad_alloc because the new
> allocator is fresh out of resources, I cannot re-establish my
> invariant that the container always has a sentinel node! I'm toast!!
>
> Then what??
>

Answering myself again (it was late yesterday :-)

This must be one place to use the copy-swap idiom:

First make a copy of the parameter and then, if that works, swap the
copy with the current object.

    if (__node_allocator_traits::
        propagate_on_container_copy_assignment::value)
    {
        _RedBlackTree   _Tmp(_Other);
        this->swap(_Tmp);
    }
  else
  {
     insert(_Other.cbegin(), _Other.cend());
  }



Was that too hard?  :-)


Bo Persson



--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On 2009-12-15, Bo Persson <bop@gmb.dk> wrote:
> Perhaps I need a How-to guide for this, but I just cannot get it to
> work. Assuming a node based container using a sentinel node, how are
> you supposed to re-establish the sentinel in an exception safe manner
> after replacing the allocator?
>
> I tried with this code:
>
> _RedBlackTree& operator=(const _RedBlackTree& _Other)
> {
>     if (this != &_Other)
>     {
>        clear();
>
>        if (__node_allocator_traits::
>            propagate_on_container_copy_assignment::value)
>        {
>           _DropSentinel();
>           _MyAllocator = _Other._MyAllocator;
>           _CreateSentinel();
>        }
>
>        insert(_Other.cbegin(), _Other.cend());
>     }
>
>     return *this;
> }
>
>
> Before replacing the allocator, I obviously must deallocate everything
> through the old allocator, including the sentinel node.

Isn't the sentinel node embedded in the _RedBlackTree object itself?
If not, that's silly. Since the tree always needs a sentinel node,
there is no point in allocating it separately. Just make it a member.

 class _RedBlackTree {
 ...
 private:
    _RedBlackNode _sentinel;
 ...
 };

There is a 1:1 association between trees and sentinels; each tree
needs its own, for any hope of thread safety.

> Now, if _CreateSentinel() throws a bad_alloc because the new allocator

The functions _CreateSentinel() and _DropSentinel() shouldn't even exist;
this makes no sense.

The constructor of _RedBlackTree should initialize the sentinel node,
which should be correctly maintained thereafter by all of the
operations.

The clear() operation should result in an empty tree, with a sentinel
that points back to itself, ready to accept new insertions.

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Kaz Kylheku wrote:
> On 2009-12-15, Bo Persson <bop@gmb.dk> wrote:
>> Perhaps I need a How-to guide for this, but I just cannot get it to
>> work. Assuming a node based container using a sentinel node, how
>> are you supposed to re-establish the sentinel in an exception safe
>> manner after replacing the allocator?
>>
>> I tried with this code:
>>
>> _RedBlackTree& operator=(const _RedBlackTree& _Other)
>> {
>>     if (this != &_Other)
>>     {
>>        clear();
>>
>>        if (__node_allocator_traits::
>>            propagate_on_container_copy_assignment::value)
>>        {
>>           _DropSentinel();
>>           _MyAllocator = _Other._MyAllocator;
>>           _CreateSentinel();
>>        }
>>
>>        insert(_Other.cbegin(), _Other.cend());
>>     }
>>
>>     return *this;
>> }
>>
>>
>> Before replacing the allocator, I obviously must deallocate
>> everything through the old allocator, including the sentinel node.
>
> Isn't the sentinel node embedded in the _RedBlackTree object itself?
> If not, that's silly. Since the tree always needs a sentinel node,
> there is no point in allocating it separately. Just make it a
> member.
>
> class _RedBlackTree {
> ...
> private:
>    _RedBlackNode _sentinel;
> ...
> };
>
> There is a 1:1 association between trees and sentinels; each tree
> needs its own, for any hope of thread safety.

Having a separate sentinel node makes it easier to swap the entire
tree to another container. Otherwise you might have to find and adjust
all pointers pointing back to the sentinel.

>
>> Now, if _CreateSentinel() throws a bad_alloc because the new
>> allocator
>
> The functions _CreateSentinel() and _DropSentinel() shouldn't even
> exist; this makes no sense.

True, that is my problem. :-)

However, when the container's allocator is replaced, all of its
allocated memory must first be released through the old allocator.
This is a new requirement that might have effects that require some
retuning of other container operations.

>
> The constructor of _RedBlackTree should initialize the sentinel
> node, which should be correctly maintained thereafter by all of the
> operations.
>
> The clear() operation should result in an empty tree, with a
> sentinel that points back to itself, ready to accept new insertions.

True, but if the sentinel is a separate object is has to go, before
replacing the allocator. Like I wrote elsewhere, I later recognized
that this can be solved by creating the new copy before destroying the
old one. The copy-swap idiom.


Bo Persson



--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]