/* Standalone teaching example, newly written for this article.
 * This demonstrates slot ownership only, not a red-black tree.
 * Single-threaded; a tree integration must unlink a node before release.
 */
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

#define CAPACITY 4
#define NONE SIZE_MAX

typedef struct {
    size_t parent, left, right;
    bool red;
} TreeLinks;

typedef struct {
    union {
        TreeLinks tree;
        size_t next_free;
    } links;
    uint64_t key;
    uint64_t value;
    bool used;
} Slot;

typedef struct {
    Slot slots[CAPACITY];
    size_t free_head;
    size_t used_count;
} Pool;

static void pool_init(Pool *p)
{
    *p = (Pool){0};
    for (size_t i = 0; i < CAPACITY; ++i)
        p->slots[i].links.next_free = i + 1 < CAPACITY ? i + 1 : NONE;
    p->free_head = 0;
}

static size_t pool_take(Pool *p)
{
    size_t i = p->free_head;
    if (i == NONE) return NONE;
    Slot *s = &p->slots[i];
    assert(!s->used);
    p->free_head = s->links.next_free;
    s->links.tree = (TreeLinks){NONE, NONE, NONE, true};
    s->key = 0;
    s->value = 0;
    s->used = true;
    ++p->used_count;
    return i;
}

/* Precondition: the slot is no longer linked into any tree. */
static bool pool_release(Pool *p, size_t i)
{
    if (i >= CAPACITY || !p->slots[i].used) return false;
    Slot *s = &p->slots[i];
    s->used = false;
    s->links.next_free = p->free_head;
    p->free_head = i;
    --p->used_count;
    return true;
}

static void check_partition(const Pool *p)
{
    bool seen[CAPACITY] = {false};
    size_t free_count = 0;
    for (size_t i = p->free_head; i != NONE; i = p->slots[i].links.next_free) {
        assert(i < CAPACITY && !seen[i] && !p->slots[i].used);
        seen[i] = true;
        ++free_count;
    }
    size_t live_count = 0;
    for (size_t i = 0; i < CAPACITY; ++i) {
        assert(p->slots[i].used != seen[i]);
        live_count += p->slots[i].used;
    }
    assert(live_count == p->used_count);
    assert(free_count + live_count == CAPACITY);
}

int main(void)
{
    Pool p;
    pool_init(&p);
    check_partition(&p);
    size_t ids[CAPACITY];
    for (size_t i = 0; i < CAPACITY; ++i) {
        ids[i] = pool_take(&p);
        assert(ids[i] != NONE);
        p.slots[ids[i]].key = 100 + i;
        check_partition(&p);
    }
    assert(pool_take(&p) == NONE);
    assert(!pool_release(&p, NONE));
    assert(!pool_release(&p, CAPACITY));
    size_t released = ids[1];
    assert(pool_release(&p, released));
    assert(!pool_release(&p, released));
    size_t reused = pool_take(&p);
    assert(reused == released && p.slots[reused].key == 0);
    printf("full pool rejected; slot %zu reused\n", reused);
    for (size_t i = 0; i < CAPACITY; ++i) assert(pool_release(&p, ids[i]));
    check_partition(&p);
    uint32_t rng = 1;
    for (size_t n = 0; n < 10000; ++n) {
        rng = rng * 1664525u + 1013904223u;
        size_t i = (rng >> 8) % CAPACITY;
        if (p.slots[i].used) assert(pool_release(&p, i));
        else (void)pool_take(&p);
        check_partition(&p);
    }
    puts("slot ownership checks passed");
    return 0;
}