Untitled

/**
 * Memory Manager class that manages a byte array pool using
 * the buddy allocation method. Blocks are allocated in powers
 * of two and merged with their buddies when released.
 *
 * @author Leguejou Awunganyi
 * @author Ishita Punna
 * @version 2026-02-12
 */
public class MemManager {

    /** The byte array representing the memory pool. */
    private byte[] memoryPool;

    /** Array of free lists indexed by block size level. */
    private FreeList[] freeBlockLists;

    /** Stores the most recent memory expansion message. */
    private String lastExpansionMessage = "";

    /**
     * Node representing a free block address in a free list.
     */
    private static class FreeNode {

        /** Address of the free block. */
        int address;

        /** Reference to next node. */
        FreeNode next;

        /**
         * Creates a new free node.
         *
         * @param blockAddress starting address of block
         */
        FreeNode(int blockAddress) {
            // Store the starting address for this free block node
            address = blockAddress;
        }
    }

    /**
     * Linked list of free block addresses for a given block size.
     */
    private static class FreeList {

        /** Head of the free list. */
        FreeNode head;

        /**
         * Adds a block address to the free list in sorted order.
         *
         * @param blockAddress address to insert
         */
        void add(int blockAddress) {

            // Create a new node for the block being inserted
            FreeNode newNode = new FreeNode(blockAddress);

            // If list is empty or block belongs at the front, insert at head
            if (head == null || head.address > blockAddress) {
                newNode.next = head;
                head = newNode;
                return;
            }

            // Traverse list until correct insertion point is found
            FreeNode currentNode = head;
            while (currentNode.next != null
                && currentNode.next.address < blockAddress) {
                currentNode = currentNode.next;
            }

            // Insert new node into the sorted list
            newNode.next = currentNode.next;
            currentNode.next = newNode;
        }

        /**
         * Removes and returns the first block address.
         *
         * @return removed block address
         */
        int removeFirst() {

            // Save the address at the head before removing it
            int blockAddress = head.address;

            // Advance head pointer to the next free node
            head = head.next;

            return blockAddress;
        }

        /**
         * Removes a specific block address if present.
         *
         * @param blockAddress address to remove
         * @return true if removed, false otherwise
         */
        boolean remove(int blockAddress) {

            // Track current node and previous node for removal
            FreeNode previousNode = null;
            FreeNode currentNode = head;

            // Walk through list searching for matching address
            while (currentNode != null) {
                if (currentNode.address == blockAddress) {

                    // If removing head, update head pointer
                    if (previousNode == null) {
                        head = currentNode.next;
                    }
                    else {
                        // Otherwise bypass the removed node
                        previousNode.next = currentNode.next;
                    }
                    return true;
                }

                // Move forward in the linked list
                previousNode = currentNode;
                currentNode = currentNode.next;
            }

            // Block was not found in this free list
            return false;
        }

        /**
         * Checks if free list is empty.
         *
         * @return true if empty
         */
        boolean isEmpty() {

            // List is empty when head is null
            return head == null;
        }

        /**
         * Returns formatted string of addresses.
         *
         * @return space-separated address list
         */
        String toStringList() {

            // Build a string containing all addresses in this free list
            StringBuilder builder = new StringBuilder();
            FreeNode currentNode = head;

            // Append each address until end of list is reached
            while (currentNode != null) {
                builder.append(" ").append(currentNode.address);
                currentNode = currentNode.next;
            }

            return builder.toString();
        }
    }

    /**
     * Constructs a new memory manager with given initial size.
     *
     * @param initialSize initial pool size (must be power of 2)
     */
    public MemManager(int initialSize) {

        // Allocate the initial byte array pool
        memoryPool = new byte[initialSize];

        // Determine number of free list levels based on pool size
        int levelCount = logBaseTwo(initialSize) + 1;
        freeBlockLists = new FreeList[levelCount];

        // Initialize each free list structure
        for (int i = 0; i < levelCount; i++) {
            freeBlockLists[i] = new FreeList();
        }

        // Entire pool begins as one free block at the largest level
        freeBlockLists[logBaseTwo(initialSize)].add(0);
    }

    /**
     * Inserts record data into memory pool.
     *
     * @param recordData byte array to insert
     * @return handle referencing stored data
     */
    public Handle insert(byte[] recordData) {

        // Compute required block size as next power of two
        int requiredSize = nextPowerOfTwo(recordData.length);
        int levelIndex = logBaseTwo(requiredSize);

        // Find the first available free block at or above needed size
        while (levelIndex < freeBlockLists.length
            && freeBlockLists[levelIndex].isEmpty()) {
            levelIndex++;
        }

        // If no block exists, expand memory pool and retry insertion
        if (levelIndex == freeBlockLists.length) {
            expandMemory();
            return insert(recordData);
        }

        // Remove a free block from the chosen free list level
        int blockAddress =
            freeBlockLists[levelIndex].removeFirst();

        // Split blocks until we reach the smallest sufficient size
        while ((1 << levelIndex) > requiredSize) {
            levelIndex--;
            int buddyAddress =
                blockAddress + (1 << levelIndex);

            // Add the unused buddy half back into the free list
            freeBlockLists[levelIndex].add(buddyAddress);
        }

        // Copy record bytes into allocated memory pool region
        System.arraycopy(
            recordData,
            0,
            memoryPool,
            blockAddress,
            recordData.length);

        // Return handle describing where record is stored
        return new Handle(
            blockAddress,
            requiredSize,
            recordData.length);
    }

    /**
     * Releases memory associated with a handle.
     *
     * @param handle handle to free
     */
    public void release(Handle handle) {

        // Get starting address and block size from handle
        int blockAddress = handle.getStart();
        int blockSize = handle.getSize();
        int levelIndex = logBaseTwo(blockSize);

        // Attempt to merge freed block with its buddy repeatedly
        while (true) {

            // Buddy address computed using XOR trick
            int buddyAddress =
                blockAddress ^ blockSize;

            // Stop merging if buddy is not currently free
            if (!freeBlockLists[levelIndex]
                .remove(buddyAddress)) {
                break;
            }

            // Update address to the smaller of the merged pair
            blockAddress =
                Math.min(blockAddress, buddyAddress);

            // Double block size and move up one level
            blockSize <<= 1;
            levelIndex++;
        }

        // Add the final merged block back into free list
        freeBlockLists[levelIndex].add(blockAddress);
    }

    /**
     * Retrieves stored record bytes.
     *
     * @param handle handle referencing record
     * @return byte array of record
     */
    public byte[] getRecord(Handle handle) {

        // Allocate an array large enough for the stored block
        byte[] recordBytes =
            new byte[handle.getSize()];

        // Copy only the real data length into the result array
        System.arraycopy(
            memoryPool,
            handle.getStart(),
            recordBytes,
            0,
            handle.getDataLength());

        return recordBytes;
    }

    /**
     * Expands memory pool to double its size.
     */
    private void expandMemory() {

        // Save current pool size before expansion
        int oldPoolSize = memoryPool.length;
        int newPoolSize = oldPoolSize * 2;

        // Create a new larger byte array pool
        byte[] expandedPool =
            new byte[newPoolSize];

        // Copy existing memory contents into expanded pool
        System.arraycopy(
            memoryPool,
            0,
            expandedPool,
            0,
            oldPoolSize);

        memoryPool = expandedPool;

        // Recompute free list structure for the larger pool
        int levelCount =
            logBaseTwo(newPoolSize) + 1;

        FreeList[] newFreeBlockLists =
            new FreeList[levelCount];

        // Initialize new free lists for expanded pool
        for (int i = 0; i < levelCount; i++) {
            newFreeBlockLists[i] = new FreeList();
        }

        // Copy existing free block addresses into new lists
        for (int i = 0; i < freeBlockLists.length; i++) {

            FreeNode currentNode =
                freeBlockLists[i].head;

            while (currentNode != null) {
                newFreeBlockLists[i]
                    .add(currentNode.address);
                currentNode = currentNode.next;
            }
        }

        freeBlockLists = newFreeBlockLists;

        // Create handle representing the new second half block
        Handle newHalfHandle =
            new Handle(oldPoolSize,
                oldPoolSize,
                oldPoolSize);

        // Release new half so it becomes available in free lists
        release(newHalfHandle);

        // Save message so DB can print expansion notice
        lastExpansionMessage =
            "Memory pool expanded to be "
                + newPoolSize
                + " bytes\r\n";
    }

    /**
     * Computes log base 2 of value.
     *
     * @param value input value
     * @return log2(value)
     */
    private int logBaseTwo(int value) {

        // Use bit operations to compute log base 2 efficiently
        return 31
            - Integer.numberOfLeadingZeros(value);
    }

    /**
     * Rounds value up to next power of two.
     *
     * @param value input size
     * @return next power of two
     */
    private int nextPowerOfTwo(int value) {

        // Start at smallest power of two and grow until big enough
        int power = 1;

        while (power < value) {
            power <<= 1;
        }

        return power;
    }

    /**
     * Prints all free blocks grouped by block size.
     *
     * @return formatted free block list
     */
    public String printBlocks() {

        // Build output showing all free blocks by size level
        StringBuilder outputBuilder =
            new StringBuilder();

        boolean hasFreeBlocks = false;

        // Loop through every level of free lists
        for (int levelIndex = 0;
            levelIndex < freeBlockLists.length;
            levelIndex++) {

            // Only print levels that contain at least one block
            if (!freeBlockLists[levelIndex]
                .isEmpty()) {

                hasFreeBlocks = true;

                int blockSize = 1 << levelIndex;

                // Append block size and its free addresses
                outputBuilder.append(blockSize)
                    .append(":")
                    .append(freeBlockLists[levelIndex]
                        .toStringList())
                    .append("\r\n");
            }
        }

        // If no blocks exist, return special message
        if (!hasFreeBlocks) {
            return "No free blocks are available.";
        }

        // Remove trailing newline characters from output
        while (outputBuilder.length() > 0
            && (outputBuilder.charAt(
                outputBuilder.length() - 1) == '\n'
            || outputBuilder.charAt(
                outputBuilder.length() - 1) == '\r')) {

            outputBuilder.setLength(
                outputBuilder.length() - 1);
        }

        return outputBuilder.toString();
    }

    /**
     * Returns last expansion message and clears it.
     *
     * @return expansion message
     */
    public String getExpandMessage() {

        // Save expansion message before resetting it
        String message = lastExpansionMessage;

        // Clear message so it only prints once
        lastExpansionMessage = "";

        return message;
    }
}