Generic C vector with exponential growth

README.md

Generic C vector that grows the buffer exponentially instead of by a fixed size (or worse, by 1), trading memory efficiency for computational efficiency. This is typically used by libraries such as C++'s STL. Inspired by things like stb_ds.h

I did only very basic testing. By default, the vector is resized to 1.5*size(vec) when full. You can change the constant by defining GROWTH_EXP

vec.h

/*
 * For the current file:
 * ---------------------
 *
 * This is free and unencumbered software released into the public domain.
 * 
 * Anyone is free to copy, modify, publish, use, compile, sell, or
 * distribute this software, either in source code form or as a compiled
 * binary, for any purpose, commercial or non-commercial, and by any
 * means.
 * 
 * In jurisdictions that recognize copyright laws, the author or authors
 * of this software dedicate any and all copyright interest in the
 * software to the public domain. We make this dedication for the benefit
 * of the public at large and to the detriment of our heirs and
 * successors. We intend this dedication to be an overt act of
 * relinquishment in perpetuity of all present and future rights to this
 * software under copyright law.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 * 
 * For more information, please refer to <http://unlicense.org/>
 */


#ifndef VEC_H
#define VEC_H
#include <stddef.h>
#include <stdlib.h>

#ifndef VEC_MALLOC
#   define VEC_MALLOC malloc
#endif

#ifndef VEC_REALLOC
#   define VEC_REALLOC realloc
#endif

#ifndef VEC_FREE
#   define VEC_FREE free
#endif

#ifndef GROWTH_EXP
#   define GROWTH_EXP 1.5
#endif

struct vec_h
{
    size_t c; /* cap */
    size_t s; /* size */
};

#define _head_size sizeof(struct vec_h)

#define vec_head(v)       ((struct vec_h *)((char *)(v) - _head_size))
#define vec_len(v)        ((v) ? vec_head(v)->s : 0)
#define vec_cap(v)        ((v) ? vec_head(v)->c : 0)
#define vec_exp(v) \
    ((void *) \
        (1 + (struct vec_h *)VEC_REALLOC( \
            vec_head(v), \
            _head_size + (vec_head(v)->c *= GROWTH_EXP)*sizeof((v)[0]) \
        )))
#define vec_ipush(v, x) \
    ((v) = (vec_len(v)+1 >= vec_cap(v)) \
                ? vec_exp(v) \
                : (v), \
    (v)[vec_head(v)->s++] = x)
#define vec_init(v, x) do \
    {\
        (v) = (void *) \
            ((struct vec_h *)VEC_MALLOC(_head_size + 16*sizeof((x))) + 1); \
        vec_head(v)->s = 1; \
        vec_head(v)->c = 16; \
        (v)[0] = x; \
    } while (0)
#define vec_push(v, x) do \
    { \
        if ((v)) vec_ipush(v, x); \
        else vec_init(v, x); \
    } while (0)
#define vec_free(v) VEC_FREE(vec_head(v))
#define vec_reserve(v, n) do \
    { \
        if (n >= vec_cap(v)) vec_cap(v) = n; \
        (v) = (void *)(1 + (struct vec_h *)VEC_REALLOC( \
                vec_head(v), \
                _head_size + vec_cap(v)*sizeof((v)[0]) \
            )) \
    } while (0)
#endif