LeetCode 2502 - 设计内存分配器

struct Node {
    Node* next;
    Node* prev;

    int size;
    int pos;

    Node(int pos, int size, Node* prev = nullptr, Node* next = nullptr) : pos(pos), size(size), prev(prev), next(next) {}
};

class Allocator {
public:
    Allocator(int n) {
        head = new Node(0, n);
    }

    //// Helpers ////
    Node* make_dummy_head() {
        Node* dummy_head = new Node(-1, -1, nullptr, head);
        if (head) head->prev = dummy_head;
        return dummy_head;
    }

    void remove_dummy_head(Node* dummy_head) {
        head = dummy_head->next;
        if (head) head->prev = nullptr;
        delete dummy_head;
    }

    int allocate(int size, int mID) {
        auto* cur = head;
        while (cur && cur->size < size) cur = cur->next;
        if (!cur) return -1;

        // 找到一个空间合适的未使用区块
        int target_pos = cur->pos;
        allocated[mID].emplace_back(target_pos, size);

        Node* dummy_head = make_dummy_head();

        // 更新未使用区块信息
        if (cur->size == size) {  // 区块刚好合适
            // 从链表中移除掉
            if (cur->prev) cur->prev->next = cur->next;
            if (cur->next) cur->next->prev = cur->prev;
        } else {
            // 剥离掉一部分，更新该区块位置长度
            cur->pos += size;
            cur->size -= size;
        }

        remove_dummy_head(dummy_head);

        return target_pos;
    }

    int freeMemory(int mID) {
        if (!allocated.count(mID)) return 0;
        auto&& blocks = allocated[mID];
        // 按pos排序已使用的区块
        std::sort(blocks.begin(), blocks.end());

        Node* dummy_head = make_dummy_head();

        auto* cur = dummy_head;
        int free_unit_cnt = 0;

        // 逐个归还区块
        for (int i = 0; i < blocks.size(); ++i) {
            auto [pos, size] = blocks[i];
            free_unit_cnt += size;
            while (cur->next && cur->next->pos < pos) cur = cur->next;
            // 对于归还的内存，新建个区块
            auto* new_block = new Node(pos, size, cur, cur->next);
            if (new_block->prev) new_block->prev->next = new_block;
            if (new_block->next) new_block->next->prev = new_block;
            // 合并连续区块
            // 看左边
            if (new_block->prev && new_block->prev->pos + new_block->prev->size == pos) {
                auto* merged = new_block->prev;  // 使用左侧区块作为合并结果
                merged->size += size;
                // 更新前后指向
                merged->next = new_block->next;
                if (merged->next) merged->next->prev = merged;
                // 删除掉刚刚新建的区块，我们直接使用左边的区块就好了
                delete new_block;
                new_block = merged;
            }
            // 看右边
            if (new_block->next && new_block->pos + new_block->size == new_block->next->pos) {
                auto* dropped = new_block->next;  // 遗弃掉右边的区块节点，使用新区快作为合并结果
                new_block->size += dropped->size;
                // 更新前后指向
                new_block->next = dropped->next;
                if (new_block->next) new_block->next->prev = new_block;
                // 删除右边的区块节点
                delete dropped;
            }
        }

        remove_dummy_head(dummy_head);
        
        blocks.clear();
        return free_unit_cnt;
    }
private:
    // 使用链表记录未使用的区块
    Node* head;
    // 使用哈希表记录已使用的区块 mId -> 区块信息向量
    unordered_map<int, vector<pair<int, int>>> allocated;
};