package core:mem/tlsf

Source

Allocator :: struct {
	// Empty lists point at this block to indicate they are free.
	block_null: Block_Header,
	// Bitmaps for free lists.
	fl_bitmap:  u32 `fmt:"-"`,
	sl_bitmap:  [25]u32 `fmt:"-"`,
	// Head of free lists.
	blocks:     [25][32]^Block_Header `fmt:"-"`,
	// Keep track of pools so we can deallocate them.
	// If `pool.allocator` is blank, we don't do anything.
	// We also use this linked list of pools to report
	// statistics like how much memory is still available,
	// fragmentation, etc.
	pool:       Pool,
}

Block_Header :: struct {
	prev_phys_block: ^Block_Header,
	size:            uint,
	// Next and previous free blocks.
	next_free:       ^Block_Header,
	prev_free:       ^Block_Header,
}

Error :: enum u8 {
	None                      = 0, 
	Invalid_Backing_Allocator = 1, 
	Invalid_Alignment         = 2, 
	Backing_Buffer_Too_Small  = 3, 
	Backing_Buffer_Too_Large  = 4, 
	Backing_Allocator_Error   = 5, 
}

Pool :: struct {
	data:      []u8 `fmt:"-"`,
	allocator: runtime.Allocator,
	next:      ^Pool,
}

ALIGN_SIZE :: 1 << ALIGN_SIZE_LOG2

ALIGN_SIZE_LOG2 :: 3 when size_of(uintptr) == 8 else 2

BLOCK_HEADER_FREE :: uint(1 << 0)

BLOCK_HEADER_OVERHEAD :: uint(size_of(uint))

BLOCK_HEADER_PREV_FREE :: uint(1 << 1)

BLOCK_SIZE_MAX :: uint(1) << FL_INDEX_MAX

BLOCK_SIZE_MIN :: uint(size_of(Block_Header) - size_of(^Block_Header))

BLOCK_START_OFFSET: uintptr : offset_of(Block_Header, size) + size_of(Block_Header{}.size)

FL_INDEX_COUNT :: FL_INDEX_MAX - FL_INDEX_SHIFT + 1

FL_INDEX_MAX :: 32 when size_of(uintptr) == 8 else 30

FL_INDEX_SHIFT :: TLSF_SL_INDEX_COUNT_LOG2 + ALIGN_SIZE_LOG2

POOL_OVERHEAD: uint : 2 * BLOCK_HEADER_OVERHEAD

SL_INDEX_COUNT :: 1 << TLSF_SL_INDEX_COUNT_LOG2

SMALL_BLOCK_SIZE :: 1 << FL_INDEX_SHIFT

TLSF_SL_INDEX_COUNT_LOG2 :: #config(TLSF_SL_INDEX_COUNT_LOG2, 5)

adjust_request_size :: proc(size, align: uint) -> (adjusted: uint) {…}

adjust_request_size_with_err :: proc(size, align: uint) -> (adjusted: uint, err: runtime.Allocator_Error) {…}

align_down :: proc(x, align: uint) -> (aligned: uint) {…}

align_ptr :: proc(ptr: rawptr, align: uint) -> (aligned: rawptr) {…}

align_up :: proc(x, align: uint) -> (aligned: uint) {…}

alloc_bytes :: proc(control: ^Allocator, size: uint, align: uint) -> (res: []u8, err: runtime.Allocator_Error) {…}

alloc_bytes_non_zeroed :: proc(control: ^Allocator, size: uint, align: uint) -> (res: []u8, err: runtime.Allocator_Error) {…}

allocator :: proc(t: ^Allocator) -> runtime.Allocator {…}

allocator_proc :: proc(
	allocator_data:  rawptr, 
	mode:            runtime.Allocator_Mode, 
	size, alignment: int, 
	old_memory:      rawptr, 
	old_size:        int, 
	location := #caller_location, 
) -> ([]u8, runtime.Allocator_Error) {…}

block_absorb :: proc(prev: ^Block_Header, block: ^Block_Header) -> (absorbed: ^Block_Header) {…}

block_can_split :: proc(block: ^Block_Header, size: uint) -> (can_split: bool) {…}

block_from_ptr :: proc(ptr: rawptr) -> (block_ptr: ^Block_Header) {…}

block_insert :: proc(control: ^Allocator, block: ^Block_Header) {…}

block_is_free :: proc "contextless" (block: ^Block_Header) -> (is_free: bool) {…}

block_is_last :: proc "contextless" (block: ^Block_Header) -> (is_last: bool) {…}

block_is_prev_free :: proc "contextless" (block: ^Block_Header) -> (is_prev_free: bool) {…}

block_link_next :: proc(block: ^Block_Header) -> (next: ^Block_Header) {…}

block_locate_free :: proc(control: ^Allocator, size: uint) -> (block: ^Block_Header) {…}

block_mark_as_free :: proc(block: ^Block_Header) {…}

block_mark_as_used :: proc(block: ^Block_Header) {…}

block_merge_next :: proc(control: ^Allocator, block: ^Block_Header) -> (merged: ^Block_Header) {…}

block_merge_prev :: proc(control: ^Allocator, block: ^Block_Header) -> (merged: ^Block_Header) {…}

block_next :: proc(block: ^Block_Header) -> (next: ^Block_Header) {…}

block_prepare_used :: proc(control: ^Allocator, block: ^Block_Header, size: uint) -> (res: []u8, err: runtime.Allocator_Error) {…}

block_prev :: proc(block: ^Block_Header) -> (prev: ^Block_Header) {…}

block_remove :: proc(control: ^Allocator, block: ^Block_Header) {…}

block_set_free :: proc "contextless" (block: ^Block_Header) {…}

block_set_prev_free :: proc "contextless" (block: ^Block_Header) {…}

block_set_prev_used :: proc "contextless" (block: ^Block_Header) {…}

block_set_size :: proc "contextless" (block: ^Block_Header, size: uint) {…}

block_set_used :: proc "contextless" (block: ^Block_Header) {…}

block_size :: proc "contextless" (block: ^Block_Header) -> (size: uint) {…}

block_split :: proc(block: ^Block_Header, size: uint) -> (remaining: ^Block_Header) {…}

block_to_ptr :: proc(block: ^Block_Header) -> (ptr: rawptr) {…}

block_trim_free :: proc(control: ^Allocator, block: ^Block_Header, size: uint) {…}

block_trim_free_leading :: proc(control: ^Allocator, block: ^Block_Header, size: uint) -> (remaining: ^Block_Header) {…}

block_trim_used :: proc(control: ^Allocator, block: ^Block_Header, size: uint) {…}

clear :: proc(control: ^Allocator) {…}

destroy :: proc(control: ^Allocator) {…}

ffs :: proc "contextless" (word: u32) -> (bit: i32) {…}

fls :: proc "contextless" (word: u32) -> (bit: i32) {…}

fls_uint :: proc "contextless" (size: uint) -> (bit: i32) {…}

free_with_size :: proc(control: ^Allocator, ptr: rawptr, size: uint) {…}

init_from_allocator :: proc(control: ^Allocator, backing: runtime.Allocator, initial_pool_size: int, new_pool_size: int = 0) -> Error {…}

init_from_buffer :: proc(control: ^Allocator, buf: []u8) -> Error {…}

insert_free_block :: proc(control: ^Allocator, block: ^Block_Header, fl: i32, sl: i32) {…}

mapping_insert :: proc(size: uint) -> (fl, sl: i32) {…}

mapping_round :: proc(size: uint) -> (rounded: uint) {…}

mapping_search :: proc(size: uint) -> (fl, sl: i32) {…}

offset_to_block :: proc(ptr: rawptr, size: uint) -> (block: ^Block_Header) {…}

offset_to_block_backwards :: proc(ptr: rawptr, size: uint) -> (block: ^Block_Header) {…}

pool_add :: proc(control: ^Allocator, pool: []u8) -> (err: Error) {…}

pool_remove :: proc(control: ^Allocator, pool: []u8) {…}

remove_free_block :: proc(control: ^Allocator, block: ^Block_Header, fl: i32, sl: i32) {…}

resize :: proc(control: ^Allocator, ptr: rawptr, old_size, new_size: uint, alignment: uint) -> (res: []u8, err: runtime.Allocator_Error) {…}

resize_non_zeroed :: proc(control: ^Allocator, ptr: rawptr, old_size, new_size: uint, alignment: uint) -> (res: []u8, err: runtime.Allocator_Error) {…}

search_suitable_block :: proc(control: ^Allocator, fli, sli: ^i32) -> (block: ^Block_Header) {…}

init :: proc{
	init_from_buffer,
	init_from_allocator,
}