-
Notifications
You must be signed in to change notification settings - Fork 118
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 ctlNote 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 ctlOnce 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.