OK, to distract myself from my current situation
I streamlined the reserve
logic, making it easier to understand and debug. This should eliminate all the edge cases.
It turns out that the prFindNext call was never actually necessary, so I removed it here.
Would you mind kicking the tires a bit? See if any other issues shake out?
diff
To ContiguousBlock, add:
nextAddress { ^start + size }
lastAddress { ^start + size - 1 }
That’s a repeated calculation that appears several times.
Then:
reserve { |address, size = 1, warn = true|
var block = array[address - addrOffset];
// block exists: if unused and big enough, reserve, else nil
if(block.notNil) {
if(block.used or: { block.size < size }) {
if(warn) {
"The block at (%, %) is already in use and cannot be reserved."
.format(address, size).warn;
};
^nil
} {
^this.prReserve(address, size, block);
};
} {
// block didn't exist:
// search backward and validate 2 conditions
block = this.prFindPrevious(address);
if(block.isNil) {
if(warn) {
"Address % should be at least %".format(address, addrOffset).warn;
};
^nil
};
if(block.nextAddress < address) {
Error("ContiguousBlockAllocator:reserve previous block doesn't span requested address (should never happen)").throw;
};
// is it used, or too small?
if(block.used or: {
block.nextAddress < (address + size)
}) {
if(warn) {
"The block at (%, %) is already in use and cannot be reserved."
.format(address, size).warn;
};
^nil
} {
^this.prReserve(address, size, nil, block);
};
};
^nil // shouldn't get here but just be safe
}
Tests:
c = ContiguousBlockAllocator(64, 0, 64);
c.reserve(64, 1); // OK, bug fixed
c.reserve(5, 1);
WARNING: Address 5 should be at least 64
c = ContiguousBlockAllocator(10);
c.reserve(0, 1);
c.reserve(5, 3);
c.reserve(3, 3); // should collide
c.reserve(6, 1); // should collide
c.reserve(9, 3); // should collide -- all 3 collisions are correctly detected
// and this is the only way to get that "should never happen"
// nobody will ever do this
c = ContiguousBlockAllocator(10);
// force an inconsistent state
c.slotAt(\array)[0] = ContiguousBlock(0, 4, false);
c.reserve(6, 1);
ERROR: ContiguousBlockAllocator:reserve previous block doesn't span requested address (should never happen)
hjh