Subject: Re: [Boost-bugs] [Boost C++ Libraries] #10777: unordered_map treats operator== on stateful allocators as stateless
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-11-09 23:49:31
#10777: unordered_map treats operator== on stateful allocators as stateless
-------------------------------+-------------------------
Reporter: anonymous | Owner: danieljames
Type: Bugs | Status: assigned
Milestone: To Be Determined | Component: unordered
Version: Boost 1.56.0 | Severity: Problem
Resolution: | Keywords:
-------------------------------+-------------------------
Changes (by danieljames):
* status: new => assigned
Old description:
> Hi,
>
> here is my problem: I have a stateful allocator that has a bunch of stuff
> inside of it. It can be move-assigned. The problem is that
> boost::unordered_map does this when you have
> propagate_on_container_move_assign typedeffed to true_type:
>
> my_alloc a;
> my_alloc b;
> a = std::move(b);
> ASSERT(a == b);
>
> That assert can obviously never be true if my_alloc is stateful, but this
> sequence of events currently happens in boost::unordered_map.
>
> Here is an allocator that shows the problem:
>
> #pragma once
>
> #include <memory>
> #include <vector>
>
> template<typename T>
> struct plalloc
> {
> typedef T value_type;
>
> plalloc() = default;
> template<typename U>
> plalloc(const plalloc<U> &) {}
> plalloc(const plalloc &) {}
> plalloc & operator=(const plalloc &) { return *this; }
> plalloc(plalloc &&) = default;
> plalloc & operator=(plalloc &&) = default;
>
> typedef std::true_type propagate_on_container_copy_assignment;
> typedef std::true_type propagate_on_container_move_assignment;
> typedef std::true_type propagate_on_container_swap;
>
> bool operator==(const plalloc & other) const
> {
> return this == &other;
> }
> bool operator!=(const plalloc & other) const
> {
> return !(*this == other);
> }
>
> T * allocate(size_t num_to_allocate)
> {
> if (num_to_allocate != 1)
> {
> return static_cast<T *>(::operator new(sizeof(T) *
> num_to_allocate));
> }
> else if (available.empty())
> {
> // first allocate 8, then double whenever
> // we run out of memory
> size_t to_allocate = 8 << memory.size();
> available.reserve(to_allocate);
> std::unique_ptr<value_holder[]> allocated(new
> value_holder[to_allocate]);
> value_holder * first_new = allocated.get();
> memory.emplace_back(std::move(allocated));
> size_t to_return = to_allocate - 1;
> for (size_t i = 0; i < to_return; ++i)
> {
> available.push_back(std::addressof(first_new[i].value));
> }
> return std::addressof(first_new[to_return].value);
> }
> else
> {
> T * result = available.back();
> available.pop_back();
> return result;
> }
> }
> void deallocate(T * ptr, size_t num_to_free)
> {
> if (num_to_free == 1)
> {
> available.push_back(ptr);
> }
> else
> {
> ::operator delete(ptr);
> }
> }
>
> // boilerplate that shouldn't be needed, except
> // libstdc++ doesn't use allocator_traits yet
> template<typename U>
> struct rebind
> {
> typedef plalloc<U> other;
> };
> typedef T * pointer;
> typedef const T * const_pointer;
> typedef T & reference;
> typedef const T & const_reference;
> template<typename U, typename... Args>
> void construct(U * object, Args &&... args)
> {
> new (object) U(std::forward<Args>(args)...);
> }
> template<typename U, typename... Args>
> void construct(const U * object, Args &&... args) = delete;
> template<typename U>
> void destroy(U * object)
> {
> object->~U();
> }
>
> private:
> union value_holder
> {
> value_holder() {}
> ~value_holder() {}
> T value;
> };
>
> std::vector<std::unique_ptr<value_holder[]>> memory;
> std::vector<T *> available;
> };
>
> And here is a sequence of events with which you can get it:
>
> boost::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
> plalloc<int>> a = { { 1, 2 } };
> boost::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
> plalloc<int>> b = { { 3, 4 } };
> boost::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
> plalloc<int>> c = { { 5, 6 } };
> a = std::move(b);
> a = c;
New description:
Hi,
here is my problem: I have a stateful allocator that has a bunch of stuff
inside of it. It can be move-assigned. The problem is that
boost::unordered_map does this when you have
propagate_on_container_move_assign typedeffed to true_type:
{{{
my_alloc a;
my_alloc b;
a = std::move(b);
ASSERT(a == b);
}}}
That assert can obviously never be true if my_alloc is stateful, but this
sequence of events currently happens in boost::unordered_map.
Here is an allocator that shows the problem:
{{{
#pragma once
#include <memory>
#include <vector>
template<typename T>
struct plalloc
{
typedef T value_type;
plalloc() = default;
template<typename U>
plalloc(const plalloc<U> &) {}
plalloc(const plalloc &) {}
plalloc & operator=(const plalloc &) { return *this; }
plalloc(plalloc &&) = default;
plalloc & operator=(plalloc &&) = default;
typedef std::true_type propagate_on_container_copy_assignment;
typedef std::true_type propagate_on_container_move_assignment;
typedef std::true_type propagate_on_container_swap;
bool operator==(const plalloc & other) const
{
return this == &other;
}
bool operator!=(const plalloc & other) const
{
return !(*this == other);
}
T * allocate(size_t num_to_allocate)
{
if (num_to_allocate != 1)
{
return static_cast<T *>(::operator new(sizeof(T) *
num_to_allocate));
}
else if (available.empty())
{
// first allocate 8, then double whenever
// we run out of memory
size_t to_allocate = 8 << memory.size();
available.reserve(to_allocate);
std::unique_ptr<value_holder[]> allocated(new
value_holder[to_allocate]);
value_holder * first_new = allocated.get();
memory.emplace_back(std::move(allocated));
size_t to_return = to_allocate - 1;
for (size_t i = 0; i < to_return; ++i)
{
available.push_back(std::addressof(first_new[i].value));
}
return std::addressof(first_new[to_return].value);
}
else
{
T * result = available.back();
available.pop_back();
return result;
}
}
void deallocate(T * ptr, size_t num_to_free)
{
if (num_to_free == 1)
{
available.push_back(ptr);
}
else
{
::operator delete(ptr);
}
}
// boilerplate that shouldn't be needed, except
// libstdc++ doesn't use allocator_traits yet
template<typename U>
struct rebind
{
typedef plalloc<U> other;
};
typedef T * pointer;
typedef const T * const_pointer;
typedef T & reference;
typedef const T & const_reference;
template<typename U, typename... Args>
void construct(U * object, Args &&... args)
{
new (object) U(std::forward<Args>(args)...);
}
template<typename U, typename... Args>
void construct(const U * object, Args &&... args) = delete;
template<typename U>
void destroy(U * object)
{
object->~U();
}
private:
union value_holder
{
value_holder() {}
~value_holder() {}
T value;
};
std::vector<std::unique_ptr<value_holder[]>> memory;
std::vector<T *> available;
};
}}}
And here is a sequence of events with which you can get it:
{{{
boost::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
plalloc<int>> a = { { 1, 2 } };
boost::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
plalloc<int>> b = { { 3, 4 } };
boost::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
plalloc<int>> c = { { 5, 6 } };
a = std::move(b);
a = c;
}}}
-- Comment: I've removed the assertion in develop. https://github.com/boostorg/unordered/commit/31211a607f1c294f973eed10e54e461a8ef920ba -- Ticket URL: <https://svn.boost.org/trac/boost/ticket/10777#comment:1> Boost C++ Libraries <http://www.boost.org/> Boost provides free peer-reviewed portable C++ source libraries.
This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:17 UTC