Building off this answer:
function allocate(bits) {
if ((bits & (bits - 1)) != 0) {
throw "Parameter is not a power of 2";
}
if (bits < 128 || bits > 4194304) {
throw "Bits required out of range";
}
var startBinIndex = Math.log2(bits >> 7);
var lastBin = BIN_OF_BINS.length - 1;
for (var binIndex = startBinIndex; binIndex <= lastBin ; binIndex++) {
var bin = BIN_OF_BINS[binIndex];
//
// We have found a bin that is not empty...
//
if (bin.length != 0) {
//
// Calculate amount of memory this bin takes up
//
var thisBinMemorySize = (128 << binIndex);
var lastBinOfBinsIndex = bin.length - 1;
var binBlock = bin[lastBinOfBinsIndex];
var memoryAddress = binBlock.start;
//
// We are going to return this block
//
var allocatedMemoryBlock = {start : memoryAddress, count : 1};
//
// Before we return the above block, we need to remove the block if count is 1 otherwise decrease count and adjust memory start pointer by bin size
//
if (binBlock.count == 1) {
bin.pop();
}
else {
binBlock.count--;
binBlock.start += thisBinMemorySize;
}
//
// if we want 1024 bits and it takes it from bin 15, we simply subtract 1024 from 4194304 which gives us 4193280
// if we then populate bin 3 (1024 bits) onward, until bin 14, the exact number we end up populating those bins with is 4183280
//
var remainingUnsedMemory = thisBinMemorySize - bits;
var adjustmentSize = bits;
while (remainingUnsedMemory != 0) {
memoryAddress += adjustmentSize;
BIN_OF_BINS[startBinIndex].push({start : memoryAddress, count : 1});
startBinIndex++;
remainingUnsedMemory -= bits;
adjustmentSize = bits;
bits <<= 1;
}
return allocatedMemoryBlock;
}
}
return null; // out of memory...
}
let BIN_OF_BINS = [
[], // 128 bits each chunk
[], // 256
[], // 512
[], // 1024
[], // 2048
[], // 4096
[], // 8192
[], // 16384
[], // 32768
[], // 65536
[], // 131072
[], // 262144
[], // 524288
[], // 1048576
[], // 2097152
[{ start: 0, count: 100 }], // 4194304
]
console.log("Memory returned:", allocate((128 << 1)));
console.log("Memory returned:", allocate((128 << 1)));
console.log("Memory returned:", allocate((128 << 1)));
console.log("Memory returned:", allocate((128 << 2)));
console.log("Memory returned:", allocate((128 << 2)));
console.log("Memory returned:", allocate((128 << 2)));
console.log("Memory returned:", allocate((128 << 1)));
console.log(JSON.stringify(BIN_OF_BINS, null, 2));How can you make it so it takes two parameters, allocate(bits, count), instead of one, where the count parameter tells how many memory slots of bits-size to allocate in advance?
I have been trying all night but have not ended up with anything that is very close to working, and it's starting to lose its simplicity from the original answer.
// desired count is a power of two only
function allocateBunch(bins, base, size, desiredCount) {
let desiredFactor = (2 ** (size - 1))
let totalFound = 0
let i = 0
let n = bins.length
while (i < n) {
// 1024 4096
let factor = 1 << i
let bin = bins[i]
while (bin.length) {
block = bin[0]
let diff = desiredCount - totalFound
let diff1 = Math.ceil(diff / factor)
let min = Math.min(block.count, diff1)
block.count -= min
totalFound += (min * factor)
base.push({
start: block.start,
count: diff
})
block.start += ((min * factor) * (64 << size))
let done = totalFound >= desiredCount
if (done) return
if (done) {
var bits = (64 << size)
var remainingUnsedMemory = ((min * factor) - diff) * bits
var adjustmentSize = bits
var startBinIndex = i
var memoryAddress = block.start + (diff * bits)
while (remainingUnsedMemory != 0) {
// memoryAddress += adjustmentSize;
// bins[startBinIndex].push({
// start: memoryAddress,
// count: 1
// });
// startBinIndex--;
remainingUnsedMemory -= bits;
// adjustmentSize = bits;
// bits >>= 1;
}
} else {
bin.shift()
}
}
i++
}
}
let BIN_OF_BINS = [
[], // 128 bits each chunk
[], // 256
[], // 512
[], // 1024
[], // 2048
[], // 4096
[], // 8192
[], // 16384
[], // 32768
[], // 65536
[], // 131072
[], // 262144
[], // 524288
[], // 1048576
[], // 2097152
[{ start: 0, count: 100 }], // 4194304
]
let base = []
allocateBunch(BIN_OF_BINS, base, 1, 4096)
allocateBunch(BIN_OF_BINS, base, 1, 8192)
console.log(BIN_OF_BINS, base)Basically what I'm trying to do is this. Say you want to allocate 100, 1000, or 4096 (to pick some numbers) blocks in advance (following the linked question for context, or the first algorithm above). You have BIN_OF_BINS which starts out with a top-level value indicating some memory available. You subdivide this as necessary to get the desired blocks, but don't need to actually recursively subdivide stuff, you can take shortcuts. You can do some calculations to tell how far to jump. But having trouble getting there.
If the blocks (after many additions/removals, or allocate/frees) are scattered all over the place, the algorithm ideally would still be able to collect a bunch of blocks in a certain size so they are ready to be plucked.
For example: if I ask for 1 block of size 512, I should get:
[
[],
[],
[ { start: 0, count: 1 } ],
[ { start: 1024, count: 1 } ],
[ { start: 2048, count: 1 } ],
[ { start: 4096, count: 1 } ],
[ { start: 8192, count: 1 } ],
[ { start: 16384, count: 1 } ],
[ { start: 32768, count: 1 } ],
[ { start: 65536, count: 1 } ],
[ { start: 131072, count: 1 } ],
[ { start: 262144, count: 1 } ],
[ { start: 524288, count: 1 } ],
[ { start: 1048576, count: 1 } ],
[ { start: 2097152, count: 1 } ],
[ { start: 4194304, count: 99 } ]
]
If instead I make a request for 8192 512 bit values, I should have:
[
[],
[],
[ { start: 0, count: 8192 } ],
[],
[],
[],
[],
[],
[],
[],
[],
[],
[],
[],
[ { start: 2097664, count: 1 } ],
[ { start: 4194304, count: 99 } ]
]