Untitled

/**
 * Memory manager class that stores records in a byte array.
 * This version uses a buddy-system allocator on top of an array.
 *
 * @author Leguejou Awunganyi
 * @author Ishita Punna
 * @version 2026-02-08
 */
public class MemManager {

    /**
     * Raw byte array used as the memory pool.
     */
    private byte[] pool;

    /**
     * Array of free lists, one per block size level.
     */
    private FreeList[] freeLists;

    /**
     * Last expansion message, cleared after it is read.
     */
    private String lastExpandMessage = "";

    /**
     * Node in a singly linked free list.
     */
    private static class FreeNode {

        /**
         * Starting address of this free block.
         */
        private int addr;

        /**
         * Next node in the free list.
         */
        private FreeNode next;

        /**
         * Create a new free-node with the given address.
         *
         * @param a starting address for this block
         */
        FreeNode(int a) {
            addr = a;
        }
    }

    /**
     * Simple linked list of free blocks for a single block size.
     */
    private static class FreeList {

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

        /**
         * Add a free block at the front of the list.
         *
         * @param a starting address of the free block
         */
        void add(int a) {
            FreeNode n = new FreeNode(a);
            n.next = head;
            head = n;
        }

        /**
         * Remove and return the first free block.
         *
         * @return starting address of the removed block
         */
        int removeFirst() {
            int a = head.addr;
            head = head.next;
            return a;
        }

        /**
         * Remove the first node whose address matches a.
         *
         * @param a address to remove
         * @return true if a block was removed, false otherwise
         */
        boolean remove(int a) {
            FreeNode prev = null;
            FreeNode cur = head;
            while (cur != null) {
                if (cur.addr == a) {
                    if (prev == null) {
                        head = cur.next;
                    }
                    else {
                        prev.next = cur.next;
                    }
                    return true;
                }
                prev = cur;
                cur = cur.next;
            }
            return false;
        }

        /**
         * Test whether this free list is empty.
         *
         * @return true if the list has no nodes
         */
        boolean isEmpty() {
            return head == null;
        }

        /**
         * Build a string of all block addresses in this list.
         *
         * @return addresses separated by a leading space
         */
        String toStringList() {
            String s = "";
            FreeNode c = head;
            while (c != null) {
                s += " " + c.addr;
                c = c.next;
            }
            return s;
        }
    }

    /**
     * Create a new MemManager object.
     *
     * @param startSize initial requested size of the memory pool
     */
    public MemManager(int startSize) {
        int actualSize = nextPowerOfTwo(startSize);
        pool = new byte[actualSize];

        int levels = log2(actualSize) + 1;

        freeLists = new FreeList[levels];
        for (int i = 0; i < levels; i++) {
            freeLists[i] = new FreeList();
        }
        // Start with one free block at address 0 of full size.
        freeLists[log2(actualSize)].add(0);
    }

    /**
     * Insert a record into the pool and return a handle.
     * Uses the buddy system to allocate a block whose size
     * is the next power of two at least as large as data.length.
     *
     * @param data byte array containing the record
     * @return handle representing the stored record
     */
    public Handle insert(byte[] data) {
        int needed = nextPowerOfTwo(data.length);
        int level = log2(needed);

        // Find the first non-empty free list at or above this level.
        while (level < freeLists.length && freeLists[level].isEmpty()) {
            level++;
        }

        if (level == freeLists.length) {
            // No blocks big enough; expand and try again.
            expand();
            return insert(data);
        }

        // Remove a free block from this level.
        int addr = freeLists[level].removeFirst();

        // Split blocks until the block size matches the needed size.
        while ((1 << level) > needed) {
            level--;
            int buddy = addr + (1 << level);
            freeLists[level].add(buddy);
        }

        // Copy the record into the pool.
        System.arraycopy(data, 0, pool, addr, data.length);

        // Handle carries block size and logical data length.
        return new Handle(addr, needed, data.length);
    }

    /**
     * Release a block given its handle back to the free lists.
     * Merges with its buddy whenever possible.
     *
     * @param h handle to the memory being freed
     */
    public void release(Handle h) {
        int addr = h.getStart();
        int size = h.getSize();
        int level = log2(size);

        while (true) {
            // Buddy is the block whose address differs in the bit for "size".
            int buddy = addr ^ size;

            if (!freeLists[level].remove(buddy)) {
                // Buddy not free; stop merging.
                break;
            }

            // Merge with buddy into a larger block.
            addr = Math.min(addr, buddy);
            size <<= 1;
            level++;
        }

        freeLists[level].add(addr);
    }

    /**
     * Retrieve the record stored at a given handle.
     *
     * @param h handle to the data
     * @return copy of the stored bytes
     */
    public byte[] getRecord(Handle h) {
        byte[] out = new byte[h.getDataLength()];
        System.arraycopy(pool, h.getStart(), out, 0, h.getDataLength());
        return out;
    }

    /**
     * Expand the memory pool by doubling its size.
     * Copies existing contents and adds the new half as a free block.
     */
    private void expand() {
        int oldSize = pool.length;
        int newSize = oldSize * 2;

        byte[] newPool = new byte[newSize];
        System.arraycopy(pool, 0, newPool, 0, oldSize);
        pool = newPool;

        FreeList[] newLists = new FreeList[freeLists.length + 1];
        for (int i = 0; i < freeLists.length; i++) {
            newLists[i] = freeLists[i];
        }
        newLists[freeLists.length] = new FreeList();
        freeLists = newLists;

        // Add new free block for the second half of the pool.
        freeLists[log2(oldSize)].add(oldSize);

        lastExpandMessage =
            "Memory pool expanded to be " + newSize + " bytes\r\n";
    }

    /**
     * Compute floor(log2(n)) using bit operations.
     *
     * @param n positive integer
     * @return exponent e such that 2^e is the highest power of two ≤ n
     */
    private int log2(int n) {
        return 31 - Integer.numberOfLeadingZeros(n);
    }

    /**
     * Find the smallest power of two that is at least n.
     *
     * @param n requested size
     * @return power-of-two size ≥ n
     */
    private int nextPowerOfTwo(int n) {
        int p = 1;
        while (p < n) {
            p <<= 1;
        }
        return p;
    }

    /**
     * Print all free blocks grouped by size.
     *
     * @return formatted string of free blocks, or a message if none are free
     */
    public String printBlocks() {
        StringBuilder sb = new StringBuilder();
        boolean any = false;

        for (int level = 0; level < freeLists.length; level++) {
            if (!freeLists[level].isEmpty()) {
                any = true;
                int size = 1 << level;
                sb.append(size)
                    .append(":");
                sb.append(freeLists[level].toStringList());
                sb.append("\r\n");
            }
        }

        if (!any) {
            return "No free blocks are available.";
        }

        // Remove final "\r\n".
        sb.setLength(sb.length() - 2);
        return sb.toString();
    }

    /**
     * Get the last expansion message and clear it.
     *
     * @return last expansion message, or empty string if none
     */
    public String getExpandMessage() {
        String m = lastExpandMessage;
        lastExpandMessage = "";
        return m;
    }
}