Allocation tracking (and maxAllocs) has an off-by-one (or off-by-two?) error

[paulbartrum]

Should the maxAllocs constructor parameter correspond to the maximum number of times allocate can be called? 'Cause if so, it's a bit off I think.

Here's a test case:

OffsetAllocator::Allocator allocator(36864, 2);
OffsetAllocator::Allocation a = allocator.allocate(32);
REQUIRE(a.offset == 0);
OffsetAllocator::Allocation b = allocator.allocate(32);
REQUIRE(a.offset == 0);
OffsetAllocator::Allocation c = allocator.allocate(32);
REQUIRE(a.offset == OffsetAllocator::Allocation::NO_SPACE);
allocator.free(a);
allocator.free(b);
allocator.free(c);

It fails on the first REQUIRE.

Thanks for open-sourcing this code by the way. I'm testing it out in my C# homebrew engine, it seems to work well so far :-)

[sebbbi]

This is true. It fails on allocation N-1. The test is wrong by one. I need to push a fix.

[JustAndreww]

Hello, no fix yet? :)

[rkevingibson]

Strictly as an FYI because I came across this issue when writing a C version of this allocator, there are two easy-to-fix issues here:

• Because there's always one node being used to store free space, the number of nodes to create should be 1+maxAllocs.
• The test in allocate against m_freeOffset means that node index 0 in the freelist isn't considered valid. Can be fixed in a couple of ways, I just changed it to test m_freeOffset == NO_SPACE as the invalid case, allowing it to overflow and wrap around after inserting a node into the bin.