Implementing a vector using memory tricks, TBC

1 files changed, 104 insertions, 0 deletions

diff --git a/impls/vec.c b/impls/vec.c
new file mode 100644
index 0000000..f73b9fc
--- /dev/null
+++ b/impls/vec.c
@@ -0,0 +1,104 @@
+/* Copyright (C) 2024 Aryadev Chavali
+ * Created: 2024-08-11
+ * Author: Aryadev Chavali
+ * Description: A fast vector
+ */
+
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define MAX(A, B) ((A) > (B) ? (A) : (B))
+#define MIN(A, B) ((A) < (B) ? (A) : (B))
+
+/**
+   @brief A vector, consisting of a header and some payload (data).
+   @details The idea is that the user must never actually interact with this
+   structure directly, only the data involved.  Any vector related functions
+   deal with
+ */
+typedef struct
+{
+  uint64_t size;
+  uint64_t capacity;
+  uint8_t data[];
+} vec_t;
+
+#define VEC_SIZE(VEC)     (((vec_t *)(VEC))[-1].size)
+#define VEC_CAPACITY(VEC) (((vec_t *)(VEC))[-1].capacity)
+
+void vec_make(uint8_t **data, uint64_t initial_capacity)
+{
+  if (!data)
+    return;
+  initial_capacity = MAX(initial_capacity, 8);
+  vec_t *vector    = calloc(1, sizeof(vec_t) + initial_capacity);
+  vector->size     = 0;
+  vector->capacity = initial_capacity;
+  *data            = vector->data;
+}
+
+void vec_free(uint8_t **data)
+{
+  if (!data || !*data)
+    return;
+  free(((vec_t *)*data) - 1);
+}
+
+void vec_expand(uint8_t **data, uint64_t extra)
+{
+  if (!data)
+    return;
+
+  // Move *data such that it is exactly at the vector header
+  vec_t *original  = ((vec_t *)(*data)) - 1;
+  uint64_t new_cap = MAX(original->capacity * 2, original->capacity + extra);
+  vec_t *new_data  = calloc(1, sizeof(vec_t) + new_cap);
+
+  new_data->size     = original->size;
+  new_data->capacity = new_cap;
+  memcpy(new_data->data, original->data, original->size);
+  free(original);
+
+  *data = new_data->data;
+}
+
+void vec_append_byte(uint8_t **data, uint8_t byte)
+{
+  if ((VEC_CAPACITY(*data) - VEC_SIZE(*data)) == 0)
+    vec_expand(data, 1);
+
+  (*data)[VEC_SIZE(*data)++] = byte;
+}
+
+void vec_append_bytes(uint8_t **data, const uint8_t *bytes, uint64_t size)
+{
+  if ((VEC_CAPACITY(*data) - VEC_SIZE(*data)) < size)
+    vec_expand(data, size);
+  printf("%p, %p\n", *data, (((vec_t *)*data) - 1));
+  memcpy(*data + VEC_SIZE(*data), bytes, size);
+  VEC_SIZE(*data) += size;
+}
+
+int main(void)
+{
+  const uint8_t *strings[] = {
+      (uint8_t *)"This",
+      (uint8_t *)"is",
+      (uint8_t *)"a",
+      (uint8_t *)"string",
+  };
+  uint8_t *vec = NULL;
+  vec_make(&vec, 1);
+  for (uint64_t i = 0; i < sizeof(strings) / sizeof(strings[0]); ++i)
+  {
+    // need sizeof(...) - 1 because of '\0'
+    vec_append_bytes(&vec, strings[i], sizeof(strings[i]) - 1);
+    vec_append_byte(&vec, ' ');
+  }
+  printf("%.*s\n", (int)VEC_SIZE(vec), vec);
+
+  vec_free(&vec);
+  return 0;
+}