Re: [boost] [interprocess][multi_index] emplace() is not sufficient for maps

Subject: Re: [boost] [interprocess][multi_index] emplace() is not sufficient for maps
From: Howard Hinnant (howard.hinnant_at_[hidden])
Date: 2009-09-19 11:02:09

On Sep 19, 2009, at 4:18 AM, Thorsten Ottosen wrote:

> Ion Gaztañaga skrev:
>> Thorsten Ottosen escribió:
>
>>>
>>> Therefore I would like to see the follwing member:
>>>
>>>  iterator modify_key( const_iterator element, const Key& new_key );
>>>
>>> This function only needs to rebalance/resort the keys and can  
>>> completely avoid deallocation/allocation.
>> Interesting. What about exception safety? We can't assure strong  
>> guarantee. It could just erase the element if the change fails? We  
>> could also use the assignment operator instead of destroy+construct  
>> to reuse some resources.
>
> For keys where assignment don't throw, we get the strong guarantee.  
> For
> the case where assignment could throw, I agree the element should be  
> erase (the user can then reinsert manually if that happens). So maybe
> we should return
>
>  pair<iterator,bool>
>
> to tell the user if the update succeeded?
>
> For cases where the ordering is based merely on a non-throwing part  
> of the Key type, it could be usable with
>
>
>  template< class Key2 >
>  iterator modify_key( const_iterator element, const Key2& new_key );
>
> This function would place the existing node in its right place, but  
> not
> change the key object which the user then has to do, e.g.
>
>  iterator i = modify_key( x, new_object.sub_object );
>  i->swap( new_object );
>
> I guess there are some additional overloads for movable types.

Suggestion:

Using std::map as an example as I am not familiar with [interprocess] 
[multi_index].  Also using C++0X notation (to be emulated in C++03).

Add to the container:

template <class Key, class T, class Compare, class Allocator>
class map
{
public:
     ...
     typedef /details/ node_ptr;

     node_ptr remove(const_iterator p);
     pair<iterator, bool> insert(node_ptr&& nd);
     iterator             insert(const_iterator p, node_ptr&& nd);
     ...
};

map::node_ptr is a move-only smart pointer which holds an Allocator*  
and a map::node* (or equivalent smart pointer as interprocess may  
need?).  node_ptr roughly looks like:

template <class Key, class T, class Allocator>
class node_ptr
{
     typedef typename Allocator::value_type node;

     node*        node_;
     Allocator*   alloc_;

     node_ptr(const node_ptr&);
     node_ptr& operator=(const node_ptr&);
public:
     typedef pair<Key, T> value_type;

     node_ptr() : node_(), alloc_() {}
     ~node_ptr() {reset();}

     node_ptr(node_ptr&& n)
         : node_(n.node_),
           alloc_(n.alloc_)
         {
             n.node_ = nullptr;
             n.alloc_ = nullptr;
         }

     node_ptr& operator=(node_ptr&& n)
         {
             reset();
             node_ = n.node_;
             alloc_ = n.alloc_;
             n.node_ = nullptr;
             n.alloc_ = nullptr;
             return *this;
         }

     void reset()
     {
         if (node_ != nullptr)
         {
             node_->__value_.~pair<const Key, T>();
             alloc_->deallocate(node_, 1);
         }
     }

     value_type& operator*() const
     {
         return *(value_type*)addressof(node_->__value_);
     }
     value_type* operator->() const
     {
         return (value_type*)addressof(node_->__value_);
     }

private:
     node_ptr(node* n, Allocator* a) : node_(n), alloc_(a) {}

     node* release()
     {
         node* r = node_;
         node_ = 0;
         alloc_ = 0;
         return r;
     }

     template <class, class, class, class> friend class map;
};

The client can default construct a node_ptr, or get one from  
map::remove().  He can extract a node, get const-free access to the  
node's value field (as if node_ptr pointed straight at the value  
field), and insert the node back into any map that has an equal  
allocator:

     M::node_ptr p = m1.remove(next(m1.cbegin(), 3));
     p->first = 10;
     m2.insert(std::move(p));

The remove() is nothrow.

The client manipulates the node's value outside of the container.  If  
that manipulation throws, or is abandoned, node_ptr cleans up.

insert() can only throw if the Compare operation throws, and if that  
happens, node_ptr continues to own the node.  Thus the client can  
catch exceptions if desired outside the insert without loosing  
ownership of the node (which is why insert doesn't take node_ptr by  
value).

Constraints:

A node_ptr returned from m.remove() must not outlive m, unless it is  
reset/move-assigned first.

Notes:

This solution addresses both Thorsten's use case and Alan's:

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#839

Has been prototyped (using raw pointers) on std::map and lightly  
tested (just a sanity check).  Actual test code below (so you can see  
how little I tested it, and any details I may have neglected to  
describe:

-Howard

#include <iostream>
#include <map>
#include <new>
#include <cstdlib>

int outstanding_news = 0;

void* operator new(std::size_t s) throw(std::bad_alloc)
{
     ++outstanding_news;
     return std::malloc(s);
}

void  operator delete(void* p) throw()
{
     if (p)
     {
         --outstanding_news;
         std::free(p);
     }
}

template <class C>
void display(const char* msg, const C& c)
{
     std::cout << msg << '\n';
     for (typename C::const_iterator i = c.begin(), e = c.end(); i !=  
e; ++i)
         std::cout << '(' << i->first << ", " << i->second << ")\n";
     std::cout << '\n';
}

int main()
{
     {
     typedef std::map<int, int> M;
     typedef M::value_type V;
     M m1;
     m1.insert(V(1, 1));
     m1.insert(V(2, 1));
     m1.insert(V(3, 1));
     m1.insert(V(4, 1));
     m1.insert(V(5, 1));
     m1.insert(V(6, 1));
     std::cout << "outstanding_news = " << outstanding_news << '\n';
     display("Before remove\nm1 =", m1);

     // new interface
     M::node_ptr p = m1.remove(next(m1.cbegin(), 3));

     display("After remove\nm1 =", m1);
     std::cout << "removed node = (" << p->first << ", " << p->second  
<< ")\n";
     std::cout << "outstanding_news = " << outstanding_news << '\n';

     // new interface
     p->first = 10;

     std::cout << "removed node = (" << p->first << ", " << p->second  
<< ")\n";
     M m2;

     // new interface
     m2.insert(std::move(p));

     display("m2 =", m2);
     std::cout << "outstanding_news = " << outstanding_news << '\n';
     }
     std::cout << "outstanding_news = " << outstanding_news << '\n';
}

outstanding_news = 6
Before remove
m1 =
(1, 1)
(2, 1)
(3, 1)
(4, 1)
(5, 1)
(6, 1)

After remove
m1 =
(1, 1)
(2, 1)
(3, 1)
(5, 1)
(6, 1)

removed node = (4, 1)
outstanding_news = 6
removed node = (10, 1)
m2 =
(10, 1)

outstanding_news = 6
outstanding_news = 0