Opened 8 years ago

Closed 7 years ago

#10777 closed Bugs (fixed)

unordered_map treats operator== on stateful allocators as stateless

Reported by: anonymous Owned by: Daniel James
Milestone: To Be Determined Component: unordered
Version: Boost 1.56.0 Severity: Problem
Keywords: Cc:

Description (last modified by Daniel James)

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;

Change History (2)

comment:1 by Daniel James, 8 years ago

Description: modified (diff)
Status: newassigned

comment:2 by Daniel James, 7 years ago

Resolution: fixed
Status: assignedclosed
Note: See TracTickets for help on using tickets.