172 lines
4.8 KiB
C
172 lines
4.8 KiB
C
#include <string.h>
|
|
#include "spaceship.h"
|
|
|
|
|
|
void spaceship_init(void *p, size_t size)
|
|
{
|
|
struct spaceship_chunk *chunk = p;
|
|
chunk->ssc_size = size;
|
|
chunk->ssc_flags = SPACESHIP_FLAG_LAST;
|
|
#if SPACESHIP_WITH_SUB
|
|
chunk->ssc_base = size;
|
|
#endif
|
|
#if SPACESHIP_WITH_PARENT
|
|
chunk->ssc_parent = 0;
|
|
#endif
|
|
#if SPACESHIP_WITH_PREV
|
|
chunk->ssc_prev = 0;
|
|
#endif
|
|
}
|
|
|
|
void *spaceship_alloc(void *p, size_t size)
|
|
{
|
|
struct spaceship_chunk *chunk = p;
|
|
if (size < sizeof(*chunk)) {
|
|
return NULL;
|
|
}
|
|
|
|
for (; chunk; chunk = spaceship_get_next(chunk)) {
|
|
if (chunk->ssc_flags & SPACESHIP_FLAG_USED || chunk->ssc_size < size) {
|
|
continue;
|
|
}
|
|
/* usable chunk! do we have any leftover size? */
|
|
if (chunk->ssc_size > size) {
|
|
size_t remain = chunk->ssc_size - size;
|
|
if (remain > sizeof(*chunk)) {
|
|
/* subdivide chunk if reasonable */
|
|
uint8_t flags = chunk->ssc_flags;
|
|
chunk->ssc_flags &= ~SPACESHIP_FLAG_LAST;
|
|
chunk->ssc_size = size;
|
|
struct spaceship_chunk *next = spaceship_get_next(chunk);
|
|
|
|
spaceship_init(next, remain);
|
|
next->ssc_flags = flags;
|
|
#if SPACESHIP_WITH_PARENT
|
|
if (chunk->ssc_parent) {
|
|
next->ssc_parent = chunk->ssc_parent + size;
|
|
}
|
|
#endif
|
|
#if SPACESHIP_WITH_PREV
|
|
next->ssc_prev = (uintptr_t)next - (uintptr_t)chunk;
|
|
struct spaceship_chunk *nnext = spaceship_get_next(next);
|
|
if (nnext) {
|
|
nnext->ssc_prev = (uintptr_t)nnext - (uintptr_t)next;
|
|
}
|
|
#endif
|
|
} else {
|
|
/* quietly allocate slowly more than necessary */
|
|
}
|
|
}
|
|
/* this chunk is now in use */
|
|
#if SPACESHIP_WITH_SUB
|
|
chunk->ssc_base = chunk->ssc_size;
|
|
#endif
|
|
chunk->ssc_flags |= SPACESHIP_FLAG_USED;
|
|
return chunk;
|
|
}
|
|
return NULL;
|
|
}
|
|
|
|
void spaceship_free(struct spaceship_chunk *chunk)
|
|
{
|
|
/* sweep for adjacent free blocks */
|
|
#if SPACESHIP_WITH_PREV || SPACESHIP_WITH_PARENT
|
|
struct spaceship_chunk *prev = spaceship_get_prev_sibling(chunk);
|
|
if (prev) {
|
|
chunk = spaceship_get_next(prev);
|
|
}
|
|
#endif
|
|
|
|
chunk->ssc_flags &= ~SPACESHIP_FLAG_USED;
|
|
|
|
struct spaceship_chunk *next = spaceship_get_next(chunk);
|
|
while (next && !(next->ssc_flags & SPACESHIP_FLAG_USED)) {
|
|
chunk->ssc_size += next->ssc_size;
|
|
next = spaceship_get_next(chunk);
|
|
#if SPACESHIP_WITH_PREV
|
|
if (next) {
|
|
next->ssc_prev = (uintptr_t)next - (uintptr_t)chunk;
|
|
}
|
|
#endif
|
|
}
|
|
}
|
|
|
|
#if SPACESHIP_WITH_SUB
|
|
int spaceship_init_sub(struct spaceship_chunk *chunk, size_t base_size)
|
|
{
|
|
size_t div_size = chunk->ssc_size - base_size;
|
|
if (div_size < sizeof(*chunk)) {
|
|
return 0;
|
|
}
|
|
chunk->ssc_base = base_size;
|
|
|
|
struct spaceship_chunk *sub = spaceship_get_sub(chunk);
|
|
spaceship_init(sub, div_size);
|
|
#if SPACESHIP_WITH_PARENT
|
|
sub->ssc_parent = (uintptr_t)sub - (uintptr_t)chunk;
|
|
#endif
|
|
return 1;
|
|
}
|
|
#endif
|
|
|
|
void spaceship_defrag(struct spaceship_chunk *unused)
|
|
{
|
|
#if SPACESHIP_WITH_PREV
|
|
size_t prev_size = 0;
|
|
#endif
|
|
|
|
for (;;) {
|
|
/* find first unused chunk */
|
|
while (unused && unused->ssc_flags & SPACESHIP_FLAG_USED) {
|
|
unused = spaceship_get_next(unused);
|
|
}
|
|
if (!unused) {
|
|
break;
|
|
}
|
|
#if SPACESHIP_WITH_PREV
|
|
prev_size = unused->ssc_prev;
|
|
#endif
|
|
|
|
/* find used chunk after */
|
|
struct spaceship_chunk *used = spaceship_get_next_sibling(unused);
|
|
if (!used) {
|
|
break;
|
|
}
|
|
size_t unused_size = (uintptr_t)used - (uintptr_t)unused;
|
|
|
|
/* find chain length of used chunks */
|
|
struct spaceship_chunk *last, *end = used;
|
|
do {
|
|
last = end;
|
|
end = spaceship_get_next(end);
|
|
} while (end && end->ssc_flags & SPACESHIP_FLAG_USED);
|
|
|
|
/* move used chunk up front */
|
|
end = (struct spaceship_chunk *)((uintptr_t)last + spaceship_get_size(last));
|
|
size_t used_size = (uintptr_t)end - (uintptr_t)used;
|
|
memmove(unused, used, used_size);
|
|
|
|
/* fixup and defrag children */
|
|
#if SPACESHIP_WITH_PREV
|
|
unused->ssc_prev = prev_size;
|
|
#endif
|
|
uint8_t flags;
|
|
end = (struct spaceship_chunk *)((intptr_t)unused + used_size);
|
|
for (last = unused; last != end; last = spaceship_get_next(last)) {
|
|
flags = last->ssc_flags;
|
|
last->ssc_flags &= ~SPACESHIP_FLAG_LAST;
|
|
#if SPACESHIP_WITH_SUB
|
|
spaceship_defrag(spaceship_get_sub(last));
|
|
#endif
|
|
#if SPACESHIP_WITH_PARENT
|
|
last->ssc_parent -= unused_size;
|
|
#endif
|
|
}
|
|
|
|
/* create unused chunk at end */
|
|
spaceship_init(end, unused_size);
|
|
end->ssc_flags = flags;
|
|
unused = end;
|
|
}
|
|
}
|