C++ Crashkurs

Classes | Public Member Functions | List of all members
Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE > Class Template Reference

Buddy Allocator Template. More...

#include <utils/alloc_buddy.h>

Public Member Functions

uintptr_t malloc (size_t request)
 Allocate uninitialized memory. More...
 
void free (uintptr_t ptr)
 Free allocated memory. More...
 
size_t size (uintptr_t ptr)
 Retrieve the allocated size. More...
 

Detailed Description

template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>
class Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >

Buddy Allocator Template.

This class implements a buddy memory allocator, which is an allocator that allocates memory within a fixed linear address range. It spans the address range with a binary tree that tracks free space. Both malloc and free are O(log N) time where N is the maximum possible number of allocations.

The "buddy" term comes from how the tree is used. When memory is allocated, nodes in the tree are split recursively until a node of the appropriate size is reached. Every split results in two child nodes, each of which is the buddy of the other. When a node is freed, the node and its buddy can be merged again if the buddy is also free. This makes the memory available for larger allocations again.

Template Parameters
MIN_ALLOC_LOG2binary logarithm value of the minimal allocation size, has to be at least 4 (= 16 bytes)
MAX_ALLOC_LOG2binary logarithm value of the maximum total memory which is allocatable
BLOCK_SIZEallocation size will be a multiple of block size.
RESERVECallback function to reserve memory for allocator. First parameter is the start address (on the first call it will be nullptr and the function has to find an adequate position, for all subsequent calls the given address inevitably has to be the start address for the requested memory.) The second parameter is the requested size, always a multiple of BLOCK_SIZE. Returns a pointer to the start address if the requested memory was successfully reserved, otherwise nullptr.

Member Function Documentation

template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>
uintptr_t Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >::malloc ( size_t  request)
inline

Allocate uninitialized memory.

Parameters
requestthe size for the memory
Returns
address of the allocated memory or NULL
template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>
void Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >::free ( uintptr_t  ptr)
inline

Free allocated memory.

Parameters
ptrpointer to the start of a memory allocated using malloc
template<size_t MIN_ALLOC_LOG2, size_t MAX_ALLOC_LOG2, size_t BLOCK_SIZE, void *(*)(void *, size_t) RESERVE>
size_t Allocator::Buddy< MIN_ALLOC_LOG2, MAX_ALLOC_LOG2, BLOCK_SIZE, RESERVE >::size ( uintptr_t  ptr)
inline

Retrieve the allocated size.

ptr pointer to the start of the allocated memory

Returns
size of the allocated memory
The documentation for this class was generated from the following file: