0

I have got a custom pool allocatorand I want it to use it with std::vector

#include <iostream>
#include <memory>
#include <vector>
#include <type_traits>

    template<typename T, uint Size>
    struct ObjectPool
    {
        using value_type = T;
        using pointer = value_type *;

        ObjectPool()
        {
            for (auto i = 1; i < Size; ++i)
                buffer[i - 1].next = &buffer[i];

            nextFreeItem = &buffer[0];
        }

        ObjectPool(const ObjectPool&) = delete;

        ObjectPool(ObjectPool&& other) noexcept
            : buffer{ std::move(other.buffer) }
            , nextFreeItem{ other.nextFreeItem }
        {
            other.nextFreeItem = nullptr;
        }

        ~ObjectPool() = default;

        template<typename U>
        struct rebind
        {
            typedef ObjectPool<U, Size> other;
        };

        template<typename U, uint other_capacity>
        ObjectPool(const ObjectPool<U, other_capacity>& other) {}

        [[nodiscard]] pointer allocate(uint size = 0)
        {
            std::cout << "ObjectPool: allocate " << size << "\n";
            if (nextFreeItem == nullptr)
                throw std::bad_alloc{};

            const auto item = nextFreeItem;
            nextFreeItem = item->next;

            return reinterpret_cast<pointer>(&item->storage);
        }

        void deallocate(pointer p, uint = 0) noexcept
        {
            std::cout << "ObjectPool: deallocate\n";
            const auto item = reinterpret_cast<Item*>(p);

            item->next = nextFreeItem;
            nextFreeItem = item;
        }

        template<typename U, typename ...Args>
        void construct(U* mem, Args&& ...args)
        {
            std::cout << "ObjectPool: construct\n";
           new (mem) value_type(std::forward<Args>(args)...);
        }

        template<typename U>
        void destroy(U* mem) noexcept
        {
            std::cout << "ObjectPool: destroy\n";
            if (mem == nullptr)
                return;

            mem->~value_type();
        }

        ObjectPool& operator =(const ObjectPool&) = delete;

        ObjectPool& operator =(ObjectPool&& other) noexcept
        {
            if (this == &other)
                return *this;

            buffer = std::move(other.buffer);
            nextFreeItem = other.nextFreeItem;

            other.nextFreeItem = nullptr;

            return *this;
        }

    private:
        union Item
        {
            std::aligned_storage_t<sizeof(value_type), alignof(value_type)> storage;
            Item* next;
        };

        std::unique_ptr<Item[]> buffer = std::make_unique<Item[]>(Size);
        Item* nextFreeItem = nullptr;
    };

    int main()
    {
        std::vector<int, ObjectPool<int, 5>> pool;

        pool.push_back(5);
        pool.push_back(3);
        pool.push_back(523);

        for(const auto& p : pool) {
            std::cout << p << std::endl;
        }

        pool.pop_back();

        for(const auto& p : pool) {
            std::cout << p << std::endl;
        }
    }

the output of this program is

  1. ObjectPool: allocate 1
  2. ObjectPool : construct
  3. ObjectPool : allocate 2
  4. ObjectPool : construct
  5. ObjectPool : construct
  6. ObjectPool : destroy
  7. ObjectPool : deallocate
  8. ObjectPool : allocate 3
  9. ObjectPool : construct
  10. ObjectPool : construct
  11. ObjectPool : construct
  12. ObjectPool : destroy
  13. ObjectPool : destroy
  14. ObjectPool : deallocate
  15. 523
  16. 3
  17. -539300144
  18. ObjectPool : destroy
  19. 523
  20. 3
  21. ObjectPool : destroy
  22. ObjectPool : destroy
  23. ObjectPool : deallocate

I expect it to be

ObjectPool: allocate whatever // this is space for 5
ObjectPool: construct         // constructs 5
ObjectPool: allocate whatever // this is space for 3
ObjectPool: construct         // constructs 3
ObjectPool: allocate whatever // this is space for 523
ObjectPool: construct         // constructs 523, but actual output gives garbage value
ObjectPool: destroy           // destroys 523
ObjectPool: deallocate        // deallocates 523
ObjectPool: destroy           // destroys 3
ObjectPool: destroy           // destroys 5
ObjectPool: deallocate        // deallocates 3 and 5

as you can see construct method is called even 3 times when it only needs to be called once.

Why 523 is garbage? How can I achieve expected output without doing pool.reserve(5)? Is it possible?

1
  • 1
    The allocator determines how allocation should occur, not when. The latter is entirely under the control of the container that is using the allocator. Commented Apr 3, 2020 at 20:40

1 Answer 1

2

The value passed to ObjectPool::allocate is the number of objects that will be stored consecutively in memory. That means that when allocator(2) is called, you need to return a pointer to a block with at least 2 * sizeof(T) blocks. Your allocator only returns a pointer to a single block. When the vector constructor adds the 2nd (or 3rd) element to the newly grown vector, it will overwrite memory that has not been specifically assigned. The next call to allocator will assign that memory resulting in corruption of your vector.

A vector's allocated memory is contiguous. When you first call push_back, one element is allocated for the vector (which will have a capacity of 1). This will generate lines 1-2 of your output.

On the second call to push_back, since the capacity of the vector is full, a new block will be requested. This generates lines 2-7 of your output. Line 4 is copying the existing element to the new memory block, line 5 is constructing the new element that was just added, line 6 is destroying that element from the original memory block. Line 7 is when that original memory block is freed (returned to the allocator). The vector's capacity will be 2.

The next call to push_back will again cause a resize of the vector, generating lines 8-14 of your output. Lines 9-10 are copying the existing elements to the new memory block, 11 constructs the newly added element, 12-13 destroying them in the old memory block, and 14 returns the old memory block to the allocator.

The output on the following lines is corrupted because later calls to your allocator return pointers to memory that the vector object is making use of. The resulting data copying moves the incorrect or corrupted data.

The solution is to have your allocate function reserve the proper number of blocks. (So allocate(2) should advance nextFreeItem two blocks, assuming the two it advances over are contiguous.)

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.