1 files changed, 247 insertions, 0 deletions
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.
+
+<hr>
+
+For those interested, here's the full source code:
+
+```c
+#include <assert.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#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.