#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <assert.h>
#define DYNAMIC_ALLOC_SIGNATURE_USED ((size_t)0xA888A8A8A8A8A0A8)
#define DYNAMIC_ALLOC_SIGNATURE_FREE ((size_t)0x8880A0A8A0A0A088)
#define DYNAMIC_ALLOC_SIGNATURE_BITS ((size_t)0x2008080008080020)
typedef struct Dynamic_Alloc_Preamble Dynamic_Alloc_Preamble;
struct Dynamic_Alloc_Preamble {
Dynamic_Alloc_Preamble *next;
size_t is_allocated;
};
size_t mem_pool_raw[4096 * 4 / sizeof(size_t)];
char *mem_pool = (char *)mem_pool_raw;
Dynamic_Alloc_Preamble *mem_next = (Dynamic_Alloc_Preamble *)mem_pool_raw;
void dynamic_print() {
Dynamic_Alloc_Preamble *preamble = (Dynamic_Alloc_Preamble *)mem_pool;
size_t used_mem = 0;
size_t free_mem = 0;
size_t used_blocks = 0;
size_t free_blocks = 0;
while(true) {
if(preamble->is_allocated == 0) {
break;
} else if(preamble->is_allocated == DYNAMIC_ALLOC_SIGNATURE_USED) {
used_mem += (char *)preamble->next - (char *)preamble;
used_blocks += 1;
} else if(preamble->is_allocated == DYNAMIC_ALLOC_SIGNATURE_FREE) {
free_mem += (char *)preamble->next - (char *)preamble;
free_blocks += 1;
}
preamble = preamble->next;
}
printf("Total Mem: %zu, Blocks: %zu\n", used_mem + free_mem, used_blocks + free_blocks);
printf("Used Mem: %zu, Blocks: %zu\n", used_mem, used_blocks);
printf("Free Mem: %zu, Blocks: %zu\n", free_mem, free_blocks);
}
void dynamic_defrag() {
mem_next = (Dynamic_Alloc_Preamble *)mem_pool_raw;
}
void dynamic_atomic_store(size_t *t, size_t v) {
*t = v;
}
void *dynamic_alloc(size_t size) {
size_t mask_size = sizeof(size_t) * 2 - 1;
size_t allocation_size = (size + sizeof(Dynamic_Alloc_Preamble) + mask_size) & ~mask_size;
Dynamic_Alloc_Preamble *preamble = mem_next;
while(true) {
if(preamble->is_allocated == 0) {
break;
} else if(preamble->is_allocated == DYNAMIC_ALLOC_SIGNATURE_USED) {
preamble = preamble->next;
continue;
} else if(preamble->is_allocated == DYNAMIC_ALLOC_SIGNATURE_FREE) {
Dynamic_Alloc_Preamble *next_used_preamble = preamble->next;
while(true) {
if(next_used_preamble->is_allocated == 0) {
preamble->next = 0;
preamble->is_allocated = 0;
goto continue_outer;
} else if(next_used_preamble->is_allocated == DYNAMIC_ALLOC_SIGNATURE_USED) {
preamble->next = next_used_preamble;
break;
} else if(next_used_preamble->is_allocated == DYNAMIC_ALLOC_SIGNATURE_FREE) {
next_used_preamble = next_used_preamble->next;
continue;
}
assert(0 && "heap corruption");
return 0;
}
if(allocation_size <= (size_t)next_used_preamble - (size_t)preamble)
break;
preamble = preamble->next;
continue_outer: continue;
}
assert(0 && "heap corruption");
return 0;
}
preamble->next = (Dynamic_Alloc_Preamble *)((char *)preamble + allocation_size);
mem_next = preamble->next;
dynamic_atomic_store(&preamble->is_allocated, DYNAMIC_ALLOC_SIGNATURE_USED);
return (void *)(preamble + 1);
}
void dynamic_dealloc(void *ptr) {
Dynamic_Alloc_Preamble *preamble = (Dynamic_Alloc_Preamble *)ptr - 1;
size_t signature = preamble->is_allocated;
if((signature & ~DYNAMIC_ALLOC_SIGNATURE_BITS) == DYNAMIC_ALLOC_SIGNATURE_FREE)
{
if((signature & DYNAMIC_ALLOC_SIGNATURE_BITS) == DYNAMIC_ALLOC_SIGNATURE_BITS) {
preamble->is_allocated = DYNAMIC_ALLOC_SIGNATURE_FREE;
return;
} else {
// Double free
assert(0 && "double dealloction\n");
return;
}
}
assert(0 && "heap corruption");
}
int main(int argc, char **argv) {
int *a1 = dynamic_alloc(4);
int *b1 = dynamic_alloc(4);
int64_t *c1 = dynamic_alloc(8);
void *d1 = dynamic_alloc(0);
dynamic_dealloc(a1);
dynamic_dealloc(b1);
dynamic_dealloc(c1);
//dynamic_dealloc(d1);
dynamic_defrag();
int *a2 = dynamic_alloc(4);
int64_t *c2 = dynamic_alloc(256);
dynamic_defrag();
int64_t *e1 = dynamic_alloc(8);
dynamic_dealloc(e1);
dynamic_print();
return 0;
}
