vec
#include <vec.h>
The CTL vec
, analogous to the STL std::vector
, is a container specializing in contiguous storage and fast cache access. A vec
may be used in place of arrays, variable length arrays, and malloc
/ realloc
pairs that manage dynamic growable arrays. Pointer validity within a vec
is not guaranteed; but is guaranteed with the <lst.h> container.
Basic built-in types, like int
, unsigned
, double
, float
, and char
, require a #define P
pre-processor directive to signal that the vec
requires no additional per-element cleanup when freed:
#include <stdio.h>
#define P
#define T int
#include <vec.h>
int compare(int* a, int* b)
{
return *b < *a;
}
int main(void)
{
vec_int a = vec_int_init();
for(int i = 0; i < 32; i++)
vec_int_push_back(&a, rand() % 1024);
vec_int_sort(&a, compare);
int sum = 0;
int index = 0;
foreach(vec_int, &a, it)
{
printf("%2d: %4d\n", index, *it.ref);
sum += *it.ref;
index += 1;
}
printf("%d\n", sum);
vec_int_free(&a);
}
gcc main.c -I ctl
Note that foreach
is used to loop through the contents of the vec
. While slower than conventional for
loops, iteration via foreach
allows swapping the vec
container with a deq
or a lst
. While container swapping is out of this tutorial's scope, faster vector iteration can be accomplished with a for
loop:
for(size_t i = 0; i < a.size; i++)
{
printf("%2d: %4d\n", index, a.value[i]);
sum += a.value[i];
index += 1;
}
3D game engines often require an array of contiguous elements to be sent to the graphics card. Assuming a simplified engine taking only 3D positions of physical entities relative to the player, a graphics card can be used more efficiently by taking advantage of the z-buffer and rendering the closest entities first:
#include <stdio.h>
#include <math.h>
typedef struct { float x, y, z; } point;
#define P
#define T point
#include <vec.h>
float mag(point* p)
{
return sqrtf(p->x * p->x + p->y * p->y + p->z * p->z);
}
int compare(point* a, point* b)
{
return mag(a) > mag(b);
}
int main(void)
{
vec_point a = vec_point_init();
for(int i = 0; i < 32; i++)
{
point p = {
32.0f * rand() / RAND_MAX,
32.0f * rand() / RAND_MAX,
32.0f * rand() / RAND_MAX,
};
vec_point_push_back(&a, p);
}
vec_point_sort(&a, compare);
for(size_t i = 0; i < a.size; i++)
printf("%5.2f %5.2f %5.2f\n",
a.value[i].x, a.value[i].y, a.value[i].z);
vec_point_free(&a);
}
gcc main.c -lm -I ctl
Once again #define P
is included to signal that no further cleanup is required for the point data type when vec
is freed.
More complicated types in ownership of pointers acquired via malloc
require _free
and _copy
declarations for that type. For instance, one may be in ownership of several raw images stored as array of unsigned bytes, each allocated originally with malloc
.
#include <stdint.h>
#include <stdlib.h>
typedef struct
{
uint8_t* data;
size_t size;
}
image;
void image_free(image*);
image image_copy(image*);
#define T image
#include <vec.h>
image image_read(void);
int main(void)
{
vec_image a = vec_image_init();
for(size_t i = 0; i < 128; i++)
vec_image_push_back(&a, image_read());
vec_image b = vec_image_copy(&a);
vec_image_free(&a);
vec_image_free(&b);
}
image image_init(size_t size)
{
image self = {
.data = malloc(sizeof(*self.data) * size),
.size = size
};
return self;
}
image image_read(void)
{
image im = image_init(rand() % 65536);
for(size_t i = 0; i < im.size; i++)
im.data[i] = rand() % UINT8_MAX;
return im;
}
void image_free(image* self)
{
free(self->data);
self->data = NULL;
self->size = 0;
}
image image_copy(image* self)
{
image copy = image_init(self->size);
for(size_t i = 0; i < copy.size; i++)
copy.data[i] = self->data[i];
return copy;
}
In this example, #define P
is omitted, and image_free
and image_copy
are made available to the template. The _copy
function must match format T T_copy(T*)
where T
is image
in this case. The free function must match void T_free(T*).
Within main
, a large collection of images are randomly generated. To exemplify a container copy, each element of vec a
is copied and inserted into vec b
. Compiling with address sanitizers enabled, all heap elements are provably freed at the time of program exit:
gcc -fsanitize=address -fsanitize=undefined main.c -I ctl
Leveraging gcc's warning system, by forgetting to declare image_free
, or image_copy
, the compiler will error out, and list the missing declaration in a human readable way:
In file included from ctl/vec.h:5,
from main.c:13:
ctl/vec.h: In function ‘vec_image_init’:
main.c:12:11: error: ‘image_free’ undeclared (first use in this function)
12 | #define T image
| ^~~~~
ctl/ctl.h:7:19: note: in definition of macro ‘CAT’
7 | #define CAT(a, b) a##b
| ^
ctl/ctl.h:11:28: note: in expansion of macro ‘PASTE’
11 | #define JOIN(prefix, name) PASTE(prefix, PASTE(_, name))
| ^~~~~
ctl/vec.h:51:17: note: in expansion of macro ‘JOIN’
51 | self.free = JOIN(T, free);
| ^~~~
ctl/vec.h:51:22: note: in expansion of macro ‘T’
51 | self.free = JOIN(T, free);
| ^
main.c:12:11: note: each undeclared identifier is reported only once for each function it appears in
12 | #define T image
| ^~~~~
ctl/ctl.h:7:19: note: in definition of macro ‘CAT’
7 | #define CAT(a, b) a##b
| ^
ctl/ctl.h:11:28: note: in expansion of macro ‘PASTE’
11 | #define JOIN(prefix, name) PASTE(prefix, PASTE(_, name))
| ^~~~~
ctl/vec.h:51:17: note: in expansion of macro ‘JOIN’
51 | self.free = JOIN(T, free);
| ^~~~
ctl/vec.h:51:22: note: in expansion of macro ‘T’
51 | self.free = JOIN(T, free);
As an improvement, the contents of image (data
and size
) are a pointer-size pair, which conveniently can be replaced with another vec
:
#include <stdint.h>
#include <stdlib.h>
#define P
#define T uint8_t
#include <vec.h>
typedef struct
{
vec_uint8_t data;
}
image;
void image_free(image*);
image image_copy(image*);
#define T image
#include <vec.h>
image image_read(void);
int main(void)
{
vec_image a = vec_image_init();
for(size_t i = 0; i < 128; i++)
vec_image_push_back(&a, image_read());
vec_image b = vec_image_copy(&a);
vec_image_free(&a);
vec_image_free(&b);
}
image image_init(size_t size)
{
image self;
self.data = vec_uint8_t_init();
vec_uint8_t_resize(&self.data, size, 0x00);
return self;
}
image image_read(void)
{
image im = image_init(rand() % 65536);
for(size_t i = 0; i < im.data.size; i++)
im.data.value[i] = rand() % UINT8_MAX;
return im;
}
void image_free(image* self)
{
vec_uint8_t_free(&self->data);
}
image image_copy(image* self)
{
image copy;
copy.data = vec_uint8_t_copy(&self->data);
return copy;
}
gcc main.c -I ctl
And finally, if no other fields need to be added to image
, the resulting container can collapse into the STL analogous of std::vector<std::vector<uint8_t>>
.
#include <stdint.h>
#include <stdlib.h>
#define P
#define T uint8_t
#include <vec.h>
#define T vec_uint8_t
#include <vec.h>
int main(void)
{
vec_vec_uint8_t a = vec_vec_uint8_t_init();
for(size_t i = 0; i < a.size; i++)
{
vec_uint8_t b = vec_uint8_t_init();
size_t size = rand() % 65536;
for(size_t j = 0; j < size; j++)
vec_uint8_t_push_back(&b, rand() % UINT8_MAX);
vec_vec_uint8_t_push_back(&a, b);
}
vec_vec_uint8_t b = vec_vec_uint8_t_copy(&a);
vec_vec_uint8_t_free(&a);
vec_vec_uint8_t_free(&b);
}
gcc main.c -I ctl
#define P
is omitted from the vec_vec_uint8_t
templating; the _free
and _copy
are automatically assigned from the vec_uint8_t
container.