Memory.cpp

#include "Memory.h"

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

#include "Node.h"

using namespace std;

// cur will be deleted!!!
void mergePrevious(Node *cur) {
    if (!cur || !cur->previous || cur->inUse != cur->previous->inUse) {
        return;
    }
    auto previous = cur->previous;
    previous->next = cur->next;
    delete cur;
    if (previous->next) {
        previous->next->previous = previous;
        mergePrevious(previous);
    }
}

void mergeNext(Node *cur) {
    if (!cur || !cur->next || cur->inUse != cur->next->inUse) {
        return;
    }
    auto next = cur->next;
    cur->next = next->next;
    delete next;
    if (cur->next) {
        cur->next->previous = cur;
        mergeNext(cur->next);
    }
}

/**
Frees the given memory address. Returns if the free was successful or not
Be sure to merge adjacent free blocks when possible
*/
bool Memory::free(unsigned address) {
    auto cur = head;
    while (cur && cur->address != address) {
        cur = cur->next;
    }
    if (!cur || !cur->inUse) {
        return false;
    }

    cur->inUse = false;
    mergeNext(cur);
    mergePrevious(cur);

    return true;
}

/**
Reorganizes memory structure so that all of the allocated memory is grouped at
the bottom (0x0000) and there is one large chunk of free memory above.

Note: We do not care about the order of the allocated memory chunks
*/
void Memory::defragment() {
    Node *cur = head, *next = head;

    while (cur && next) {
        // find first node that is free
        while (cur && cur->inUse) {
            cur = cur->next;
        }
        // full
        if (!cur) {
            return;
        }
        next = cur->next;
        // find first node that needs to shift
        while (next && !next->inUse) {
            next = next->next;
        }
        // no need to shift
        if (!next) {
            return;
        }

        auto sz = getSize(next);
        // cout << hex << cur->address << " " << next->address << endl;
        next->address = cur->address + sz;
        cur->inUse = true;
        next->inUse = false;
        mergeNext(next);
        mergeNext(head);
    }
}