From 82edda96ef68a4e4d0695fe1e056b609fdd83074 Mon Sep 17 00:00:00 2001 From: iamcheeseman Date: Thu, 19 Mar 2026 16:57:18 -0400 Subject: hello, world --- ramblings/c-is-the-best/index.md | 247 +++++++++++++++++++++++++++++++++++++++ ramblings/index.md | 8 ++ 2 files changed, 255 insertions(+) create mode 100644 ramblings/c-is-the-best/index.md create mode 100644 ramblings/index.md (limited to 'ramblings') diff --git a/ramblings/c-is-the-best/index.md b/ramblings/c-is-the-best/index.md new file mode 100644 index 0000000..87d29d7 --- /dev/null +++ b/ramblings/c-is-the-best/index.md @@ -0,0 +1,247 @@ +\> [go back](/ramblings) + +# Rambling: Implementing a Dynamic Array in C + +Have you ever wanted C to have a fully featured, easy-to-use, generic dynamic +array, which can be implemennted in a small of time? + +What if I told you that C can have a full, easy-to-use, generic dynamic array, +which can be implemented in a small amount of time? Because it can. I wrote the +whole thing without testing, and it worked *almost* first try. + +Let's start with the creation of a dynamic array. You might need to scroll +horizontally if your screen is teensy weensy. + +```c +#define DA_MIN_CAP 8 + +// Wrap the function in a macro to make it a little nicer to use. +#define da_create(T, init_cap) \ + ((T*)_da_create(sizeof(T), init_cap)) + +void* _da_create(size_t type_size, int init_cap) { + // Ensure a mimimum capacity. + init_cap = init_cap < DA_MIN_CAP + ? DA_MIN_CAP + : init_cap; + + // Those + 2 ints are our length and capacity. You can use + // whatever integer type you want; int is fine for this use-case. + int* arr = (int*)malloc(type_size * init_cap + sizeof(int) * 2); + + // Which we assign here. + arr[0] = 0; + arr[1] = init_cap; + + return (void*)(arr + 2); +} +``` + +So, we define a function `_da_create()`. It takes in the size of the type you +want to create, and how many elements to reserve space for. It allocates that +space, plus space for two integers. + +Those two integers are your array length and array capacity. They are placed in +front of the array. + +And then we return the pointer we allocated, but offset to point to the start +of your data. Finally, we wrap all this in a nice little macro called +`da_create()` so we don't need to explicitly pass the size and cast the +resulting pointer. + +Tada! You now have a generic dynamic array. Okay, well not really. You have +a heap-allocated array with two useless integers in front. Now, we need to be +able to access those integers in order to make them useful: + +```c +#define da_len_ptr(arr) ((int*)arr - 2) +#define da_len(arr) (*da_len_ptr(arr)) + +#define da_cap_ptr(arr) ((int*)arr - 1) +#define da_cap(arr) (*da_cap_ptr(arr)) +``` + +And now you have access to them. We have a separate macro to get a pointer to +the length/capacity so we can assign it. But anyway, how do you append? Well, +like so: + +```c +// This fancy lil macro just gets the pointer that +// we actually alloc'd. +#define da_base(arr) ((void*)arr - 2) + +// Of course, we wrap it in a macro for convenience. +#define da_append_slot(T, arr) + ((T*)_da_append_slot(sizeof(T), (void*)arr)) + +// This function returns the slot it just appended. +void* _da_append_slot(size_t type_size, void** arr) { + int cap = da_cap_ptr(*arr); + int len = da_len_ptr(*arr); + + (*len)++; + + // If we need space, grow the array. + if (*len > *cap) { + // This won't work if the initial capacity is 0, which + // is why we implemented a minimum. + *cap *= 2; + + // The base array is what realloc expects. + void* base = da_base(*arr); + base = realloc(base, (type_size * *cap) + sizeof(int) * 2); + assert(base != NULL); // Just to handle the case. + *arr = (void*)((int*)base + 2); + + // Update the length so we don't get a use-after-free later. + len = da_len_ptr(*arr); + } + + return *arr + ((*len - 1) * type_size); +} +``` + +So this doesn't actually really truly append anything. It ensures the existence +of a new slot at the end of the array, increments the length, and returns a +pointer to the last element. I didn't want to name it something like +`da_ensure_one()`, because it does a bit more than just make sure there's space +for your new element. + +Anyway, you can append an element onto the end of the array by doing something +like this: + +```c +int* arr = da_create(int, 0); +*da_append_slot(int, &arr) = 5; +``` + +Which you might notice can be wrapped up in a macro: + +```c +#define da_append(T, arr, elem) (*da_append_slot(T, arr) = elem) +``` + +And tada, you now can append elements to your very own dynamic array. And best +of all, you don't need to care too much about the internals in your usage. You +don't need to use some bespoke array data type. You don't need to worry about +storing the length and capacity; it's all already handled for you. + +But before I finish, we need to clean up the array, of course: + +```c +void da_free(void* arr) { + void* base = da_base(arr); + free(base); +} +``` + +Here's a fancy schmancy example of how to use it: + +```c +int main(void) { + uint64_t* arr = da_create(uint64_t, 0); + + // Append some stuff. + for (int i = 0; i < 20; i++) { + da_append(uint64_t, &arr, 900000000000000 + i); + } + + // Show some data. + printf("capacity: %d, length: %d\n", da_cap(arr), da_len(arr)); + for (int i = 0; i < da_len(arr); i++) { + printf("[%d] = %lu\n", i, arr[i]); + } + + da_free(arr); +} +``` + +I'll leave implementing extra methods like `da_remove()` and `da_find()` as an +exercise to the reader. If you know the basics of C, this shouldn't be too +hard, since as you might've noticed, the code for this dynamic array is pretty +similar to how someone would usually implement one. + +
+ +For those interested, here's the full source code: + +```c +#include +#include +#include +#include + +#define DA_MIN_CAP 8 + +#define da_create(T, init_capacity) \ + ((T*)_da_create(sizeof(T), init_capacity)) + +#define da_len_ptr(arr) ((int*)arr - 2) +#define da_len(arr) (*da_len_ptr(arr)) + +#define da_cap_ptr(arr) ((int*)arr - 1) +#define da_cap(arr) (*da_cap_ptr(arr)) + +#define da_base(arr) ((void*)da_len_ptr(arr)) + +#define da_append_slot(T, arr) \ + ((T*)_da_append_slot(sizeof(T), (void**)arr)) + +#define da_append(T, arr, elem) (*da_append_slot(T, arr) = elem) + +void* _da_create(size_t type_size, int init_cap) { + init_cap = init_cap < DA_MIN_CAP + ? DA_MIN_CAP + : init_cap; + + int* arr = (int*)malloc(type_size * init_cap + sizeof(int) * 2); + + arr[0] = 0; + arr[1] = init_cap; + return (void*)(arr + 2); +} + +void* _da_append_slot(size_t type_size, void** arr) { + int* cap = da_cap_ptr(*arr); + int* len = da_len_ptr(*arr); + + (*len)++; + + if (*len > *cap) { + *cap *= 2; + + void* base = da_base(*arr); + base = realloc(base, (type_size * *cap) + sizeof(int) * 2); + assert(base != NULL); + *arr = (void*)((int*)base + 2); + + len = da_len_ptr(*arr); + } + + return *arr + ((*len - 1) * type_size); +} + +void da_free(void* arr) { + void* base = da_base(arr); + free(base); +} + +int main(void) { + uint64_t* arr = da_create(uint64_t, 0); + + int* len = da_len_ptr(arr); + for (int i = 0; i < 20; i++) { + da_append(uint64_t, &arr, 900000000000000 + i); + } + + printf("capacity: %d, length: %d\n", da_cap(arr), da_len(arr)); + for (int i = 0; i < da_len(arr); i++) { + printf("[%d] = %lu\n", i, arr[i]); + } + + da_free(arr); +} +``` + +And to be clear: I'm aware of how basic this article is. I just wrote it to +fill out space on my website. diff --git a/ramblings/index.md b/ramblings/index.md new file mode 100644 index 0000000..d3b0274 --- /dev/null +++ b/ramblings/index.md @@ -0,0 +1,8 @@ +# Ramblings + +These are my ramblings. They might occassionally be useful. I hope that over +the years, I amass a large amount of old-man sounding ramblings. + +### 2026 +- [Implementing a Dynamic Array in C](/ramblings/c-is-the-best) - March 10 + -- cgit v1.3-2-g0d8e