#include "stdlib.h"
#include "string.h"

#define HEAP_SIZE      (1024 * 1024)     
#define ALIGN          8
#define ALIGN_UP(n)    (((n) + (ALIGN - 1)) & ~(ALIGN - 1))

struct Block {
    unsigned int   size;       
    unsigned int   free;       
    struct Block  *next;
};

static char heap[HEAP_SIZE];
static struct Block *head;
static int heap_ready = 0;
static unsigned int heap_used_bytes = 0;

void heap_init(void)
{
    head = (struct Block *)heap;
    head->size = HEAP_SIZE - sizeof(struct Block);
    head->free = 1;
    head->next = 0;
    heap_ready = 1;
    heap_used_bytes = 0;
}

static void split_block(struct Block *b, unsigned int want)
{
   
    if (b->size < want + sizeof(struct Block) + ALIGN) return;

    struct Block *nb = (struct Block *)((char *)(b + 1) + want);
    nb->size = b->size - want - sizeof(struct Block);
    nb->free = 1;
    nb->next = b->next;

    b->size = want;
    b->next = nb;
}

void *malloc(unsigned int size)
{
    struct Block *b;

    if (!heap_ready) heap_init();
    if (size == 0) return 0;

    size = ALIGN_UP(size);

    for (b = head; b; b = b->next) {
        if (b->free && b->size >= size) {
            split_block(b, size);
            b->free = 0;
            heap_used_bytes += b->size;
            return (void *)(b + 1);
        }
    }
    return 0;   
}

void free(void *p)
{
    struct Block *b, *prev;

    if (!p) return;
    if ((char *)p < heap || (char *)p >= heap + HEAP_SIZE) return;

    b = (struct Block *)p - 1;
    b->free = 1;
    heap_used_bytes -= b->size;

    
    while (b->next && b->next->free) {
        b->size += sizeof(struct Block) + b->next->size;
        b->next = b->next->next;
    }

  
    prev = head;
    while (prev && prev->next != b) prev = prev->next;
    if (prev && prev->free) {
        prev->size += sizeof(struct Block) + b->size;
        prev->next = b->next;
    }
}

void *calloc(unsigned int n, unsigned int size)
{
    unsigned int total = n * size;
    void *p = malloc(total);
    if (!p) return 0;
    memset(p, 0, total);
    return p;
}

void *realloc(void *p, unsigned int new_size)
{
    struct Block *b;
    void *np;
    unsigned int copy;

    if (!p) return malloc(new_size);
    if (new_size == 0) { free(p); return 0; }

    b = (struct Block *)p - 1;
    if (b->size >= new_size) return p;

    np = malloc(new_size);
    if (!np) return 0;

    copy = b->size;
    memcpy(np, p, copy);
    free(p);
    return np;
}

void heap_stats(unsigned int *total, unsigned int *used, unsigned int *blocks)
{
    struct Block *b;
    unsigned int n = 0;
    if (!heap_ready) heap_init();
    *total = HEAP_SIZE;
    *used = heap_used_bytes;
    for (b = head; b; b = b->next) n++;
    *blocks = n;
}