list_pool.inl

// https://gist.github.com/pervognsen/c56d4ddce94fbef3c80e228b39efc028
// https://gist.github.com/pervognsen/fb31981701b534e495a8baa2a6c3ae86
// https://gist.github.com/pervognsen/d4dc1dc159f93a0ad5b6
// https://gist.github.com/vurtun/2e32089f0f012aab2b4c6385f145b5bd
// http://blog.pkh.me/p/20-templating-in-c.html

#ifndef LISTPOOL_VAL 
#error "LISTPOOL_VAL must be #defined to a type."
#endif


#ifndef LISTPOOL_REF
#define LISTPOOL_REF unsigned int
#endif

#ifndef LISTPOOL_NAME
#define LISTPOOL_NAME list_pool
#endif

#define ListPool_(part) list_pooli_##part

#ifdef __cplusplus
extern "C" {
#endif

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


typedef LISTPOOL_REF list_ref_t;

struct ListPool_(cell)
{
    LISTPOOL_VAL head;
    list_ref_t tail;
};

typedef struct
{
    struct ListPool_(cell)* cells;
    LISTPOOL_REF size;
    LISTPOOL_REF capacity;
    list_ref_t free_list;
} ListPool_(t);

list_ref_t ListPool_(null)(void);
int ListPool_(is_null)(list_ref_t x);
LISTPOOL_VAL ListPool_(car)(ListPool_(t)* p, list_ref_t x);


#ifdef __cplusplus
}
#endif


#ifdef LISTPOOL_IMPLEMENTATION

list_ref_t ListPool_(null)(void)
{
    return 0;
}

int ListPool_(is_null)(list_ref_t x)
{
    return x == ListPool_(null)();
}

LISTPOOL_VAL ListPool_(car)(ListPool_(t)* p, list_ref_t x)
{
    return p->cells[x - 1].head;
}

void ListPool_(set_car)(ListPool_(t)* p, list_ref_t x, LISTPOOL_VAL v)
{
    p->cells[x - 1].head = v;
}

LISTPOOL_VAL ListPool_(cdr)(ListPool_(t)* p, list_ref_t x)
{
    return p->cells[x - 1].tail;
}

void ListPool_(set_cdr)(ListPool_(t)* p, list_ref_t x, LISTPOOL_VAL v)
{
    p->cells[x - 1].tail = v;
}


void ListPool_(init_opt)(ListPool_(t)* pool, size_t capacity)
{
    pool->capacity = capacity;
    pool->cells = calloc(sizeof(struct ListPool_(cell)), capacity);
    pool->size = 0;
    pool->free_list = ListPool_(null)();
}

void ListPool_(init)(ListPool_(t)* pool)
{
    ListPool_(init_opt)(pool, 32);
}

void ListPool_(shutdown)(ListPool_(t)* pool)
{
    free(pool->cells);
}

LISTPOOL_VAL ListPool_(cons)(ListPool_(t)* p, LISTPOOL_VAL head, list_ref_t tail)
{
    list_ref_t new_cell = p->free_list;
    if (ListPool_(is_null)(p->free_list))
    {
        ++p->size;
        if (p->size > p->capacity)
        {
            p->capacity *= 2;
            p->cells = realloc(p->cells, sizeof(struct ListPool_(cell)) * p->capacity);
        }

        new_cell = p->size;
    }
    else
    {
        p->free_list = ListPool_(cdr)(p, p->free_list);
    }

    p->cells[new_cell - 1].head = head;
    p->cells[new_cell - 1].tail = tail;
    return new_cell;
}

LISTPOOL_REF ListPool_(length)(ListPool_(t)* p, list_ref_t x)
{
    int n = 0;
    while (!ListPool_(is_null)(x))
    {
        ++n;
        x = ListPool_(cdr)(p, x);
    }
    return n;
}

list_ref_t ListPool_(reverse)(ListPool_(t)* p, list_ref_t x)
{
    list_ref_t n = ListPool_(null)();

    while (!ListPool_(is_null)(x))
    {
        n = ListPool_(cons)(p, ListPool_(car)(p, x), n);
        x = ListPool_(cdr)(p, x);
    }

    return n;
}

list_ref_t ListPool_(reverse_inplace)(ListPool_(t)* p, list_ref_t x)
{
    list_ref_t prev = ListPool_(null)();

    while (!ListPool_(is_null)(x))
    {
        list_ref_t next = ListPool_(cdr)(p, x);
        ListPool_(set_cdr)(p, x, prev);
        prev = x;
        x = next;
    }
    return prev;
}

list_ref_t ListPool_(map_inplace)(ListPool_(t)* p, list_ref_t x, LISTPOOL_VAL (*fn)(LISTPOOL_VAL, void*), void* user_data)
{
    list_ref_t start = x;
    while (!ListPool_(is_null)(x))
    {
        ListPool_(set_car)(p, x, fn(ListPool_(car)(p, x), user_data));
        x = ListPool_(cdr)(p, x);
    }
    return start;

}

list_ref_t ListPool_(map)(ListPool_(t)* p, list_ref_t x, LISTPOOL_VAL (*fn)(LISTPOOL_VAL, void*), void* user_data)
{
    list_ref_t results = ListPool_(null)();

    while (!ListPool_(is_null)(x))
    {
        results = ListPool_(cons)(p, fn(ListPool_(car)(p, x), user_data), results);
        x = ListPool_(cdr)(p, x);
    }

    return ListPool_(reverse_inplace)(p, results);
}

void ListPool_(fprint)(FILE* f, ListPool_(t)* p, list_ref_t l, const char* format_str)
{
    fprintf(f, "(");

    while (!ListPool_(is_null)(l))
    {
        fprintf(f, format_str, ListPool_(car)(p, l));
        fprintf(f, " ");
        l = ListPool_(cdr)(p, l);
    }

    fprintf(f, ")");
}

#endif 

test.c

#include <math.h>

#define LISTPOOL_IMPLEMENTATION

#define LISTPOOL_REF int
#define LISTPOOL_VAL int
#define LISTPOOL_NAME list_pooli
#include "test.inl"


int dub(int x, void* user_data)
{
    return x * 2;
}

int main(int argc, const char* argv[])
{
    list_pooli_t p;
    list_pooli_init(&p);


    list_ref_t l = list_pooli_null();
    
    for (int i = 0; i < 100; ++i)
    {
        list_ref_t n = list_pooli_cons(&p, i, l);
        l = n;
    }

    printf("%i\n", list_pooli_length(&p, l));

    l = list_pooli_map(&p, l, dub, NULL);

    list_pooli_fprint(stdout, &p, list_pooli_reverse(&p, l), "%i");

    list_pooli_shutdown(&p);

    return 0;
}