🧮 Heap Allocator Visualization

ℹ️ About Free Lists

Implicit Free List: Free blocks are found by linear scan through all blocks.

Explicit Free List: Free blocks are linked together using next/prev pointers stored in the payload area, enabling O(1) coalescing with footers.

📊 Performance Metrics

Fragmentation: Percentage of free memory that cannot be used due to being split into small, non-contiguous blocks.

Coalescing: Merging adjacent free blocks to reduce fragmentation (explicit allocator only).

Note: Implicit allocator has NO coalescing - free blocks remain separate!

📚 Key Concepts

• 8-byte Alignment: All blocks are aligned to 8-byte boundaries for performance (ALIGNMENT = 8).
• Headers: Each block has a header containing size and allocation status (size_t).
• Implicit Allocator: NO coalescing, NO footer, uses linear scan O(n) to find free blocks.
• Explicit Allocator: Has footer for free blocks, immediate coalescing, doubly-linked free list O(1).
• Splitting: Large free blocks are split if remainder >= minimum block size.
• First-fit: Allocator searches from the beginning and uses the first suitable block.

🎯 CS107 Implementation Details

This visualization demonstrates the concepts from CS107 Assignment 6:

• Implicit: Header-only, no coalescing, linear search through all blocks
• Explicit: Header + footer (for free blocks), immediate coalescing on free
• Free List: Explicit uses doubly-linked list with prev/next pointers in payload
• Minimum block size: 16 bytes (header + minimum payload)
• Bit flags: ALLOC_BIT (0x1 implicit, 0x2 explicit), LEFT_ALLOC_BIT (0x4 explicit only)