Simple sequence manipulation

seq.h

#pragma once
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#if defined(_WIN32)
    #include <malloc.h>
    #define malloc_size(p) _msize(p)
#elif defined(__APPLE__)
    #include <malloc/malloc.h>
    #define malloc_size(p) malloc_size(p)
#elif defined(__linux__)
    #include <malloc.h>
    #define malloc_size(p) malloc_usable_size(p)
#else
    #error "!!!"
#endif


//------------------------------------------------------------------------------
/**
    seq_local_t(T, N)

    A local sequence contains an array of type T and length N.

    Examples:

        typedef seq_local_t(int, 8) seq_int_length_8;

        seq_int_length_8 q = {0}; // zero-initialize q

        seq_push(q, 1);
*/
#define seq_local_t(T, N)\
        union {\
            size_t _;\
            struct { T begin[N]; char cap[1]; };\
            struct { T at[N];    T*   end;    };\
            char dynamic[false];\
        }

//------------------------------------------------------------------------------
/**
    seq_remote_t(T)

    A remote sequence points to another block of memory.  This is particularly
    useful when allocating a large block of memory containing one or more
    sequences.

    Examples:

        typedef seq_remote_t(int) seq_int;

        typedef struct sos {
            seq_int a;
            seq_int b;
            int data[];
        } sos;

        sos* p = (sos*)alloca(sizeof(sos) + sizeof(int[16]));
        p->a = (seq_int){ p->data + 0, p->data + 8 };  // init begin, cap
        p->b = (seq_int){ p->data + 8, p->data + 16 }; // init begin, cap

        seq_push(p->a, 1);
        seq_push(p->b, 1);
*/
#define seq_remote_t(T)\
        union {\
            struct { T* begin; void* cap; T* end; };\
            struct { T* at; };\
            char dynamic[false];\
        }

//------------------------------------------------------------------------------
/**
    seq_dynamic_t(T)

    A dynamic sequence points to a heap-allocated block of memory.
    This is similar to C++ std::vector<T>.

    Examples:

        typedef seq_dynamic_t(int) seq_int;

        seq_int q = {0}; // zero-initialize q

        seq_reserve(q, 128);
        seq_push(q, 1);
        seq_free(q);
*/
#define seq_dynamic_t(T)\
        union {\
            size_t _;\
            struct { T* begin; void* cap; T* end; };\
            struct { T* at; };\
            char dynamic[true];\
        }

//------------------------------------------------------------------------------

#define seq_init() {0}

//------------------------------------------------------------------------------

#define seq_is_dynamic(seq) ((bool)sizeof(seq.dynamic))

//------------------------------------------------------------------------------

#define seq_stride(seq) ((size_t)sizeof(seq.at[0]))

//------------------------------------------------------------------------------

#define seq_validate(seq)\
        ((void)(\
            (assert(seq.begin || !seq.end)),\
            (assert(seq.cap   || !seq.end)),\
            (seq.end ? ((void)0) : ((seq.end = seq.begin),(void)0)),\
            /*(echo(seq.begin),echo(seq.end),echo(seq.cap)),*/\
            (assert((size_t)seq.begin <= (size_t)seq.end)),\
            (assert((size_t)seq.end   <= (size_t)seq.cap)),\
            ((void)0)\
        ))

//------------------------------------------------------------------------------

#define seq_capacity(seq)\
        ((size_t)(\
            seq_validate(seq),\
            (((char*)seq.cap - (char*)seq.begin)/seq_stride(seq))\
        ))

#define seq_length(seq)\
        ((size_t)(\
            seq_validate(seq),\
            (((char*)seq.end - (char*)seq.begin)/seq_stride(seq))\
        ))

//------------------------------------------------------------------------------

#define seq_at(seq, index)\
        (\
            seq_validate(seq),\
            assert((seq.end - seq.begin) > index),\
            seq.at[index]\
        )

//------------------------------------------------------------------------------

#define seq_front(seq)\
        (\
            seq_validate(seq),\
            assert(seq.end > seq.begin),\
            seq.begin[0]\
        )

#define seq_back(seq)\
        (\
            seq_validate(seq),\
            assert(seq.end > seq.begin),\
            seq.end[-1]\
        )

//------------------------------------------------------------------------------

static inline bool
seq_reserve(
    void** const seq_begin,
    void** const seq_end,
    void** const seq_cap,
    const size_t seq_stride,
    const size_t seq_min_capacity)
{
    size_t seq_min_capacity_pow2 = seq_min_capacity;
    seq_min_capacity_pow2--;
    seq_min_capacity_pow2 |= seq_min_capacity_pow2 >> 1;
    seq_min_capacity_pow2 |= seq_min_capacity_pow2 >> 2;
    seq_min_capacity_pow2 |= seq_min_capacity_pow2 >> 4;
    seq_min_capacity_pow2 |= seq_min_capacity_pow2 >> 8;
    seq_min_capacity_pow2 |= seq_min_capacity_pow2 >> 16;
#if UINTPTR_MAX == 0xffffffffffffffff
    seq_min_capacity_pow2 |= seq_min_capacity_pow2 >> 32;
#endif
    seq_min_capacity_pow2++;
    void* const mem = realloc(*seq_begin, seq_min_capacity_pow2);
    if (mem) {
        const size_t mem_capacity = malloc_size(mem);
        const size_t seq_capacity = (mem_capacity / seq_stride) * seq_stride;
        const size_t seq_size = (char*)*seq_end - (char*)*seq_begin;
        *seq_begin = mem;
        *seq_cap   = mem + seq_capacity;
        *seq_end   = mem + seq_size;
        return true;
    }
    return false;
}
#define seq_reserve(seq, min_capacity)\
        ((bool)(\
            (seq_capacity(seq) >= min_capacity) ||\
            (seq_is_dynamic(seq) && seq_reserve(\
                (void**)&seq.begin, (void**)&seq.end, (void**)&seq.cap,\
                seq_stride(seq), seq_stride(seq) * min_capacity))\
        ))

//------------------------------------------------------------------------------

static inline bool
seq_free(
    void** const seq_begin,
    void** const seq_end,
    void** const seq_cap)
{
    if (*seq_begin) {
        free(*seq_begin);
        *seq_begin = NULL;
        *seq_cap   = NULL;
        *seq_end   = NULL;
        return true;
    }
    return false;
}
#define seq_free(seq)\
        ((bool)(\
            seq_validate(seq),\
            seq_is_dynamic(seq) &&\
            seq_free((void**)&seq.begin, (void**)&seq.end, (void**)&seq.cap)\
        ))

//------------------------------------------------------------------------------

static inline bool
seq_push(
    const void* const seq_begin,
    void**      const seq_end,
    const void* const seq_cap,
    const size_t      seq_stride)
{
    void* const new_seq_end = (char*)*seq_end + seq_stride;
    assert(new_seq_end <= seq_cap);
    *seq_end = new_seq_end;
    return true;
}
#define seq_push(seq, value)\
        ((bool)(\
            seq_reserve(seq, (seq_length(seq) + 1)) &&\
            seq_push(seq.begin, (void**)&seq.end, seq.cap, seq_stride(seq))\
            ? ((seq.end[-1] = (value)),true)\
            : (false)\
        ))

//------------------------------------------------------------------------------

static inline bool
seq_pop(
    const void* const seq_begin,
    void**      const seq_end,
    const void* const seq_cap,
    const size_t      seq_stride)
{
    void* const new_seq_end = (char*)*seq_end - seq_stride;
    if (new_seq_end >= seq_begin) {
        *seq_end = new_seq_end;
        return true;
    }
    return false;
}
#define seq_pop(seq)\
        ((bool)(\
            seq_validate(seq),\
            seq_pop(seq.begin, (void**)&seq.end, seq.cap, seq_stride(seq))\
        ))

//------------------------------------------------------------------------------

static inline bool
seq_insert(
    const void* const seq_begin,
    void**      const seq_end,
    const void* const seq_cap,
    const size_t      seq_stride,
    void*       const seq_itr)
{
    if (seq_itr <= *seq_end) {
        void* const new_seq_end = (char*)*seq_end + seq_stride;
        assert(new_seq_end <= seq_cap);
        void* const dst = (char*)seq_itr + seq_stride;
        const void* const src = seq_itr;
        const size_t size = (size_t)seq_end - (size_t)seq_itr;
        memmove(dst, src, size);
        *seq_end = new_seq_end;
        return true;
    }
    return false;
}
#define seq_insert(seq, index, value)\
        ((bool)(\
            seq_reserve(seq, (seq_length(seq) + 1)) &&\
            seq_insert(\
                seq.begin, (void**)&seq.end, seq.cap,\
                seq_stride(seq), seq.begin + index)\
            ? ((seq.at[index] = (value)),true)\
            : (false)\
        ))

//------------------------------------------------------------------------------

static inline bool
seq_remove(
    const void* const seq_begin,
    void**      const seq_end,
    const void* const seq_cap,
    const size_t      seq_stride,
    void*       const seq_itr)
{
    if (seq_itr < *seq_end) {
        void* const new_seq_end = (char*)*seq_end - seq_stride;
        if (new_seq_end >= seq_begin) {
            void* const dst = seq_itr;
            const void* const src = (char*)seq_itr + seq_stride;
            const size_t size = (size_t)seq_end - (size_t)src;
            memmove(dst, src, size);
            *seq_end = new_seq_end;
            return true;
        }
    }
    return false;
}
#define seq_remove(seq, index)\
        ((bool)(\
            seq_validate(seq),\
            seq_remove(\
                seq.begin, (void**)&seq.end, seq.cap,\
                seq_stride(seq), seq.begin + index)\
        ))

//------------------------------------------------------------------------------