Where `new` gets its memory
Every object, array and string you create comes from the heap. An allocator keeps track of free and used blocks: malloc finds a free block big enough (splitting off the rest), free marks it free again and coalesces it with free neighbours, so memory doesn't crumble into useless pieces — fragmentation.
First fit
function createHeap(size) {
let blocks = [{ start: 0, size, free: true }];
return {
malloc(n) {
const block = blocks.find((b) => b.free && b.size >= n); // first fit
if (!block) return null;
if (block.size > n) {
blocks.splice(blocks.indexOf(block) + 1, 0, { start: block.start + n, size: block.size - n, free: true });
}
block.size = n;
block.free = false;
return block.start;
},
free(address) {
const block = blocks.find((b) => b.start === address && !b.free);
if (!block) throw new Error(`Bad free: ${address}`);
block.free = true;
// Coalesce: merge neighbouring free blocks into one.
blocks = blocks.reduce((out, b) => {
const last = out[out.length - 1];
if (last && last.free && b.free) last.size += b.size;
else out.push({ ...b });
return out;
}, []);
},
blocks() {
return blocks.map((b) => ({ ...b }));
},
};
}