' Buddy memory allocator: power-of-2 block splitting and merging
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL i  AS LONG
    LOCAL j  AS LONG
    LOCAL level  AS LONG
    LOCAL maxLevel  AS LONG
    LOCAL poolSize  AS LONG
    LOCAL blockSize  AS LONG
    LOCAL reqSize  AS LONG
    LOCAL idx  AS LONG
    LOCAL buddyIdx  AS LONG
    LOCAL parentIdx  AS LONG
    LOCAL splitCount  AS LONG
    LOCAL mergeCount  AS LONG
    LOCAL found AS LONG
    LOCAL freeList(10) AS LONG
    LOCAL blockTree(1024) AS LONG
    LOCAL allocMap(64) AS LONG
    LOCAL allocSize(64) AS LONG
    LOCAL allocCount AS LONG
    LOCAL testSizes(20) AS LONG
    LOCAL numTests AS LONG
    LOCAL treeOffset AS LONG
    LOCAL leftChild  AS LONG
    LOCAL rightChild  AS LONG
    LOCAL localSplit  AS LONG
    LOCAL localMerge  AS LONG
    LOCAL localFound  AS LONG
    poolSize = 1024
    maxLevel = 10
    treeOffset = 512

    FOR i = 0 TO 1023
        blockTree(i) = 0
    NEXT i

    FOR i = 0 TO 9
        freeList(9) = 1
    NEXT i

    allocCount = 0
    splitCount = 0
    mergeCount = 0

    PRINT "=== Buddy Memory Allocator ==="
    PRINT "Pool size:" & STR$(poolSize) & " bytes"
    PRINT "Max order:" & STR$(maxLevel) & " (smallest block: 1 byte)"
    PRINT

    FOR i = 0 TO 9
        freeList(i) = 0
    NEXT i
    freeList(maxLevel) = 1

    numTests = 8
    testSizes(0) = 64
    testSizes(1) = 128
    testSizes(2) = 32
    testSizes(3) = 256
    testSizes(4) = 16
    testSizes(5) = 64
    testSizes(6) = 512
    testSizes(7) = 8

    FOR i = 0 TO numTests - 1
        reqSize = testSizes(i)
        blockSize = 1
        level = 0
        WHILE blockSize < reqSize
            blockSize = blockSize * 2
            level = level + 1
        WEND

        IF blockSize > poolSize THEN
            PRINT "Request" & STR$(i) & ": size" & STR$(reqSize) & " [TOO LARGE]"
            GOTO nextRequest
        END IF

        localFound = 0
        FOR j = level TO maxLevel
            IF freeList(j) > 0 THEN
                freeList(j) = freeList(j) - 1
                localFound = 1
                idx = j
                EXIT FOR
            END IF
        NEXT j

        IF localFound = 0 THEN
            PRINT "Request" & STR$(i) & ": size" & STR$(reqSize) & " [OUT OF MEMORY]"
            GOTO nextRequest
        END IF

        localSplit = 0
        WHILE idx > level
            idx = idx - 1
            freeList(idx) = freeList(idx) + 1
            localSplit = localSplit + 1
            splitCount = splitCount + 1
        WEND

        allocMap(allocCount) = allocCount
        allocSize(allocCount) = blockSize
        allocCount = allocCount + 1
        PRINT "Request" & STR$(i) & ": size" & STR$(reqSize) & " -> block" & STR$(blockSize) & " at order" & STR$(level) & " [OK, splits:" & STR$(localSplit) & "]"
        GOTO nextRequest

nextRequest:
    NEXT i

    PRINT
    PRINT "--- Free some blocks to test merging ---"
    PRINT

    FOR i = 0 TO allocCount - 1 STEP 2
        IF allocSize(i) > 0 THEN
            blockSize = allocSize(i)
            level = 0
            j = 1
            WHILE j < blockSize
                j = j * 2
                level = level + 1
            WEND

            freeList(level) = freeList(level) + 1
            allocSize(i) = 0
            PRINT "Free block" & STR$(i) & " (size" & STR$(blockSize) & ") at order" & STR$(level)

            localMerge = 0
            WHILE level < maxLevel AND freeList(level) > 1
                freeList(level) = freeList(level) - 2
                level = level + 1
                freeList(level) = freeList(level) + 1
                localMerge = localMerge + 1
                mergeCount = mergeCount + 1
            WEND
            IF localMerge > 0 THEN
                PRINT "  Merged" & STR$(localMerge) & " levels upward"
            END IF
        END IF
    NEXT i

    PRINT
    PRINT "--- Free list state ---"
    FOR i = 0 TO maxLevel
        IF freeList(i) > 0 THEN
            PRINT "  Order" & STR$(i) & " (block" & STR$(2^i) & "):" & STR$(freeList(i)) & " free"
        END IF
    NEXT i

    PRINT
    PRINT "Total splits:" & STR$(splitCount)
    PRINT "Total merges:" & STR$(mergeCount)
    PRINT "Buddy allocator simulation complete."

    FUNCTION = 0
END FUNCTION
