4
\$\begingroup\$

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:

ryvnf:~/Programming/test$ time ./c

real    0m2.251s
user    0m1.220s
sys 0m1.024s
ryvnf:~/Programming/test$ 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.

\$\endgroup\$
  • \$\begingroup\$ Well, typeof is supported by GCC since a long time now, and Clang also supports it, so I'd say it is pretty good! \$\endgroup\$ – glampert Aug 24 '15 at 19:28
  • \$\begingroup\$ BTW, there is a somewhat similar implementation here. \$\endgroup\$ – glampert Aug 24 '15 at 19:33
  • \$\begingroup\$ 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. \$\endgroup\$ – Brandon Aug 31 '15 at 1:13
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ There are good reasons to wrap function-like macros in a do/while: stackoverflow.com/questions/154136/… \$\endgroup\$ – glampert Aug 24 '15 at 19:29
  • \$\begingroup\$ 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. :) \$\endgroup\$ – wefwefa3 Aug 25 '15 at 15:22

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.