Source

Toy C#-ish compiler / mm.cpp

Full commit
// This is the C++ code the allocate and deallocate in the standard library are based on.
// I'm using Word instead of explicit pointers because it's easier.  This code
// is just intended to test whether what I'm doing actually works.

#include <vector>
#include <iostream>
#include <iomanip>

struct Word;

std::vector<Word> heap(16);

struct Word {
    Word() : u() {}
    Word(unsigned u) : u(u) {}
    unsigned u;
    operator unsigned() const {
        return u;
    }

    Word& operator*() const {
        return heap[u];
    }

    Word& operator[](unsigned n) const {
        return heap[u+n];
    }
};

Word heap_top{0};

void init_heap() {
    heap[0] = 2;
    heap[2] = 0;
    heap[1] = heap.size() - 2;
}

Word allocate(Word n) {
    Word p = heap_top;
    while ((*p)[-1] < n)
        p = *p;
    Word q = *p;
    if (q[-1] <= n + 1) {
        *p = *q;
        return q;
    }
    q[n] = q[-1] - n - 1;
    q[-1] = n;
    q[n+1] = *q;
    *p = q + n + 1;
    return q;
}

void deallocate(Word x) {
    Word p = heap_top;
    // All memory has been allocated.
    if (p == *p) {
        *p = x;
        *x = p;
        return;
    }
    while (*p < x)
        p = *p;
    if (p != heap_top && p + p[-1] + 1 == x) {
        p[-1] = p[-1] + x[-1] + 1;
        if (p + p[-1] + 1 == *p) {
            p[-1] = p[-1] + (*p)[-1] + 1;
            *p = **p;
        }
    } else if (x + x[-1] + 1 == *p) {
        *p = x;
        *x = x[x[-1]+1];
        x[-1] = x[-1] + x[x[-1]] + 1;
    } else {
        *x = *p;
        *p = x;
    }
}

void print_heap() {
    static int i;
    std::cout << (i++) << ": ";
    for (auto e : heap)
        std::cout << std::hex << e << " ";
    std::cout << std::endl;
}

int main() {
    init_heap();
    print_heap();
    auto p = allocate(14);
    print_heap();
    deallocate(p);
    print_heap();
    p = allocate(3);
    print_heap();
    deallocate(p);
    print_heap();
}