' Bitmap-based memory allocator — first-fit search across a bitmap of blocks
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL i  AS LONG
    LOCAL j  AS LONG
    LOCAL k  AS LONG
    LOCAL numBlocks  AS LONG
    LOCAL blockSize  AS LONG
    LOCAL totalMem  AS LONG
    LOCAL numBitmapWords  AS LONG
    LOCAL needBlocks  AS LONG
    LOCAL startBlock  AS LONG
    LOCAL count  AS LONG
    LOCAL found  AS LONG
    LOCAL fits  AS LONG
    LOCAL canAlloc  AS LONG
    LOCAL allocStart  AS LONG
    LOCAL allocBlocks  AS LONG
    LOCAL bitsRemaining  AS LONG
    LOCAL bitPos  AS LONG
    LOCAL wordIdx  AS LONG
    LOCAL bitIdx  AS LONG
    LOCAL testVal  AS LONG
    LOCAL tempWord  AS LONG
    LOCAL maskBit  AS LONG
    LOCAL bitmap(32) AS LONG
    LOCAL allocTable(100) AS LONG
    LOCAL allocSizes(100) AS LONG
    LOCAL allocCount  AS LONG
    LOCAL freeCount  AS LONG
    LOCAL freeMe  AS LONG
    LOCAL ops(30) AS LONG
    LOCAL opCount  AS LONG
    LOCAL opType  AS LONG
    LOCAL freed AS LONG

    numBlocks = 256
    blockSize = 16
    totalMem = numBlocks * blockSize
    numBitmapWords = 8

    FOR i = 0 TO 31
        bitmap(i) = 0
    NEXT i
    FOR i = 0 TO 99
        allocTable(i) = -1
        allocSizes(i) = 0
    NEXT i
    allocCount = 0
    freeCount = 0

    PRINT "=== Bitmap Memory Allocator ==="
    PRINT "Total memory:" & STR$(totalMem) & " bytes"
    PRINT "Block size:" & STR$(blockSize) & " bytes"
    PRINT "Number of blocks:" & STR$(numBlocks)
    PRINT "Bitmap size:" & STR$(numBitmapWords) & " DWORDs (" & STR$(numBitmapWords * 32) & " bits)"
    PRINT

    opCount = 20
    ops(0) = 100
    ops(1) = 50
    ops(2) = 30
    ops(3) = 200
    ops(4) = 80
    ops(5) = -3
    ops(6) = 60
    ops(7) = 120
    ops(8) = 40
    ops(9) = -0
    ops(10) = 90
    ops(11) = 150
    ops(12) = -2
    ops(13) = 70
    ops(14) = 110
    ops(15) = -5
    ops(16) = 180
    ops(17) = 45
    ops(18) = -1
    ops(19) = 55

    FOR i = 0 TO opCount - 1
        opType = ops(i)
        IF opType > 0 THEN
            needBlocks = opType / blockSize
            IF opType MOD blockSize > 0 THEN
                needBlocks = needBlocks + 1
            END IF
            IF needBlocks < 1 THEN needBlocks = 1
            IF needBlocks > numBlocks THEN needBlocks = numBlocks

            found = -1
            j = 0
            WHILE j < numBlocks AND found = -1
                IF (bitmap(j / 32) AND (1 SHL (j MOD 32))) = 0 THEN
                    fits = 1
                    k = 0
                    WHILE k < needBlocks AND fits = 1
                        IF j + k >= numBlocks THEN
                            fits = 0
                        ELSE
                            IF (bitmap((j + k) / 32) AND (1 SHL ((j + k) MOD 32))) > 0 THEN
                                fits = 0
                            END IF
                        END IF
                        k = k + 1
                    WEND
                    IF fits = 1 THEN
                        found = j
                    END IF
                END IF
                j = j + 1
            WEND

            IF found >= 0 THEN
                FOR k = 0 TO needBlocks - 1
                    bitPos = found + k
                    wordIdx = bitPos / 32
                    bitIdx = bitPos MOD 32
                    bitmap(wordIdx) = bitmap(wordIdx) OR (1 SHL bitIdx)
                NEXT k
                allocTable(allocCount) = found
                allocSizes(allocCount) = needBlocks * blockSize
                PRINT "ALLOC " & FORMAT$(needBlocks * blockSize) & " bytes at block" & STR$(found) & " (" & STR$(needBlocks) & " blocks)"
                allocCount = allocCount + 1
            ELSE
                PRINT "ALLOC " & FORMAT$(opType) & " bytes: FAILED (no contiguous space)"
            END IF
        ELSE
            freeMe = -opType
            IF freeMe < allocCount AND allocTable(freeMe) >= 0 THEN
                startBlock = allocTable(freeMe)
                freed = allocSizes(freeMe)
                needBlocks = freed / blockSize
                IF freed MOD blockSize > 0 THEN
                    needBlocks = needBlocks + 1
                END IF
                FOR k = 0 TO needBlocks - 1
                    bitPos = startBlock + k
                    wordIdx = bitPos / 32
                    bitIdx = bitPos MOD 32
                    bitmap(wordIdx) = bitmap(wordIdx) AND (NOT (1 SHL bitIdx))
                NEXT k
                PRINT "FREE  alloc" & STR$(freeMe) & " (" & STR$(freed) & " bytes at block" & STR$(startBlock) & ")"
                allocTable(freeMe) = -1
                allocSizes(freeMe) = 0
                freeCount = freeCount + 1
            ELSE
                PRINT "FREE  alloc" & STR$(freeMe) & ": already freed or invalid"
            END IF
        END IF
    NEXT i

    PRINT
    PRINT "=== Bitmap State ==="
    FOR i = 0 TO numBitmapWords - 1
        IF bitmap(i) > 0 THEN
            PRINT "  Bitmap[" & FORMAT$(i) & "] = " & FORMAT$(bitmap(i)) & " (bits " & FORMAT$(i * 32) & "-" & FORMAT$(i * 32 + 31) & ")"
        END IF
    NEXT i

    count = 0
    FOR i = 0 TO numBlocks - 1
        IF (bitmap(i / 32) AND (1 SHL (i MOD 32))) = 0 THEN
            count = count + 1
        END IF
    NEXT i

    PRINT
    PRINT "Free blocks:" & STR$(count) & "/" & STR$(numBlocks)
    PRINT "Free memory:" & STR$(count * blockSize) & "/" & STR$(totalMem) & " bytes"
    PRINT "Allocation count:" & STR$(allocCount)
    PRINT "Free count:" & STR$(freeCount)
    PRINT "Bitmap allocator simulation complete."

    FUNCTION = 0
END FUNCTION
