util: New BFS_FLEX_SIZEOF() macro for more precise flexible array allocations

See http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_282.htm for all
the fun behind this.

4 files changed, 28 insertions, 4 deletions

diff --git a/bftw.c b/bftw.c
index dc04ce0..0e541c6 100644
--- a/bftw.c
+++ b/bftw.c
@@ -300,7 +300,7 @@ static size_t bftw_child_nameoff(const struct bftw_file *parent) {
 /** Create a new bftw_file. */
 static struct bftw_file *bftw_file_new(struct bftw_cache *cache, struct bftw_file *parent, const char *name) {
 	size_t namelen = strlen(name);
-	size_t size = sizeof(struct bftw_file) + namelen + 1;
+	size_t size = BFS_FLEX_SIZEOF(struct bftw_file, name, namelen + 1);
 
 	struct bftw_file *file = malloc(size);
 	if (!file) {
diff --git a/dstring.c b/dstring.c
index d370598..bfcf9bd 100644
--- a/dstring.c
+++ b/dstring.c
@@ -37,7 +37,7 @@ static struct dstring *dstrheader(const char *dstr) {
 
 /** Get the correct size for a dstring with the given capacity. */
 static size_t dstrsize(size_t capacity) {
-	return sizeof(struct dstring) + capacity + 1;
+	return BFS_FLEX_SIZEOF(struct dstring, data, capacity + 1);
 }
 
 /** Allocate a dstring with the given contents. */
diff --git a/trie.c b/trie.c
index b9adc8c..6489b0c 100644
--- a/trie.c
+++ b/trie.c
@@ -77,6 +77,7 @@
  */
 
 #include "trie.h"
+#include "util.h"
 #include <assert.h>
 #include <limits.h>
 #include <stdbool.h>
@@ -319,7 +320,7 @@ struct trie_leaf *trie_find_prefix(const struct trie *trie, const char *key) {
 
 /** Create a new leaf, holding a copy of the given key. */
 static struct trie_leaf *new_trie_leaf(const void *key, size_t length) {
-	struct trie_leaf *leaf = malloc(sizeof(*leaf) + length);
+	struct trie_leaf *leaf = malloc(BFS_FLEX_SIZEOF(struct trie_leaf, key, length));
 	if (leaf) {
 		leaf->value = NULL;
 		leaf->length = length;
@@ -335,7 +336,7 @@ static size_t trie_node_size(unsigned int size) {
 	// Node size must be a power of two
 	assert((size & (size - 1)) == 0);
 
-	return sizeof(struct trie_node) + size*sizeof(uintptr_t);
+	return BFS_FLEX_SIZEOF(struct trie_node, children, size);
 }
 
 /** Find the offset of the first nibble that differs between two keys. */
diff --git a/util.h b/util.h
index a9bdecf..15e983f 100644
--- a/util.h
+++ b/util.h
@@ -26,6 +26,7 @@
 #include <fnmatch.h>
 #include <regex.h>
 #include <stdbool.h>
+#include <stddef.h>
 #include <sys/types.h>
 
 // Some portability concerns
@@ -91,6 +92,28 @@
 #	define BFS_FORMATTER(fmt, args)
 #endif
 
+// Lower bound on BFS_FLEX_SIZEOF()
+#define BFS_FLEX_LB(type, member, length) (offsetof(type, member) + sizeof(((type *)NULL)->member[0]) * (length))
+
+// Maximum macro for BFS_FLEX_SIZE()
+#define BFS_FLEX_MAX(a, b) ((a) > (b) ? (a) : (b))
+
+/**
+ * Computes the size of a struct containing a flexible array member of the given
+ * length.
+ *
+ * @param type
+ *         The type of the struct containing the flexible array.
+ * @param member
+ *         The name of the flexible array member.
+ * @param length
+ *         The length of the flexible array.
+ */
+#define BFS_FLEX_SIZEOF(type, member, length) \
+	(sizeof(type) <= BFS_FLEX_LB(type, member, 0) \
+		? BFS_FLEX_LB(type, member, length) \
+		: BFS_FLEX_MAX(sizeof(type), BFS_FLEX_LB(type, member, length)))
+
 /**
  * readdir() wrapper that makes error handling cleaner.
  */