diheap was designed for the Modit Operating System. Therefore, it was created with the assumption that the linked libraries have direct access to memory and has no other dynamic allocation scheme. Because of these constraints, the heap has an initial capacity as defined by the user through the "heap_create" function. To expand the heap, the user has to allocate the memory following it's bounds.
A vast majority of the technical descriptions of how the heap works are in the header file. see heap.h for more details.
diheap is a thread-unsafe double linked-list bucket heap allocator. It was written to allow for respectably fast variable size object allocations without external memory regions. The heap information is stored in a single heap struct, which is created through heap_create.
When heap_create is called, the library creates a struct called a "crate", which stores the buckets used for heap allocation. Each crate is 4KiB in size, and can store an arbitrary ammount of buckets. When the crate is out of buckets, another crate is appended to the last allocation and is linked to the previous crate.
Buckets act as both a pointer to allocated memory and a node in a doubly linked list. Buckets store their neighbors, the address, size, and if the bucket is occupied. The elements buckets store allows for checking the status of an arbitrary ammount of neighbors from any point in the linked list. Buckets that don't have a memory address assigned to them are added to a free list, which lets the heap allocate more memory for itself. When the freelist is drained, a new crate is created at the end of the address space and the new buckets are added to the freelist.
diheap is designed to "drop in" to any project. I designed the interface to be independent of the system and operate without many quality of life features like dynamic memory and reference counting.
int heap_create(struct heap *heap, uintptr_t at, size_t len);
Populates the heap with the initial crate and bucket lists. Fills the fields in the provided heap object with the bucket lists and usage information.
heap
Pointer to object defined at compile time.
at
Address allocated for heap to operate in
len
Size of memory allocated for heap to operate in. Must be larger than MODIT_HEAP_CRATE_SIZE
return
Success code. Anything that is not zero should be treated as an error code.
void heap_resize(struct heap *heap, size_t newlen);
Marks the space appended by newlen as usable inside of the passed heap.
heap
Pointer to heap object in which to resize.
newlen
Size of memory appended to the heap allocation space. Because the heap cannot be relocated, this is the only way to expand it.
void *heap_alloc(struct heap *heap, size_t size);
Looks for and assigns the best fitting empty block in heap memory. If the block is too large, the heap splits the block into a perfectly sized bucket and a spare bucket. The heap returns the perfectly sized bucket if possible.
heap
Pointer to heap object in which to make the allocation
size
Size of memory allocated in heap.
return
Pointer to memory assigned by heap. If the heap has run out of memory, function returns NULL
void heap_free(struct heap *heap, void *ptr);
Looks for the bucket corresponding to the passed pointer and clears the taken flag bit. When two buckets are adjacent and free, they are merged.
heap
Pointer to heap object in which to make the allocation
size
Size of memory allocated in heap.
return
Pointer to memory assigned by heap. If the heap has run out of memory, function returns NULL
diheap can be built as either a static or linked library
NOTE: build instructions are written assuming linux with gcc
diheap is built using a makefile following GNU Make specifications. To build the library, simply call
make
By default, the makefile builds a shared library without debugging symbols. This can be changed with the following build flags:
SHARED
Defines if the makefile should build a shared library.
default: 1
STATIC
Defines if the makefile should build a static library.
default: 0
TEST
Forces the makefile to build a shared library and test program. Said program automatically runs.
default: 0
LICENSE: MIT (c) 2021 Jon Santmyer (jon@jonsantmyer.com)