/* Demo of sorted-array map using binary search and insertion sort.
 * JSF AV C++ Coding Standards compliance.
 * C23: no macros for constants, no globals, bool/nullptr/[[nodiscard]] native.
 *
 * All heap memory is served from a single arena_t whose backing store is a
 * plain char array.  After startup() the arena is full and no further OS
 * allocations occur.  (JSF AV Rule 206.) */

/* Expose POSIX clock_gettime / CLOCK_MONOTONIC under strict C standards. */
#define _POSIX_C_SOURCE 200809L

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

/* arena_t - Allocations advance top; there is no per- object free.  Alignment
 * is _Alignof(max_align_t) on every allocation, which is conservative but
 * correct for every type used here.
 */

static const size_t k_arena_capacity = 4096u;
static const size_t k_max_align      = _Alignof(max_align_t);

typedef struct {
    char   buf[4096]; /* sized to match k_arena_capacity */
    size_t top;
} arena_t;

[[nodiscard]] static void *arena_alloc(arena_t *a, size_t n)
{
    size_t aligned_top = (a->top + k_max_align - 1u) & ~(k_max_align - 1u);
    if (aligned_top + n > k_arena_capacity) {
        printf("[arena] EXHAUSTED: requested %zu, used %zu / %zu\n",
               n, a->top, k_arena_capacity);
        return nullptr;
    }
    void *ptr = &a->buf[aligned_top];
    a->top    = aligned_top + n;
    return ptr;
}

/* sorted_map_t - Entries kept in ascending key order.  Binary search locates
 * the insertion point; memmove shifts for insert/remove.
 */

static const int k_map_capacity = 16;

typedef struct {
    int key;
    int val;
} entry_t;

typedef struct {
    entry_t entries[16]; /* sized to match k_map_capacity */
    int     size;
} sorted_map_t;

/* Returns index of first entry with key >= k (lower_bound semantics). */
[[nodiscard]] static int map_lower_bound(const sorted_map_t *m, int k)
{
    int lo = 0;
    int hi = m->size;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (m->entries[mid].key < k) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

/* Lookup by key.  Returns pointer to entry, or nullptr if not found. */
[[nodiscard]] static const entry_t *map_find(const sorted_map_t *m, int k)
{
    int pos = map_lower_bound(m, k);
    if (pos < m->size && m->entries[pos].key == k) {
        return &m->entries[pos];
    }
    return nullptr;
}

/* Insert k->v.  Returns true on success, false on collision or full map. */
[[nodiscard]] static bool map_insert(sorted_map_t *m, int k, int v)
{
    if (m->size >= k_map_capacity) {
        return false;
    }
    int pos = map_lower_bound(m, k);
    if (pos < m->size && m->entries[pos].key == k) {
        return false; /* collision */
    }
    memmove(&m->entries[pos + 1], &m->entries[pos],
            (size_t)(m->size - pos) * sizeof(entry_t));
    m->entries[pos].key = k;
    m->entries[pos].val = v;
    m->size++;
    return true;
}

/* Remove by key.  Returns true on success, false if not found. */
static bool map_remove(sorted_map_t *m, int k)
{
    int pos = map_lower_bound(m, k);
    if (pos >= m->size || m->entries[pos].key != k) {
        return false;
    }
    memmove(&m->entries[pos], &m->entries[pos + 1],
            (size_t)(m->size - pos - 1) * sizeof(entry_t));
    m->size--;
    return true;
}

/* node_t / pool_t - Fixed array of slots allocated from the arena at startup,
 * plus a free-index stack.  After startup() no allocation occurs.
 */

static const int k_pool_size = 16;

typedef struct {
    int  key;
    int  val;
} node_t;

typedef struct {
    node_t *slots;          /* points into arena */
    int     free_stack[16]; /* sized to match k_pool_size */
    int     free_top;
} pool_t;

static bool pool_startup(pool_t *p, arena_t *a)
{
    p->slots = (node_t *)arena_alloc(a, (size_t)k_pool_size * sizeof(node_t));
    if (p->slots == nullptr) {
        return false;
    }
    p->free_top = 0;
    for (int i = 0; i < k_pool_size; ++i) {
        p->slots[i].key  = i;
        p->slots[i].val  = 0;
        p->free_stack[p->free_top++] = i;
    }
    return true;
}

/* Pop a free slot index.  Returns -1 if pool is empty. */
[[nodiscard]] static int pool_acquire(pool_t *p)
{
    if (p->free_top == 0) {
        return -1;
    }
    return p->free_stack[--p->free_top];
}

/* Return slot index back to the free stack. */
static void pool_release(pool_t *p, int idx)
{
    p->free_stack[p->free_top++] = idx;
}

static const int      k_run_iterations = 32;
static const uint32_t k_lcg_a          = 1664525u;
static const uint32_t k_lcg_c          = 1013904223u;

/* Knuth multiplicative LCG — no allocations, no side effects. */
[[nodiscard]] static uint32_t lcg(uint32_t s)
{
    return s * k_lcg_a + k_lcg_c;
}

typedef struct {
    arena_t     arena;
    pool_t      pool;
    sorted_map_t map;
} demo_t;

static void try_insert(demo_t *d, int iter, uint32_t seed, bool verbose)
{
    int pool_idx = pool_acquire(&d->pool);
    if (pool_idx < 0) {
        return;
    }
    d->pool.slots[pool_idx].key = pool_idx; /* slot index doubles as map key */
    d->pool.slots[pool_idx].val = (int)(seed % 1000u);

    int k = d->pool.slots[pool_idx].key;
    int v = d->pool.slots[pool_idx].val;

    if (map_insert(&d->map, k, v)) {
        if (verbose) {
            printf("[iter %2d] INSERT  key=%2d val=%4d map=%2d free=%2d\n",
                   iter, k, v, d->map.size, d->pool.free_top);
        }
    } else {
        pool_release(&d->pool, pool_idx);
        if (verbose) {
            printf("[iter %2d] COLLIDE key=%2d val=%4d map=%2d free=%2d\n",
                   iter, k, v, d->map.size, d->pool.free_top);
        }
    }
}

static void do_remove(demo_t *d, int iter, uint32_t seed, bool verbose)
{
    int target = (int)((uint32_t)seed % (uint32_t)d->map.size);
    int k = d->map.entries[target].key;
    int pool_idx = k; /* invariant: key == original slot index */

    (void)map_remove(&d->map, k); /* AV Rule 113: suppress unused result */
    pool_release(&d->pool, pool_idx);

    if (verbose) {
        printf("[iter %2d] REMOVE  key=%2d map=%2d free=%2d\n",
               iter, k, d->map.size, d->pool.free_top);
    }
}

/* Resets map and free list to post-startup() state. Zero allocations. */
static void reset(demo_t *d)
{
    memset(&d->map, 0, sizeof(d->map));
    d->pool.free_top = 0;
    for (int i = 0; i < k_pool_size; ++i) {
        d->pool.free_stack[d->pool.free_top++] = i;
    }
}

static bool startup(demo_t *d)
{
    (void)map_find; /* utility; suppress unused-function warning */
    printf("[startup] arena capacity: %zu bytes\n", k_arena_capacity);
    memset(&d->map, 0, sizeof(d->map));
    if (!pool_startup(&d->pool, &d->arena)) {
        return false;
    }
    printf("[startup] pool ready - %d nodes available\n", k_pool_size);
    printf("[startup] arena used: %zu / %zu bytes\n",
           d->arena.top, k_arena_capacity);
    return true;
}

static void run_demo(demo_t *d, bool verbose)
{
    uint32_t seed = 42u;
    for (int iter = 0; iter < k_run_iterations; ++iter) {
        seed = lcg(seed);
        bool want_insert = (((seed >> 16u) & 3u) != 0u) || (d->map.size == 0);
        bool pool_empty  = (d->pool.free_top == 0);

        if (want_insert && !pool_empty) {
            try_insert(d, iter, seed = lcg(seed), verbose);
        } else if (d->map.size > 0) {
            do_remove(d, iter, seed = lcg(seed), verbose);
        }
    }
    if (verbose) {
        printf("[run_demo] arena used after demo: %zu / %zu bytes"
               " (no change expected)\n",
               d->arena.top, k_arena_capacity);
    }
}

static const int k_warmup_runs = 10;
static const int k_bench_runs  = 100;

int main(void)
{
    demo_t demo = {0};
    if (!startup(&demo)) {
        return 1;
    }

    for (int i = 1; i < k_warmup_runs; ++i) {
        run_demo(&demo, /*verbose=*/false);
        reset(&demo);
    }

    /* Benchmark: 100 silent runs back-to-back. */
    reset(&demo);
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (int i = 0; i < k_bench_runs; ++i) {
        run_demo(&demo, /*verbose=*/false);
        reset(&demo);
    }
    clock_gettime(CLOCK_MONOTONIC, &t1);

    long long total_ns = (t1.tv_sec - t0.tv_sec) * 1000000000LL
                       + (t1.tv_nsec - t0.tv_nsec);
    printf("[bench] %d runs: total %lld ns,  avg %.1f ns/run (%.3f us/run)\n",
           k_bench_runs, total_ns,
           (double)total_ns / k_bench_runs,
           (double)total_ns / k_bench_runs / 1000.0);

    run_demo(&demo, /*verbose=*/true);

    return 0;
}