VectorPool.h

// Copyright(c) 2019 - 2020, #Momo
// All rights reserved.
// 
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met :
// 
// 1. Redistributions of source code must retain the above copyright notice, this
// list of conditions and the following disclaimer.
// 
// 2. Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and /or other materials provided with the distribution.
// 
// 3. Neither the name of the copyright holder nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
// 
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED.IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#pragma once

#include "Utilities/STL/MxVector.h"
#include "Utilities/Memory/PoolAllocator.h"

namespace MxEngine
{
    template<typename T, template<typename> typename Container = MxVector>
    class VectorPool
    {
    public:
        class PoolIterator
        {
            size_t index = 0;
            VectorPool<T, Container>& poolRef;
        public:
            size_t GetBase() const
            {
                return index;
            }

            VectorPool<T, Container>& GetPoolRef()
            {
                return poolRef;
            }

            PoolIterator(size_t index, VectorPool<T, Container>& ref)
                : index(index), poolRef(ref)
            {
                while (this->index < this->poolRef.Capacity() && !poolRef.IsAllocated(this->index))
                {
                    this->index++; // 0 element may not exists, so we should skip it until find any allocated
                }
            }

            PoolIterator operator++(int)
            {
                PoolIterator copy = *this;
                ++(*this);
                return copy;
            }

            PoolIterator operator++()
            {
                do { index++; } while (index < poolRef.Capacity() && !poolRef.IsAllocated(index));
                return *this;
            }

            PoolIterator operator--(int)
            {
                PoolIterator copy = *this;
                --(*this);
                return copy;
            }

            PoolIterator operator--()
            {
                do { index--; } while (index < poolRef.Capacity() && !poolRef.IsAllocated(index));
                return *this;
            }

            T* operator->()
            {
                return &poolRef[index];
            }

            const T* operator->() const
            {
                return &poolRef[index];
            }

            T& operator*()
            {
                return poolRef[index];
            }

            const T& operator*() const
            {
                return poolRef[index];
            }

            bool operator==(const PoolIterator& it) const
            {
                return (index == it.index) && (&poolRef == &it.poolRef);
            }

            bool operator!=(const PoolIterator& it) const
            {
                return !(*this == it);
            }
        };

        using Allocator = PoolAllocator<T>;
        using Block = typename Allocator::Block;
    private:
        Container<uint8_t> memoryStorage;
        Allocator allocator;
        size_t allocated = 0;

        Block* GetBlockByIndex(size_t index)
        {
            size_t byteIndex = index * sizeof(Block);
            MX_ASSERT(byteIndex < memoryStorage.size());
            return (Block*)(memoryStorage.data() + byteIndex);
        }

        const Block* GetBlockByIndex(size_t index) const
        {
            size_t byteIndex = index * sizeof(Block);
            MX_ASSERT(byteIndex < memoryStorage.size());
            return (Block*)(memoryStorage.data() + byteIndex);
        }
    public:
        VectorPool() = default;

        VectorPool(size_t count)
        {
            this->Resize(count);
        }

        void Resize(size_t count)
        {
            if (count <= this->Capacity()) return;

            Container<uint8_t> newMemory(count * sizeof(Block));
            allocator.Transfer(newMemory.data(), newMemory.size());
            memoryStorage = std::move(newMemory);
        }

        size_t Allocated() const
        {
            return this->allocated;
        }

        size_t Capacity() const
        {
            return memoryStorage.size() / sizeof(Block);
        }

        T& operator[] (size_t index)
        {
            return GetBlockByIndex(index)->data;
        }

        const T& operator[] (size_t index) const
        {
            return GetBlockByIndex(index)->data;
        }

        void Clear()
        {
            allocator.~PoolAllocator();
            memoryStorage.clear();
        }

        bool IsAllocated(size_t index)
        {
            return !GetBlockByIndex(index)->IsFree();
        }

        void Deallocate(size_t index)
        {
            if (IsAllocated(index))
            {
                T& ptr = GetBlockByIndex(index)->data;
                allocator.Free(&ptr);
                this->allocated--;
            }
        }

        void Deallocate(const PoolIterator& it)
        {
            this->Deallocate(it.GetBase());
        }

        template<typename... Args>
        size_t Allocate(Args&&... args)
        {
            if (this->allocated == this->Capacity())
            {
                size_t newSize = (this->allocated + 1) * 3 / 2;
                this->Resize(newSize);
            }

            T* obj = allocator.Alloc(std::forward<Args>(args)...);
            this->allocated++;
            return this->IndexOf(*obj);
        }

        size_t IndexOf(const T& obj)
        {
            const uint8_t* ptr = (uint8_t*)&obj - offsetof(Block, data);
            MX_ASSERT(memoryStorage.data() <= ptr && ptr < memoryStorage.data() + memoryStorage.size());
            return (Block*)ptr - (Block*)memoryStorage.data();
        }

        PoolIterator begin()
        {
            return PoolIterator{ 0, *this };
        }

        const PoolIterator begin() const
        {
            return PoolIterator{ 0, *this };
        }

        PoolIterator end()
        {
            return PoolIterator{ this->Capacity(), *this };
        }

        const PoolIterator end() const
        {
            return PoolIterator{ this->Capacity(), *this };
        }
    };
}