미션

Python, JavaScript, C# 같은 언어는 가비지 컬렉터를 이용해 메모리를 자동으로 정리하는 매니지드 언어(Managed Language)에 속합니다. 매니지드 언어의 가비지 컬렉터는 개발자가 메모리를 요청하면 운영체제의 힙 영역에 할당하고, 더 이상 필요하지 않을 때 자동으로 해제하며 메모리를 관리합니다.

여러분이 속한 회사에서 새로운 매니지드 언어를 개발 중이며, 여러분은 가비지 컬렉터 개발을 담당하게 되었습니다. 특히 메모리 검색 부분을 맡게 되었는데, 사용자가 특정 크기(Byte)의 메모리를 요청하면 사용 가능한 메모리 중 가장 적절한 크기를 찾아 반환하는 GarbageCollector 클래스를 구현해보세요.(같은 크기의 메모리는 없다고 가정)

답

import { AVLTree } from "./avlTree.mjs"

class GarbageCollector {
    constructor() {
        this.memoryTree = new AVLTree();
    }

    insertFreeMemory(size) {
        this.memoryTree.insert(this.memoryTree.root, size);
    }

    searchFreeMemory(requestedSize) {
        return this.findBestFit(this.memoryTree.root, requestedSize);
    }

    findBestFit(node, requestedSize, target = null) {
        if (node == null) {
            return target;
        }
        
        if (node.getData() === requestedSize) {
            return node;
        }

        if (node.getData() >= requestedSize) {
            if (target == null || node.getData() < target.getData()) {
                target = node;
            }
            
            target = this.findBestFit(node.getLeftSubTree(), requestedSize, target);
        }

        target = this.findBestFit(node.getRightSubTree(), requestedSize, target);

        return target;
    }

    releaseFreeMemory(size) {
        this.memoryTree.root = this.memoryTree.remove(this.memoryTree.root, size);
    }
}