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;
}
```