Standard Library

allocators/freelist

The free list allocator is a general-purpose allocator that supports variable-sized allocations and out-of-order deallocation. It maintains a linked list of free memory blocks and supports coalescence (merging adjacent free blocks) to reduce fragmentation.

import "conjure/allocators/freelist" as freelist

When to Use Free List Allocators

Free list allocators are appropriate when:

  • Allocation sizes vary (different structs, variable-length data)
  • You need to free in any order (unpredictable lifetimes)
  • You can’t use specialized allocators (requirements don’t fit)

Common use cases:

  • Asset loading (textures, models of various sizes)
  • Dynamic data structures (trees, graphs)
  • Plugin/extension memory management
  • Fallback allocator when patterns are unknown

Creating a Free List

new

Creates a new free list allocator with the specified capacity.

// Automatic heap allocation (most common)
var fl = freelist.new(4 * 1024 * 1024)  // 4 MB
defer freelist.destroy(&fl)

// With provided buffer (you manage the memory)
var buffer = memory.alloc(4 * 1024 * 1024)
var fl = freelist.new(4 * 1024 * 1024, buffer)
defer memory.free(buffer)

// With best-fit placement policy
var fl = freelist.new(4 * 1024 * 1024, null, PlacementPolicy.BestFit)
defer freelist.destroy(&fl)

Signature:

func new(capacity usize, buffer rawptr = null, policy PlacementPolicy = PlacementPolicy.FirstFit) FreeList

If buffer is null (the default), heap memory is allocated automatically.

destroy

Frees the backing memory of a free list created without a provided buffer.

freelist.destroy(&fl)

Signature:

func destroy(fl *FreeList)

Placement Policies

The free list supports two strategies for selecting which free block to use:

FirstFit

Uses the first free block that’s large enough. Fast allocation but may cause more fragmentation.

var fl = freelist.createWithPolicy(size, freelist.PlacementPolicy.FirstFit)

BestFit

Scans all free blocks to find the smallest one that fits. Slower allocation but reduces fragmentation.

var fl = freelist.createWithPolicy(size, freelist.PlacementPolicy.BestFit)

Signatures:

enum PlacementPolicy {
    FirstFit   // Fast, more fragmentation
    BestFit    // Slower, less fragmentation
}

Allocating Memory

alloc

Allocates a block of the requested size with default alignment.

var data = freelist.alloc(&fl, 1024)
if data == null {
    io.println("Out of memory!")
}

Signature:

func alloc(fl *FreeList, size usize) rawptr

Returns null if there’s no suitable free block.

allocAligned

Allocates memory with a specific alignment.

var aligned = freelist.allocAligned(&fl, 256, 16)

Signature:

func allocAligned(fl *FreeList, size usize, alignment usize) rawptr

allocZeroed

Allocates memory and sets all bytes to zero.

var zeroed = freelist.allocZeroed(&fl, 512)

Signature:

func allocZeroed(fl *FreeList, size usize) rawptr

allocType

Allocates memory for a specific type.

struct Asset { type u8, size usize, data rawptr }
var asset = freelist.allocType[Asset](&fl)

Signature:

func allocType[T](fl *FreeList) rawptr

Freeing Memory

free

Frees a previously allocated block. The block is added to the free list and merged with adjacent free blocks if possible (coalescence).

freelist.free(&fl, data)

Signature:

func free(fl *FreeList, ptr rawptr)

reset

Resets the free list, making all memory available as one large block.

freelist.reset(&fl)

Signature:

func reset(fl *FreeList)

Resizing Allocations

resize

Attempts to resize an allocation. If it can’t grow in place, allocates new memory and copies the data.

var data = freelist.alloc(&fl, 100)
data = freelist.resize(&fl, data, 100, 200)
if data == null {
    io.println("Not enough memory to resize!")
}

Signature:

func resize(fl *FreeList, ptr rawptr, oldSize usize, newSize usize) rawptr

Introspection

used / capacity / freeSpace

Query memory usage.

var bytesUsed = freelist.used(&fl)
var total = freelist.capacity(&fl)
var available = freelist.freeSpace(&fl)

Signatures:

func used(fl *FreeList) usize
func capacity(fl *FreeList) usize
func freeSpace(fl *FreeList) usize

freeBlockCount

Returns the number of separate free blocks. More blocks generally means more fragmentation.

var blocks = freelist.freeBlockCount(&fl)
io.println("Free list has #{blocks} fragments")

Signature:

func freeBlockCount(fl *FreeList) usize

largestFreeBlock

Returns the size of the largest available block. This is the maximum allocation size currently possible.

var maxAlloc = freelist.largestFreeBlock(&fl)
if size > maxAlloc {
    io.println("Cannot allocate #{size} bytes, max is #{maxAlloc}")
}

Signature:

func largestFreeBlock(fl *FreeList) usize

isEmpty

Returns true if all memory is allocated (no free blocks).

if freelist.isEmpty(&fl) {
    io.println("Free list exhausted!")
}

Signature:

func isEmpty(fl *FreeList) bool

fragmentation

Returns a fragmentation ratio from 0.0 (no fragmentation) to 1.0 (heavily fragmented).

Calculated as: 1 - (largest_block / total_free)

var frag = freelist.fragmentation(&fl)
if frag > 0.5 {
    io.println("Warning: Memory is #{frag * 100}% fragmented!")
}

Signature:

func fragmentation(fl *FreeList) f32

Types

FreeList

The main free list allocator structure.

struct FreeList {
    buffer rawptr              // Backing memory
    capacity usize             // Total size
    head *FreeNode             // First free block
    used usize                 // Bytes allocated
    policy PlacementPolicy     // Allocation strategy
}

FreeNode

Internal structure representing a free block.

struct FreeNode {
    size usize      // Block size
    next *FreeNode  // Next free block
}

AllocationHeader

Internal header stored before each allocation.

struct AllocationHeader {
    blockSize usize    // Total block size
    padding usize      // Padding bytes
}

Example: Asset Manager

import "conjure/allocators/freelist" as freelist
import "conjure/io"

var assetMemory = freelist.create(64 * 1024 * 1024)  // 64 MB for assets

struct Asset {
    name string
    type u8
    dataSize usize
    data rawptr
}

func loadAsset(path string) *Asset {
    var size = getAssetSize(path)

    // Allocate header
    var asset = *Asset(freelist.allocType[Asset](&assetMemory))
    if asset == null {
        io.println("Out of asset memory!")
        return null
    }

    // Allocate data
    asset.data = freelist.alloc(&assetMemory, size)
    if asset.data == null {
        freelist.free(&assetMemory, asset)
        io.println("Out of asset memory for data!")
        return null
    }

    asset.name = path
    asset.dataSize = size
    readFile(path, asset.data)

    return asset
}

func unloadAsset(asset *Asset) {
    freelist.free(&assetMemory, asset.data)
    freelist.free(&assetMemory, asset)
}

func getAssetMemoryStats() {
    var used = freelist.used(&assetMemory)
    var total = freelist.capacity(&assetMemory)
    var frag = freelist.fragmentation(&assetMemory)

    io.println("Asset memory: #{used / 1024}KB / #{total / 1024}KB")
    io.println("Fragmentation: #{frag * 100}%")
    io.println("Largest allocatable: #{freelist.largestFreeBlock(&assetMemory) / 1024}KB")
}

Example: Dynamic String Buffer

import "conjure/allocators/freelist" as freelist

var stringMemory = freelist.create(1024 * 1024)  // 1 MB for strings

struct DynamicString {
    data rawptr
    length usize
    capacity usize
}

func newString(initial string) DynamicString {
    var cap = initial.len + 32  // Some extra space
    var data = freelist.alloc(&stringMemory, cap)

    if data != null {
        memory.copy(data, initial.data, initial.len)
    }

    return DynamicString{
        data = data,
        length = initial.len,
        capacity = cap,
    }
}

func appendString(s *DynamicString, text string) {
    var newLen = s.length + text.len

    if newLen > s.capacity {
        // Need to grow
        var newCap = newLen * 2
        s.data = freelist.resize(&stringMemory, s.data, s.capacity, newCap)
        s.capacity = newCap
    }

    memory.copy(s.data[s.length], text.data, text.len)
    s.length = newLen
}

func freeString(s *DynamicString) {
    freelist.free(&stringMemory, s.data)
    s.data = null
    s.length = 0
    s.capacity = 0
}

Example: Plugin Memory Isolation

import "conjure/allocators/freelist" as freelist

// Each plugin gets its own memory region
struct PluginMemory {
    allocator freelist.FreeList
    name string
}

func createPluginMemory(name string, size usize) PluginMemory {
    return PluginMemory{
        allocator = freelist.create(size),
        name = name,
    }
}

func destroyPluginMemory(pm *PluginMemory) {
    freelist.destroy(&pm.allocator)
}

// Plugin API
func pluginAlloc(pm *PluginMemory, size usize) rawptr {
    return freelist.alloc(&pm.allocator, size)
}

func pluginFree(pm *PluginMemory, ptr rawptr) {
    freelist.free(&pm.allocator, ptr)
}

func getPluginMemoryUsage(pm *PluginMemory) f32 {
    var used = freelist.used(&pm.allocator)
    var total = freelist.capacity(&pm.allocator)
    return f32(used) / f32(total)
}

Fragmentation and Coalescence

The free list automatically coalesces (merges) adjacent free blocks when you free memory:

Before free(B):
[A used][B used][C free][D used]

After free(B):
[A used][B+C free........][D used]

This reduces fragmentation over time, but heavy allocation/deallocation patterns can still fragment memory.

Monitoring Fragmentation

func checkFragmentation(fl *freelist.FreeList) {
    var frag = freelist.fragmentation(fl)
    var blocks = freelist.freeBlockCount(fl)

    if frag > 0.7 or blocks > 100 {
        io.println("Warning: High fragmentation detected!")
        io.println("  Fragmentation: #{frag * 100}%")
        io.println("  Free blocks: #{blocks}")
        io.println("  Consider resetting or defragmenting")
    }
}

Defragmentation Strategy

If fragmentation becomes severe, the simplest solution is to:

  1. Allocate a new free list
  2. Copy live data to the new allocator
  3. Destroy the old allocator
func defragmentAssets(assets []Asset) {
    var newMemory = freelist.create(freelist.capacity(&assetMemory))

    for asset in assets {
        var newData = freelist.alloc(&newMemory, asset.dataSize)
        memory.copy(newData, asset.data, asset.dataSize)
        asset.data = newData
    }

    freelist.destroy(&assetMemory)
    assetMemory = newMemory
}

Performance Considerations

OperationTime Complexity
alloc (first-fit)O(n)
alloc (best-fit)O(n)
freeO(n) for sorted insert
resetO(1)

Where n = number of free blocks.

For performance-critical code, prefer:

  • Arena for bulk lifetime management
  • Pool for same-size objects
  • Free list only when you truly need variable sizes and random lifetimes