Memory Fragmentation and Compaction

# Contiguous allocation driven to external fragmentation, then compacted.
# blocks: list of [owner|None, size] in address order.

def alloc(blocks, name, size):
    for i, (owner, sz) in enumerate(blocks):
        if owner is None and sz >= size:            # first fit
            rest = sz - size
            blocks[i:i+1] = [[name, size]] + ([[None, rest]] if rest else [])
            return True
    return False                                     # no single hole big enough

def free(blocks, name):
    for b in blocks:
        if b[0] == name:
            b[0] = None
    coalesce(blocks)

def coalesce(blocks):
    i = 0                                            # merge adjacent free runs
    while i < len(blocks) - 1:
        if blocks[i][0] is None and blocks[i+1][0] is None:
            blocks[i][1] += blocks[i+1][1]
            del blocks[i+1]
        else:
            i += 1

def compact(blocks):
    used = [b for b in blocks if b[0] is not None]   # slide everything down
    hole = sum(b[1] for b in blocks if b[0] is None)
    return used + ([[None, hole]] if hole else [])

def holes(blocks):
    return [b[1] for b in blocks if b[0] is None]

mem = [[None, 64]]
for name, size in [("A", 12), ("B", 9), ("C", 14), ("D", 7), ("E", 10)]:
    alloc(mem, name, size)
free(mem, "B")
free(mem, "D")

h = holes(mem)
print("holes %s -> %d KB free, largest %d KB" % (h, sum(h), max(h)))
print("request 26 KB ->", "ok" if alloc(list(mem), "F", 26) else "FAILS (external fragmentation)")
mem = compact(mem)
print("after compaction: largest hole %d KB" % max(holes(mem)))
print("request 26 KB ->", "ok" if alloc(mem, "F", 26) else "FAILS")

// External fragmentation demonstrated on a contiguous region.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
struct Block {
    std::string owner;
    int size;
}; // owner "" means free
bool alloc(std::vector<Block>& b, const std::string& name, int size) {
    for (size_t i = 0; i < b.size(); ++i)
    if (b[i].owner.empty() && b[i].size >= size) {
        int rest = b[i].size - size;
        b[i] = {name, size};
        if (rest) b.insert(b.begin() + i + 1, {"", rest});
        return true;
    }
    return false; // fragmented, not full
}
void coalesce(std::vector<Block>& b) {
    for (size_t i = 0; i + 1 < b.size();)
    if (b[i].owner.empty() && b[i + 1].owner.empty()) {
        b[i].size += b[i + 1].size;
        b.erase(b.begin() + i + 1);
    } else ++i;
}
void release(std::vector<Block>& b, const std::string& name) {
    for (auto& x : b) if (x.owner == name) x.owner.clear();
    coalesce(b);
}
std::vector<Block> compact(const std::vector<Block>& b) {
    std::vector<Block> out;
    int hole = 0;
    for (const auto& x : b) {
        if (x.owner.empty()) hole += x.size;
        else out.push_back(x);
    }
    if (hole) out.push_back({"", hole}); // one contiguous run
    return out;
}
int largestHole(const std::vector<Block>& b) {
    int m = 0;
    for (const auto& x : b) if (x.owner.empty()) m = std::max(m, x.size);
    return m;
}
int main() {
    std::vector<Block> mem {
        {
            "", 64
        }
    };
    for (auto p : {std::pair<const char*,int>{"A",12},{"B",9},{"C",14},{"D",7},{"E",10}})
    alloc(mem, p.first, p.second);
    release(mem, "B");
    release(mem, "D");
    std::cout << "largest hole " << largestHole(mem) << " KB\n";
    mem = compact(mem);
    std::cout << "after compaction " << largestHole(mem) << " KB\n";
}

// Contiguous allocation, fragmentation, and compaction.
import java.util.*;
class Region {
    record Block(String owner, int size) {
    }
    // owner == null -> free
    List<Block> blocks = new ArrayList<>();
    boolean alloc(String name, int size) {
        for (int i = 0; i < blocks.size(); i++) {
            Block b = blocks.get(i);
            if (b.owner() == null && b.size() >= size) {
                int rest = b.size() - size;
                blocks.set(i, new Block(name, size));
                if (rest > 0) blocks.add(i + 1, new Block(null, rest));
                return true;
            }
        }
        return false; // no hole large enough
    }
    void coalesce() {   // merge neighbouring holes
        for (int i = 0; i + 1 < blocks.size(); ) {
            if (blocks.get(i).owner() == null && blocks.get(i+1).owner() == null) {
                blocks.set(i, new Block(null, blocks.get(i).size() + blocks.get(i+1).size()));
                blocks.remove(i + 1);
            } else i++;
        }
    }
    void compact() {   // slide allocations down
        List<Block> used = blocks.stream().filter(b -> b.owner() != null).toList();
        int hole = blocks.stream().filter(b -> b.owner() == null)
        .mapToInt(Block::size).sum();
        blocks = new ArrayList<>(used);
        if (hole > 0) blocks.add(new Block(null, hole));
    }
}