235 lines
5.8 KiB
C
235 lines
5.8 KiB
C
/*
|
|
* spaceship: a portable simple tree structured-allocator for static memory,
|
|
* with full memory dump-and-restore functionality
|
|
* (c) 2020 Shiz
|
|
*/
|
|
#pragma once
|
|
#include <stdint.h>
|
|
#include <stddef.h>
|
|
|
|
#define SPACESHIP_WITH_SUB 1
|
|
#define SPACESHIP_WITH_PARENT 1 && SPACESHIP_WITH_SUB
|
|
#define SPACESHIP_WITH_PREV 1
|
|
|
|
|
|
enum spaceship_flag
|
|
{
|
|
SPACESHIP_FLAG_LAST = 1,
|
|
SPACESHIP_FLAG_USED = 2,
|
|
};
|
|
|
|
struct spaceship_chunk
|
|
{
|
|
size_t ssc_size;
|
|
#if SPACESHIP_WITH_SUB
|
|
size_t ssc_base;
|
|
#endif
|
|
#if SPACESHIP_WITH_PARENT
|
|
ptrdiff_t ssc_parent;
|
|
#endif
|
|
#if SPACESHIP_WITH_PREV
|
|
ptrdiff_t ssc_prev;
|
|
#endif
|
|
uint8_t ssc_flags;
|
|
};
|
|
|
|
|
|
/*
|
|
* init features
|
|
*/
|
|
|
|
/* init spaceship static memory chunk */
|
|
void spaceship_init(void *chunk, size_t size);
|
|
/* allocate `size` bytes in chunk */
|
|
void *spaceship_alloc(void *chunk, size_t size);
|
|
/* free previously-allocated bytes */
|
|
void spaceship_free(struct spaceship_chunk *chunk);
|
|
/* defragment chunk. only do this if there are no active pointers. */
|
|
void spaceship_defrag(struct spaceship_chunk *chunk);
|
|
|
|
static inline size_t spaceship_get_size(struct spaceship_chunk *chunk)
|
|
{
|
|
if (!chunk || !(chunk->ssc_flags & SPACESHIP_FLAG_USED)) {
|
|
return 0;
|
|
}
|
|
return chunk->ssc_size;
|
|
}
|
|
|
|
#if SPACESHIP_WITH_SUB
|
|
/* init sub-allocation space, leaving `base_size` bytes for the base structure */
|
|
int spaceship_init_sub(struct spaceship_chunk *chunk, size_t base_size);
|
|
|
|
static inline size_t spaceship_get_sub_size(struct spaceship_chunk *chunk)
|
|
{
|
|
if (!chunk || !(chunk->ssc_flags & SPACESHIP_FLAG_USED)) {
|
|
return 0;
|
|
}
|
|
return chunk->ssc_size - chunk->ssc_base;
|
|
}
|
|
#endif
|
|
|
|
|
|
/*
|
|
* tree features
|
|
*/
|
|
static inline struct spaceship_chunk *spaceship_get_next(struct spaceship_chunk *chunk)
|
|
{
|
|
if (!chunk || chunk->ssc_flags & SPACESHIP_FLAG_LAST) {
|
|
return NULL;
|
|
}
|
|
return (struct spaceship_chunk *)((uintptr_t)chunk + chunk->ssc_size);
|
|
}
|
|
|
|
/* get first allocated memory in chunk */
|
|
static inline void *spaceship_get_first_used(void *p)
|
|
{
|
|
struct spaceship_chunk *chunk = p;
|
|
while (chunk && !(chunk->ssc_flags & SPACESHIP_FLAG_USED)) {
|
|
chunk = spaceship_get_next(chunk);
|
|
}
|
|
return chunk;
|
|
}
|
|
|
|
/* get last allocated memory in chunk */
|
|
static inline void *spaceship_get_last_used(void *p)
|
|
{
|
|
struct spaceship_chunk *chunk = p, *used = NULL;
|
|
while (chunk) {
|
|
if (chunk->ssc_flags & SPACESHIP_FLAG_USED) {
|
|
used = chunk;
|
|
}
|
|
chunk = spaceship_get_next(chunk);
|
|
}
|
|
return used;
|
|
}
|
|
|
|
/* get next allocated sibling */
|
|
static inline void *spaceship_get_next_sibling(struct spaceship_chunk *chunk)
|
|
{
|
|
return spaceship_get_first_used(spaceship_get_next(chunk));
|
|
}
|
|
|
|
|
|
#if SPACESHIP_WITH_SUB
|
|
/* get sub-allocation chunk */
|
|
static inline struct spaceship_chunk *spaceship_get_sub(struct spaceship_chunk *chunk)
|
|
{
|
|
if (!chunk || chunk->ssc_base == chunk->ssc_size) {
|
|
return NULL;
|
|
}
|
|
return (struct spaceship_chunk *)((uintptr_t)chunk + chunk->ssc_base);
|
|
}
|
|
|
|
/* get first allocated child */
|
|
static inline void *spaceship_get_first_child(struct spaceship_chunk *chunk)
|
|
{
|
|
return spaceship_get_first_used(spaceship_get_sub(chunk));
|
|
}
|
|
|
|
/* get last allocated child */
|
|
static inline void *spaceship_get_last_child(struct spaceship_chunk *chunk)
|
|
{
|
|
return spaceship_get_last_used(spaceship_get_sub(chunk));
|
|
}
|
|
#endif
|
|
|
|
|
|
#if SPACESHIP_WITH_PARENT
|
|
/* get parent */
|
|
static inline void *spaceship_get_parent(struct spaceship_chunk *chunk)
|
|
{
|
|
if (!chunk || !chunk->ssc_parent) {
|
|
return NULL;
|
|
}
|
|
return (struct spaceship_chunk *)((uintptr_t)chunk - chunk->ssc_parent);
|
|
}
|
|
#endif
|
|
|
|
|
|
#if SPACESHIP_WITH_PREV
|
|
static inline struct spaceship_chunk *spaceship_get_prev(struct spaceship_chunk *chunk)
|
|
{
|
|
if (!chunk || !chunk->ssc_prev) {
|
|
return NULL;
|
|
}
|
|
return (struct spaceship_chunk *)((uintptr_t)chunk - chunk->ssc_prev);
|
|
}
|
|
#elif SPACESHIP_WITH_PARENT
|
|
static inline struct spaceship_chunk *spaceship_get_prev(struct spaceship_chunk *chunk)
|
|
{
|
|
struct spaceship_chunk *c = spaceship_get_parent(chunk), *prev = NULL;
|
|
if (!c) {
|
|
return NULL;
|
|
}
|
|
|
|
c = spaceship_get_first_child(c);
|
|
while ((c = spaceship_get_next(c) != chunk && c) {
|
|
prev = c;
|
|
}
|
|
if (!c) {
|
|
prev = NULL;
|
|
}
|
|
|
|
return prev;
|
|
}
|
|
#endif
|
|
|
|
#if SPACESHIP_WITH_PREV || SPACESHIP_WITH_PARENT
|
|
/* get first allocated memory in chunk, backwards */
|
|
static inline void *spaceship_get_first_used_backwards(void *p)
|
|
{
|
|
struct spaceship_chunk *chunk = p, *used = NULL;
|
|
while (chunk) {
|
|
if (chunk->ssc_flags & SPACESHIP_FLAG_USED) {
|
|
used = chunk;
|
|
}
|
|
chunk = spaceship_get_prev(chunk);
|
|
}
|
|
return used;
|
|
}
|
|
|
|
/* get last allocated memory in chunk, backwards */
|
|
static inline void *spaceship_get_last_used_backwards(void *p)
|
|
{
|
|
struct spaceship_chunk *chunk = p;
|
|
while (chunk && !(chunk->ssc_flags & SPACESHIP_FLAG_USED)) {
|
|
chunk = spaceship_get_prev(chunk);
|
|
}
|
|
return chunk;
|
|
}
|
|
#endif
|
|
|
|
#if SPACESHIP_WITH_PREV
|
|
/* get previous allocated sibling */
|
|
static inline void *spaceship_get_prev_sibling(struct spaceship_chunk *chunk)
|
|
{
|
|
return spaceship_get_last_used_backwards(spaceship_get_prev(chunk));
|
|
}
|
|
#elif SPACESHIP_WITH_PARENT
|
|
/* get previous allocated sibling */
|
|
static inline void *spaceship_get_prev_sibling(struct spaceship_chunk *chunk)
|
|
{
|
|
struct spaceship_chunk *c = spaceship_get_parent(chunk), *prev = NULL;
|
|
if (!c) {
|
|
return NULL;
|
|
}
|
|
|
|
uint8_t flags = chunk->ssc_flags;
|
|
chunk->ssc_flags |= SPACESHIP_FLAG_USED;
|
|
|
|
c = spaceship_get_first_child(c);
|
|
while ((c = spaceship_get_next_sibling(c) != chunk && c) {
|
|
prev = c;
|
|
}
|
|
if (!c) {
|
|
prev = NULL;
|
|
}
|
|
|
|
chunk->ssc_flags = flags;
|
|
return prev;
|
|
}
|
|
#endif
|
|
|
|
|
|
/* dump/restore features: just copy around the block of memory, or save it to a file! */
|