Dynamic generic array list implementation in C99

Question

As an exercise to get to know C a bit more, I decided to implement a dynamic array implementation in C99 with generic support.

Everything is implemented with series of macros. The array_list struct definition itself is an anonymous struct, which allows client (user) to have very easy access to it. When capacity is reached it will automaticly resize by a growth factor of 1.618.

I'm currently mostly looking for: 1) Readability, 2) Correctness, and 3) Performance

array_list.h

#pragma once #ifndef ARRAY_LIST_H #define ARRAY_LIST_H #include <memory.h> #include <stdlib.h> // Anonymous struct for array_list definition #define array_list(T) \ struct { \ T* values; \ size_t size; \ size_t capacity; \ } // Gets the size of the T element in bytes #define array_list_T_size(arr) sizeof((arr)->values[0]) // Gets the pointer of the array_list #define array_list_ptr(arr) (void*)&arr // Initializes array_list with starting capacity n #define array_list_init_size(T, arr, n) \ ({ \ size_t size_bytes = sizeof(T) * n; \ (arr)->values = malloc(size_bytes); \ memset((arr)->values, 0, size_bytes); \ (arr)->size = 0; \ (arr)->capacity = n; \ }) // Initializes array_list with starting capacity 10 #define array_list_init(T, arr) array_list_init_size(T, arr, 10); // Destroys array_list and frees the allocated memory #define array_list_destroy(arr) \ ({ \ free((arr)->values); \ (arr)->values = NULL; \ (arr)->size = 0; \ (arr)->capacity = 0; \ }) // Makes a deep copy from src_arr to dst_arr #define array_list_cpy(dst_arr, src_arr) \ ({ \ size_t size_bytes = \ sizeof((src_arr)->values[0]) * (src_arr)->capacity; \ (dst_arr)->values = malloc(size_bytes); \ memcpy((dst->arr)->values, (src_arr)->values, size_bytes); \ (dst_arr)->size = (src_arr)->size; \ (dst_arr)->capacity = (src_arr)->capacity; \ (dst_arr); \ }) // Moves src_arr to dst_arr #define array_list_mov(dst_arr, src_arr) \ ({ \ (dst_arr)->values = (src_arr)->values; \ (dst_arr)->size = (src_arr)->size; \ (dst_arr)->capacity = (src_arr)->capacity; \ \ (src_arr)->values = NULL; \ (src_arr)->size = 0; \ (src_arr)->capacity = 0; \ (dst_arr); \ }) // Resizes array_list arr to new_size #define array_list_resize(arr, new_size) \ ({ \ size_t new_size_bytes = new_size * array_list_T_size(arr); \ void* new_values = malloc(new_size_bytes); \ /* copying old values to new values */ \ size_t old_size_bytes = array_list_T_size(arr) * (arr)->capacity; \ memcpy(new_values, (arr)->values, old_size_bytes); \ /* setting trailing part to zeros */ \ memset((char*)new_values + old_size_bytes, 0, \ new_size_bytes - old_size_bytes); \ /* setting new values, and freeing old values */ \ free((arr)->values); \ (arr)->values = new_values; \ /* setting new capacity */ \ (arr)->capacity = new_size; \ }) // Shifts array_list elements to the right from starting idx #define array_list_rshift_elements(arr, idx) \ ({ \ void* p_start = (void*)((arr)->values + idx - 1); \ void* p_end = (void*)((arr)->values + idx); \ size_t num_bytes = ((arr)->size - idx) * array_list_T_size(arr); \ memmove(p_end, p_start, num_bytes); \ }) // Shifts array_list elements to the left from starting idx #define array_list_lshift_elements(arr, idx) \ ({ \ void* p_start = (void*)((arr)->values + idx); \ void* p_end = (void*)((arr)->values + idx + 1); \ size_t num_bytes = ((arr)->size - idx - 1) * array_list_T_size(arr); \ memmove(p_start, p_end, num_bytes); \ }) // Inserts element at the end and grows array_list, if needed #define array_list_insert(arr, ...) \ ({ \ if ((arr)->size + 1 >= (arr)->capacity) \ array_list_resize(arr, (size_t)((arr)->capacity * 1.618)); \ (arr)->values[(arr)->size] = __VA_ARGS__; \ ++((arr)->size); \ }) // Inserts element at a specific index and grows array_list, if needed #define array_list_insert_at(arr, idx, ...) \ ({ \ if ((arr)->size + 1 >= (arr)->capacity) \ array_list_resize(arr, (size_t)((arr)->capacity * 1.618)); \ array_list_rshift_elements(arr, idx); \ (arr)->values[idx] = __VA_ARGS__; \ ++((arr)->size); \ }) // Removes element at a specified index #define array_list_remove(arr, idx) \ ({ \ array_list_lshift_elements(arr, idx); \ --((arr)->size); \ }) // Retrieves the size of the collection #define array_list_size(arr) (arr)->size; // Retrieves element at idx #define array_list_get(arr, idx) (arr)->values[idx] #endif // ARRAY_LIST_H 

Example of using array_list.h

#include <array_list.h> #include <stdio.h> int main() { // creating array_list of type int array_list(int) arr; // initializing array_list array_list_init(int, &arr); // inserting 0..1000000 numbers into array list for (size_t i = 0; i < 1000000lu; ++i) array_list_insert(&arr, i + 1llu); size_t sum = 0; // iterating over each element and calulating sum for (size_t i = 0; i < arr.size; ++i) sum += arr.values[i]; printf("sum: %lu\n", sum); // destroying arr array_list_destroy(&arr); struct Particle { float pos[2]; float velocity[2]; }; // creating another array list with Particle struct array_list(struct Particle) arr2; array_list_init(struct Particle, &arr2); // inserting some data array_list_insert(&arr2, (struct Particle){.pos = {10, 20}, .velocity = {30, 0}}); // retrieving data printf("x: %.2f, velocity y: %.2f\n", arr2.values[0].pos[0], arr2.values[0].velocity[1]); // destroying arr2 array_list_destroy(&arr2); // reusing arr struct for another array_list array_list_init(int, &arr); // inserting some ints array_list_insert(&arr, 3); array_list_insert(&arr, 6); array_list_insert(&arr, 7); array_list_insert(&arr, 8); array_list_insert(&arr, 1); array_list_insert(&arr, 2); array_list_insert(&arr, 6); // removing some elements array_list_remove(&arr, 1); array_list_remove(&arr, 0); // inserting at index 0 array_list_insert_at(&arr, 0, 100); // printing each element for (size_t i = 0; i < arr.size; ++i) printf("%d, ", arr.values[i]); // prints: 100, 7, 8, 1, 2, 6, printf("\n"); array_list_destroy(&arr); return 0; } ```

Answer 1

Answers to your questions

I'm currently mostly looking for: 1) Readability,

Macros make things less readable, both for humans and for source code editors. It is a necessary evil if you still want this kind of somewhat type-safe dynamic array in C. This problem is fixed in C++, where you can just use std::vector.

2. Correctness,

See below for some correctness issues I found.

and 3) Performance

The performance should be very good, as the macro calls will all be inlined of course, and I don't see anything wrong performance-wise, except possibly that you explicitly set all memory to zero. This is different from regular C arrays, where the elements or not zeroed by default.

Issues with macros

There are several problems with macros. First, the arguments you give it are placed in the body mostly verbatim. This means that you have issues if you for example call:

array_list(int) arr; array_list_init_size(int, arr, 1 + 2); 

You expect this to allocate memory for 3 elements. However, the macro expension will generate this code:

({ size_t size_bytes = sizeof(int) * 1 + 2; // <- Problem! (arr)->values = malloc(size_bytes); memset((arr)->values, 0, size_bytes); (arr)->size = 0; (arr)->capacity = 1 + 2; }); 

Only 6 bytes will be allocated here, only enough for one and a half integer, but it records that the capacity is 3 integers. This will likely cause a buffer overflow later.

Another issue, as you already encountered, is that it is a bit hard to create a macro that contains multiple statements. You solved this by using statement expressions, however those are a GCC extension and not standard C. The standard way to solve this issue is to use a do...while(0) block:

#define array_list_init_size(T, arr, n) \ do { \ (arr)->values = calloc((n), sizeof(T)); \ (arr)->size = 0; \ (arr)->capacity = (n); \ } while(0) 

Ensure you handle corner cases correctly

What if you initialize an array with a capacity of 0 or 1, and then try to insert multiple elements? When you try to grow the array, you multiply the capacity by 1.618, but the result when cast back to a size_t will still be 0 or 1 respectively. I would ensure you always set capacity to at least 2 to avoid this issue.