//
// Copyright 2015 The ANGLE Project Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// Unit tests for HandleAllocator.
//

#include <array>
#include <unordered_set>
#include "common/unsafe_buffers.h"

#include "gmock/gmock.h"
#include "gtest/gtest.h"

#include "libANGLE/HandleAllocator.h"

namespace
{

constexpr GLuint kMaxHandleForTesting = std::numeric_limits<GLuint>::max();

TEST(HandleAllocatorTest, ReservationsWithGaps)
{
    gl::HandleAllocator allocator(kMaxHandleForTesting);

    std::set<GLuint> allocationList;
    for (GLuint id = 2; id < 50; id += 2)
    {
        allocationList.insert(id);
    }

    for (GLuint id : allocationList)
    {
        allocator.reserve(id);
    }

    std::set<GLuint> allocatedList;
    for (size_t allocationNum = 0; allocationNum < allocationList.size() * 2; ++allocationNum)
    {
        GLuint handle = 0;
        EXPECT_TRUE(allocator.allocate(&handle));
        EXPECT_EQ(0u, allocationList.count(handle));
        EXPECT_EQ(0u, allocatedList.count(handle));
        allocatedList.insert(handle);
    }
}

TEST(HandleAllocatorTest, Random)
{
    gl::HandleAllocator allocator(kMaxHandleForTesting);

    std::set<GLuint> allocationList;
    for (size_t iterationCount = 0; iterationCount < 40; ++iterationCount)
    {
        for (size_t randomCount = 0; randomCount < 40; ++randomCount)
        {
            GLuint randomHandle = (rand() % 1000) + 1;
            if (allocationList.count(randomHandle) == 0)
            {
                allocator.reserve(randomHandle);
                allocationList.insert(randomHandle);
            }
        }

        for (size_t normalCount = 0; normalCount < 40; ++normalCount)
        {
            GLuint normalHandle = 0;
            EXPECT_TRUE(allocator.allocate(&normalHandle));
            EXPECT_EQ(0u, allocationList.count(normalHandle));
            allocationList.insert(normalHandle);
        }
    }
}

TEST(HandleAllocatorTest, Reallocation)
{
    // Note: no current test for overflow
    gl::HandleAllocator limitedAllocator(10);

    for (GLuint count = 1; count < 10; count++)
    {
        GLuint result = 0;
        EXPECT_TRUE(limitedAllocator.allocate(&result));
        EXPECT_EQ(count, result);
    }

    for (GLuint count = 1; count < 10; count++)
    {
        limitedAllocator.release(count);
    }

    for (GLuint count = 2; count < 10; count++)
    {
        limitedAllocator.reserve(count);
    }

    GLuint finalResult = 0;
    EXPECT_TRUE(limitedAllocator.allocate(&finalResult));
    EXPECT_EQ(finalResult, 1u);
}

// The following test covers reserving a handle with max uint value. See
// http://anglebug.com/42260058
TEST(HandleAllocatorTest, ReserveMaxUintHandle)
{
    gl::HandleAllocator allocator(kMaxHandleForTesting);

    GLuint maxUintHandle = std::numeric_limits<GLuint>::max();
    allocator.reserve(maxUintHandle);

    GLuint normalHandle = 0;
    EXPECT_TRUE(allocator.allocate(&normalHandle));
    EXPECT_EQ(1u, normalHandle);
}

// The following test covers reserving a handle with max uint value minus one then max uint value.
TEST(HandleAllocatorTest, ReserveMaxUintHandle2)
{
    gl::HandleAllocator allocator(kMaxHandleForTesting);

    GLuint maxUintHandle = std::numeric_limits<GLuint>::max();
    allocator.reserve(maxUintHandle - 1);
    allocator.reserve(maxUintHandle);

    GLuint normalHandle = 0;
    EXPECT_TRUE(allocator.allocate(&normalHandle));
    EXPECT_EQ(1u, normalHandle);
}

// To test if the allocator keep the handle in a sorted order.
TEST(HandleAllocatorTest, SortedOrderHandle)
{
    gl::HandleAllocator allocator(kMaxHandleForTesting);

    allocator.reserve(3);

    std::array<GLuint, 5> allocatedList;
    for (GLuint count = 0; count < 5; count++)
    {
        EXPECT_TRUE(allocator.allocate(&allocatedList[count]));
    }

    EXPECT_EQ(1u, allocatedList[0]);
    EXPECT_EQ(2u, allocatedList[1]);
    EXPECT_EQ(4u, allocatedList[2]);
    EXPECT_EQ(5u, allocatedList[3]);
    EXPECT_EQ(6u, allocatedList[4]);
}

// Tests the reset method.
TEST(HandleAllocatorTest, Reset)
{
    gl::HandleAllocator allocator(kMaxHandleForTesting);

    for (int iteration = 0; iteration < 1; ++iteration)
    {
        allocator.reserve(3);
        GLuint handle = 0;
        EXPECT_TRUE(allocator.allocate(&handle));
        EXPECT_EQ(1u, handle);
        EXPECT_TRUE(allocator.allocate(&handle));
        EXPECT_EQ(2u, handle);
        EXPECT_TRUE(allocator.allocate(&handle));
        EXPECT_EQ(4u, handle);
        allocator.reset();
    }
}

// Tests the reset method of custom allocator works as expected.
TEST(HandleAllocatorTest, ResetAndReallocate)
{
    // Allocates handles - [1, 3]
    gl::HandleAllocator allocator(3);
    const std::unordered_set<GLuint> expectedHandles = {1, 2, 3};
    std::unordered_set<GLuint> handles;

    auto allocateHandle = [&]() {
        GLuint handle = 0;
        EXPECT_TRUE(allocator.allocate(&handle));
        handles.insert(handle);
    };
    EXPECT_EQ(allocator.anyHandleAvailableForAllocation(), true);
    allocateHandle();
    allocateHandle();
    allocateHandle();
    EXPECT_EQ(expectedHandles, handles);
    EXPECT_EQ(allocator.anyHandleAvailableForAllocation(), false);

    // Reset the allocator
    allocator.reset();

    EXPECT_EQ(allocator.anyHandleAvailableForAllocation(), true);
    allocateHandle();
    allocateHandle();
    allocateHandle();
    EXPECT_EQ(expectedHandles, handles);
    EXPECT_EQ(allocator.anyHandleAvailableForAllocation(), false);
}

// Covers a particular bug with reserving and allocating sub ranges.
TEST(HandleAllocatorTest, ReserveAndAllocateIterated)
{
    gl::HandleAllocator allocator(kMaxHandleForTesting);

    for (int iteration = 0; iteration < 3; ++iteration)
    {
        allocator.reserve(5);
        allocator.reserve(6);
        GLuint a = 0, b = 0, c = 0;
        EXPECT_TRUE(allocator.allocate(&a));
        EXPECT_TRUE(allocator.allocate(&b));
        EXPECT_TRUE(allocator.allocate(&c));
        allocator.release(c);
        allocator.release(a);
        allocator.release(b);
        allocator.release(5);
        allocator.release(6);
    }
}

// This test reproduces invalid heap bug when reserve resources after release.
TEST(HandleAllocatorTest, ReserveAfterReleaseBug)
{
    gl::HandleAllocator allocator(kMaxHandleForTesting);

    for (int iteration = 1; iteration <= 16; ++iteration)
    {
        EXPECT_TRUE(allocator.allocate(nullptr));
    }

    allocator.release(15);
    allocator.release(16);

    for (int iteration = 1; iteration <= 14; ++iteration)
    {
        allocator.release(iteration);
    }

    allocator.reserve(1);

    EXPECT_TRUE(allocator.allocate(nullptr));
}

// This test is to verify that we consolidate handle ranges when releasing a handle.
TEST(HandleAllocatorTest, ConsolidateRangeDuringRelease)
{
    gl::HandleAllocator allocator(kMaxHandleForTesting);

    // Reserve GLuint(-1)
    allocator.reserve(static_cast<GLuint>(-1));
    // Allocate a few others
    EXPECT_TRUE(allocator.allocate(nullptr));
    EXPECT_TRUE(allocator.allocate(nullptr));

    // Release GLuint(-1)
    allocator.release(static_cast<GLuint>(-1));

    // Allocate one more handle.
    // Since we consolidate handle ranges during a release we do not expect to get back a
    // handle value of GLuint(-1).
    GLuint handle = 0;
    EXPECT_TRUE(allocator.allocate(&handle));
    EXPECT_NE(handle, static_cast<GLuint>(-1));
}

// Test that HandleAllocator::allocate returns false when there are no more available handles.
TEST(HandleAllocatorTest, HandleExhaustion)
{
    constexpr size_t kCount = 16;
    gl::HandleAllocator allocator(kCount);

    // Use all available handles
    std::vector<GLuint> handles;
    for (size_t iteration = 0; iteration < kCount; ++iteration)
    {
        GLuint handle;
        EXPECT_TRUE(allocator.allocate(&handle));
        handles.push_back(handle);
    }

    // allocations should fail
    EXPECT_FALSE(allocator.allocate(nullptr));
    EXPECT_FALSE(allocator.anyHandleAvailableForAllocation());

    // Release one handle, the next allocation should succeed
    allocator.release(handles[0]);
    EXPECT_TRUE(allocator.anyHandleAvailableForAllocation());
    EXPECT_TRUE(allocator.allocate(nullptr));

    // The allocator is full again, allocations should fail
    EXPECT_FALSE(allocator.allocate(nullptr));
    EXPECT_FALSE(allocator.anyHandleAvailableForAllocation());
}

// Verifies that released handles are reused in FIFO order.
TEST(HandleAllocatorTest, ReleaseThenReuseInFIFO)
{
    gl::HandleAllocator allocator(1000);

    // Allocate handles 1-11. The next unallocated index is 12.
    std::array<GLuint, 11> handles;
    for (int i = 0; i < 11; i++)
    {
        EXPECT_TRUE(allocator.allocate(&handles[i]));
    }

    // Release handles in a non-sorted order. None is adjacent to 12, so all go into mReleasedList
    // rather than being consolidated into mUnallocatedList.
    constexpr GLuint kReleaseOrder[] = {3, 1, 5, 2, 4, 8, 6, 10, 7, 9};
    for (GLuint i : kReleaseOrder)
    {
        allocator.release(i);
    }

    // Each allocation should return the next handle in the same order they were released.
    for (GLuint expected : kReleaseOrder)
    {
        GLuint handle = 0;
        EXPECT_TRUE(allocator.allocate(&handle));
        EXPECT_EQ(expected, handle);
    }
}

// Verifies that reserve() correctly removes handles from the released list even when the released
// list has many entries.
TEST(HandleAllocatorTest, ReserveFromLargeReleasedList)
{
    gl::HandleAllocator allocator(1000);

    // Need to allocate 101 to push the next unallocated index to 102, so it is no longer adjacent
    // to 1-100.
    GLuint prevHandle;
    for (GLuint i = 1; i <= 101; i++)
    {
        EXPECT_TRUE(allocator.allocate(&prevHandle));
    }

    // Release 1-100. All should go to mReleasedList.
    for (GLuint i = 1; i <= 100; i++)
    {
        allocator.release(i);
    }

    // Reserve some specific handles.
    allocator.reserve(50);
    allocator.reserve(75);
    allocator.reserve(25);

    // Verify those reserved handles are not allocated.
    GLuint handle;
    for (GLuint i = 1; i <= 100; i++)
    {
        if (allocator.allocate(&handle))
        {
            EXPECT_NE(25u, handle);
            EXPECT_NE(50u, handle);
            EXPECT_NE(75u, handle);
        }
    }
}

// Verifies that interleaved release and allocate operations work correctly.
// Simulates handle usage patterns similar to real-world resource management.
TEST(HandleAllocatorTest, InterleavedReleaseAllocate)
{
    gl::HandleAllocator allocator(kMaxHandleForTesting);
    constexpr GLuint kPoolSize = 16;

    // Allocate more handles than the pool to prevent consolidation.
    std::vector<GLuint> pool;
    for (GLuint i = 0; i < kPoolSize; i++)
    {
        GLuint handle;
        EXPECT_TRUE(allocator.allocate(&handle));
        pool.push_back(handle);
    }

    // Keep the next unallocated handle advanced.
    GLuint gapHandle;
    EXPECT_TRUE(allocator.allocate(&gapHandle));

    // Release half of the pool.
    std::vector<GLuint> releasedHandles;
    for (GLuint i = 0; i < kPoolSize / 2; i++)
    {
        allocator.release(pool[i]);
        releasedHandles.push_back(pool[i]);
    }

    // Release more handles.
    std::vector<GLuint> releasedHandles2;
    for (GLuint i = kPoolSize / 2; i < kPoolSize; i++)
    {
        allocator.release(pool[i]);
        releasedHandles2.push_back(pool[i]);
    }

    // Allocate them back. It should return in FIFO order.
    for (GLuint handle : releasedHandles)
    {
        GLuint newHandle;
        EXPECT_TRUE(allocator.allocate(&newHandle));
        EXPECT_EQ(handle, newHandle);
    }

    for (GLuint handle : releasedHandles2)
    {
        GLuint newHandle;
        EXPECT_TRUE(allocator.allocate(&newHandle));
        EXPECT_EQ(handle, newHandle);
    }
}

// Test MinimumReleasedToKeep parameter behavior for HandleAllocator.
TEST(HandleAllocatorTest, MinimumReleasedToKeep)
{
    // MinimumReleasedToKeep = 3
    gl::HandleAllocator allocator(100, 3);

    // Allocate 5 handles (1, 2, 3, 4, 5)
    for (GLuint i = 1; i <= 5; ++i)
    {
        GLuint handle = 0;
        EXPECT_TRUE(allocator.allocate(&handle));
        EXPECT_EQ(handle, i);
    }

    // Release 1 and 3 (mReleasedList size becomes 2 <= 3)
    allocator.release(1);
    allocator.release(3);

    // Next allocation should NOT recycle from mReleasedList because size (2) <= 3.
    // It should allocate handle 6 from mUnallocatedList.
    GLuint handle = 0;
    EXPECT_TRUE(allocator.allocate(&handle));
    EXPECT_EQ(6u, handle);

    // Release handle 2 (mReleasedList size becomes 3 <= 3: [1, 3, 2])
    allocator.release(2);

    // Next allocation should NOT recycle from mReleasedList because size (3) <= 3.
    // It should allocate handle 7 from mUnallocatedList.
    EXPECT_TRUE(allocator.allocate(&handle));
    EXPECT_EQ(7u, handle);

    // Release handle 4 (mReleasedList size becomes 4 > 3: [1, 3, 2, 4])
    allocator.release(4);

    // Next allocation SHOULD recycle from mReleasedList because size (4) > 3.
    // Recycles handle 1 in FIFO order.
    EXPECT_TRUE(allocator.allocate(&handle));
    EXPECT_EQ(1u, handle);

    // Now mReleasedList size is 3 <= 3. Next allocation should take handle 8 from mUnallocatedList.
    EXPECT_TRUE(allocator.allocate(&handle));
    EXPECT_EQ(8u, handle);
}

// Test that HandleAllocator falls back to recycling from mReleasedList when mUnallocatedList is
// empty
TEST(HandleAllocatorTest, MinimumReleasedToKeepExhaustionFallback)
{
    // MinimumReleasedToKeep = 3, max handles = 3
    gl::HandleAllocator allocator(3, 3);

    // Allocate all 3 handles
    for (GLuint i = 1; i <= 3; ++i)
    {
        GLuint handle = 0;
        EXPECT_TRUE(allocator.allocate(&handle));
        EXPECT_EQ(handle, i);
    }

    // Release 1 and 2 (mReleasedList size = 2 < 3)
    allocator.release(1);
    allocator.release(2);

    // mUnallocatedList is empty. Even though mReleasedList size (2) < 3,
    // allocation should fallback to recycling from mReleasedList rather than failing.
    GLuint handle = 0;
    EXPECT_TRUE(allocator.allocate(&handle));
    EXPECT_EQ(1u, handle);
}

}  // anonymous namespace