Compiler Explorer

Source code

// Basically this:
//  - https://github.com/ennorehling/dlmalloc/blob/master/malloc.c
//  - https://sourceware.org/glibc/wiki/MallocInternals
// but worse.

#define WIN32_LEAN_AND_MEAN
#define NOMINMAX
#include <Windows.h>

typedef unsigned char u8;
typedef char i8;
typedef unsigned short u16;
typedef short i16;
typedef unsigned int u32;
typedef int i32;
typedef unsigned long long u64;
typedef long long i64;

typedef unsigned long long usize;
typedef long long isize;

#if 1
    #define FMT_USIZE_T usize
    #define FMT_ISIZE_T isize
    #define FMT_IMPLEMENTATION
    #include "fmt.h"
    #undef bool
    #undef true
    #undef false
    #undef USIZE_MAX
#endif

typedef _Bool bool;
#define false 0
#define true 1

#if defined(__GNUC__) && !defined(__clang__)
    #define GCC_COMPILER true
#else
    #define GCC_COMPILER false
#endif

#if defined(_MSC_VER) && !defined(__clang__)
    #define MSVC_COMPILER true
#else
    #define MSVC_COMPILER false
#endif

#if defined(__clang__)
    #define CLANG_COMPILER true
#else
    #define CLANG_COMPILER false
#endif

#if GCC_COMPILER || CLANG_COMPILER
    #define NO_RETURN __attribute__((noreturn))
#endif

#if MSVC_COMPILER
    #define NO_RETURN __declspec(noreturn)
#endif

#if defined(NDEBUG) && !defined(_DEBUG)
    #define IS_DEBUG false
#else
    #define IS_DEBUG true
#endif

NO_RETURN void exit_process(i32 exit_code) {
    ExitProcess(exit_code);
}

#define ARRAY_SIZE(array) ((isize) sizeof(array) / sizeof((array)[0]))

// =================================================================================================
//  Configuration
// =================================================================================================

// clang-format off

// Using an integer type smaller than the word size (e.g. i32 and u32) may reduce allocation
// overhead for some allocators (e.g. chunk header size in the heap allocator has the same size as
// the size of this type).
#ifndef ALLOC_SIZE_T
    #define ALLOC_SIZE_T isize
    #define ALLOC_SIZE_MAX ISIZE_MAX

#define ALLOC_USIZE_T usize
    #define ALLOC_USIZE_MAX USIZE_MAX
#endif

// The default alignment of memory returned by the heap allocator. Must be a power of two >= 8 (on
// both 32-bit and 64-bit platforms).
//
// The ">= 8" restriction exists because the heap allocator organizes memory in sequential chunks
// that are sized in multiples of 8. If the alignment requirement was lower, it could lead to an
// 8-byte unaligned chunk, causing all subsequent chunks to also be unaligned, as the chunk
// addresses increase in increments of 8. Consequently, if we later needed to allocate a chunk with
// a higher alignment, it would be impossible to do so within this "unaligned" sequence of chunks.
//
// This restriction also covers the alignment requirements for the HeapAllocatorData struct
// (internal heap allocator state) which is stored within a regular heap allocator chunk.
#ifndef HEAP_ALLOC_ALIGNMENT
    #define HEAP_ALLOC_ALIGNMENT ((usize) sizeof(usize))
#endif

#ifndef ALLOC_ASSERT
    #if IS_DEBUG
        #define ALLOC_ASSERT(condition) assert_impl(condition, #condition, __FILE__, __LINE__)
    #else
        #define ALLOC_ASSERT(condition)
    #endif
#endif

#ifndef ALLOC_MEMCPY
    #define ALLOC_MEMCPY nostd_memcpy
#endif

#ifndef ALLOC_MEMSET
    #define ALLOC_MEMSET nostd_memset
#endif

// clang-format on

// =================================================================================================
//  Common code
// =================================================================================================

#define U32_MAX ((u32) 0 - 1)
#define I32_MAX ((i32) (U32_MAX >> 1))

#define USIZE_MAX ((usize) 0 - 1)
#define ISIZE_MAX ((isize) (USIZE_MAX >> 1))

bool usize_is_power_of_two(usize self) {
    return (self & (self - 1)) == 0;
}

#define UNUSED(x) ((void) (x))

void assert_impl(bool assertion, char const *assertion_string, char const *file_path, isize line) {
    if (!assertion) {

#ifdef FMT_H
        FMT_STDERR(
            "[ERROR] Assertion '{}' failed at {}:{}\n",
            FMT(String, assertion_string),
            FMT(String, file_path),
            FMT(isize, line),
        );
#else
        UNUSED(assertion_string);
        UNUSED(file_path);
        UNUSED(line);
#endif

exit_process(1);
    }
}

#define UNIMPLEMENTED() unimplemented_impl(__FUNCTION__, __FILE__, __LINE__)

NO_RETURN void unimplemented_impl(char const *function_name, char const *file_path, isize line) {

#ifdef FMT_H
    FMT_STDERR(
        "[ERROR] Function '{}' not implemented at {}:{}\n",
        FMT(String, function_name),
        FMT(String, file_path),
        FMT(isize, line),
    );
#else
    UNUSED(function_name);
    UNUSED(file_path);
    UNUSED(line);
#endif

exit_process(1);
}

// "usize size" is for the compatibility with memcpy from "string.h".
void *nostd_memcpy(void *dest_void, void const *source_void, usize size) {
    u8 *dest = dest_void;
    u8 const *source = source_void;

for (usize i = 0; i < size; i += 1) {
        dest[i] = source[i];
    }

return dest_void;
}

// "i32 value" and "usize size" is for the compatibility with memset from "string.h".
void *nostd_memset(void *dest_void, i32 value, usize size) {
    u8 *dest = dest_void;

for (usize i = 0; i < size; i += 1) {
        dest[i] = (u8) value;
    }

return dest;
}

// Not entirely sure, but it seems like taking an arbitrary char pointer and trying to read or write
// to it as if it was a pointer to an integer of a bigger size is considered UB in C, even if the
// pointer is properly aligned and there is enough memory for the bigger integer value.
//
// I don't know if it actually matters in practice, but I tried to avoid the UB by using these
// helper functions for reading and writing integers at random memory locations instead of
// type-punning. Usually compilers are smart enough to optimize these function calls down to a
// single MOV instruction, though, using a custom memcpy implementation might confuse them (e.g.
// MSVC doesn't perform the optimization unless you use the "real" memcpy).

static inline void usize_write(u8 *ptr, usize value) {
    ALLOC_MEMCPY(ptr, &value, sizeof(usize));
}

static inline usize usize_read(u8 *ptr) {
    usize value;
    ALLOC_MEMCPY(&value, ptr, sizeof(usize));
    return value;
}

static inline void isize_write(u8 *ptr, isize value) {
    ALLOC_MEMCPY(ptr, &value, sizeof(isize));
}

static inline isize isize_read(u8 *ptr) {
    isize value;
    ALLOC_MEMCPY(&value, ptr, sizeof(isize));
    return value;
}

// =================================================================================================
//  Generic allocator interface
// =================================================================================================

typedef ALLOC_SIZE_T AllocSize;
typedef ALLOC_USIZE_T AllocUSize;

// clang-format off

#ifdef FMT_H
    #define FMT_AllocSize(type, name, value, ...) FMT_INT(type, name, value, __VA_ARGS__)
    #define FMT_AllocUSize(type, name, value, ...) FMT_INT(type, name, value, __VA_ARGS__)
#endif

// clang-format on

static inline void alloc_size_write(u8 *ptr, AllocSize value) {
    ALLOC_MEMCPY(ptr, &value, sizeof(AllocSize));
}

static inline AllocSize alloc_size_read(u8 *ptr) {
    AllocSize value;
    ALLOC_MEMCPY(&value, ptr, sizeof(AllocSize));
    return value;
}

AllocSize alloc_size_align_up(AllocSize size, usize alignment) {
    ALLOC_ASSERT(alignment > 0 && usize_is_power_of_two(alignment));

usize alignment_mask = alignment - 1;
    usize aligned_size = ((usize) size + alignment_mask) & ~alignment_mask;

if (aligned_size > ALLOC_SIZE_MAX) {
        exit_process(1);
    }

return (AllocSize) aligned_size;
}

AllocSize alloc_size_align_down(AllocSize size, usize alignment) {
    ALLOC_ASSERT(alignment > 0 && usize_is_power_of_two(alignment));

usize alignment_mask = alignment - 1;
    usize aligned_size = (usize) size & ~alignment_mask;

return (AllocSize) aligned_size;
}

typedef void AllocatorData;

typedef enum {
    ALLOC_OP_ALLOC,
    ALLOC_OP_ALLOC_ALIGNED,
    ALLOC_OP_RESIZE,
    ALLOC_OP_DEALLOC,
    ALLOC_OP_DEALLOC_ALL,
    ALLOC_OP_GET_INFO,
} AllocatorOperation;

typedef struct AllocatorInfo {
    usize min_alignment;
    usize max_alignment;
    u32 ops_support_bitfield;
} AllocatorInfo;

// I stole the idea of merging all of the allocator operations into a single function from Odin:
// https://pkg.odin-lang.org/base/runtime/#heap_allocator_proc
//
// Not sure what was the original vision, but I just find it convenient that this way an allocator
// can be represented just with two pointers.
typedef void *(*AllocatorProcedure)(
    AllocatorData *,
    AllocatorOperation,
    AllocSize size,
    usize alignment,
    void *old_memory
);

typedef struct Allocator {
    AllocatorData *data;
    AllocatorProcedure procedure;
} Allocator;

void *alloc(Allocator allocator, AllocSize size) {
    return allocator.procedure(allocator.data, ALLOC_OP_ALLOC, size, 0, NULL);
}

void *alloc_aligned(Allocator allocator, AllocSize size, usize alignment) {
    return allocator.procedure(allocator.data, ALLOC_OP_ALLOC_ALIGNED, size, alignment, NULL);
}

void *resize_alloc(Allocator allocator, void *old_memory, AllocSize new_size, usize alignment) {
    return allocator.procedure(allocator.data, ALLOC_OP_RESIZE, new_size, alignment, old_memory);
}

void dealloc(Allocator allocator, void *old_memory) {
    allocator.procedure(allocator.data, ALLOC_OP_DEALLOC, 0, 0, old_memory);
}

void dealloc_all(Allocator allocator) {
    allocator.procedure(allocator.data, ALLOC_OP_DEALLOC_ALL, 0, 0, NULL);
}

void allocator_get_info(Allocator allocator, AllocatorInfo *allocator_info) {
    allocator.procedure(allocator.data, ALLOC_OP_GET_INFO, 0, 0, allocator_info);
}

bool allocator_supports_operation(AllocatorInfo *alloc_info, AllocatorOperation operation) {
    u32 operation_mask = (u32) 1 << (i32) operation;
    return (alloc_info->ops_support_bitfield & operation_mask) != 0;
}

// =================================================================================================
//  System allocator
// =================================================================================================

typedef struct SystemAllocatorData {
    usize granularity;
} SystemAllocatorData;

void *sys_alloc(SystemAllocatorData *alloc_data, AllocSize requested_size) {
    UNUSED(alloc_data);

return VirtualAlloc(NULL, requested_size, MEM_RESERVE | MEM_COMMIT, PAGE_READWRITE);
}

void *sys_alloc_aligned(
    SystemAllocatorData *alloc_data,
    AllocSize requested_size,
    usize alignment
) {
    if (alignment > alloc_data->granularity) {
        return NULL;
    }

return sys_alloc(alloc_data, requested_size);
}

void sys_dealloc(SystemAllocatorData *alloc_data, void *memory) {
    UNUSED(alloc_data);

VirtualFree(memory, 0, MEM_RELEASE);
}

void sys_alloc_get_info(SystemAllocatorData *alloc_data, AllocatorInfo *alloc_info) {
    alloc_info->min_alignment = alloc_data->granularity;
    alloc_info->max_alignment = alloc_data->granularity;

void *sys_alloc_procedure(
    AllocatorData *alloc_data,
    AllocatorOperation alloc_op,
    AllocSize size,
    usize alignment,
    void *old_memory
) {
    switch (alloc_op) {
    case ALLOC_OP_ALLOC:
    {
        return sys_alloc(alloc_data, size);
    } break;

case ALLOC_OP_ALLOC_ALIGNED:
    {
        return sys_alloc_aligned(alloc_data, size, alignment);
    } break;

case ALLOC_OP_DEALLOC:
    {
        sys_dealloc(alloc_data, old_memory);
    } break;

case ALLOC_OP_GET_INFO:
    {
        sys_alloc_get_info(alloc_data, old_memory);
    } break;

case ALLOC_OP_RESIZE:
    case ALLOC_OP_DEALLOC_ALL:
    {
        return NULL;
    } break;
    }

return NULL;
}

void sys_alloc_create(Allocator *allocator) {
    SystemAllocatorData *alloc_data = HeapAlloc(GetProcessHeap(), 0, sizeof(SystemAllocatorData));
    if (alloc_data == NULL) {
        exit_process(1);
    }

SYSTEM_INFO system_info;
    GetSystemInfo(&system_info);
    alloc_data->granularity = system_info.dwAllocationGranularity;

allocator->data = alloc_data;
    allocator->procedure = sys_alloc_procedure;
}

void sys_alloc_destroy(Allocator allocator) {
    HeapFree(GetProcessHeap(), 0, allocator.data);
}

// =================================================================================================
//  Heap allocator
// =================================================================================================

#define HEAP_ALLOC_ALIGNMENT_MASK (HEAP_ALLOC_ALIGNMENT - 1)

// Whenever you see a pointer to Chunk, it's a pointer to this structure:
// +---------------------+
// | ChunkHeader header  |
// |---------------------| __
// |   Chunk *prev_free  |   \
// |   Chunk *next_free  |    \ user data
// |         ...         |    / section
// | AllocSize prev_size | __/
// +---------------------+
//
// prev_free, next_free, and prev_size are only stored when the chunk is not used.
// header is stored for both used and unused chunks.
// Chunk size includes the size of the header.
typedef void Chunk;

typedef AllocUSize ChunkHeader;

// Chunk sizes need to be divisible at least by 8, so that the lower 3 bits of the size could be
// used to store flags.
#define CHUNK_SIZE_MIN_ALIGNMENT ((usize) 8)

#define CHUNK_HEADER_PREV_IN_USE_BIT ((ChunkHeader) 1 << 0)
#define CHUNK_HEADER_ALLOCATED_DIRECTLY_BIT ((ChunkHeader) 1 << 1)
#define CHUNK_HEADER_IS_FIRST_BIT ((ChunkHeader) 1 << 2)

#define CHUNK_HEADER_SIZE_MASK (~(                                                                 \
    CHUNK_HEADER_PREV_IN_USE_BIT                                                                   \
    | CHUNK_HEADER_ALLOCATED_DIRECTLY_BIT                                                          \
    | CHUNK_HEADER_IS_FIRST_BIT                                                                    \
))

// By making chunk sizes divisible by the memory alignment, only the first chunk within the system
// chunk needs to be manually aligned. This ensures that all subsequent chunks are automatically
// aligned, as each next chunk's address is offset by a multiple of the memory alignment.
#define CHUNK_SIZE_ALIGNMENT HEAP_ALLOC_ALIGNMENT
#define CHUNK_SIZE_ALIGNMENT_MASK HEAP_ALLOC_ALIGNMENT_MASK

// "2 * sizeof(usize)" is for the prev_free and next_free pointers.
// "sizeof(AllocSize)" is for the prev_size boundary tag.
#define CHUNK_MIN_SIZE_UNALIGNED (sizeof(ChunkHeader) + 2 * sizeof(usize) + sizeof(AllocSize))

#define CHUNK_MIN_SIZE ((AllocSize) (                                                              \
    ((AllocUSize) CHUNK_MIN_SIZE_UNALIGNED + CHUNK_SIZE_ALIGNMENT_MASK)                            \
    & ~CHUNK_SIZE_ALIGNMENT_MASK                                                                   \
))

#define GUARD_CHUNK_SIZE ((AllocSize)                                                              \
    ((AllocUSize) sizeof(ChunkHeader) + (AllocUSize) (CHUNK_SIZE_MIN_ALIGNMENT - 1))               \
    & ~((AllocUSize) (CHUNK_SIZE_MIN_ALIGNMENT - 1))                                               \
)

static inline void chunk_header_write(u8 *ptr, ChunkHeader value) {
    ALLOC_MEMCPY(ptr, &value, sizeof(ChunkHeader));
}

static inline ChunkHeader chunk_header_read(u8 *ptr) {
    ChunkHeader value;
    ALLOC_MEMCPY(&value, ptr, sizeof(ChunkHeader));
    return value;
}

static inline AllocSize chunk_get_size(Chunk *chunk) {
    return (AllocSize) (chunk_header_read((u8 *) chunk) & CHUNK_HEADER_SIZE_MASK);
}

static inline void chunk_header_set_size(Chunk *chunk, AllocSize size) {
    ChunkHeader header = chunk_header_read((u8 *) chunk);

ChunkHeader prev_in_use = header & CHUNK_HEADER_PREV_IN_USE_BIT;
    ChunkHeader allocated_directly = header & CHUNK_HEADER_ALLOCATED_DIRECTLY_BIT;
    ChunkHeader is_first = header & CHUNK_HEADER_IS_FIRST_BIT;

chunk_header_write(
        (u8 *) chunk,
        (ChunkHeader) size | is_first | allocated_directly | prev_in_use
    );
}

void chunk_tail_set_size(Chunk *chunk, AllocSize size) {
    u8 *tail_size_ptr = (u8 *) chunk + chunk_get_size(chunk) - sizeof(AllocSize);
    alloc_size_write(tail_size_ptr, size);
}

bool chunk_prev_in_use(Chunk *chunk) {
    return (chunk_header_read((u8 *) chunk) & CHUNK_HEADER_PREV_IN_USE_BIT) != 0;
}

void chunk_set_prev_in_use(Chunk *chunk, bool prev_in_use) {
    ChunkHeader header = chunk_header_read((u8 *) chunk);

if (prev_in_use) {
        chunk_header_write((u8 *) chunk, header | CHUNK_HEADER_PREV_IN_USE_BIT);
    } else {
        chunk_header_write((u8 *) chunk, header & ~CHUNK_HEADER_PREV_IN_USE_BIT);
    }
}

bool chunk_allocated_directly(Chunk *chunk) {
    return (chunk_header_read((u8 *) chunk) & CHUNK_HEADER_ALLOCATED_DIRECTLY_BIT) != 0;
}

void chunk_set_allocated_directly(Chunk *chunk, bool allocated_directly) {
    ChunkHeader header = chunk_header_read((u8 *) chunk);

if (allocated_directly) {
        chunk_header_write((u8 *) chunk, header | CHUNK_HEADER_ALLOCATED_DIRECTLY_BIT);
    } else {
        chunk_header_write((u8 *) chunk, header & ~CHUNK_HEADER_ALLOCATED_DIRECTLY_BIT);
    }
}

bool chunk_is_first(Chunk *chunk) {
    return (chunk_header_read((u8 *) chunk) & CHUNK_HEADER_IS_FIRST_BIT) != 0;
}

void chunk_set_is_first(Chunk *chunk, bool is_first) {
    ChunkHeader header = chunk_header_read((u8 *) chunk);

if (is_first) {
        chunk_header_write((u8 *) chunk, header | CHUNK_HEADER_IS_FIRST_BIT);
    } else {
        chunk_header_write((u8 *) chunk, header & ~CHUNK_HEADER_IS_FIRST_BIT);
    }
}

void *chunk_to_memory(Chunk *chunk) {
    return (u8 *) chunk + sizeof(ChunkHeader);
}

Chunk *memory_to_chunk(void *memory) {
    return (Chunk *) ((u8 *) memory - sizeof(ChunkHeader));
}

AllocSize chunk_prev_size(Chunk *chunk) {
    u8 *prev_size_ptr = (u8 *) chunk - sizeof(AllocSize);
    return alloc_size_read(prev_size_ptr);
}

Chunk *chunk_prev_free(Chunk *chunk) {
    u8 *prev_free_ptr = (u8 *) chunk_to_memory(chunk) + sizeof(Chunk *);
    return (Chunk *) usize_read(prev_free_ptr);
}

void chunk_set_prev_free(Chunk *chunk, Chunk *prev_free) {
    u8 *prev_free_ptr = (u8 *) chunk_to_memory(chunk) + sizeof(Chunk *);
    usize_write(prev_free_ptr, (usize) prev_free);
}

Chunk *chunk_next_free(Chunk *chunk) {
    u8 *next_free_ptr = (u8 *) chunk_to_memory(chunk);
    return (Chunk *) usize_read(next_free_ptr);
}

void chunk_set_next_free(Chunk *chunk, Chunk *next_free) {
    u8 *next_free_ptr = (u8 *) chunk_to_memory(chunk);
    usize_write(next_free_ptr, (usize) next_free);
}

Chunk *chunk_prev(Chunk *chunk) {
    u8 *prev_ptr = (u8 *) chunk - chunk_prev_size(chunk);
    return (Chunk *) prev_ptr;
}

Chunk *chunk_next(Chunk *chunk) {
    u8 *next_ptr = (u8 *) chunk + chunk_get_size(chunk);
    return (Chunk *) next_ptr;
}

#define FAST_BINS_COUNT ((isize) 20)
#define FAST_BIN_MAX_SIZE ((AllocSize) 160)

#define SMALL_BINS_COUNT ((isize) 63)
#define LARGE_BIN_MIN_SIZE ((AllocSize) 512)

#define LARGE_BINS_COUNT ((isize) 63)
#define ALLOC_DIRECTLY_MIN_SIZE ((AllocSize) 1024 * 1024)

#define SIZED_BINS_COUNT (SMALL_BINS_COUNT + LARGE_BINS_COUNT)

// A circular doubly-linked list of free chunks which is represented by a dummy head node which is
// kept in a list at all times. The benefit of a dummy node is that deletion of the first/last
// elements is not different from deleting any other element.
typedef Chunk ChunksBin;

// A singly-linked list of free chunks which is repesented by a dummy head node.
typedef Chunk FastBin;

typedef struct SystemChunk SystemChunk;

struct SystemChunk {
    isize size;
    SystemChunk *next, *prev;
    Chunk *first_chunk;
    u8 data[];
};

typedef struct SystemChunksList {
    SystemChunk *first, *last;
} SystemChunksList;

// Buffer sizes to hold dummy head elements for the linked lists. sizeof(ChunkHeader) is needed
// because prev/next pointers within chunks point at the other chunks' headers.
#define SINGLY_LINKED_BINS_SIZE(bins_count) (sizeof(ChunkHeader) + (bins_count) * sizeof(usize))
#define DOUBLY_LINKED_BINS_SIZE(bins_count) (sizeof(ChunkHeader) + 2 * (bins_count) * sizeof(usize))

typedef struct HeapAllocatorData {
    Allocator system_allocator;
    SystemChunksList system_chunks;

// An array of doubly-linked lists each of which contains chunks of similar sizes. First
    // SMALL_BINS_COUNT lists each contains chunks of the same size, next LARGE_BINS_COUNT have
    // chunk sizes distributed ~ logarithmically within them.
    u8 bins[DOUBLY_LINKED_BINS_SIZE(SIZED_BINS_COUNT)];

// Chunks that have been recently freed or split off larger chunks and have not yet been
    // combined with neighboring free chunks or sorted into size-specific bins.
    u8 unsorted_bin[DOUBLY_LINKED_BINS_SIZE(1)];

// An array of singly-linked lists each of which contains chunks of the same size which are kept
    // separate even if they are adjacent to other chunks. Fast path for small
    // deallocations/allocations.
    u8 fast_bins[SINGLY_LINKED_BINS_SIZE(FAST_BINS_COUNT)];
} HeapAllocatorData;

SystemChunk *system_chunk_alloc(Allocator system_allocator, isize min_system_chunk_data_size) {
    AllocatorInfo system_allocator_info;
    allocator_get_info(system_allocator, &system_allocator_info);

isize system_chunk_size = sizeof(SystemChunk);
    system_chunk_size += min_system_chunk_data_size;
    usize alignment_mask = (usize) system_allocator_info.min_alignment - 1;
    system_chunk_size = (isize) (((usize) system_chunk_size + alignment_mask) & ~alignment_mask);

SystemChunk *system_chunk;
    if (system_allocator_info.min_alignment >= sizeof(usize)) {
        system_chunk = alloc(system_allocator, system_chunk_size);
    } else {
        system_chunk = alloc_aligned(system_allocator, system_chunk_size, sizeof(usize));
    }
    if (system_chunk == NULL) {
        return NULL;
    }

system_chunk->size = system_chunk_size;
    system_chunk->next = NULL;
    system_chunk->prev = NULL;
    system_chunk->first_chunk = NULL;

return system_chunk;
}

void heap_alloc_print_chunks(HeapAllocatorData *alloc_data);
void heap_alloc_print_bins(HeapAllocatorData *alloc_data);

isize bin_index_by_chunk_size(AllocSize chunk_size) {
    if (chunk_size >= ALLOC_DIRECTLY_MIN_SIZE) {
        isize largest_bin_index = SIZED_BINS_COUNT - 1;
        return largest_bin_index;
    }

if (chunk_size < LARGE_BIN_MIN_SIZE) {
        isize small_bin_index = (chunk_size - CHUNK_SIZE_MIN_ALIGNMENT) / CHUNK_SIZE_MIN_ALIGNMENT;
        return small_bin_index;
    }

AllocSize spacing = CHUNK_SIZE_MIN_ALIGNMENT;
    AllocSize const spacing_multiplier = CHUNK_SIZE_MIN_ALIGNMENT;

AllocSize size_from, size_to = LARGE_BIN_MIN_SIZE;

isize bins_count = 32;
    isize base_large_bin_index = 0;

while (bins_count > 0) {
        spacing *= spacing_multiplier;

size_from = size_to;
        size_to += spacing * bins_count;

if (chunk_size < size_to) {
            isize large_bin_index = base_large_bin_index + (chunk_size - size_from) / spacing;
            return SMALL_BINS_COUNT + large_bin_index;
        }

base_large_bin_index += bins_count;
        bins_count /= 2;
    }

bins_count /= 2;
    isize largest_bin_index = SIZED_BINS_COUNT - 1;
    return largest_bin_index;
}

bool chunk_sizes_interval_by_bin_index(
    isize bin_index,
    AllocSize *chunk_size_from,
    AllocSize *chunk_size_to
) {
    if (bin_index < 0 || bin_index >= SIZED_BINS_COUNT) {
        return false;
    }

if (bin_index < SMALL_BINS_COUNT) {
        *chunk_size_from = (bin_index + 1) * CHUNK_SIZE_MIN_ALIGNMENT;
        *chunk_size_to = (bin_index + 2) * CHUNK_SIZE_MIN_ALIGNMENT;
        return true;
    }
    bin_index -= SMALL_BINS_COUNT;

AllocSize spacing = CHUNK_SIZE_MIN_ALIGNMENT * CHUNK_SIZE_MIN_ALIGNMENT;
    *chunk_size_from = LARGE_BIN_MIN_SIZE;

// How many bins which have the same spacing between chunks sizes do we have in front of us
    // (e.g. in the begining we have 32 bins for chunk sizes X..X+64).
    isize next_bins_batch_size = 32;

while (next_bins_batch_size > 0) {
        if (bin_index < next_bins_batch_size) {
            *chunk_size_from += bin_index * spacing;
            break;
        }

*chunk_size_from += next_bins_batch_size * spacing;

spacing *= CHUNK_SIZE_MIN_ALIGNMENT;
        bin_index -= next_bins_batch_size;
        next_bins_batch_size /= 2;
    }

*chunk_size_to = *chunk_size_from + spacing;
    if (*chunk_size_to > ALLOC_DIRECTLY_MIN_SIZE) {
        *chunk_size_to = ALLOC_DIRECTLY_MIN_SIZE;
    }

return true;
}

ChunksBin *sized_bin_by_index(HeapAllocatorData *alloc_data, isize bin_index) {
    return (ChunksBin *) (alloc_data->bins + 2 * sizeof(usize) * bin_index);
}

FastBin *fast_bin_by_index(HeapAllocatorData *alloc_data, isize bin_index) {
    return (ChunksBin *) (alloc_data->fast_bins + sizeof(usize) * bin_index);
}

ChunksBin *sized_bin_by_chunk_size(HeapAllocatorData *alloc_data, AllocSize chunk_size) {
    return sized_bin_by_index(alloc_data, bin_index_by_chunk_size(chunk_size));
}

FastBin *fast_bin_by_chunk_size(HeapAllocatorData *alloc_data, AllocSize chunk_size) {
    ALLOC_ASSERT(chunk_size <= FAST_BIN_MAX_SIZE);

return fast_bin_by_index(alloc_data, chunk_size / CHUNK_SIZE_MIN_ALIGNMENT - 1);
}

bool bin_is_empty(ChunksBin *bin) {
    return bin == chunk_next_free(bin);
}

Chunk *bin_first_chunk(ChunksBin *bin) {
    return chunk_next_free(bin);
}

Chunk *bin_last_chunk(ChunksBin *bin) {
    return chunk_prev_free(bin);
}

Chunk *bin_end(ChunksBin *bin) {
    return (Chunk *) bin;
}

// Does not work for fast bins, because they are neither doubly-linked nor circular.
isize bin_chunks_count(ChunksBin *bin) {
    isize chunks_count = 0;

Chunk *chunks_iter = bin_first_chunk(bin);

while (chunks_iter != bin_end(bin)) {
        chunks_count += 1;
        chunks_iter = chunk_next_free(chunks_iter);
    }

return chunks_count;
}

void bin_chunk_append(ChunksBin *bin, Chunk *new_chunk) {
    Chunk *last_chunk = bin_last_chunk(bin);

chunk_set_next_free(last_chunk, new_chunk);
    chunk_set_prev_free(new_chunk, last_chunk);

chunk_set_next_free(new_chunk, bin);
    chunk_set_prev_free(bin, new_chunk);
}

void bin_chunk_append_sorted(ChunksBin *bin, Chunk *new_chunk) {
    Chunk *chunks_iter = bin_first_chunk(bin);

while (chunks_iter != bin_end(bin)) {
        if (chunk_get_size(new_chunk) > chunk_get_size(chunks_iter)) {
            chunk_set_next_free(chunk_prev_free(chunks_iter), new_chunk);
            chunk_set_prev_free(chunks_iter, new_chunk);

chunk_set_prev_free(new_chunk, chunk_prev_free(chunks_iter));
            chunk_set_next_free(new_chunk, chunks_iter);

return;
        }

chunks_iter = chunk_next_free(chunks_iter);
    }

bin_chunk_append(bin, new_chunk);
}

void chunk_remove_from_free_list(Chunk *chunk) {
    if (chunk_prev_free(chunk) != NULL) {
        chunk_set_next_free(chunk_prev_free(chunk), chunk_next_free(chunk));
    }
    if (chunk_next_free(chunk) != NULL) {
        chunk_set_prev_free(chunk_next_free(chunk), chunk_prev_free(chunk));
    }

chunk_set_next_free(chunk, NULL);
    chunk_set_prev_free(chunk, NULL);
}

void *heap_alloc(HeapAllocatorData *alloc_data, AllocSize requested_size) {
    if (requested_size == 0) {
        return NULL;
    }

AllocSize max_overhead_size = CHUNK_MIN_SIZE + sizeof(ChunkHeader) + CHUNK_SIZE_ALIGNMENT_MASK;
    if (requested_size > ALLOC_SIZE_MAX - max_overhead_size) {
        return NULL;
    }

AllocSize requested_chunk_size = sizeof(ChunkHeader) + requested_size;
    if (requested_chunk_size < CHUNK_MIN_SIZE) {
        requested_chunk_size = CHUNK_MIN_SIZE;
    }
    requested_chunk_size = alloc_size_align_up(requested_chunk_size, CHUNK_SIZE_ALIGNMENT);

if (requested_chunk_size <= FAST_BIN_MAX_SIZE) {
        FastBin *fast_bin = fast_bin_by_chunk_size(alloc_data, requested_chunk_size);
        if (chunk_next_free(fast_bin) != NULL) {
            Chunk *victim = chunk_next_free(fast_bin);
            chunk_set_next_free(fast_bin, chunk_next_free(victim));
            return chunk_to_memory(victim);
        }
    }

if (requested_chunk_size >= ALLOC_DIRECTLY_MIN_SIZE) {
        isize system_chunk_data_size = 0;
        system_chunk_data_size += HEAP_ALLOC_ALIGNMENT_MASK;
        // Offset from the chunk to the system chunk start
        system_chunk_data_size += sizeof(isize);
        system_chunk_data_size += requested_chunk_size;

SystemChunk *system_chunk =
            system_chunk_alloc(alloc_data->system_allocator, system_chunk_data_size);
        if (system_chunk == NULL) {
            return NULL;
        }

// There is always at least one system chunk in the list (the one used to store
        // HeapAllocatorData), so no need to check for empty list.
        system_chunk->prev = alloc_data->system_chunks.last;
        alloc_data->system_chunks.last->next = system_chunk;
        alloc_data->system_chunks.last = system_chunk;

usize chunk_addr = (usize) ((u8 *) system_chunk + sizeof(SystemChunk) + sizeof(isize));
        chunk_addr += sizeof(ChunkHeader);
        chunk_addr = (chunk_addr + HEAP_ALLOC_ALIGNMENT_MASK) & ~HEAP_ALLOC_ALIGNMENT_MASK;
        chunk_addr -= sizeof(ChunkHeader);

Chunk *chunk = (Chunk *) chunk_addr;
        isize chunk_size = ((u8 *) system_chunk + system_chunk->size - (u8 *) (chunk));
        ALLOC_MEMSET(chunk, 0, sizeof(ChunkHeader));
        chunk_header_set_size(chunk, chunk_size);
        chunk_set_prev_in_use(chunk, true);
        chunk_set_allocated_directly(chunk, true);
        chunk_set_is_first(chunk, true);

system_chunk->first_chunk = chunk;

isize_write((u8 *) chunk - sizeof(isize), (u8 *) chunk - (u8 *) system_chunk);

return chunk_to_memory(chunk);
    }

if (requested_chunk_size < LARGE_BIN_MIN_SIZE) {
        ChunksBin *small_bin = sized_bin_by_chunk_size(alloc_data, requested_chunk_size);

if (!bin_is_empty(small_bin)) {
            Chunk *small_chunk = bin_first_chunk(small_bin);

chunk_remove_from_free_list(small_chunk);
            chunk_set_prev_in_use(chunk_next(small_chunk), true);

return chunk_to_memory(small_chunk);
        }
    }

// Consolidate chunks from fast bins and put them into the unsorted bin before proceeding
    // further to avoid fragmentation.
    // for (isize fast_bin_index = 0; fast_bin_index < FAST_BINS_COUNT; fast_bin_index += 1) {
    //     FastBin *fast_bin = fast_bin_by_index(alloc_data, fast_bin_index);
    //
    //     if (chunk_next_free(fast_bin) == NULL) {
    //         continue;
    //     }
    //
    //     Chunk *chunks_iter = chunk_next_free(fast_bin);
    //     while (chunks_iter != NULL) {
    //         chunks_iter = chunk_next_free(chunks_iter);
    //         // TODO: Continue from here.
    //         UNIMPLEMENTED();
    //     }
    // }

Chunk *chunks_iter = bin_first_chunk(alloc_data->unsorted_bin);
    Chunk *unsorted_bin_end = bin_end(alloc_data->unsorted_bin);

while (chunks_iter != unsorted_bin_end) {
        if (chunk_get_size(chunks_iter) == requested_chunk_size) {
            Chunk *victim_chunk = chunks_iter;
            chunk_remove_from_free_list(victim_chunk);
            chunk_set_prev_in_use(chunk_next(victim_chunk), true);
            return chunk_to_memory(victim_chunk);
        } else {
            Chunk *chunk = chunks_iter;
            chunks_iter = chunk_next_free(chunks_iter);

chunk_remove_from_free_list(chunk);

ChunksBin *bin = sized_bin_by_chunk_size(alloc_data, chunk_get_size(chunk));
            if (chunk_get_size(chunks_iter) < LARGE_BIN_MIN_SIZE) {
                bin_chunk_append(bin, chunk);
            } else {
                bin_chunk_append_sorted(bin, chunk);
            }
        }
    }

isize bin_index = bin_index_by_chunk_size(requested_chunk_size);
    while (bin_index < SIZED_BINS_COUNT) {
        ChunksBin *bin = sized_bin_by_index(alloc_data, bin_index);

if (!bin_is_empty(bin)) {
            Chunk *chunks_iter = bin_first_chunk(bin);
            while (chunks_iter != bin_end(bin)) {
                if (chunk_get_size(chunks_iter) < requested_chunk_size) {
                    chunks_iter = chunk_next_free(chunks_iter);
                    continue;
                }

Chunk *victim_chunk = chunks_iter;
                chunk_remove_from_free_list(victim_chunk);

if (chunk_get_size(victim_chunk) - requested_chunk_size >= CHUNK_MIN_SIZE) {
                    Chunk *remainder_chunk = (Chunk *) ((u8 *) victim_chunk + requested_chunk_size);
                    ALLOC_MEMSET(remainder_chunk, 0, sizeof(ChunkHeader));
                    chunk_header_set_size(
                        remainder_chunk,
                        chunk_get_size(victim_chunk) - requested_chunk_size
                    );

chunk_set_prev_in_use(remainder_chunk, true);
                    chunk_set_allocated_directly(remainder_chunk, false);
                    chunk_set_is_first(remainder_chunk, false);
                    chunk_set_prev_free(remainder_chunk, NULL);
                    chunk_set_next_free(remainder_chunk, NULL);
                    chunk_tail_set_size(remainder_chunk, chunk_get_size(remainder_chunk));

bin_chunk_append(&alloc_data->unsorted_bin, remainder_chunk);

chunk_header_set_size(victim_chunk, requested_chunk_size);
                    return chunk_to_memory(victim_chunk);
                } else {
                    chunk_set_prev_in_use(chunk_next(victim_chunk), true);

return chunk_to_memory(victim_chunk);
                }
            }
        }

bin_index += 1;
    }

isize system_chunk_data_size = 0;
    system_chunk_data_size += HEAP_ALLOC_ALIGNMENT_MASK;
    // Offset from the first chunk to the system chunk start
    system_chunk_data_size += sizeof(isize);
    system_chunk_data_size += requested_chunk_size;
    // 2 guard chunks at the end of the system chunk
    system_chunk_data_size += 2 * GUARD_CHUNK_SIZE;

SystemChunk *new_system_chunk =
        system_chunk_alloc(alloc_data->system_allocator, system_chunk_data_size);
    if (new_system_chunk == NULL) {
        return NULL;
    }

usize first_chunk_addr =
        (usize) ((u8 *) new_system_chunk + sizeof(SystemChunk) + sizeof(isize));
    first_chunk_addr += sizeof(ChunkHeader);
    first_chunk_addr = (first_chunk_addr + HEAP_ALLOC_ALIGNMENT_MASK) & ~HEAP_ALLOC_ALIGNMENT_MASK;
    first_chunk_addr -= sizeof(ChunkHeader);

Chunk *first_chunk = (Chunk *) first_chunk_addr;

// How much memory from the begining of the first chunk to the begining of the first of the two
    // guard chunks?
    AllocSize max_first_chunk_size = (u8 *) new_system_chunk
                                     + new_system_chunk->size
                                     - (u8 *) first_chunk
                                     - 2 * GUARD_CHUNK_SIZE;

AllocSize first_chunk_size;
    if (max_first_chunk_size - requested_chunk_size >= CHUNK_MIN_SIZE) {
        first_chunk_size = requested_chunk_size;
    } else {
        first_chunk_size = max_first_chunk_size;
    }

ALLOC_MEMSET(first_chunk, 0, sizeof(ChunkHeader));
    chunk_header_set_size(first_chunk, first_chunk_size);
    chunk_set_prev_in_use(first_chunk, true);
    chunk_set_allocated_directly(first_chunk, false);
    chunk_set_is_first(first_chunk, true);

new_system_chunk->first_chunk = first_chunk;
    isize_write((u8 *) first_chunk - sizeof(isize), (u8 *) first_chunk - (u8 *) new_system_chunk);

Chunk *remainder_chunk = NULL;
    if (first_chunk_size != max_first_chunk_size) {
        remainder_chunk = chunk_next(first_chunk);
        ALLOC_MEMSET(remainder_chunk, 0, sizeof(ChunkHeader));

// Ensure that the remainder size has its lower bits set to zero, but we don't really need
        // to align its size to CHUNK_SIZE_ALIGNMENT here, because this is the last chunk within the
        // system chunk.
        AllocSize remainder_chunk_size = alloc_size_align_down(
            max_first_chunk_size - first_chunk_size,
            CHUNK_SIZE_MIN_ALIGNMENT
        );
        ALLOC_ASSERT(remainder_chunk_size != 0);

chunk_header_set_size(remainder_chunk, remainder_chunk_size);
        chunk_set_prev_in_use(remainder_chunk, true);
        chunk_set_allocated_directly(remainder_chunk, false);
        chunk_set_is_first(remainder_chunk, false);
        chunk_set_prev_free(remainder_chunk, NULL);
        chunk_set_next_free(remainder_chunk, NULL);

bin_chunk_append(alloc_data->unsorted_bin, remainder_chunk);
    }

Chunk *first_guard_chunk;
    if (remainder_chunk != NULL) {
        first_guard_chunk = chunk_next(remainder_chunk);
    } else {
        first_guard_chunk = chunk_next(first_chunk);
    }

chunk_header_set_size(first_guard_chunk, GUARD_CHUNK_SIZE);
    chunk_set_allocated_directly(first_guard_chunk, false);
    chunk_set_is_first(first_guard_chunk, false);
    if (first_chunk_size == max_first_chunk_size) {
        // Could not fit a remainder chunk, the only one is going to get allocated right now.
        chunk_set_prev_in_use(first_guard_chunk, true);
    } else {
        // Could fit a remainder chunk which is going into the unsorted bin.
        chunk_set_prev_in_use(first_guard_chunk, false);
    }

Chunk *second_guard_chunk = chunk_next(first_guard_chunk);
    chunk_header_set_size(second_guard_chunk, GUARD_CHUNK_SIZE);
    chunk_set_prev_in_use(second_guard_chunk, true);
    chunk_set_allocated_directly(second_guard_chunk, false);
    chunk_set_is_first(second_guard_chunk, false);

ALLOC_ASSERT(alloc_data->system_chunks.last != NULL);
    alloc_data->system_chunks.last->next = new_system_chunk;
    new_system_chunk->prev = alloc_data->system_chunks.last->next;
    alloc_data->system_chunks.last = new_system_chunk;

return chunk_to_memory(first_chunk);
}

void *heap_alloc_aligned(
    HeapAllocatorData *alloc_data,
    AllocSize requested_size,
    AllocSize alignment
) {
    UNUSED(alloc_data);
    UNUSED(alignment);

if (requested_size == 0) {
        return NULL;
    }

UNIMPLEMENTED();
}

void *heap_alloc_resize(
    HeapAllocatorData *alloc_data,
    void *old_memory,
    AllocSize requested_new_size
) {
    UNUSED(alloc_data);
    UNUSED(old_memory);
    UNUSED(requested_new_size);

UNIMPLEMENTED();
}

void heap_dealloc(HeapAllocatorData *alloc_data, void *memory) {
    if (memory == NULL) {
        return;
    }

Chunk *chunk = memory_to_chunk(memory);

if (chunk_allocated_directly(chunk)) {
        SystemChunk *system_chunk =
            (SystemChunk *) ((u8 *) chunk - isize_read((u8 *) chunk - sizeof(isize)));

if (system_chunk->prev == NULL) {
            alloc_data->system_chunks.first = system_chunk->next;
        }
        if (system_chunk->next == NULL) {
            alloc_data->system_chunks.last = system_chunk->prev;
        }
        if (system_chunk->prev != NULL) {
            system_chunk->prev->next = system_chunk->next;
        }
        if (system_chunk->next != NULL) {
            system_chunk->next->prev = system_chunk->prev;
        }

dealloc(alloc_data->system_allocator, system_chunk);
        return;
    }

// if (chunk_get_size(chunk) <= FAST_BIN_MAX_SIZE) {
    //     FastBin *fast_bin = fast_bin_by_chunk_size(alloc_data, chunk_get_size(chunk));
    //
    //     // Fast bins are singly-linked lists, elements are added in front of the list.
    //     chunk_set_next_free(chunk, chunk_next_free(fast_bin));
    //     chunk_set_next_free(fast_bin, chunk);
    //
    //     return;
    // }

if (!chunk_prev_in_use(chunk)) {
        Chunk *prev_chunk = chunk_prev(chunk);
        chunk_remove_from_free_list(prev_chunk);

chunk_header_set_size(prev_chunk, chunk_get_size(prev_chunk) + chunk_get_size(chunk));

chunk = prev_chunk;
    }

if (!chunk_prev_in_use(chunk_next(chunk_next(chunk)))) {
        Chunk *next_chunk = chunk_next(chunk);
        chunk_remove_from_free_list(next_chunk);

chunk_header_set_size(chunk, chunk_get_size(chunk) + chunk_get_size(next_chunk));
    }

chunk_set_prev_in_use(chunk_next(chunk), false);
    chunk_tail_set_size(chunk, chunk_get_size(chunk));

bin_chunk_append(&alloc_data->unsorted_bin, chunk);
}

void heap_dealloc_all(HeapAllocatorData *alloc_data) {
    UNUSED(alloc_data);

UNIMPLEMENTED();
}

void heap_alloc_get_info(HeapAllocatorData *alloc_data, AllocatorInfo *alloc_info) {
    UNUSED(alloc_data);

alloc_info->min_alignment = HEAP_ALLOC_ALIGNMENT;
    alloc_info->max_alignment = 0;

alloc_info->ops_support_bitfield = 0;
    alloc_info->ops_support_bitfield |= (u32) 1 << ALLOC_OP_ALLOC;
    alloc_info->ops_support_bitfield |= (u32) 1 << ALLOC_OP_ALLOC_ALIGNED;
    alloc_info->ops_support_bitfield |= (u32) 1 << ALLOC_OP_RESIZE;
    alloc_info->ops_support_bitfield |= (u32) 1 << ALLOC_OP_DEALLOC;
    alloc_info->ops_support_bitfield |= (u32) 1 << ALLOC_OP_DEALLOC_ALL;
    alloc_info->ops_support_bitfield |= (u32) 1 << ALLOC_OP_GET_INFO;
}

void *heap_alloc_procedure(
    AllocatorData *alloc_data,
    AllocatorOperation alloc_op,
    AllocSize size,
    usize alignment,
    void *old_memory
) {
    switch (alloc_op) {
    case ALLOC_OP_ALLOC:
    {
        return heap_alloc(alloc_data, size);
    } break;

case ALLOC_OP_ALLOC_ALIGNED:
    {
        return heap_alloc_aligned(alloc_data, size, alignment);
    } break;

case ALLOC_OP_RESIZE:
    {
        if (alignment <= HEAP_ALLOC_ALIGNMENT) {
            return heap_alloc_resize(alloc_data, old_memory, size);
        } else {
            return NULL;
        }
    } break;

case ALLOC_OP_DEALLOC:
    {
        heap_dealloc(alloc_data, old_memory);
    } break;

case ALLOC_OP_DEALLOC_ALL:
    {
        heap_dealloc_all(alloc_data);
    } break;

case ALLOC_OP_GET_INFO:
    {
        heap_alloc_get_info(alloc_data, old_memory);
    } break;
    }

return NULL;
}

// Heap allocator inner state (HeapAllocatorData) is stored within a regular chunk:
//
// +-----[System chunk]------+
// |         Header          |
// |-------------------------|
// |           ...           |
// |    Padding to reach     |
// |    default alignment    |
// |           ...           |
// |  +-------------------+  |
// |  |   Offset to the   |  |
// |  |   system chunk    |  |
// |  |       start       |  |
// |  +-------------------+  |
// |  +--[Regular chunk]--+  |
// |  |      Header       |  |
// |  |-------------------|  |
// |  | HeapAllocatorData |  |
// |  +-------------------+  |
// |  +--[Regular chunk]--+  |
// |  |      Header       |  |
// |  |-------------------|  |
// |  |  Remaining free   |  |
// |  | space within the  |  |
// |  |   system chunk    |  |
// |  +-------------------+  |
// |  +---[Guard chunk]---+  |
// |  |      Header       |  |
// |  +-------------------+  |
// |  +---[Guard chunk]---+  |
// |  |      Header       |  |
// |  +-------------------+  |
// +-------------------------+

// I don't think we can retrieve the pointer to the system chunk header just from the pointer to the
// first chunk within it alone (+ the constants such as default alignment and headers' sizes).
//
// For example, let's say:
//  - header size = 8 bytes
//  - default alignment = 16 bytes
//  - system chunk requires 8-byte alignment
//
// Then there could be two different placements of a system chunk header and the first chunk within
// it relative to each other, depending on where the system chunk header got allocated in memory:
//
// ---------------------------------------------------
// [System chunk header]          [Header] [User data]
//                      |        |        |
// Alignment:           16       8        16
// ---------------------------------------------------
//          [System chunk header] [Header] [User data]
//                      |        |        |
// Alignment:           16       8        16
// ---------------------------------------------------
//
// So, basically, the problem is that the system chunk header might have weaker alignment than the
// alignment what we might want from the heap allocator by default.
//
// Which means that we need to store the offset from the first chunk to the start of the system
// chunk to be able to retrieve the pointer to the system chunk from the first chunk stored within.

void heap_alloc_create(Allocator system_allocator, Allocator *allocator) {
    AllocSize first_chunk_size = sizeof(ChunkHeader) + sizeof(HeapAllocatorData);
    if (first_chunk_size < CHUNK_MIN_SIZE) {
        first_chunk_size = CHUNK_MIN_SIZE;
    }
    first_chunk_size = alloc_size_align_up(first_chunk_size, CHUNK_SIZE_ALIGNMENT);

isize system_chunk_data_size = 0;
    system_chunk_data_size += HEAP_ALLOC_ALIGNMENT_MASK;
    // Offset from the first chunk to the system chunk start
    system_chunk_data_size += sizeof(isize);
    system_chunk_data_size += first_chunk_size;
    // At least one free chunk that we could place into unsorted bin
    system_chunk_data_size += CHUNK_MIN_SIZE;
    // 2 guard chunks at the end of the system chunk
    system_chunk_data_size += 2 * GUARD_CHUNK_SIZE;

SystemChunk *system_chunk = system_chunk_alloc(system_allocator, system_chunk_data_size);

if (system_chunk == NULL) {
        exit_process(1);
    }

usize first_chunk_addr = (usize) ((u8 *) system_chunk + sizeof(SystemChunk) + sizeof(isize));
    first_chunk_addr += sizeof(ChunkHeader);
    first_chunk_addr = (first_chunk_addr + HEAP_ALLOC_ALIGNMENT_MASK) & ~HEAP_ALLOC_ALIGNMENT_MASK;
    first_chunk_addr -= sizeof(ChunkHeader);

Chunk *first_chunk = (Chunk *) first_chunk_addr;
    ALLOC_MEMSET(first_chunk, 0, sizeof(ChunkHeader));
    chunk_header_set_size(first_chunk, first_chunk_size);
    chunk_set_prev_in_use(first_chunk, true);
    chunk_set_allocated_directly(first_chunk, false);
    chunk_set_is_first(first_chunk, true);

system_chunk->first_chunk = first_chunk;

isize_write((u8 *) first_chunk - sizeof(isize), (u8 *) first_chunk - (u8 *) system_chunk);

Chunk *remainder_chunk = chunk_next(first_chunk);
    ALLOC_MEMSET(remainder_chunk, 0, sizeof(ChunkHeader));

// Allocate the rest of the memory to the remainder chunk...
    AllocSize remainder_chunk_size =
        (AllocSize) (((u8 *) system_chunk + system_chunk->size) - (u8 *) remainder_chunk);
    // ... and two guard chunks at the end.
    remainder_chunk_size -= 2 * GUARD_CHUNK_SIZE;
    remainder_chunk_size = alloc_size_align_down(remainder_chunk_size, CHUNK_SIZE_MIN_ALIGNMENT);

chunk_header_set_size(remainder_chunk, remainder_chunk_size);
    chunk_set_prev_in_use(remainder_chunk, true);
    chunk_set_allocated_directly(remainder_chunk, false);
    chunk_set_is_first(remainder_chunk, false);
    chunk_set_prev_free(remainder_chunk, NULL);
    chunk_set_next_free(remainder_chunk, NULL);

Chunk *first_guard_chunk = chunk_next(remainder_chunk);
    chunk_header_set_size(first_guard_chunk, GUARD_CHUNK_SIZE);
    chunk_set_prev_in_use(first_guard_chunk, false);
    chunk_set_allocated_directly(first_guard_chunk, false);
    chunk_set_is_first(first_guard_chunk, false);

// HeapAllocatorData alignment requirements should be satisified by the HEAP_ALLOC_ALIGNMENT
    // default alignment (it must be >= 8).
    HeapAllocatorData *alloc_data = chunk_to_memory(first_chunk);

ALLOC_MEMSET(alloc_data, 0, sizeof(HeapAllocatorData));
    alloc_data->system_allocator = system_allocator;

// No need to initialize fast bins they are singly linked and elements are always added to the
    // front of the list.
    for (isize bin_index = 0; bin_index < SIZED_BINS_COUNT; bin_index += 1) {
        ChunksBin *bin = sized_bin_by_index(alloc_data, bin_index);
        chunk_set_next_free(bin, bin);
        chunk_set_prev_free(bin, bin);
    }
    chunk_set_next_free(alloc_data->unsorted_bin, alloc_data->unsorted_bin);
    chunk_set_prev_free(alloc_data->unsorted_bin, alloc_data->unsorted_bin);

bin_chunk_append(alloc_data->unsorted_bin, remainder_chunk);

alloc_data->system_chunks.first = system_chunk;
    alloc_data->system_chunks.last = system_chunk;

allocator->data = alloc_data;
    allocator->procedure = heap_alloc_procedure;
}

void heap_alloc_destroy(Allocator allocator) {
    UNUSED(allocator);

UNIMPLEMENTED();
}

// =================================================================================================
//  Heap allocator debug functions
// =================================================================================================

#ifdef FMT_H

void heap_alloc_print_chunk_bins_sizes(HeapAllocatorData *alloc_data) {
    typedef enum {
        BIN_TYPE_NONE,
        BIN_TYPE_SMALL,
        BIN_TYPE_LARGE,
    } BinType;

char const *bin_type_string[] = {
        [BIN_TYPE_NONE] = "none",
        [BIN_TYPE_SMALL] = "small",
        [BIN_TYPE_LARGE] = "large",
    };

// Print which allocation sizes correspond to which chunk bins
    {
        BinType prev_bin_type = BIN_TYPE_NONE;
        ChunksBin *prev_bin = NULL;
        isize prev_bin_index = 0;

AllocSize chunk_size_from = CHUNK_SIZE_MIN_ALIGNMENT,
                  chunk_size_to = CHUNK_SIZE_MIN_ALIGNMENT;

while (true) {
            ChunksBin *bin = sized_bin_by_index(alloc_data, bin_index_by_chunk_size(chunk_size_to));

isize bin_index = bin_index_by_chunk_size(chunk_size_to);
            BinType bin_type;
            if (bin_index < SMALL_BINS_COUNT) {
                bin_type = BIN_TYPE_SMALL;
            } else {
                bin_type = BIN_TYPE_LARGE;
                bin_index -= SMALL_BINS_COUNT;
            }

if (prev_bin != bin && prev_bin != NULL || chunk_size_to == ALLOC_DIRECTLY_MIN_SIZE) {
                u8 interval[64];
                isize interval_size = FMT_STRING(
                    interval,
                    sizeof(interval),
                    "{}..{}",
                    FMT(AllocSize, chunk_size_from),
                    FMT(AllocSize, chunk_size_to),
                );

FMT_STDOUT(
                    "{} chunk sizes | {} bytes spacing | {} bin #{}\n",
                    FMT(StringView, interval, .size = interval_size, .pad = 16),
                    FMT(AllocSize, chunk_size_to - chunk_size_from, .pad = 8),
                    FMT(String, bin_type_string[prev_bin_type]),
                    FMT(isize, prev_bin_index),
                );

chunk_size_from = chunk_size_to;
            }

if (chunk_size_to == ALLOC_DIRECTLY_MIN_SIZE) {
                break;
            }

prev_bin_type = bin_type;
            prev_bin = bin;
            prev_bin_index = bin_index;

chunk_size_to += CHUNK_SIZE_MIN_ALIGNMENT;
        }
    }
}

void heap_alloc_print_chunks(HeapAllocatorData *alloc_data) {
    SystemChunk *system_chunks_iter = alloc_data->system_chunks.first;

while (system_chunks_iter != NULL) {
        FMT_STDOUT(
            "System chunk (0x{address}):\n"
            "    size = {size} bytes\n"
            "\n",
            FMT_KEY(usize, address, (usize) system_chunks_iter, .hex = true),
            FMT_KEY(isize, size, system_chunks_iter->size),
        );

u8 *system_chunk_end_ptr = (u8 *) system_chunks_iter + system_chunks_iter->size;
        Chunk *chunks_iter = system_chunks_iter->first_chunk;

bool met_first_guard_chunk = false, met_second_guard_chunk = false;

while ((u8 *) chunks_iter < system_chunk_end_ptr) {
            // Quit early in case we met two guard chunks and there is definitely not enough memory
            // for more chunks.
            if (met_first_guard_chunk
                && met_second_guard_chunk
                && system_chunk_end_ptr - (u8 *) chunks_iter < CHUNK_SIZE_ALIGNMENT)
            {
                break;
            }

if (chunk_to_memory(chunks_iter) == alloc_data) {
                FMT_STDOUT(
                    "    Chunk with allocator data (0x{address})\n"
                    "        user data starts at 0x{user_data}\n"
                    "        user data size = {size} bytes\n"
                    "\n",
                    FMT_KEY(usize, address, (usize) chunks_iter, .hex = true),
                    FMT_KEY(isize, size, (isize) chunk_get_size(chunks_iter) - sizeof(ChunkHeader)),
                    FMT_KEY(usize, user_data, (usize) chunk_to_memory(chunks_iter), .hex = true),
                );
            } else if (chunk_allocated_directly(chunks_iter)) {
                FMT_STDOUT(
                    "    Directly allocated chunk (0x{address})\n"
                    "        user data starts at 0x{user_data}\n"
                    "        user data size = {size} bytes\n"
                    "        is in use = true\n"
                    "\n",
                    FMT_KEY(usize, address, (usize) chunks_iter, .hex = true),
                    FMT_KEY(isize, size, (isize) chunk_get_size(chunks_iter) - sizeof(ChunkHeader)),
                    FMT_KEY(usize, user_data, (usize) chunk_to_memory(chunks_iter), .hex = true),
                );

// If the chunk is marked as "allocated directly" then it means that it is the only
                // one within the system chunk.
                break;
            } else if (chunk_get_size(chunks_iter) >= CHUNK_MIN_SIZE) {
                FMT_STDOUT(
                    "    Chunk (0x{address}):\n"
                    "        user data starts at 0x{user_data}\n"
                    "        user data size = {size} bytes\n"
                    "        is in use = {is_used}\n"
                    "\n",
                    FMT_KEY(usize, address, (usize) chunks_iter, .hex = true),
                    FMT_KEY(isize, size, (isize) chunk_get_size(chunks_iter) - sizeof(ChunkHeader)),
                    FMT_KEY(bool, is_used, chunk_prev_in_use(chunk_next(chunks_iter))),
                    FMT_KEY(usize, user_data, (usize) chunk_to_memory(chunks_iter), .hex = true),
                );
            } else {
                FMT_STDOUT(
                    "    Guard chunk (0x{address})\n"
                    "\n",
                    FMT_KEY(usize, address, (usize) chunks_iter, .hex = true),
                );

if (!met_first_guard_chunk) {
                    met_first_guard_chunk = true;
                } else if (!met_second_guard_chunk) {
                    met_second_guard_chunk = true;
                }
            }

chunks_iter = chunk_next(chunks_iter);
        }

system_chunks_iter = system_chunks_iter->next;
    }
}

void heap_alloc_print_bins(HeapAllocatorData *alloc_data) {
    bool all_bins_empty = true;

for (isize fast_bin_index = 0; fast_bin_index < FAST_BINS_COUNT; fast_bin_index += 1) {
        ChunksBin *fast_bin = fast_bin_by_index(alloc_data, fast_bin_index);
        if (chunk_next_free(fast_bin) == NULL) {
            continue;
        } else {
            all_bins_empty = false;
        }

isize chunks_count = 0;
        {
            Chunk *chunks_iter = chunk_next_free(fast_bin);
            while (chunks_iter != NULL) {
                chunks_count += 1;
                chunks_iter = chunk_next_free(chunks_iter);
            }
        }

FMT_STDOUT(
            "Fast bin #{} for chunks of size {} bytes ({} chunks):\n",
            FMT(isize, fast_bin_index),
            FMT(AllocSize, (AllocSize) ((fast_bin_index + 1) * CHUNK_SIZE_MIN_ALIGNMENT)),
            FMT(isize, chunks_count),
        );

Chunk *chunks_iter = chunk_next_free(fast_bin);
        while (chunks_iter != NULL) {
            FMT_STDOUT(
                "    Chunk of size {} bytes (0x{})\n",
                FMT(isize, chunk_get_size(chunks_iter)),
                FMT(usize, (usize) chunks_iter, .hex = true),
            );
            chunks_iter = chunk_next_free(chunks_iter);
        }
    }

for (isize bin_index = 0; bin_index < SIZED_BINS_COUNT; bin_index += 1) {
        ChunksBin *bin = sized_bin_by_index(alloc_data, bin_index);

if (bin_is_empty(bin)) {
            continue;
        } else {
            all_bins_empty = false;
        }

AllocSize chunks_size_from, chunks_size_to;
        chunk_sizes_interval_by_bin_index(bin_index, &chunks_size_from, &chunks_size_to);

if (bin_index < SMALL_BINS_COUNT) {
            FMT_STDOUT(
                "Small bin #{} for chunks of size {} bytes ({} chunks):\n",
                FMT(isize, bin_index),
                FMT(AllocSize, chunks_size_from),
                FMT(isize, bin_chunks_count(bin)),
            );
        } else {
            FMT_STDOUT(
                "Large bin #{} for chunks with sizes from {} to {} bytes ({} chunks):\n",
                FMT(isize, bin_index - SMALL_BINS_COUNT),
                FMT(AllocSize, chunks_size_from),
                FMT(AllocSize, chunks_size_to),
                FMT(isize, bin_chunks_count(bin)),
            );
        }

Chunk *chunks_iter = bin_first_chunk(bin);
        while (chunks_iter != bin_end(bin)) {
            FMT_STDOUT(
                "    Chunk of size {} bytes (0x{})\n",
                FMT(isize, chunk_get_size(chunks_iter)),
                FMT(usize, (usize) chunks_iter, .hex = true),
            );
            chunks_iter = chunk_next_free(chunks_iter);
        }
    }

if (!bin_is_empty(alloc_data->unsorted_bin)) {
        all_bins_empty = false;

FMT_STDOUT(
            "Unsorted bin ({} chunks):\n",
            FMT(isize, bin_chunks_count(alloc_data->unsorted_bin)),
        );
        {
            Chunk *chunks_iter = bin_first_chunk(alloc_data->unsorted_bin);
            Chunk *unsorted_bin_end = bin_end(alloc_data->unsorted_bin);
            while (chunks_iter != unsorted_bin_end) {
                FMT_STDOUT(
                    "    Chunk of size {} bytes (0x{})\n",
                    FMT(isize, chunk_get_size(chunks_iter)),
                    FMT(usize, (usize) chunks_iter, .hex = true),
                );
                chunks_iter = chunk_next_free(chunks_iter);
            }
        }
    }

if (all_bins_empty) {
        FMT_STDOUT("{}", FMT(String, "All bins are empty.\n"));
    }

FMT_STDOUT("{}", FMT(char, '\n'));
}

#endif

// =================================================================================================
//  Examples and tests
// =================================================================================================

i32 main(void) {
    Allocator system_allocator;
    sys_alloc_create(&system_allocator);

Allocator allocator;
    heap_alloc_create(system_allocator, &allocator);

FMT_STDOUT(
        "{hr}\n Small and large bins' sizes\n{hr}\n\n",
        FMT_KEY(String, hr, "", .pad = 80, .padder = '='),
    );
    heap_alloc_print_chunk_bins_sizes(allocator.data);
    FMT_STDOUT("{}", FMT(char, '\n'));

// Allocate 0 bytes.
    {
        void *ptr = alloc(allocator, 0);
        ALLOC_ASSERT(ptr == NULL);
        dealloc(allocator, ptr);
    }

// Try to allocate so much memory that it could cause an integer overflow within internal
    // computations.
    {
        void *ptr = alloc(allocator, ALLOC_SIZE_MAX - sizeof(ChunkHeader));
        ALLOC_ASSERT(ptr == NULL);
    }

// Try to allocate a bunch of integers one at a time and then dealloc them.
    {
        i64 *ptrs[16];

for (isize i = 0; i < ARRAY_SIZE(ptrs); i += 1) {
            ptrs[i] = alloc(allocator, sizeof(i64));
            ALLOC_ASSERT(ptrs[i] != NULL);

*ptrs[i] = (i64) i;
        }

i64 control_sum = 0;
        for (isize i = 0; i < ARRAY_SIZE(ptrs); i += 1) {
            control_sum += *ptrs[i];
        }
        ALLOC_ASSERT(control_sum == ARRAY_SIZE(ptrs) * (ARRAY_SIZE(ptrs) - 1) / 2);

for (isize i = 0; i < ARRAY_SIZE(ptrs) / 4; i += 2) {
            dealloc(allocator, ptrs[4 * i]);
            dealloc(allocator, ptrs[4 * i + 1]);
            dealloc(allocator, ptrs[4 * i + 2]);
            dealloc(allocator, ptrs[4 * i + 3]);
        }

// Test allocating from a small bin
        {
            // Trigger collecting all chunks into sized bins
            void *sligtly_large_memory = alloc(allocator, 200);

isize memory_size = 120;
            void *memory[4];

for (isize i = 0; i < ARRAY_SIZE(memory); i += 1) {
                memory[i] = alloc(allocator, memory_size);

ALLOC_ASSERT(memory[i] != NULL);
                ALLOC_MEMSET(memory[i], 0, memory_size);
            }

for (isize i = 0; i < ARRAY_SIZE(memory); i += 1) {
                dealloc(allocator, memory[i]);
            }

dealloc(allocator, sligtly_large_memory);
        }

FMT_STDOUT(
            "{hr}\n Allocator state after allocating and deallocating a bunch of stuff\n{hr}\n\n",
            FMT_KEY(String, hr, "", .pad = 80, .padder = '='),
        );

heap_alloc_print_bins(allocator.data);
        heap_alloc_print_chunks(allocator.data);

for (isize i = 1; i < ARRAY_SIZE(ptrs) / 4; i += 2) {
            dealloc(allocator, ptrs[4 * i]);
            dealloc(allocator, ptrs[4 * i + 1]);
            dealloc(allocator, ptrs[4 * i + 2]);
            dealloc(allocator, ptrs[4 * i + 3]);
        }
    }

// Try to alocate and deallocate a bunch of very large chunks.
    {
        AllocSize memory_size = 2 * ALLOC_DIRECTLY_MIN_SIZE;
        void *memory[4];

for (isize i = 0; i < ARRAY_SIZE(memory); i += 1) {
            memory[i] = alloc(allocator, memory_size);
            ALLOC_ASSERT(memory[i] != NULL);
            ALLOC_MEMSET(memory[i], 0, memory_size);
        }

dealloc(allocator, memory[1]);
        dealloc(allocator, memory[2]);
        dealloc(allocator, memory[0]);
        dealloc(allocator, memory[3]);
    }

// Try to allocate a chunk of memory so large that we don't have one available in the free list
    {
        void *memory = alloc(allocator, 100 * 1024);
        ALLOC_ASSERT(memory != NULL);
        dealloc(allocator, memory);
    }

FMT_STDOUT(
        "{hr}\n Final allocator state\n{hr}\n\n",
        FMT_KEY(String, hr, "", .pad = 80, .padder = '='),
    );

heap_alloc_print_bins(allocator.data);
    heap_alloc_print_chunks(allocator.data);

return 0;
}

Source code

// fmt.h
//
// Include library implementation into the translation unit:
// #define FMT_IMPLEMENTATION

#ifndef FMT_H
#define FMT_H

// Automatically flush file and console writers after each newline. Otherwise, by default, writers
// are only auto-flushed once the internal buffer gets full.
//
// Enable this option, so you don't have to manually flush the writers.
//
// #define FMT_FLUSH_AFTER_NEWLINES

// Include an interface for dynamic allocation of writers:
// #define FMT_DYN_INTERFACE

// Define a custom interface implementation for writing into console and files.
//
// Otherwise, by default:
//  - WriteFile from kernel32 is used on Windows.
//  - write from <unistd.h> is used on Linux.

#ifndef FMT_FILE_T
    #define FMT_USE_DEFAULT_FILE_INTERFACE

#if defined(_WIN32)
        #define FMT_FILE_T void *
        #define FMT_FILE_STDOUT fmt__win32_console_handle(FMT_CONSOLE_STDOUT)
        #define FMT_FILE_STDERR fmt__win32_console_handle(FMT_CONSOLE_STDERR)
        #define FMT_FILE_WRITE(file, ptr, size) fmt__file_write(file, (u8 const *) (ptr), size)
    #elif defined(linux)
        #define FMT_FILE_T int
        #define FMT_FILE_STDOUT ((FMT_FILE_T) 1)
        #define FMT_FILE_STDERR ((FMT_FILE_T) 2)
        #define FMT_FILE_WRITE(file, ptr, size) fmt__file_write(file, (u8 const *) (ptr), size)
    #else
        #error "This platform is not supported by default. " \
               "You need to manually define an interface for writing into console and files."
    #endif
#endif

// Define a custom allocator for dynamic allocation of writers.
//
// Otherwise, by default:
//  - HeapAlloc/HeapFree from kernel32 is used on Windows.
//  - malloc/free from <stdlib.h> is used on Linux.

#if defined(FMT_DYN_INTERFACE) && !defined(FMT_ALLOCATOR_T)
    #define FMT_USE_DEFAULT_ALLOCATOR

#if defined(_WIN32)

#define FMT_ALLOCATOR_T void *
        #define FMT_ALLOCATOR NULL

#define FMT_ALLOC(allocator, size) \
            ((void) (allocator), HeapAlloc(GetProcessHeap(), 0, size))

#define FMT_DEALLOC(allocator, ptr) \
            ((void) (allocator), HeapFree(GetProcessHeap(), 0, ptr))

#elif defined(linux)

#define FMT_ALLOCATOR_T void *
        #define FMT_ALLOCATOR NULL

#define FMT_ALLOC(allocator, size) ((void) (allocator), malloc(size))
        #define FMT_DEALLOC(allocator, ptr) ((void) (allocator), free(ptr))

#else
        #error "This platform is not supported by default. " \
               \
               "You need to either define a custom allocator or disable the interface for " \
               "dynamic allocation of writers."
    #endif
#endif

#ifndef FMT_BUFFER_SIZE
    #define FMT_BUFFER_SIZE ((isize) 4096)
#endif

// Make implementation private to the translation unit:
#ifdef FMT_STATIC_IMPLEMENTATION
    #define FMT_API static
#else
    #define FMT_API
#endif

#ifndef FMT_USIZE_T
    #define FMT_USIZE_T unsigned long
    #define FMT_ISIZE_T long
#endif

#ifndef FMT_U8_T
    #define FMT_U8_T unsigned char
    #define FMT_I8_T char

#define FMT_U16_T unsigned short
    #define FMT_I16_T short

#define FMT_U32_T unsigned int
    #define FMT_I32_T int

#define FMT_U64_T unsigned long long
    #define FMT_I64_T long long
#endif

#ifndef FMT_MEMCPY
    #define FMT_MEMCPY fmt__nostd_memcpy
#endif

#ifndef FMT_MEMMOVE
    #define FMT_MEMMOVE fmt__nostd_memmove
#endif

// =================================================================================================
//  Usage examples
// =================================================================================================

// clang-format off

// Formatting a variety of different types of values.
#if 0
    #define FMT_IMPLEMENTATION
    #include "fmt.h"

int main(void) {
        FMT_STDOUT("Bool: {} or {}\n", FMT(bool, true), FMT(bool, false));

FMT_STDOUT("ASCII char: '{}'\n", FMT(char, '@'));

FMT_STDOUT("Unicode code point: '{}'\n", FMT(CodePoint, 0x1f41b));

FMT_STDOUT("C-style string: \"{}\"\n", FMT(String, "hello"));

FMT_STDOUT(
            "UTF-16 string: \"{}\"\n",
            FMT(U16String,
                u"Оказывается, под линуксом строковые литералы с префиксом L кодируются в UTF-32. "
                u"А этот UTF-16 префикс появился только в C11."),
        );

FMT_STDOUT("Max 64-bit int: {}\n", FMT(i64, I64_MAX, .plus = true));
        FMT_STDOUT("Min 64-bit int: {}\n", FMT(i64, I64_MIN));

FMT_STDOUT(
            "Hex int: 0x{}\n",
            FMT(u32, 0xababa, .hex = true, .uppercase = true, .precision = 8)
        );

FMT_STDOUT("Negative int in binary: 0b{}\n", FMT(i16, -64, .bin = true));

// This writer is stack-allocated.
        FmtWriter console = FMT_STDOUT_WRITER();

i32 cell_width = 5;
        i32 table_size = 21;
        for (i32 i = 0; i < table_size * table_size; i += 1) {
            i32 x = i % table_size, y = i / table_size;

if (x == 0 && y == 0) {
                fmt_write_arg(&console, &FMT(String, "", .pad = cell_width));
            } else if (x == 0 || y == 0) {
                fmt_write_arg(&console, &FMT(i32, x | y, .pad = cell_width, .padder = ' '));
            } else {
                fmt_write_arg(&console, &FMT(i32, x * y, .pad = cell_width, .padder = ' '));
            }

if (x == table_size - 1) {
                fmt_write_char(&console, '\n');
            }
        }

fmt_flush(&console);
    }
#endif

// Defining a custom formatter.
#if 0
    #define FMT_IMPLEMENTATION
    #include "fmt.h"

typedef struct {
        i32 x, y;
    } Vec2;

#define FMT_Vec2(type, name, value, ...) \
        FMT_Pointer(type, name, value, .fmt = fmt_vec2, __VA_ARGS__)

isize fmt_vec2(FmtWriter *writer, void const *vector) {
        Vec2 const *v = vector;
        return FMT_WRITE(writer, "vec2({}, {})", FMT(i32, v->x), FMT(i32, v->y));
    }

int main(void) {
        Vec2 vector = {42, -24};
        FMT_STDOUT("{}\n", FMT(Vec2, &vector));
    }
#endif

// Defining a custom allocator.
#if 0
    #include <stddef.h> // NULL
    #include <stdint.h> // uint8_t, intptr_t
    #include <stdlib.h> // exit

#define FMT_ALLOCATOR_T MyAllocator *
    typedef struct {
        uint8_t buffer[8192];
        intptr_t size;
    } MyAllocator;

#define FMT_ALLOCATOR (&my_allocator)
    MyAllocator my_allocator = {.size = 0};

#define FMT_ALLOC my_alloc
    void *my_alloc(MyAllocator *my_alloc, intptr_t size) {
        if (my_alloc->size + size <= sizeof(my_alloc->buffer)) {
            uint8_t *ptr = my_alloc->buffer + my_alloc->size;
            my_alloc->size += size;
            return ptr;
        } else {
            return NULL;
        }
    }

#define FMT_DEALLOC my_dealloc
    void my_dealloc(MyAllocator *my_alloc, void *ptr) {
        (void) my_alloc;
        (void) ptr;
    }

#define FMT_IMPLEMENTATION
    #define FMT_DYN_INTERFACE
    #include "fmt.h"

FmtWriter get_console(void) {
        FmtWriter console;
        if (!fmt_dyn_console_writer(FMT_ALLOCATOR, FMT_CONSOLE_STDOUT, &console)) {
            exit(1);
        }

return console;
    }

int main(void) {
        FmtWriter console = get_console();

fmt_write_string(&console, "Hey\n");
        fmt_flush(&console);

fmt_dyn_console_writer_destroy(FMT_ALLOCATOR, &console);
    }
#endif

// Rendering to a string + an example of how to use named args.
#if 0
    #include <stdlib.h> // malloc/free

#define FMT_IMPLEMENTATION
    #include "fmt.h"

int main(void) {
        char const *format = "{pill}Rendering{heart}to{heart}a{heart}string{heart}example{pill}\n";
        FormatArg format_args[2] = {
            FMT_KEY(CodePoint, pill, 0x1f48a, .pad = 3, .align = FMT_ALIGN_CENTER),
            FMT_KEY(U16String, heart, u"🩷", .pad = 3, .align = FMT_ALIGN_CENTER),
        };

isize required_string_size = fmt_string_write_args(NULL, 0, format, format_args, 2);
        char *string = malloc(required_string_size);
        if (string == NULL) {
            return 1;
        }

fmt_string_write_args(string, required_string_size, format, format_args, 2);
        FMT_STDOUT("{}", FMT(StringView, string, .size = required_string_size));

free(string);

return 0;
    }
#endif

// clang-format on

// =================================================================================================
//  Typedefs used within the library interface
// =================================================================================================

// I tried to make the library implementation compilable with a C++ compiler, however, heavy use of
// compound literals in macros (e.g. within FMT and FMT_STDOUT) makes it mostly useless in C++.

#ifdef __cplusplus
extern "C" {
#endif

// "ifdef __STDC_VERSION__" check is there because MSVC doesn't define it unless you specify the
// "/std" option explicitly. It would obviously be much better to include <stdbool.h> here instead
// of reinventing the wheel, but I couldn't care less about C standard library headers, I'm sorry.
//
// "#define bool _Bool" instead of "typedef _Bool bool", so that you could #undef my bool, if you
// don't like it.

#if !defined(__cplusplus) && !defined(bool)                                                        \
    && (!defined(__STDC_VERSION__) || __STDC_VERSION__ < 202300L)

#define true 1
    #define false 0
    #define bool _Bool

#endif

// I don't want to prefix these types, so configure them to be the same as in the code where the
// header gets included, if you happen to use the same alias names. (C doesn't complain when you
// repeat the same typedef multiple times.)

typedef FMT_U8_T u8;
typedef FMT_I8_T i8;

typedef FMT_U16_T u16;
typedef FMT_I16_T i16;

typedef FMT_U32_T u32;
typedef FMT_I32_T i32;

typedef FMT_U64_T u64;
typedef FMT_I64_T i64;

typedef FMT_USIZE_T usize;
typedef FMT_ISIZE_T isize;

// =================================================================================================
//  Generic polymorphic writer interface
// =================================================================================================

typedef void (*FmtWriteFunction)(void *writer_data, u8 const *data, isize size);
typedef void (*FmtFlushFunction)(void *writer_data);

typedef struct {
    void *data;
    FmtWriteFunction write;
    FmtFlushFunction flush;
} FmtWriter;

FMT_API void fmt_write(FmtWriter *writer, u8 const *data, isize size);
FMT_API void fmt_flush(FmtWriter *writer);

// =================================================================================================
//  Specific writers' implementations
// =================================================================================================

typedef struct {
    u8 *data;
    isize size;
    isize capacity;
} FmtBuffer;

typedef FMT_FILE_T FmtFile;

typedef struct {
    FmtFile file;
    FmtBuffer buffer;
} FmtFileWriter;

FMT_API void fmt_file_writer_write(void *writer_data, u8 const *data, isize size);
FMT_API void fmt_file_writer_flush(void *writer_data);

typedef enum {
    FMT_CONSOLE_STDOUT,
    FMT_CONSOLE_STDERR,
} FmtConsoleOutputType;

FMT_API FmtFile fmt_console_handle(FmtConsoleOutputType console_type);

typedef FmtFileWriter FmtConsoleWriter;

typedef FmtBuffer FmtStringWriter;

FMT_API void fmt_string_writer_write(void *writer_data, u8 const *data, isize size);
FMT_API void fmt_string_writer_flush(void *writer_data);

// =================================================================================================
//  Dynamically allocated writers (they can be copied around and stored anywhere)
// =================================================================================================

#ifdef FMT_DYN_INTERFACE

typedef FMT_ALLOCATOR_T FmtAllocator;

FMT_API bool fmt_dyn_file_writer(FmtAllocator allocator, FmtFile file, FmtWriter *writer);
FMT_API void fmt_dyn_file_writer_destroy(FmtAllocator allocator, FmtWriter *writer);

FMT_API bool fmt_dyn_console_writer(
    FmtAllocator allocator,
    FmtConsoleOutputType console_type,
    FmtWriter *writer
);
FMT_API void fmt_dyn_console_writer_destroy(FmtAllocator allocator, FmtWriter *writer);

FMT_API bool fmt_dyn_string_writer(
    FmtAllocator allocator,
    char *string,
    isize string_capacity,
    FmtWriter *writer
);
FMT_API void fmt_dyn_string_writer_destroy(FmtAllocator allocator, FmtWriter *writer);

#endif // FMT_DYN_INTERFACE

// =================================================================================================
//  Stack-allocated writers (they don't survive getting out of the outer scope)
// =================================================================================================

// https://en.cppreference.com/w/c/language/compound_literal
// > The unnamed object to which the compound literal evaluates has static storage duration if the
// > compound literal occurs at file scope and automatic storage duration if the compound literal
// > occurs at block scope (in which case the object's lifetime ends at the end of the enclosing
// > block).
//
// Also:
// https://x.com/mono_morphic/status/1869303586502397994

#define FMT_FILE_WRITER(file_) (FmtWriter) {                                                       \
    .data = &(FmtFileWriter) {                                                                     \
        .file = (file_),                                                                           \
        .buffer = {                                                                                \
            .data = (u8[FMT_BUFFER_SIZE]){},                                                       \
            .size = 0,                                                                             \
            .capacity = FMT_BUFFER_SIZE,                                                           \
        },                                                                                         \
    },                                                                                             \
    .write = fmt_file_writer_write,                                                                \
    .flush = fmt_file_writer_flush,                                                                \
}

#define FMT_CONSOLE_WRITER(console_type) (FmtWriter) {                                             \
    .data = &(FmtConsoleWriter) {                                                                  \
        .file = fmt_console_handle(console_type),                                                  \
        .buffer = {                                                                                \
            .data = (u8[FMT_BUFFER_SIZE]){},                                                       \
            .size = 0,                                                                             \
            .capacity = FMT_BUFFER_SIZE,                                                           \
        },                                                                                         \
    },                                                                                             \
    .write = fmt_file_writer_write,                                                                \
    .flush = fmt_file_writer_flush,                                                                \
}
#define FMT_STDOUT_WRITER() FMT_CONSOLE_WRITER(FMT_CONSOLE_STDOUT)
#define FMT_STDERR_WRITER() FMT_CONSOLE_WRITER(FMT_CONSOLE_STDERR)

#define FMT_STRING_WRITER(string, string_capacity) (FmtWriter) {                                   \
    .data = &(FmtStringWriter) {                                                                   \
        .data = (u8 *) (string),                                                                   \
        .size = 0,                                                                                 \
        .capacity = (string_capacity),                                                             \
    },                                                                                             \
    .write = fmt_string_writer_write,                                                              \
    .flush = fmt_string_writer_flush,                                                              \
}

// =================================================================================================
//  Functions for writing primitive values
// =================================================================================================

typedef u32 FmtCodePoint;

FMT_API isize fmt_write_char(FmtWriter *writer, char value);
FMT_API isize fmt_write_char_repeat(FmtWriter *writer, isize repeat_count, char value);
FMT_API isize fmt_write_code_point(FmtWriter *writer, FmtCodePoint code_point);

FMT_API isize fmt_write_sv(FmtWriter *writer, u8 const *data, isize size);
FMT_API isize fmt_write_u16_sv(FmtWriter *writer, u16 const *data, isize size);

FMT_API isize fmt_write_string(FmtWriter *writer, char const *data);
FMT_API isize fmt_write_u16_string(FmtWriter *writer, u16 const *data);

FMT_API isize fmt_write_bool(FmtWriter *writer, bool value);

typedef struct {
    u64 unsigned_value;
    isize size;
    bool is_negative;
} FmtIntValue;

typedef struct {
    u64 base;
    bool make_uppercase;
    bool include_plus;
    isize precision;
} FmtIntParams;

FMT_API isize
fmt_write_int(FmtWriter *writer, FmtIntValue const *value, FmtIntParams const *params);

typedef enum {
    FMT_ALIGN_RIGHT,
    FMT_ALIGN_CENTER,
    FMT_ALIGN_LEFT,
} FormatAlignment;

FMT_API isize
fmt_left_padding_amount(isize content_width, isize padding, FormatAlignment alignment);

FMT_API isize
fmt_right_padding_amount(isize content_width, isize padding, FormatAlignment alignment);

// =================================================================================================
//  Format arguments
// =================================================================================================

typedef enum {
    FORMAT_ARG_INT,
    FORMAT_ARG_BOOL,
    FORMAT_ARG_CHAR,
    FORMAT_ARG_CODE_POINT,
    FORMAT_ARG_STRING_VIEW,
    FORMAT_ARG_U16_STRING_VIEW,
    FORMAT_ARG_STRING,
    FORMAT_ARG_U16_STRING,
    FORMAT_ARG_POINTER,
} FormatArgKind;

#define FMT_PADDING_PARAMS                                                                         \
    isize pad;                                                                                     \
    char padder;                                                                                   \
    FormatAlignment align

typedef struct {
    FMT_PADDING_PARAMS;
} FormatArgPaddingParams;