From b6e93a033aa46cd8349964ae8a60d1d411fa49fe Mon Sep 17 00:00:00 2001
From: Aryadev Chavali <aryadev@aryadevchavali.com>
Date: Sun, 11 Aug 2024 22:44:19 +0100
Subject: Implementing a vector using memory tricks, TBC
---
impls/vec.c | 104 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 104 insertions(+)
create mode 100644 impls/vec.c
(limited to 'impls')
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;
+}
--
cgit v1.2.3-13-gbd6f