ID store

idstore.c

// ID store
// Ref: https://old.reddit.com/r/C_Programming/comments/upv7lx
// This is free and unencumbered software released into the public domain.
#include <stdlib.h>

#define IDSTORE_INIT {0, 0, 0, 0}
struct idstore {
    size_t len, cap;
    long *heap;
    long counter;
};

static void idstore_swap(struct idstore *s, size_t i, size_t j)
{
    long t = s->heap[i];
    s->heap[i] = s->heap[j];
    s->heap[j] = t;
}

long idstore_borrow(struct idstore *s)
{
    if (s->len == 0) {
        return s->counter++;
    }

    long r = s->heap[0];
    s->heap[0] = s->heap[--s->len];
    for (size_t i = 0;;) {
        size_t a = 2*i + 1;
        size_t b = 2*i + 2;
        size_t j = i;
        if (a < s->len && s->heap[a] < s->heap[j]) j = a;
        if (b < s->len && s->heap[b] < s->heap[j]) j = b;
        if (i == j) break;
        idstore_swap(s, i, j);
        i = j;
    }
    return r;
}

int idstore_return(struct idstore *s, long id)
{
    if (s->len == s->cap) {
        size_t cap = s->cap ? s->cap*2 : 8;
        size_t size = cap * sizeof(s->heap[0]);
        if (size < cap) return 0;
        void *p = realloc(s->heap, size);
        if (!p) return 0;
        s->heap = p;
        s->cap = cap;
    }

    s->heap[s->len] = id;
    for (size_t i = s->len++; i;) {
        size_t p = (i - 1) / 2;
        if (s->heap[p] < s->heap[i]) break;
        idstore_swap(s, p, i);
        i = p;
    }
    return 1;
}

void idstore_free(struct idstore *s)
{
    s->cap = s->len = s->counter = 0;
    free(s->heap);
    s->heap = 0;
}

#ifdef TEST

#include <stdio.h>
int main(void)
{
    struct idstore s = IDSTORE_INIT;
    for (int i = 0; i < 5; i++) {
        printf("# %ld\n", idstore_borrow(&s));
    }
    puts(". 2"); idstore_return(&s, 2);
    puts(". 3"); idstore_return(&s, 3);
    printf("# %ld\n", idstore_borrow(&s));
    printf("# %ld\n", idstore_borrow(&s));
    printf("# %ld\n", idstore_borrow(&s));
}
#endif