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.

2 files changed, 256 insertions, 44 deletions

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