Add aligned allocation interface and use it in ZixBTree

4 files changed, 132 insertions, 9 deletions

diff --git a/src/.clang-tidy b/src/.clang-tidy
new file mode 100644
index 0000000..aa4ea77
--- /dev/null
+++ b/src/.clang-tidy
@@ -0,0 +1,17 @@
+Checks: >
+  *,
+  -*-magic-numbers,
+  -*-uppercase-literal-suffix,
+  -altera-struct-pack-align,
+  -bugprone-reserved-identifier,
+  -cert-dcl37-c,
+  -cert-dcl51-cpp,
+  -clang-analyzer-security.insecureAPI.DeprecatedOrUnsafeBufferHandling,
+  -hicpp-multiway-paths-covered,
+  -llvm-header-guard,
+  -llvmlibc-*,
+  -misc-no-recursion,
+  -readability-function-cognitive-complexity,
+WarningsAsErrors: '*'
+HeaderFilterRegex: '.*'
+FormatStyle: file
diff --git a/src/allocator.c b/src/allocator.c
index c998463..bedef47 100644
--- a/src/allocator.c
+++ b/src/allocator.c
@@ -1,7 +1,18 @@
 // Copyright 2011-2021 David Robillard <d@drobilla.net>
 // SPDX-License-Identifier: ISC
 
+#define _POSIX_C_SOURCE 200809L
+
+#include "zix_config.h"
+
 #include "zix/allocator.h"
+#include "zix/attributes.h"
+
+#ifdef _WIN32
+#  define WIN32_LEAN_AND_MEAN 1
+#  include <malloc.h>
+#  include <windows.h>
+#endif
 
 #include <stdlib.h>
 
@@ -39,6 +50,37 @@ zix_default_free(ZixAllocator* const allocator, void* const ptr)
   free(ptr);
 }
 
+ZIX_MALLOC_FUNC
+static void*
+zix_default_aligned_alloc(ZixAllocator* const allocator,
+                          const size_t        alignment,
+                          const size_t        size)
+{
+  (void)allocator;
+
+#if defined(_WIN32)
+  return _aligned_malloc(size, alignment);
+#elif USE_POSIX_MEMALIGN
+  void*     ptr = NULL;
+  const int ret = posix_memalign(&ptr, alignment, size);
+  return ret ? NULL : ptr;
+#else
+#  error No aligned memory allocation available
+#endif
+}
+
+static void
+zix_default_aligned_free(ZixAllocator* const allocator, void* const ptr)
+{
+  (void)allocator;
+
+#if defined(_WIN32)
+  _aligned_free(ptr);
+#else
+  free(ptr);
+#endif
+}
+
 ZixAllocator*
 zix_default_allocator(void)
 {
@@ -47,6 +89,8 @@ zix_default_allocator(void)
     zix_default_calloc,
     zix_default_realloc,
     zix_default_free,
+    zix_default_aligned_alloc,
+    zix_default_aligned_free,
   };
 
   return &default_allocator;
diff --git a/src/btree.c b/src/btree.c
index 869b98a..9bb0904 100644
--- a/src/btree.c
+++ b/src/btree.c
@@ -50,6 +50,7 @@ struct ZixBTreeNodeImpl {
 
 #if ((defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112l) || \
      (defined(__cplusplus) && __cplusplus >= 201103L))
+static_assert(sizeof(ZixBTree) <= ZIX_BTREE_PAGE_SIZE, "");
 static_assert(sizeof(ZixBTreeNode) <= ZIX_BTREE_PAGE_SIZE, "");
 static_assert(sizeof(ZixBTreeNode) >=
                 ZIX_BTREE_PAGE_SIZE - 2u * sizeof(ZixBTreeNode*),
@@ -66,8 +67,8 @@ zix_btree_node_new(ZixAllocator* const allocator, const bool leaf)
          ZIX_BTREE_PAGE_SIZE - 2u * sizeof(ZixBTreeNode*));
 #endif
 
-  ZixBTreeNode* const node =
-    (ZixBTreeNode*)zix_malloc(allocator, sizeof(ZixBTreeNode));
+  ZixBTreeNode* const node = (ZixBTreeNode*)zix_aligned_alloc(
+    allocator, ZIX_BTREE_PAGE_SIZE, ZIX_BTREE_PAGE_SIZE);
 
   if (node) {
     node->is_leaf = leaf;
@@ -91,15 +92,22 @@ zix_btree_new(ZixAllocator* const allocator,
               const ZixComparator cmp,
               const void* const   cmp_data)
 {
+#if !((defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112l) || \
+      (defined(__cplusplus) && __cplusplus >= 201103L))
+  assert(sizeof(ZixBTree) <= ZIX_BTREE_PAGE_SIZE);
+#endif
+
   assert(cmp);
 
-  ZixBTree* const t = (ZixBTree*)zix_malloc(allocator, sizeof(ZixBTree));
+  ZixBTree* const t = (ZixBTree*)zix_aligned_alloc(
+    allocator, ZIX_BTREE_PAGE_SIZE, ZIX_BTREE_PAGE_SIZE);
+
   if (!t) {
     return NULL;
   }
 
   if (!(t->root = zix_btree_node_new(allocator, true))) {
-    zix_free(allocator, t);
+    zix_aligned_free(allocator, t);
     return NULL;
   }
 
@@ -121,7 +129,7 @@ zix_btree_free_children(ZixBTree* const      t,
     for (ZixShort i = 0; i < n->n_vals + 1u; ++i) {
       zix_btree_free_children(
         t, zix_btree_child(n, i), destroy, destroy_user_data);
-      zix_free(t->allocator, zix_btree_child(n, i));
+      zix_aligned_free(t->allocator, zix_btree_child(n, i));
     }
   }
 
@@ -145,8 +153,8 @@ zix_btree_free(ZixBTree* const      t,
 {
   if (t) {
     zix_btree_clear(t, destroy, destroy_user_data);
-    zix_free(t->allocator, t->root);
-    zix_free(t->allocator, t);
+    zix_aligned_free(t->allocator, t->root);
+    zix_aligned_free(t->allocator, t);
   }
 }
 
@@ -618,10 +626,10 @@ zix_btree_merge(ZixBTree* const t, ZixBTreeNode* const n, const unsigned i)
     // Root is now empty, replace it with its only child
     assert(n == t->root);
     t->root = lhs;
-    zix_free(t->allocator, n);
+    zix_aligned_free(t->allocator, n);
   }
 
-  zix_free(t->allocator, rhs);
+  zix_aligned_free(t->allocator, rhs);
   return lhs;
 }
 
diff --git a/src/zix_config.h b/src/zix_config.h
new file mode 100644
index 0000000..832b50f
--- /dev/null
+++ b/src/zix_config.h
@@ -0,0 +1,54 @@
+// Copyright 2021 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+/*
+  Configuration header that defines reasonable defaults at compile time.
+
+  This allows compile-time configuration from the command line (typically via
+  the build system) while still allowing the source to be built without any
+  configuration.  The build system can define ZIX_NO_DEFAULT_CONFIG to disable
+  defaults, in which case it must define things like HAVE_FEATURE to enable
+  features.  The design here ensures that compiler warnings or
+  include-what-you-use will catch any mistakes.
+*/
+
+#ifndef ZIX_CONFIG_H
+#define ZIX_CONFIG_H
+
+#if !defined(ZIX_NO_DEFAULT_CONFIG)
+
+// We need unistd.h to check _POSIX_VERSION
+#  ifndef ZIX_NO_POSIX
+#    ifdef __has_include
+#      if __has_include(<unistd.h>)
+#        include <unistd.h>
+#      endif
+#    elif defined(__unix__)
+#      include <unistd.h>
+#    endif
+#  endif
+
+// POSIX.1-2001: posix_memalign()
+#  ifndef HAVE_POSIX_MEMALIGN
+#    if defined(_POSIX_VERSION) && _POSIX_VERSION >= 200112L
+#      define HAVE_POSIX_MEMALIGN
+#    endif
+#  endif
+
+#endif // !defined(ZIX_NO_DEFAULT_CONFIG)
+
+/*
+  Make corresponding USE_FEATURE defines based on the HAVE_FEATURE defines from
+  above or the command line.  The code checks for these using #if (not #ifdef),
+  so there will be an undefined warning if it checks for an unknown feature,
+  and this header is always required by any code that checks for features, even
+  if the build system defines them all.
+*/
+
+#ifdef HAVE_POSIX_MEMALIGN
+#  define USE_POSIX_MEMALIGN 1
+#else
+#  define USE_POSIX_MEMALIGN 0
+#endif
+
+#endif // ZIX_CONFIG_H