Generic vector implementation in C using macros

Question

I while ago I experimented with macros in C and came up with the idea of implementing a generic vector library using macros.

This code uses the non standard typeof extension that returns the type of an expression.

#ifndef VECTOR_H
#define VECTOR_H
#include <stdlib.h>
#include <string.h>
#define VECTOR_OF(T) struct { \
 typeof (T) *data; \
 unsigned size; \
 unsigned capacity; \
}
#define VECTOR_INIT_ASSIGN(VEC, VAL) do { \
 typeof (VEC) *vec = &(VEC); \
 typeof (VAL) val = (VAL); \
 vec->data = malloc(sizeof *vec->data); \
 vec->size = vec->capacity = 1; \
 vec->data[0] = val; \
} while (0)
#define VECTOR_INIT_ASSIGN_N(VEC, N, VAL) do { \
 typeof (VEC) *vec = &(VEC); \
 unsigned n = (N); \
 typeof (VAL) val = (VAL); \
 vec->data = malloc(n * sizeof *vec->data); \
 vec->size = vec->capacity = n; \
 while (n-- > 0) \
 vec->data[n] = val; \
} while (0)
#define VECTOR_INIT_ASSIGN_PTR(VEC, N, PTR) do { \
 typeof (VEC) *vec = &(VEC); \
 unsigned n = (N); \
 typeof (*PTR) *ptr = (PTR); \
 vec->data = malloc(n * sizeof *vec->data); \
 vec->size = vec->capacity = n; \
 while (n-- > 0) \
 vec->data[n] = ptr[n]; \
} while (0)
#define VECTOR_INIT_RESERVE(VEC, N) do { \
 typeof (VEC) *vec = &(VEC); \
 unsigned n = (N); \
 vec->data = malloc(n * sizeof *vec->data); \
 vec->size = 0; \
 vec->capacity = n; \
} while (0)
#define VECTOR_INIT(VEC) VECTOR_INIT_RESERVE((VEC), 1)
#define VECTOR_SIZE(VEC) (VEC).size
#define VECTOR_EMPTY(VEC) ((VEC).size == 0)
#define VECTOR_CAPACITY(VEC) (VEC).capacity
#define VECTOR_RESERVE(VEC, N) do { \
 typeof (VEC) *vec = &(VEC); \
 typeof (N) n = (N); \
 if (vec->capacity < n) { \
 vec->data = realloc(n * sizeof *vec->data); \
 vec->capacity = n; \
 } \
} while (0)
#define VECTOR_RESIZE(VEC, N, VAL) do { \
 typeof (VEC) *vec = &(VEC); \
 unsigned n = (N), i; \
 typeof (VAL) val = (VAL); \
 if (n > vec->capacity) \
 vec->data = realloc(vec->data, n * sizeof *vec->data); \
 for (i = vec->size; i < n; ++i) \
 vec->data[i] = val; \
 vec->size = n; \
} while (0)
#define VECTOR_SHRINK_TO_FIT(VEC) do { \
 typeof (VEC) *vec = &(VEC); \
 vec->data = realloc(vec->data, vec->size * sizeof *vec->data); \
 vec->capacity = vec->size; \
} while (0)
#define VECTOR_ASSIGN(VEC, VAL) do { \
 typeof (VEC) *vec = &(VEC); \
 typeof (VAL) val = (VAL); \
 vec->size = vec->capacity = 1; \
 vec->data = realloc(vec->data, sizeof *vec->data); \
 vec->data[0] = val; \
} while (0)
#define VECTOR_ASSIGN_N(VEC, N, VAL) do { \
 typeof (VEC) *vec = &(VEC); \
 unsigned n = (N); \
 typeof (VAL) val = (VAL); \
 vec->data = realloc(vec->data, n * sizeof *vec->data); \
 vec->size = vec->capacity = n; \
 while (n-- > 0) \
 vec->data[n] = val; \
} while (0)
#define VECTOR_ASSIGN_PTR(VEC, N, PTR) do { \
 typeof (VEC) *vec = &(VEC); \
 unsigned n = (N); \
 typeof (*PTR) *ptr = (PTR); \
 vec->data = realloc(vec->data, n * sizeof *vec->data); \
 while (n-- > 0) \
 vec->data[n] = ptr[n]; \
} while (0)
#define VECTOR_INSERT(VEC, POS, VAL) do { \
 typeof (VEC) *vec = &(VEC); \
 unsigned pos = (POS); \
 typeof (VAL) val = (VAL); \
 while (vec->size + 1 > vec->capacity) { \
 vec->capacity *= 2; \
 vec->data = realloc(vec->data, vec->capacity * sizeof *vec->data); \
 } \
 memmove(vec->data + pos + 1, vec->data + pos, (vec->size - pos) * sizeof val); \
 ++vec->size; \
 vec->data[pos] = val; \
} while (0)
#define VECTOR_INSERT_N(VEC, POS, N, VAL) do { \
 typeof (VEC) *vec = &(VEC); \
 unsigned pos = (POS), n = (N), i; \
 typeof (VAL) val = (VAL); \
 while (vec->size + n > vec->capacity) { \
 vec->capacity *= 2; \
 vec->data = realloc(vec->data, vec->capacity * sizeof *vec->data); \
 } \
 memmove(vec->data + pos + n, vec->data + pos, (vec->size - pos) * sizeof *vec->data); \
 for (i = 0; i < n; i++) \
 vec->data[pos + i] = val; \
 vec->size += n; \
} while (0)
#define VECTOR_INSERT_PTR(VEC, POS, N, PTR) do { \
 typeof (VEC) *vec = &(VEC); \
 unsigned pos = (POS), n = (N), i; \
 typeof (*PTR) *ptr = (PTR); \
 while (vec->size + n > vec->capacity) { \
 vec->capacity *= 2; \
 vec->data = realloc(vec->data, vec->capacity * sizeof *vec->data); \
 } \
 memmove(vec->data + pos + n, vec->data + pos, (vec->size - pos) * sizeof *vec->data); \
 for (i = 0; i < n; i++) \
 vec->data[pos + i] = ptr[i]; \
 vec->size += n; \
} while (0)
#define VECTOR_PUSH_BACK(VEC, VAL) do { \
 typeof (VEC) *vec = &(VEC); \
 typeof (VAL) val = val; \
 while (vec->size + 1 > vec->capacity) { \
 vec->capacity *= 2; \
 vec->data = realloc(vec->data, vec->capacity * sizeof *vec->data); \
 } \
 vec->data[vec->size] = val; \
 vec->size += 1; \
} while (0)
#define VECTOR_PUSH_BACK_N(VEC, N, VAL) do { \
 typeof (VEC) *vec = &(VEC); \
 unsigned n = (N), i; \
 typeof (VAL) val = (VAL); \
 while (vec->size + n > vec->capacity) { \
 vec->capacity *= 2; \
 vec->data = realloc(vec->data, vec->capacity * sizeof *vec->data); \
 } \
 for (i = 0; i < n; ++i) \
 vec->data[vec->size + i] = val; \
 vec->size += n; \
} while (0)
#define VECTOR_PUSH_BACK_PTR(VEC, N, PTR) do { \
 typeof (VEC) *vec = &(VEC); \
 unsigned n = (N), i; \
 typeof (*PTR) *ptr = (PTR); \
 while (vec->size + n > vec->capacity) { \
 vec->capacity *= 2; \
 vec->data = realloc(vec->data, vec->capacity * sizeof *vec->data); \
 } \
 for (i = 0; i < n; ++i) \
 vec->data[vec->size + i] = ptr[i]; \
 vec->size += n; \
} while (0)
#define VECTOR_ERASE(VEC, POS) do { \
 typeof (VEC) *vec = &(VEC); \
 unsigned pos = (POS); \
 vec->size -= 1; \
 memmove(vec->data + pos, vec->data + pos + 1, (vec->size - pos) * sizeof *vec->data); \
} while (0)
#define VECTOR_ERASE_N(VEC, POS, N) do { \
 typeof (VEC) *vec = &(VEC); \
 unsigned pos = (POS), n = (N); \
 vec->size -= n; \
 memmove(vec->data + pos, vec->data + pos + n, (vec->size - pos) * sizeof *vec->data); \
} while (0)
#define VECTOR_POP_BACK(VEC) do { \
 (VEC).size -= 1; \
} while (0)
#define VECTOR_POP_BACK_N(VEC, N) do { \
 (VEC).size -= (N); \
} while (0)
#define VECTOR_CLEAR(VEC) do { \
 (VEC).size = 0; \
} while (0)
#define VECTOR_DATA(VEC) (VEC).data
#define VECTOR_AT(VEC, POS) (VEC).data[POS]
#define VECTOR_FRONT(VEC) (VEC).data[0]
#define VECTOR_BACK(VEC) (VEC).data[vec->size - 1]
#define VECTOR_FOR_EACH(VEC, VAR, DO) do { \
 typeof (VEC) *vec = &(VEC); \
 unsigned i = 0; \
 for (i = 0; i < vec->size; ++i) { \
 typeof (*vec->data) VAR = vec->data[i]; \
 DO; \
 } \
} while (0)
#define VECTOR_FREE(VEC) do { \
 typeof (VEC) *vec = &(VEC); \
 vec->size = 0; \
 vec->capacity = 0; \
 free(vec->data); \
} while(0)
#endif /* !defined VECTOR_H */

This code can also be found here!

This is almost a direct clone of the C++ std::vector. I analyzed and copied the resizing behavior of std::vector on my system and implemented it here.

Because there is no function overloading in C I had rename similar functions differently based on their variations. I also named the function based on their C++ equivalent (for example VECTOR_ERASE for std::vector::erase).

For example:

VECTOR_INSERT(VEC, POS, VAL) inserts the value VAL at position POS.

VECTOR_INSERT_N(VEC, POS, N, VAL) inserts the value VAL N number of times at position POS.

VECTOR_INSERT_PTR(VEC, POS, N, PTR) inserts N number of elements starting at position POS reading memory from PTR

I tried to keep the naming logical and consistent among the various functions.

This header file is lacking comments but I think that you can figure out what each function is supposed to do based on their C++ std::vector equivalent.

This is how the header file is meant to be used:

#include <stdio.h>
#include "vector.h"
int main()
{
 VECTOR_OF(int) int_vec;
 VECTOR_OF(double) dbl_vec;
 int i;
 VECTOR_INIT(int_vec);
 VECTOR_INIT(dbl_vec);
 for (i = 0; i < 100000000; ++i) {
 VECTOR_PUSH_BACK(int_vec, i);
 VECTOR_PUSH_BACK(dbl_vec, i);
 }
 for (i = 0; i < 100; ++i) {
 printf("int_vec[%d] = %d\n", i, VECTOR_AT(int_vec, i));
 printf("dbl_vec[%d] = %f\n", i, VECTOR_AT(dbl_vec, i));
 }
 VECTOR_FREE(int_vec);
 VECTOR_FREE(dbl_vec);
 return 0;
}

I also found my own implementation is faster than std::vector by a large margin at pushing back 100000000 ints and 100000000 doubless:

$ time ./c
real 0m2.251s
user 0m1.220s
sys 0m1.024s
$ time ./cpp
real 0m6.850s
user 0m4.908s
sys 0m1.924s

I feel very proud of this! I also think that it would have been useful in serious code if it was not relying on non standard extensions. I am quite disappointed that the C standard committee did not add typeof to C11 because it makes preprocessor macros very much safer.

• glampert: Well, typeof is supported by GCC since a long time now, and Clang also supports it, so I'd say it is pretty good!
• glampert: BTW, there is a somewhat similar implementation here.
• Brandon: You cannot compare this to the C++ version: You use malloc and don't initialize/zero-out all the memory like C++'s vector does. To do the same in C++, use an allocator that doesn't memset/default the vector's memory. OR use calloc in your implementation OR malloc + memset defaults.

Answer 1

I never thought macro code could be pretty, but this is actually very readable. However, why do you wrap your macros with do-while blocks? I would do away with inline code and prefer to use functions. First of all, they would be easier for the compiler to deal with, and it could then inline the functions as it saw fit.

Second, they would be easier for you to deal with. You could initialize the functions by calling a macro with a type argument. If the generated function names are predictable, you could then call the functions themselves, which provides the benefit of code completion and documentation.

• glampert: There are good reasons to wrap function-like macros in a do/while: stackoverflow.com/questions/154136/…
• wefwefa3: I am glad you find the code readable. I never thought about the idea of implementing something like this using generator functions. That would also work. :)

Answer 2

You evidently suffer the handicap of developing on a machine where memory allocation never fails.

To pick one example:

#define VECTOR_RESIZE(VEC, N, VAL) do { \
 typeof (VEC) *vec = &(VEC); \
 unsigned n = (N), i; \
 typeof (VAL) val = (VAL); \
 if (n > vec->capacity) \
 vec->data = realloc(vec->data, n * sizeof *vec->data); \
 for (i = vec->size; i < n; ++i) \
 vec->data[i] = val; \
 vec->size = n; \
} while (0)

This form (p = realloc(p, n)) is particularly harmful - not only does a failure cause undefined behaviour if we use p, but even if we detect the failure and avoid the UB, we have overwritten the pointer to the memory that's still allocated - a memory leak.

The entire codebase needs a re-think of how to deal with allocation failure, I'm afraid. The suggestion in another answer to use the macros to generate a set of function definitions may well help give us a consistent means of reporting success/failure.