4
\$\begingroup\$

I wanted to create a vector that can be used for different types, as generics do not exist in C. I came up with an implementation that maintains a buffer on the heap and reallocs itself when the buffer size is exceeded. The heart of the implementation are the macros that can be used to retrieve and insert elements conveniently.

Example:

Vector vec = vec_create(sizeof(char*), 1); // Params: Size of each element, start size
VEC_PUSH_ELEM(&vec, char*, "hello");       // Params: Vector, type and value
char *test = VEC_GET_ELEM(&vec, char*, 0); // Params: Vector, type and index
vec_destroy(&vec);                         // Free buffer

vector.h:

#pragma once
#include <stdbool.h>
#include <stdlib.h>
#include <stdarg.h>

// May change the buffer location
#define VEC_PUSH_ELEM(vec, type, expr) (*(type*)vec_push_empty(vec)) = expr
#define VEC_SET_ELEM(vec, type, index, expr) (*(type*)vec_get(vec, index)) = expr
// The following macros will dereference a NULL pointer on invalid index or empty vector
#define VEC_GET_ELEM(vec, type, index) (*(type*)vec_get(vec, index))
#define VEC_POP_ELEM(vec, type) *(type*)vec_pop(vec)
#define VEC_PEEK_ELEM(vec, type) *(type*)vec_peek(vec)

/*
 * Never save pointers when there are elements
 * inserted into the buffer! It can be realloc'ed!
 */

typedef struct
{
    size_t elem_size;
    size_t elem_count;
    size_t buffer_size;
    void *buffer;
} Vector;

// Buffer handling
void vec_trim(Vector *vec);
bool vec_ensure_size(Vector *vec, size_t needed_size);
Vector vec_create(size_t elem_size, size_t start_size);
void vec_reset(Vector *vec);
void vec_destroy(Vector *vec);

// Insertion
void *vec_push(Vector *vec, void *elem);
void *vec_push_many(Vector *vec, size_t num, void *elem);
void *vec_push_empty(Vector *vec);

// Retrieval
void *vec_get(Vector *vec, size_t index);
void *vec_pop(Vector *vec);
void *vec_peek(Vector *vec);

// Attributes
size_t vec_count(Vector *vec);

vector.c:

#include <string.h>
#include "alloc_wrappers.h"
#include "vector.h"

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define VECTOR_GROWTHFACTOR 0.5

void vec_trim(Vector *vec)
{
    vec->buffer_size = vec->elem_count + 1;
    vec->buffer = realloc_wrapper(vec->buffer, vec->elem_size * vec->buffer_size);
}

// Returns true if buffer needed to be extended.
bool vec_ensure_size(Vector *vec, size_t needed_size)
{
    bool res = false;
    while (needed_size > vec->buffer_size)
    {
        res = true;
        vec->buffer_size += MAX(1, (size_t)(vec->buffer_size * VECTOR_GROWTHFACTOR));
    }
    vec->buffer = realloc_wrapper(vec->buffer, vec->elem_size * vec->buffer_size);
    return res;
}

Vector vec_create(size_t elem_size, size_t start_size)
{
    return (Vector){
        .elem_size   = elem_size,
        .elem_count  = 0,
        .buffer_size = start_size,
        .buffer      = malloc_wrapper(elem_size * start_size)
    };
}

void vec_reset(Vector *vec)
{
    vec->elem_count = 0;
}

void vec_destroy(Vector *vec)
{
    free(vec->buffer);
}

void *vec_push(Vector *vec, void *elem)
{
    return vec_push_many(vec, 1, elem);
}

/*
Summary: To push a literal fast, for convenience use VEC_PUSH_LITERAL-Macro
*/
void *vec_push_empty(Vector *vec)
{
    vec_ensure_size(vec, vec->elem_count + 1);
    return vec_get(vec, vec->elem_count++);
}

void *vec_push_many(Vector *vec, size_t num, void *elem)
{
    vec_ensure_size(vec, vec->elem_count + num);
    void *first = (char*)vec->buffer + vec->elem_size * vec->elem_count;
    memcpy(first, elem, num * vec->elem_size);
    vec->elem_count += num;
    return first;
}

void *vec_get(Vector *vec, size_t index)
{
    return (char*)vec->buffer + vec->elem_size * index;
}

void *vec_pop(Vector *vec)
{
    if (vec->elem_count == 0) return NULL;
    vec->elem_count--;
    return vec_get(vec, vec->elem_count);
}

void *vec_peek(Vector *vec)
{
    if (vec->elem_count == 0) return NULL;
    return vec_get(vec, vec->elem_count - 1);
}

size_t vec_count(Vector *vec)
{
    return vec->elem_count;
}

malloc_wrapper and realloc_wrapper are just malloc and realloc that print to stderr and exit the application when NULL is returned and the size was not 0. My main concerns are that pointers to items within the vector can be passed to client code and stored there. These will become invalid if realloc changes the base address of the buffer. Are there any ways to do it differently, or is it just something to live with? Also, are the macros any good or too error-prone?

I'm looking forward to better my coding style, thanks in advance! Philipp

You can see the whole code at: vector.h and vector.c

\$\endgroup\$
4
  • \$\begingroup\$ Do you have code for unit testing this that you can add to the question? That would provide a better explanation of use then the brief snippet you provided at the top, \$\endgroup\$
    – pacmaninbw
    Sep 17 '20 at 21:53
  • \$\begingroup\$ I've made an edit extending my example :) \$\endgroup\$ Sep 17 '20 at 23:07
  • \$\begingroup\$ I rolled back your edit, because editing the code after the answer was received invalidates the answer. Feel free to post a follow-up question with all necessary changes. \$\endgroup\$
    – vnp
    Sep 17 '20 at 23:29
  • 3
    \$\begingroup\$ @vnp I don't see how editing the example usage, not their actual code, has invalidated your answer. What point in your answer does it make moot? \$\endgroup\$
    – Peilonrayz
    Sep 17 '20 at 23:52
2
\$\begingroup\$

The biggest improvement you can do of this is to convert to so-called "opaque type", meaning private encapsulation. This means that you have to re-write the code a bit and provide "constructors"/"destructors". vec_create is supposed to be this and not some "buffer handling" member function.

So you could change the header to this:

// forward declaration, opaque type
typedef struct Vector Vector;

// Constructors
Vector* vec_create(size_t elem_size, size_t start_size);

// Destructor
void vec_free (Vector* vec);

And then in the C file:

// struct implementation, private members:
struct Vector
{
    size_t elem_size;
    size_t elem_count;
    size_t buffer_size;
    void *buffer;
};


Vector* vec_create(size_t elem_size, size_t start_size)
{
    Vector* obj = malloc(sizeof(Vector));
    if(obj != NULL)
    {
        *obj = (Vector){
            .elem_size   = elem_size,
            .elem_count  = 0,
            .buffer_size = start_size,
            .buffer      = malloc(elem_size * start_size)
        };
    }
    return obj;
}

void vec_free (Vector* vec)
{
    free(vec->buffer);
    free(vec);
}

Now all struct members are completely private and can't be accessed by the caller. But this also means that the caller can't allocate objects of type Vector themselves, so they have to declare Vector* and pass those to your class.

Other remarks:

  • I'd recommend to get rid of the macros. They do not add any type safety, but just hide away casts. Let the caller do the casts. However, exposing a void* to a private member is a bad idea, all of these should be const void* if anything.

    You could perhaps consider including type information with the struct, in which case more intricate and type safe wrapper macros might be possible.

  • All function like macros must be surrounded by parenthesis.

  • Don't use non-portable #pragma once, there is no reason to use non-standard extensions that are 100% equivalent to standard C features. Use #ifndef VECTOR_H #define VECTOR_H #endif instead.

  • You should move all #include to the header file, in order to document code dependencies to the user of your code. For example you have some "alloc_wrappers.h" that you didn't post, so when trying to compile this, I get various errors in the .c file.

  • Use const correctness on member functions that don't modify the passed Vector.

\$\endgroup\$
7
  • \$\begingroup\$ Thank you, all these remarks are very helpful and I think I'll implement them. On your first remark: On my first draft I did it like this, but I feared that the additional heap chunk of size Vector had too much overhead. I could go with one heap chunk by making "buffer" a flexible array member at the end of the vector, like the "data" member of the TrieNode here: github.com/PhilippHochmann/ccalc/blob/master/src/util/trie.h Are there any reasons against this? \$\endgroup\$ Sep 21 '20 at 9:52
  • 1
    \$\begingroup\$ @PhilippHochmann If you could make it a flexible array member (of uint8_t), then you can allocate all heap memory in one go, which will be much more effective than the code with multiple malloc that I posted above. Better heap use, more cache friendly data, faster execution of vec_create. \$\endgroup\$
    – Lundin
    Sep 21 '20 at 9:58
  • \$\begingroup\$ Why is it beneficial to return const void* instead of void* when the first thing I do after retrieval is casting it to a non-const pointer type? \$\endgroup\$ Sep 22 '20 at 9:13
  • \$\begingroup\$ @PhilippHochmann If you allow the caller to modify member variables, then you break private encapsulation and create a "tight coupling" dependency between everything. Needless to say, nobody is allowed to "cast away" const qualified variables since that invokes undefined behavior. If some nutto caller does that anyway, that's their problem. \$\endgroup\$
    – Lundin
    Sep 22 '20 at 9:27
  • \$\begingroup\$ @PhilippHochmann But most sensibly written classes/ADTs don't return data by reference at all, but by value through hard copies. Sacrificing a tiny bit of performance in order to prevent that the whole program turns into some pointer spaghetti nightmare, where everything is connected to everything else. \$\endgroup\$
    – Lundin
    Sep 22 '20 at 9:28
2
\$\begingroup\$
  • To address your immediate concern, there are so many ways for the client to invalidate the vector, that you should not worry. STL bluntly documents the conditions when the iterators are invalidated. Just follow the suit.

    Depending on the use case, you may not let the client have pointer to individual elements at all (just do not return them).

  • To expand on the bullet point above, I strongly recommend to add mapping (apply a function to each element of vector) and folding (apply a function while accumulating result) capabilities. This would eliminate 99% of client needs to have pointers to the vector elements.

  • I don't see how the caller may use the value returned by vec_ensure_size. Making it void seems more natural.

  • Macros are to be avoided. In C, the void * is automatically converted to a suitable one, as LHS is declared. GET, POP, PEEK provide neither help nor security. PUSH and SET - in my opinion - only clutter the code. Other people may have other opinions.

    BTW, VEC_GET may also dereference an invalid index.

PS: In a private conversation Alex Stepanov said that the biggest mistake of STL was calling it vector. It is not a vector, it is a (dynamic) array.

\$\endgroup\$
1
  • \$\begingroup\$ I've removed the retrieval macros but I guess I will hold on to PUSH and SET for now. Also, I needed the return value for vec_ensure_size for something else, but as I looked at it again now I realised I could do this thing a lot easier without the return value! Thanks for your elaborate answer. \$\endgroup\$ Sep 17 '20 at 23:09
1
\$\begingroup\$

Little review.

vec_ensure_size() improvements

Rather than loop to the needed size, get there directly.

Also, no need to to realloc() if vec->buffer_size did not increase.

Alternate:

bool vec_ensure_size(Vector *vec, size_t needed_size) {
  if (needed_size <= vec->buffer_size) {
    return false;
  }
  vec->buffer_size += (size_t)(vec->buffer_size * VECTOR_GROWTHFACTOR);
  if (vec->buffer_size < needed_size) {
    vec->buffer_size = needed_size;
  }
  // Pedantic check for overflow
  assert(vec->buffer_size <= SIZE_MAX/vec->elem_size);

  vec->buffer = realloc_wrapper(vec->buffer, vec->elem_size * vec->buffer_size);
  return true;
}
\$\endgroup\$
2
  • \$\begingroup\$ I thought it would be nice to always realloc to give the allocator the opportunity to defragment the memory space. I guess most of the time it will just do nothing when the size does not change. \$\endgroup\$ Sep 18 '20 at 10:44
  • 1
    \$\begingroup\$ @PhilippHochmann Perhaps. Yet rather than code to what the allocate might do (there a lots of allocation algorithms) make clear code. IAC, with exponential growth, the allocation costs should have minimal impact anyways. \$\endgroup\$ Sep 18 '20 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.