Fix buffer list not having stable ptrs

Was caused by using a vector that used realloc to grow. That only works
sometimes. Now instead, the buffer list is a chunked linked list, i.e. a
linked list where each element is a fixed size array.

6 files changed, 401 insertions, 49 deletions

diff --git a/Makefile b/Makefile
index 5630d10..63e46e4 100644
--- a/Makefile
+++ b/Makefile
@@ -46,7 +46,8 @@ MAIN_SOURCES = src/main/main.c src/main/cmds.c src/main/bindings.c src/main/sear
 
 TEST_SOURCES = test/assert.c test/buffer.c test/text.c test/utf8.c test/main.c \
 	test/command.c test/keyboard.c test/fake-reactor.c test/allocator.c \
-	test/minibuffer.c test/undo.c test/settings.c test/container.c
+	test/minibuffer.c test/undo.c test/settings.c test/container.c \
+	test/buflist.c
 
 prefix ?= /usr/local
 DESTDIR ?= $(prefix)
diff --git a/src/dged/buffers.c b/src/dged/buffers.c
index f591385..d20be39 100644
--- a/src/dged/buffers.c
+++ b/src/dged/buffers.c
@@ -5,32 +5,60 @@
 #include <stdlib.h>
 #include <string.h>
 
-struct buffer_entry {
-  struct buffer buffer;
-  bool empty;
-};
+static struct buffer_chunk *new_chunk(uint32_t sz) {
+  struct buffer_chunk *chunk = calloc(1, sizeof(struct buffer_chunk));
+  chunk->entries = calloc(sz, sizeof(struct buffer_entry));
+  return chunk;
+}
+
+static bool chunk_empty(const struct buffer_chunk *chunk, uint32_t sz) {
+  for (uint32_t i = 0; i < sz; ++i) {
+    if (chunk->entries[i].occupied) {
+      return false;
+    }
+  }
+
+  return true;
+}
+
+static void free_chunk(struct buffer_chunk *chunk) {
+  free(chunk->entries);
+  chunk->entries = NULL;
+  chunk->next = NULL;
+  free(chunk);
+}
 
 void buffers_init(struct buffers *buffers, uint32_t initial_capacity) {
-  VEC_INIT(&buffers->buffers, initial_capacity);
+  buffers->chunk_size = initial_capacity;
+  buffers->head = new_chunk(buffers->chunk_size);
   VEC_INIT(&buffers->add_hooks, 32);
   VEC_INIT(&buffers->remove_hooks, 32);
 }
 
 struct buffer *buffers_add(struct buffers *buffers, struct buffer buffer) {
   struct buffer_entry *slot = NULL;
-  VEC_FOR_EACH(&buffers->buffers, struct buffer_entry * e) {
-    if (e->empty) {
-      slot = e;
+  struct buffer_chunk *chunk = buffers->head, *prev_chunk = buffers->head;
+  while (chunk != NULL) {
+    for (uint32_t i = 0; i < buffers->chunk_size; ++i) {
+      if (!chunk->entries[i].occupied) {
+        slot = &chunk->entries[i];
+        goto found;
+      }
     }
-  }
 
-  if (slot == NULL) {
-    VEC_APPEND(&buffers->buffers, struct buffer_entry * new);
-    slot = new;
+    prev_chunk = chunk;
+    chunk = chunk->next;
   }
 
+  chunk = new_chunk(buffers->chunk_size);
+  prev_chunk->next = chunk;
+
+  slot = &chunk->entries[0];
+
+found:
+
   slot->buffer = buffer;
-  slot->empty = false;
+  slot->occupied = true;
 
   VEC_FOR_EACH(&buffers->add_hooks, struct buffers_hook * hook) {
     hook->callback(&slot->buffer, hook->userdata);
@@ -60,10 +88,22 @@ uint32_t buffers_add_remove_hook(struct buffers *buffers,
 }
 
 struct buffer *buffers_find(struct buffers *buffers, const char *name) {
-  VEC_FOR_EACH(&buffers->buffers, struct buffer_entry * e) {
-    if (!e->empty && strcmp(name, e->buffer.name) == 0) {
-      return &e->buffer;
+  struct buffer_chunk *chunk = buffers->head;
+  size_t namelen = strlen(name);
+  while (chunk != NULL) {
+    for (uint32_t i = 0; i < buffers->chunk_size; ++i) {
+      if (!chunk->entries[i].occupied) {
+        continue;
+      }
+
+      struct buffer *b = &chunk->entries[i].buffer;
+      size_t bnamelen = b->name != NULL ? strlen(b->name) : 0;
+      if (namelen == bnamelen && memcmp(name, b->name, bnamelen) == 0) {
+        return b;
+      }
     }
+
+    chunk = chunk->next;
   }
 
   return NULL;
@@ -71,65 +111,118 @@ struct buffer *buffers_find(struct buffers *buffers, const char *name) {
 
 struct buffer *buffers_find_by_filename(struct buffers *buffers,
                                         const char *path) {
-  VEC_FOR_EACH(&buffers->buffers, struct buffer_entry * e) {
-    if (!e->empty && e->buffer.filename != NULL &&
-        strcmp(path, e->buffer.filename) == 0) {
-      return &e->buffer;
+  struct buffer_chunk *chunk = buffers->head;
+  size_t pathlen = strlen(path);
+  while (chunk != NULL) {
+    for (uint32_t i = 0; i < buffers->chunk_size; ++i) {
+      if (!chunk->entries[i].occupied) {
+        continue;
+      }
+
+      struct buffer *b = &chunk->entries[i].buffer;
+      if (b->filename == NULL) {
+        continue;
+      }
+
+      size_t bnamelen = strlen(b->filename);
+      if (bnamelen == pathlen && memcmp(path, b->filename, bnamelen) == 0) {
+        return b;
+      }
     }
+
+    chunk = chunk->next;
   }
 
   return NULL;
 }
 
 bool buffers_remove(struct buffers *buffers, const char *name) {
+  struct buffer_chunk *chunk = buffers->head, *prev_chunk = buffers->head;
   struct buffer_entry *buf_entry = NULL;
-  VEC_FOR_EACH(&buffers->buffers, struct buffer_entry * e) {
-    if (!e->empty && strcmp(name, e->buffer.name) == 0) {
-      buf_entry = e;
+  size_t namelen = strlen(name);
+  while (chunk != NULL) {
+    for (uint32_t i = 0; i < buffers->chunk_size; ++i) {
+      struct buffer *b = &chunk->entries[i].buffer;
+      size_t bnamelen = strlen(b->name);
+      if (chunk->entries[i].occupied && namelen == bnamelen &&
+          memcmp(name, b->name, bnamelen) == 0) {
+        buf_entry = &chunk->entries[i];
+        goto found;
+      }
     }
-  }
 
-  if (buf_entry == NULL) {
-    return false;
+    prev_chunk = chunk;
+    chunk = chunk->next;
   }
 
+  return false;
+
+found:
+
   VEC_FOR_EACH(&buffers->remove_hooks, struct buffers_hook * hook) {
     hook->callback(&buf_entry->buffer, hook->userdata);
   }
 
-  buf_entry->empty = true;
+  buf_entry->occupied = false;
   buffer_destroy(&buf_entry->buffer);
+
+  if (chunk_empty(chunk, buffers->chunk_size) && chunk != buffers->head) {
+    prev_chunk->next = chunk->next;
+    free_chunk(chunk);
+  }
   return true;
 }
 
 void buffers_for_each(struct buffers *buffers, buffers_hook_cb callback,
                       void *userdata) {
-  VEC_FOR_EACH(&buffers->buffers, struct buffer_entry * e) {
-    if (!e->empty) {
-      callback(&e->buffer, userdata);
+  struct buffer_chunk *chunk = buffers->head;
+  while (chunk != NULL) {
+    for (uint32_t i = 0; i < buffers->chunk_size; ++i) {
+      if (chunk->entries[i].occupied) {
+        callback(&chunk->entries[i].buffer, userdata);
+      }
     }
+
+    chunk = chunk->next;
   }
 }
 
 uint32_t buffers_num_buffers(struct buffers *buffers) {
-  return VEC_SIZE(&buffers->buffers);
+  uint32_t total_buffers = 0;
+  struct buffer_chunk *chunk = buffers->head;
+  while (chunk != NULL) {
+    for (uint32_t i = 0; i < buffers->chunk_size; ++i) {
+      if (chunk->entries[i].occupied) {
+        ++total_buffers;
+      }
+    }
+
+    chunk = chunk->next;
+  }
+
+  return total_buffers;
 }
 
 struct buffer *buffers_first(struct buffers *buffers) {
-  return buffers_num_buffers(buffers) > 0
-             ? &VEC_ENTRIES(&buffers->buffers)[0].buffer
-             : NULL;
+  return buffers_num_buffers(buffers) > 0 ? &buffers->head->entries[0].buffer
+                                          : NULL;
 }
 
 void buffers_destroy(struct buffers *buffers) {
-  VEC_FOR_EACH(&buffers->buffers, struct buffer_entry * e) {
-    if (!e->empty) {
-      buffer_destroy(&e->buffer);
-      e->empty = true;
+  struct buffer_chunk *chunk = buffers->head;
+  while (chunk != NULL) {
+    for (uint32_t i = 0; i < buffers->chunk_size; ++i) {
+      if (chunk->entries[i].occupied) {
+        buffer_destroy(&chunk->entries[i].buffer);
+        chunk->entries[i].occupied = false;
+      }
     }
+
+    struct buffer_chunk *old = chunk;
+    chunk = chunk->next;
+    free_chunk(old);
   }
 
-  VEC_DESTROY(&buffers->buffers);
   VEC_DESTROY(&buffers->add_hooks);
   VEC_DESTROY(&buffers->remove_hooks);
 }
diff --git a/src/dged/buffers.h b/src/dged/buffers.h
index d521a78..e1bdd8a 100644
--- a/src/dged/buffers.h
+++ b/src/dged/buffers.h
@@ -1,10 +1,12 @@
+#ifndef _BUFFERS_H
+#define _BUFFERS_H
+
+#include "buffer.h"
 #include "vec.h"
 
 #include <stdbool.h>
 #include <stdint.h>
 
-struct buffer;
-
 typedef void (*buffers_hook_cb)(struct buffer *buffer, void *userdata);
 
 struct buffers_hook {
@@ -12,32 +14,149 @@ struct buffers_hook {
   void *userdata;
 };
 
-struct buffer_entry;
+/**
+ * An entry in a buffer list.
+ */
+struct buffer_entry {
+  /** Storage for the actual buffer. */
+  struct buffer buffer;
+
+  /** False if this entry is free to use. */
+  bool occupied;
+};
 
+struct buffer_chunk {
+  struct buffer_entry *entries;
+  struct buffer_chunk *next;
+};
+
+/**
+ * A buffer list.
+ */
 struct buffers {
-  VEC(struct buffer_entry) buffers;
+  struct buffer_chunk *head;
+  uint32_t chunk_size;
   VEC(struct buffers_hook) add_hooks;
   VEC(struct buffers_hook) remove_hooks;
 };
 
+/**
+ * Initialize a buffer list.
+ *
+ * @param [in] buffers The buffer list to initialize.
+ * @param [in] initial_capacity The initial number of buffers
+               that this buffer list should be able to hold.
+ */
 void buffers_init(struct buffers *buffers, uint32_t initial_capacity);
 
+/**
+ * Destroy a buffer list.
+ *
+ * This will free any memory associated with the list and all
+ * associated buffer pointers will be invalid after this.
+ *
+ * @param [in] buffers The buffer list to destroy.
+ */
+void buffers_destroy(struct buffers *buffers);
+
+/**
+ * Add a buffer to the list.
+ *
+ * @param [in] buffers The buffer list to add to.
+ * @param [in] buffer The buffer to add to the list.
+ *
+ * @returns A stable pointer to the buffer in the buffer list.
+ *          This pointer do not change when the buffer list resizes.
+ */
 struct buffer *buffers_add(struct buffers *buffers, struct buffer buffer);
+
+/**
+ * Find a buffer using its name.
+ *
+ * @param [in] buffers The buffer list to search in.
+ * @param [in] name The buffer name to search from.
+ *
+ * @returns A stable pointer to the buffer in the buffer list.
+ *          This pointer do not change when the buffer list resizes.
+ *          If not found, NULL is returned.
+ */
 struct buffer *buffers_find(struct buffers *buffers, const char *name);
+
+/**
+ * Find a buffer using its filename.
+ *
+ * @param [in] buffers The buffer list to search in.
+ * @param [in] name The buffer filename to search from.
+ *
+ * @returns A stable pointer to the buffer in the buffer list.
+ *          This pointer do not change when the buffer list resizes.
+ *          If not found, NULL is returned.
+ */
 struct buffer *buffers_find_by_filename(struct buffers *buffers,
                                         const char *path);
 
+/**
+ * Remove a buffer from the buffer list.
+ *
+ * @param [in] buffers The buffer list to remove from.
+ * @param [in] name The buffer name to remove.
+ *
+ * @returns True if the buffer was found and removed.
+ */
 bool buffers_remove(struct buffers *buffers, const char *name);
 
+/**
+ * Add a hook for when buffers are added to the buffer list.
+ *
+ * @param [in] buffers The buffer list to add hook to.
+ * @param [in] callback The callback to call when a buffer is added.
+ * @param [in] userdata Pointer to userdata that is passed unmodified to the
+ * callback.
+ *
+ * @returns A handle to the hook.
+ */
 uint32_t buffers_add_add_hook(struct buffers *buffers, buffers_hook_cb callback,
                               void *userdata);
+
+/**
+ * Add a hook for when buffers are removed from the buffer list.
+ *
+ * @param [in] buffers The buffer list to add hook to.
+ * @param [in] callback The callback to call when a buffer is removed.
+ * @param [in] userdata Pointer to userdata that is passed unmodified to the
+ * callback.
+ *
+ * @returns A handle to the hook.
+ */
 uint32_t buffers_add_remove_hook(struct buffers *buffers,
                                  buffers_hook_cb callback, void *userdata);
 
+/**
+ * Iterate the buffers in a buffer list.
+ *
+ * @param [in] buffers The buffer list to iterate.
+ * @param [in] callback The callback to call for each buffer in `buffers`.
+ * @param [in] userdata Pointer to userdata that is passed unmodified to the
+ * callback.
+ */
 void buffers_for_each(struct buffers *buffers, buffers_hook_cb callback,
                       void *userdata);
 
+/**
+ * Number of buffers in the buffer list.
+ *
+ * @param [in] buffers The buffer list to iterate.
+ * @returns The number of buffers in the buffer list.
+ */
 uint32_t buffers_num_buffers(struct buffers *buffers);
+
+/**
+ * Get the first buffer in the buffer list.
+ *
+ * @param [in] buffers The buffer list.
+ * @returns A stable pointer to the first buffer
+            in `buffers`.
+ */
 struct buffer *buffers_first(struct buffers *buffers);
 
-void buffers_destroy(struct buffers *buffers);
+#endif
diff --git a/test/buflist.c b/test/buflist.c
new file mode 100644
index 0000000..b0bc241
--- /dev/null
+++ b/test/buflist.c
@@ -0,0 +1,135 @@
+#include "assert.h"
+#include "test.h"
+
+#include "dged/buffer.h"
+#include "dged/buffers.h"
+
+struct hook_call_args {
+  struct buffer *buffer[64];
+  size_t call_count;
+};
+
+static void add_remove_hook(struct buffer *buffer, void *userdata) {
+  struct hook_call_args *args = (struct hook_call_args *)userdata;
+
+  if (args->call_count < 64) {
+    args->buffer[args->call_count] = buffer;
+  }
+
+  ++args->call_count;
+}
+
+static void add(void) {
+  struct buffers buflist;
+  buffers_init(&buflist, 16);
+
+  ASSERT(buffers_num_buffers(&buflist) == 0,
+         "Expected buffer list to be empty upon creation.");
+
+  struct buffer b1 = buffer_create("b1");
+  struct buffer b2 = buffer_create("b2");
+
+  struct hook_call_args hook_args = {0};
+  buffers_add_add_hook(&buflist, add_remove_hook, &hook_args);
+
+  struct buffer *bp1 = buffers_add(&buflist, b1);
+  struct buffer *bp2 = buffers_add(&buflist, b2);
+
+  ASSERT(hook_args.call_count == 2,
+         "Expected add hook to be called two times when adding two buffers.");
+  ASSERT(hook_args.buffer[0] == bp1,
+         "Expected add hook to be called with first buffer first.");
+  ASSERT(hook_args.buffer[1] == bp2,
+         "Expected add hook to be called with second buffer second.");
+
+  buffers_destroy(&buflist);
+}
+
+static void find(void) {
+  struct buffers buflist;
+  buffers_init(&buflist, 16);
+
+  struct buffer b1 = buffer_create("b1");
+  struct buffer b2 = buffer_create("b2");
+  struct buffer b3 = buffer_create("b3");
+  buffer_set_filename(&b3, "b3.txt");
+
+  struct buffer *bp1 = buffers_add(&buflist, b1);
+  struct buffer *bp2 = buffers_add(&buflist, b2);
+  struct buffer *bp3 = buffers_add(&buflist, b3);
+
+  struct buffer *found1 = buffers_find(&buflist, "b1");
+  ASSERT(found1 == bp1, "Expected to find equally named buffer");
+
+  struct buffer *found2 = buffers_find(&buflist, "b2");
+  ASSERT(found2 == bp2, "Expected to find equally named buffer");
+
+  struct buffer *ne = buffers_find(&buflist, "nonsense");
+  ASSERT(ne == NULL, "Expected to not find non-existent buffer");
+
+  struct buffer *found3 = buffers_find_by_filename(&buflist, "b3.txt");
+  ASSERT(found3 == bp3,
+         "Expected to be able to find buffer 3 by filename since it has one.");
+
+  buffers_destroy(&buflist);
+}
+
+static void remove_buffer() {
+  struct buffers buflist;
+  buffers_init(&buflist, 16);
+
+  struct buffer b1 = buffer_create("b1");
+  struct buffer b2 = buffer_create("b2");
+
+  buffers_add(&buflist, b1);
+  struct buffer *bp2 = buffers_add(&buflist, b2);
+
+  struct hook_call_args hook_args = {0};
+  buffers_add_remove_hook(&buflist, add_remove_hook, &hook_args);
+
+  bool removed = buffers_remove(&buflist, "b2");
+  ASSERT(removed, "Expected existing buffer to have been removed");
+  struct buffer *ne = buffers_find(&buflist, "b2");
+  ASSERT(ne == NULL, "Expected to not find buffer after removal");
+  ASSERT(buffers_num_buffers(&buflist) == 1,
+         "Expected number of buffers to be 1 after removal.");
+
+  ASSERT(hook_args.call_count == 1, "Expected remove hook to be called once.");
+  ASSERT(
+      hook_args.buffer[0] == bp2,
+      "Expected remove hook to be called with the removed buffer as argument.");
+
+  buffers_destroy(&buflist);
+}
+
+static void grow_list() {
+  struct buffers buflist;
+  buffers_init(&buflist, 2);
+
+  struct buffer b1 = buffer_create("b1");
+  struct buffer b2 = buffer_create("b2");
+  struct buffer b3 = buffer_create("b3");
+  struct buffer b4 = buffer_create("b4");
+
+  struct buffer *bp1 = buffers_add(&buflist, b1);
+  buffers_add(&buflist, b2);
+  buffers_add(&buflist, b3);
+  struct buffer *bp4 = buffers_add(&buflist, b4);
+  ASSERT(buffers_num_buffers(&buflist) == 4,
+         "Expected buffer count to be 4 after adding 4 buffers.");
+
+  struct buffer *found = buffers_find(&buflist, "b1");
+  ASSERT(found == bp1, "Expected pointer to remain stable after resize.");
+
+  found = buffers_find(&buflist, "b4");
+  ASSERT(found == bp4, "Expected to be able to find last added buffer.");
+
+  buffers_destroy(&buflist);
+}
+
+void run_buflist_tests(void) {
+  run_test(add);
+  run_test(find);
+  run_test(remove_buffer);
+  run_test(grow_list);
+}
diff --git a/test/main.c b/test/main.c
index 29e031f..f8e1eca 100644
--- a/test/main.c
+++ b/test/main.c
@@ -29,9 +29,12 @@ int main(void) {
   printf("\n⏪ \x1b[1;36mRunning undo tests...\x1b[0m\n");
   run_undo_tests();
 
-  printf("\n🕴️ \x1b[1;36mRunning buffer tests...\x1b[0m\n");
+  printf("\n🕴️  \x1b[1;36mRunning buffer tests...\x1b[0m\n");
   run_buffer_tests();
 
+  printf("\n📋 \x1b[1;36mRunning buffer list tests...\x1b[0m\n");
+  run_buflist_tests();
+
   printf("\n🐒 \x1b[1;36mRunning command tests...\x1b[0m\n");
   run_command_tests();
 
@@ -44,14 +47,14 @@ int main(void) {
   printf("\n🐜 \x1b[1;36mRunning minibuffer tests...\x1b[0m\n");
   run_minibuffer_tests();
 
-  printf("\n 📓 \x1b[1;36mRunning settings tests...\x1b[0m\n");
+  printf("\n📓 \x1b[1;36mRunning settings tests...\x1b[0m\n");
   run_settings_tests();
 
-  printf("\n 🎁 \x1b[1;36mRunning container tests...\x1b[0m\n");
+  printf("\n🎁 \x1b[1;36mRunning container tests...\x1b[0m\n");
   run_container_tests();
 
 #if defined(LSP_ENABLED)
-  printf("\n 📃 \x1b[1;36mRunning JSON tests...\x1b[0m\n");
+  printf("\n📃 \x1b[1;36mRunning JSON tests...\x1b[0m\n");
   run_json_tests();
 #endif
 
diff --git a/test/test.h b/test/test.h
index 5b9cafc..d099cc3 100644
--- a/test/test.h
+++ b/test/test.h
@@ -10,6 +10,7 @@
   printf("\033[32mok!\033[0m\n");
 
 void run_buffer_tests(void);
+void run_buflist_tests(void);
 void run_utf8_tests(void);
 void run_text_tests(void);
 void run_undo_tests(void);