// Hand-C reference for bench_list_sum_explicit — full malloc + free.
//
// Companion to list_sum.c (which leaks); this version adds explicit
// `free()` calls to mirror AILang's explicit-mode RC dec-tax. Pairs
// with examples/bench_list_sum_explicit.ail via bench/cross_lang.py.
//
// The free pass walks the list after sum, freeing each cell. This is
// genuinely O(N) work that bench_list_sum.c never paid; the rc/c
// ratio for this fixture is therefore the honest answer to "how
// much does RC's dec-and-free pipeline cost vs hand-C's malloc-free
// pipeline on the same workload?".
//
// Note: we sum first, then free, rather than fold-with-free. This
// matches the AILang fixture's structure: sum_list owns the chain
// and consumes it; the dec walk happens implicitly as sum_acc
// pattern-matches LCons and re-binds the tail to the recursive call.
// AILang's pattern there is "consume during sum" — codegen emits
// dec on the consumed cells as the match arm closes. The C version
// could in principle interleave free into the sum loop too; doing it
// in two passes is structurally cleaner and the cost is the same
// (one O(N) walk + one O(N) walk-and-free).
//
// Build: clang -O2 -o list_sum_explicit_free list_sum_explicit_free.c
// Expected stdout (one int per line):
//   4999950000
//   499999500000
//   4499998500000

#include <stdio.h>
#include <stdlib.h>

typedef struct cell {
    long head;
    struct cell *tail;
} cell_t;

static cell_t *cons_n(long n) {
    cell_t *acc = NULL;
    for (long i = n - 1; i >= 0; i--) {
        cell_t *c = (cell_t *) malloc(sizeof(cell_t));
        c->head = i;
        c->tail = acc;
        acc = c;
    }
    return acc;
}

static long sum_list(const cell_t *xs) {
    long acc = 0;
    while (xs) {
        acc += xs->head;
        xs = xs->tail;
    }
    return acc;
}

static void free_list(cell_t *xs) {
    while (xs) {
        cell_t *next = xs->tail;
        free(xs);
        xs = next;
    }
}

static void run_one(long n) {
    cell_t *xs = cons_n(n);
    printf("%ld\n", sum_list(xs));
    free_list(xs);
}

int main(void) {
    run_one(100000);
    run_one(1000000);
    run_one(3000000);
    return 0;
}