Dynamic_Alloc

#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;
}