C - Generic vector library

Question

I'm quite new to C, and I decided to create a generic vector library. Here is the code:

#ifndef VECTOR_H
#define VECTOR_H
#define DEFAULT_CAPACITY 10
#define EXPAND_RATIO 1.5
#include <stdlib.h>
#include <string.h>
enum error {
 NO_ERROR,
 INDEX_ERROR,
 KEY_ERROR,
 NULL_POINTER_ERROR,
 MEMORY_ERROR
};
#define VECTOR_NEW(vec_name, type) \
 /* a resizable array */ \
 struct vec_name { \
 size_t length; \
 size_t capacity; \
 type* items; \
 }; \
 \
 /* initializes a vector with a specific capacity */ \
 enum error init_##vec_name##_c(struct vec_name* vec, size_t capacity) { \
 if (!vec) \
 return NULL_POINTER_ERROR; \
 \
 vec->length = 0; \
 vec->capacity = capacity; \
 vec->items = malloc(capacity * sizeof(*vec->items)); \
 \
 return (vec->items) ? NO_ERROR : MEMORY_ERROR; \
 } \
 \
 /* initializes a vector with the default capacity */ \
 static inline enum error init_##vec_name(struct vec_name* vec) { \
 return init_##vec_name##_c(vec, DEFAULT_CAPACITY); \
 } \
 \
 /* frees the memory allocated for the vector */ \
 static inline enum error free_##vec_name(struct vec_name* vec) { \
 if (!vec) \
 return NULL_POINTER_ERROR; \
 free(vec->items); \
 vec->items = NULL; \
 return NO_ERROR; \
 } \
 \
 /* adds an item to the end of the vector */ \
 enum error append_##vec_name(struct vec_name* vec, type item) { \
 if (!vec) \
 return NULL_POINTER_ERROR; \
 if (vec->length >= vec->capacity) { \
 vec->capacity *= EXPAND_RATIO; \
 vec->items = \
 realloc(vec->items, vec->capacity * sizeof(vec->items)); \
 if (!vec->items) \
 return MEMORY_ERROR; \
 } \
 vec->items[vec->length++] = item; \
 return NO_ERROR; \
 } \
 \
 /* removes and item from the vector at a specified index (-1 as an index \
 * is pop back) \
 */ \
 static inline enum error pop_##vec_name(struct vec_name* vec, \
 size_t index, type* item) { \
 if (!vec) \
 return NULL_POINTER_ERROR; \
 if (vec->length <= index) \
 return INDEX_ERROR; \
 if (item) \
 *item = vec->items[index]; \
 const size_t block_size = (vec->length - index - 1) * sizeof(type); \
 memmove(&(vec->items[index]), &(vec->items[index + 1]), block_size); \
 --vec->length; \
 return NO_ERROR; \
 } \
 \
 /* sets an existing vector index to a specifid item */ \
 static inline enum error set_##vec_name(struct vec_name* vec, \
 size_t index, type item) { \
 if (!vec) \
 return NULL_POINTER_ERROR; \
 if (vec->length <= index) \
 return INDEX_ERROR; \
 vec->items[index] = item; \
 return NO_ERROR; \
 } \
 \
 /* applies the given function pointer to every item in the vector */ \
 static inline enum error map_##vec_name(struct vec_name* vec, \
 void(func)(type*)) { \
 if (!vec) \
 return NULL_POINTER_ERROR; \
 for (size_t i = 0; i < vec->length; ++i) \
 func(&vec->items[i]); \
 return NO_ERROR; \
 } \
 \
 /* places the item at a specifed index in the`value` parameter */ \
 static inline enum error get_##vec_name(struct vec_name* vec, \
 size_t index, type* value) { \
 if (!vec) \
 return NULL_POINTER_ERROR; \
 if (vec->length <= index) \
 return INDEX_ERROR; \
 *value = vec->items[index]; \
 return NO_ERROR; \
 }
#endif // VECTOR_H

Here is how it is used:

#include "veclib.h"
VECTOR_NEW(vector_int, int)
int main() {
 struct vector_int vec;
 init_vector_int(&vec);
 for (size_t i = 0; i <= 10; ++i) append_vector_int(&vec, i);
}

I'm unsure if my code is elegant, fast, etc. Thanks!

• vnp: Is VECTOR_NEQ a typo?
• Mr R: map is possibly a bad name - it's usage across other modern libraries tends to be map(from, to, convFunc)
• Mr R: Need to look at boundary conditions.. for instance pop seems like it might have an issue if there's only 1 element left. And minor spelling issue in removes and item and should be an.
• Mr R: Presumably the error return code is important - so why in your example aren't you using it? (possibly that will show an issue with usage??).
• Mr R: VECTOR_NEW doesn't create a "new" vector - it just defines the type/methods - so maybe should be VECTOR_DEFINE_TYPE? Or something more like what it is. And what if init_vector_int isn't called - everything breaks (it assumes that it has been init'd properly) ... is there a way you can setup so by default if it's not init'd properly it catches that and tells the user.

Answer 1

Naming

Very good comments and documentation. I had a clear picture of what you were trying to accomplish.

Instead of giving your users the ability to create any ##vec_name, I would consider, eg vec_##name, to give my vector types a naming consistency.

It is possible that not all of your functions are used; this generally leads well-meaning compilers to emit a warning for static functions. I received this good advice, silencing unused static functions by using them.

Allocation

append##vec_name converts to double and back. This might work for the DEFAULT_CAPACITY 10, but printing off,

printf("append " #vec_name " capacity %lu -> ", vec->capacity); \
vec->capacity *= EXPAND_RATIO; \
printf("%lu\n", vec->capacity); \

If it's 0 or 1, it gets stuck in undefined behaviour,

append vec_foo capacity 1 -> 1

On my computer, the code works for one re-allocation, then it segmentation faults. It's easier to debug when the memory allocation is in one function instead of both init_##vec_name##_c and append_##vec_name. A feature of realloc,

If ptr is a null pointer, realloc() shall be equivalent to malloc() for the specified size.

allows easily moving functions around to get one-point-of-failure, for example,

static enum error resize_##vec_name(struct vec_name* vec, size_t min_capacity) { \
 size_t new_capacity; \
 type* new_items; \
 if (!vec) \
 return NULL_POINTER_ERROR; \
 for (new_capacity = vec->capacity > DEFAULT_CAPACITY \
 ? vec->capacity : DEFAULT_CAPACITY; \
 new_capacity < min_capacity; new_capacity *= EXPAND_RATIO);\
 if (vec->capacity >= new_capacity) \
 return NO_ERROR; \
 new_items = realloc(vec->items, new_capacity * sizeof *new_items); \
 if (!new_items) \
 return MEMORY_ERROR; \
 vec->items = new_items; \
 vec->capacity = new_capacity; \
 return NO_ERROR; \
} \

Then this simplifies init_##vec_name##_c,

vec->length = 0; \
vec->capacity = 0; \
vec->items = 0; \
return resize_##vec_name(vec, capacity); \

and append_##vec_name,

if((e = resize_##vec_name(vec, vec->length + 1)) != NO_ERROR) \
 return e; \
vec->items[vec->length++] = item; \

Functions

Viewed as a state machine, your programme has some invalid states. Suggest in free##vec_name,

vec->capacity = vec->length = 0; \

In pop##vec_name, the documentation says that -1 is the back, which is useful, kind of like Python, but I don't it see the code.

In set##vec_name, you use an assignment. For large types, this might mean a lot of copying. It would be faster to construct it in place; this is kind of like the difference between push_back and emplace_back in C++.

The value of vec is const in set_##vec_name, map_##vec_name, and get_##vec_name. This might help the compiler to more aggressively optimise, and may be important self-documentation: it's a statement that vector's topology will not change.

Typo: specified. init_##vec_name##_c and append_##vec_name, I assume you also meant to make them static.

Errors

Your abstraction of errors and passing them on to the user is great. stdio.h is not needed and not even included.

enum error has a high probability of namespace clashes with other headers. You might want to use the facilities given in errno.h instead of inventing your own. Instead of having to return one of several values, one returns a bit — a null value or a flag — telling your users to check errno. This will also simplify passing errors from the standard library because you can just pass on the error to the caller instead of making up a new error.

It depends on what the use case for this is, but I would consider making programming errors assert instead of dynamic checks, (eg NULL_POINTER_ERROR.) I've found that this frees a lot of cases from your testing and verification.

• xilpex: In set##vec_name, you use an assignment. This limits the vectors to assignable types. I would question the use of this function at all. -- Could you please elaborate on this?
• Neil: I edited that -- eg a struct or union is not going to be assignable. A more general memset(...sizeof item...) like one did for the constructor is more general.
• xilpex: On the restrict keyword -- Would static inline enum error pop_##vec_name(struct vec_name* restrict vec, size_t index, type* restrict item) be a good idea (I haven't used restrict before)?
• Neil: I think it might help, see usage of restrict, but it affects pointers of compatible types.
• xilpex: I have seen that, but is my usage above a good idea?