Simplistic extensible vector (XV)

xv.c

#include <stddef.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

struct xv_base { ptrdiff_t xv__size, xv__alloc; };
#define XV(type) struct { struct xv_base xv__base; type *xv__ptr; }
#define XV_BASE(xv) ((xv).xv__base)
#define XV_SIZE(xv) (XV_BASE(xv).xv__size)
#define XV_ALLOC(xv) (XV_BASE(xv).xv__alloc)
#define XV_PTR(xv) ((xv).xv__ptr)
#define XV_ITEMSIZE(xv) (ptrdiff_t) sizeof(*XV_PTR(xv))
#define XV_EMPTY {.xv__base = {.xv__size = 0, .xv__alloc = 0}, .xv__ptr = NULL}
#define XV_INIT(xv) (XV_SIZE(xv) = XV_ALLOC(xv) = 0, XV_PTR(xv) = NULL)
#define XV_INVARIANT(xv) \
	(XV_SIZE(xv) >= 0 && XV_ALLOC(xv) >= 0 && XV_SIZE(xv) <= XV_ALLOC(xv) && \
	 (XV_ALLOC(xv) > 0) == (XV_PTR(xv) != NULL))
#define XV_CHECK(xv,i) ((ptrdiff_t) (i) >= 0 && (ptrdiff_t) (i) < XV_SIZE(xv))
#define XV_RESERVE(xv,n) \
	((ptrdiff_t) (n) > XV_ALLOC(xv) && \
	 (XV_PTR(xv) = xv_do_resize(&XV_BASE(xv), XV_PTR(xv), (n), XV_ITEMSIZE(xv)), 1))
#define XV_RESIZE(xv,n) (XV_SIZE(xv) = (ptrdiff_t) (n), XV_RESERVE(xv, XV_SIZE(xv)))
#define XV_RESIZEBY(xv,n) XV_RESIZE(xv, XV_SIZE(xv) + (ptrdiff_t) (n))
#define XV_AT(xv,i) (XV_PTR(xv)[(ptrdiff_t) (i)])
#define XV_ATEND(xv,i) (XV_PTR(xv)[XV_SIZE(xv) - (ptrdiff_t) (i) - 1])
#define XV_LOOP(xv,itype,i,before,after) \
	for (itype (i) = 0; (ptrdiff_t) (i) < XV_SIZE(xv) && ((void) (before), 1); \
	     (void) (after), ++(i))
#define XV_IEACH(i,v,xv) XV_LOOP(xv, ptrdiff_t, i, (v) = XV_AT(xv,i), 0)
#define XV_IEACHPTR(i,p,xv) XV_LOOP(xv, ptrdiff_t, i, (p) = &XV_AT(xv,i), 0)
#define XV_EACH(v,xv) XV_IEACH(xv__i_##__LINE__,v,xv)
#define XV_EACHPTR(p,xv) XV_IEACHPTR(xv__i_##__LINE__,p,xv)
#define XV_PUSH(xv,x) (XV_RESERVE(xv, XV_SIZE(xv)+1), XV_AT(xv, XV_SIZE(xv)++) = (x))
#define XV_POP(xv) (XV_PTR(xv)[--XV_SIZE(xv)])
#define XV_COPYTO(p,xv,i,n) memcpy((p), XV_PTR(xv)+i, (n)*XV_ITEMSIZE(xv))
#define XV_COPYFROM(xv,i,p,n) ((void) memcpy(XV_PTR(xv)+i, (p), (n)*XV_ITEMSIZE(xv)))
#define XV_COPYPUSH(xv,p,n) \
	(XV_RESERVE(xv, XV_SIZE(xv) + (ptrdiff_t) (n)), \
	 XV_COPYFROM(xv, XV_SIZE(xv), p, n), (void) (XV_SIZE(xv) += (n)))
#define XV_ZEROIZE(xv,i,n) memset(XV_PTR(xv) + (i), 0, (n) * XV_ITEMSIZE(xv))
#define XV_FREE(xv) if (XV_ALLOC(xv) == 0) { } else free(XV_PTR(xv))

static void *xv_do_resize(struct xv_base *base, void *ptr, ptrdiff_t n, ptrdiff_t itemsize)
{
	static const ptrdiff_t GROWLIMIT = 0x7fff;
	if (n <= GROWLIMIT) {
		--n; n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; ++n;
		if (n < 4) n = 4;
	} else {
		if (n > (PTRDIFF_MAX & ~GROWLIMIT)) abort(); /* overflow */
		n = (n + GROWLIMIT) & ~GROWLIMIT;
	}
	ptr = realloc(ptr, n * itemsize);
	if (!ptr) abort();
	base->xv__alloc = n;
	return ptr;
}

xv.txt

This is an extensible vector (XV) routine designed for C99 (no C++! nor C90).
This particular implementation avoids difficult problems arising from the strict
aliasing, which is prevalent in many other similar routines (e.g. stb.h stb_arr_*).

This code is trivial enough and thus put in the public domain.

Example Usage:

	int i, j;
	typedef XV(int) xv_int;
	xv_int arr, *parr;
	XV(xv_int) arr2 = XV_EMPTY;
	for (j = 0; j < 10; ++j) {
		XV_INIT(arr);
		for (i = 0; i < j; ++i) {
			XV_PUSH(arr, i * i);
			printf("(%d %d)\n", (int) XV_SIZE(arr), XV_AT(arr,i));
		}
		printf("%d\n", (int) XV_SIZE(arr));
		XV_COPYPUSH(arr, XV_PTR(arr), i);
		XV_PUSH(arr, -42);
		int v; XV_IEACH(i, v, arr) {
			printf("%d -> %d\n", (int) i, v);
		}
		XV_PUSH(arr2, arr);
	}
	XV_EACHPTR(parr, arr2) XV_FREE(*parr);
	XV_FREE(arr2);

References:

The routine consists of lots of macros and a handful number of internal functions.

The "xv" argument below should be a reference to the XV structure, not a pointer.

If not specified below, the caller should assume that macros may evaluate their "xv"
argument and index/size argument multiple times. Macros will evaluate their pointer
argument or item argument only once, so XV_PUSH can be safely used for example.

Every index and size argument is converted to ptrdiff_t.

	Declaration
	- Use XV(type) for type declaration.
	- If you have to be able to assign XV(type) to other XV(type), or make
	  an XV of XV(type) then you should typedef XV(type) to some identifier
	  and use it thereafter.

	Initialization
	- XV_EMPTY can be used as an initializer for XV(type).
	- XV_INIT(xv) resets given XV to the initial state (no free called).

	Accessor
	- XV_SIZE(xv) returns a size as an ptrdiff_t. Evaluates xv only once.
	- XV_ALLOC(xv) returns an allocated size as an ptrdiff_t. Ditto.
	- XV_PTR(xv) returns a pointer to the first item. Ditto.
	- XV_AT(xv,i) returns a reference to the item at index i. Ditto.
	- XV_ATEND(xv,i) returns a reference to the item at index i to the end.
	  Thus XV_ATEND(xv,0) equals to XV_AT(xv,XV_SIZE(xv)-1) and so on.
	- (Advanced use only) XV_BASE(xv) returns a reference to the base structure.
	- (Advanced use only) XV_ITEMSIZE(xv) returns a byte size of each item.

	Debugging
	- XV_INVARIANT(xv) returns 1 iff the XV invariant holds. Use with ASSERT.
	- XV_CHECK(xv,i) returns 1 iff i is valid index for XV_AT(xv,i) and
	  XV_ATEND(xv,i). (These macros by default don't check for the array bounds.)

	Manipulation (no invalidation)
	- You can update the item directly as follows: XV_AT(xv,i) = v;
	- XV_POP(xv) removes and returns the value at the end. Don't use for empty XV.
	- XV_COPYTO(p,xv,i,n) copies n items starting from index i to p. Returns p.

	Manipulation (may invalidate the pointer)
	- XV_PUSH(xv,v) inserts the value at the end. Returns the inserted value.
	- XV_COPYFROM(xv,i,p,n) copies n items from p to index i..i+n-1.
	- XV_COPYPUSH(xv,p,n) inserts n items from p at the end of the XV.
	  XV_INIT(b) followed by XV_COPYPUSH(b,XV_PTR(a),XV_SIZE(a)) will copy the XV.
	- XV_RESIZE(xv,n) forces the size to n. If this is larger than the original
	  size, remaining items will be filled to garbages.
	- XV_RESIZEBY(xv,n) increases the size by n. Otherwise same as above.
	- XV_ZEROIZE(xv,i,n) clears (i.e. bzero) n items starting from index i.
	- (Advanced use only) XV_RESERVE(xv,n) ensures that the XV has at least n
	  allocated items. Calls abort() on failure; returns 1 iff the realloc has
	  been called.

	Iteration
	- XV_EACH(v,xv) { ... } loops over each items, storing the value to v.
	  v should be defined elsewhere; modifying v don't affect the XV.
	- XV_EACHPTR(p,xv) { ... } is similar, but v is now a pointer to the item.
	- XV_IEACH(i,v,xv) { ... } is similar to XV_EACH but also stores the index to i.
	- XV_IEACHPTR(i,p,xv) { ... } will need no further explanation.
	- (Advanced use only) XV_LOOP(xv,itype,i,before,after) generalizes loops.
	  itype is a type for i (normally ptrdiff_t) or empty (uses an existing var);
	  before/after is an expression to be executed before/after the loop body.

	Finalization
	- XV_FREE(xv) frees the memory directly allocated by the XV. This does not
	  clear the XV itself, you should also call XV_INIT(xv) for that.

Internals:

The XV is a structure of size (.xv__base.xv__size), allocated size (.xv__base.xv__alloc)
and the pointer to items (.xv__ptr). Nothing else. No fancy pointer twiddling.

There are several reasons to avoid pointer-masqueraded vectors:
- It is very prone to use incorrectly, especially on the function boundary. You should
  return the updated pointer or receive a pointer to the masqueraded pointer, but this is
  not typical usage. The structure is instinctively more natural.
- A strict aliasing is very hard. I have considered several variants but could not find
  a good solution.

The strict aliasing is ensured by splitting type-independent parts (struct xv_base) from
type-dependent parts (xv__ptr). Note that you cannot even cast a pointer to xv__ptr
to void ** for the purpose of in-place pointer update, as in general T ** and void **
is not compatible to each other and not considered aliased. Thus XV_RESERVE passes
xv__ptr as void *, and receives the updated xv__ptr to assign it to the correct variable.

Usage of ptrdiff_t as an index and size comes from several reasons:
- An unsigned integer is useless at the least and harmful in general. It silently
  underflows, it does not offer any performance gain, its comparison to a signed integer
  is ill-defined, etc. Its usage should be confined to the cryptography, where an unsigned
  integer can be replaced with a signed one and two well-defined right bit shift operators.
- It is obvious that the maximum possible vector size corresponds to the maximum difference
  of two pointers. ptrdiff_t (and its cousin, intptr_t) is able to contain it.
- intmax_t (guaranteed to be able to contain the maximum vector size) and intptr_t requires
  #include <stdint.h>, which is less common than #include <stddef.h>. (The routine still
  requires both, but the former can be omitted for macros.)
- ptrdiff_t, at least, can be printf()ed with %td modifier.

The resize factor is determined in usual ways: start at 4, multiply by 2 until 32768,
and increase by 32768 thereafter. This is to avoid excessive (~50%) memory allocation
for very long vector. 32768 is chosen due to the minimum range of ptrdiff_t (+/-65535).