// mymalloc.c — asignador first fit con división (splitting) y fusión
// (coalescing) sobre una arena estática de ARENA_SIZE bytes.
//
// Cada bloque asignado empieza con un encabezado de 16 bytes:
//     [ size | magic ][ ...size bytes para el usuario... ]
// Cada trozo libre empieza con un nodo de la lista libre, también de 16 bytes:
//     [ size | next  ][ ...size bytes libres... ]
// En ambos casos size cuenta solo los bytes que siguen al encabezado.
// La lista libre se mantiene ordenada por dirección para poder fusionar.
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include "mymalloc.h"

#define MAGIC 0x1234567890abcdefUL

typedef struct header {
    size_t size;   // bytes útiles del bloque
    size_t magic;  // MAGIC: sirve para detectar punteros inválidos
} header_t;

typedef struct node {
    size_t size;        // bytes libres después de este nodo
    struct node *next;  // siguiente trozo libre (por dirección)
} node_t;

static _Alignas(16) unsigned char arena[ARENA_SIZE];
static node_t *head;      // primer trozo libre
static int do_coalesce;

static size_t round_up(size_t n) {
    return (n + ALIGN - 1) & ~(size_t)(ALIGN - 1);
}

void mm_init(int coalesce) {
    head = (node_t *)arena;
    head->size = ARENA_SIZE - sizeof(node_t);
    head->next = NULL;
    do_coalesce = coalesce;
}

void *mm_malloc(size_t size) {
    if (size == 0)
        return NULL;
    size = round_up(size);

    // First fit: el primer trozo libre que alcance.
    node_t **link = &head;
    for (node_t *cur = head; cur != NULL; link = &cur->next, cur = cur->next) {
        if (cur->size < size)
            continue;
        if (cur->size >= size + sizeof(node_t) + ALIGN) {
            // División: el resto queda libre como un trozo nuevo.
            node_t *rest = (node_t *)((char *)cur + sizeof(header_t) + size);
            rest->size = cur->size - size - sizeof(node_t);
            rest->next = cur->next;
            *link = rest;
        } else {
            // El resto no alcanza para un trozo útil: se entrega completo.
            size = cur->size;
            *link = cur->next;
        }
        header_t *h = (header_t *)cur;
        h->size = size;
        h->magic = MAGIC;
        return h + 1;  // el usuario recibe la dirección después del encabezado
    }
    return NULL;  // ningún trozo alcanza
}

int mm_valid(void *ptr) {
    unsigned char *p = ptr;
    if (p < arena + sizeof(header_t) || p >= arena + ARENA_SIZE)
        return 0;
    header_t *h = (header_t *)ptr - 1;
    return h->magic == MAGIC;
}

// ¿El trozo a termina justo donde empieza b?
static int adjacent(node_t *a, node_t *b) {
    return (char *)a + sizeof(node_t) + a->size == (char *)b;
}

void mm_free(void *ptr) {
    if (ptr == NULL)
        return;
    if (!mm_valid(ptr)) {
        fprintf(stderr, "mm_free: puntero inválido %p\n", ptr);
        abort();
    }
    // free no recibe el tamaño: lo lee del encabezado, justo antes de ptr.
    header_t *h = (header_t *)ptr - 1;
    node_t *n = (node_t *)h;  // el encabezado se convierte en nodo
    n->size = h->size;        // (mismo lugar; magic se pisa con next)

    // Insertar en orden de dirección.
    node_t *prev = NULL, *cur = head;
    while (cur != NULL && cur < n) {
        prev = cur;
        cur = cur->next;
    }
    n->next = cur;
    if (prev == NULL)
        head = n;
    else
        prev->next = n;

    if (!do_coalesce)
        return;
    // Fusión con el vecino de la derecha y luego con el de la izquierda.
    if (cur != NULL && adjacent(n, cur)) {
        n->size += sizeof(node_t) + cur->size;
        n->next = cur->next;
    }
    if (prev != NULL && adjacent(prev, n)) {
        prev->size += sizeof(node_t) + n->size;
        prev->next = n->next;
    }
}

size_t mm_offset(void *ptr) {
    return (size_t)((unsigned char *)ptr - arena);
}

void mm_dump(void) {
    printf("  lista libre:");
    for (node_t *c = head; c != NULL; c = c->next)
        printf(" [%zu, size %zu]", mm_offset(c), c->size);
    printf("%s\n", head == NULL ? " (vacía)" : "");
}

size_t mm_free_chunks(void) {
    size_t n = 0;
    for (node_t *c = head; c != NULL; c = c->next)
        n++;
    return n;
}

size_t mm_free_largest(void) {
    size_t max = 0;
    for (node_t *c = head; c != NULL; c = c->next)
        if (c->size > max)
            max = c->size;
    return max;
}