[WIP] Add ZixRankTreerank-tree

13 files changed, 706 insertions, 10 deletions

diff --git a/NEWS b/NEWS
index 9970fcc..1e77117 100644
--- a/NEWS
+++ b/NEWS
@@ -1,9 +1,10 @@
-zix (0.6.3) unstable; urgency=medium
+zix (0.7.0) unstable; urgency=medium
 
+  * Add ZixRankTree
   * Reduce empty BTree memory requirements
   * Use getenv() instead of environ to avoid issues on FreeBSD
 
- -- David Robillard <d@drobilla.net>  Thu, 29 May 2025 15:22:01 +0000
+ -- David Robillard <d@drobilla.net>  Fri, 30 May 2025 17:51:39 +0000
 
 zix (0.6.2) stable; urgency=medium
 
diff --git a/doc/Doxyfile.in b/doc/Doxyfile.in
index 0c60cab..c157b81 100644
--- a/doc/Doxyfile.in
+++ b/doc/Doxyfile.in
@@ -1,4 +1,4 @@
-# Copyright 2021-2022 David Robillard <d@drobilla.net>
+# Copyright 2021-2025 David Robillard <d@drobilla.net>
 # SPDX-License-Identifier: 0BSD OR ISC
 
 PROJECT_NAME           = Zix
@@ -60,6 +60,7 @@ INPUT                  = @ZIX_SRCDIR@/include/zix/zix.h \
                          \
                          @ZIX_SRCDIR@/include/zix/btree.h \
                          @ZIX_SRCDIR@/include/zix/hash.h \
+                         @ZIX_SRCDIR@/include/zix/rank_tree.h \
                          @ZIX_SRCDIR@/include/zix/ring.h \
                          @ZIX_SRCDIR@/include/zix/tree.h \
                          \
diff --git a/doc/conf.py.in b/doc/conf.py.in
index a7c254d..e4153ce 100644
--- a/doc/conf.py.in
+++ b/doc/conf.py.in
@@ -35,6 +35,7 @@ _opaque = [
     "ZixBTreeNodeImpl",
     "ZixHash",
     "ZixHashImpl",
+    "ZixRankTreeImpl",
     "ZixRing",
     "ZixRingImpl",
     "ZixSem",
@@ -52,6 +53,7 @@ _opaque = [
     "uint32_t",
     "uint64_t",
     "uint8_t",
+    "uintptr_t",
 ]
 
 _c_nitpick_ignore = map(lambda x: ("c:identifier", x), _opaque)
diff --git a/doc/xml/meson.build b/doc/xml/meson.build
index f5a6b1d..c9f4a27 100644
--- a/doc/xml/meson.build
+++ b/doc/xml/meson.build
@@ -1,4 +1,4 @@
-# Copyright 2021-2023 David Robillard <d@drobilla.net>
+# Copyright 2021-2025 David Robillard <d@drobilla.net>
 # SPDX-License-Identifier: 0BSD OR ISC
 
 config = configuration_data()
@@ -60,6 +60,10 @@ doxygen_xml = custom_target(
     'group__zix__path__decomposition.xml',
     'group__zix__path__lexical.xml',
     'group__zix__path__queries.xml',
+    'group__zix__rank__tree.xml',
+    'group__zix__rank__tree__access.xml',
+    'group__zix__rank__tree__modification.xml',
+    'group__zix__rank__tree__setup.xml',
     'group__zix__ring.xml',
     'group__zix__ring__read.xml',
     'group__zix__ring__setup.xml',
@@ -79,6 +83,7 @@ doxygen_xml = custom_target(
     'group__zix__utilities.xml',
     'hash_8h.xml',
     'path_8h.xml',
+    'rank__tree_8h.xml',
     'ring_8h.xml',
     'sem_8h.xml',
     'status_8h.xml',
diff --git a/include/zix/rank_tree.h b/include/zix/rank_tree.h
new file mode 100644
index 0000000..b0abf63
--- /dev/null
+++ b/include/zix/rank_tree.h
@@ -0,0 +1,164 @@
+// Copyright 2011-2025 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#ifndef ZIX_RANK_TREE_H
+#define ZIX_RANK_TREE_H
+
+#include <zix/allocator.h>
+#include <zix/attributes.h>
+#include <zix/status.h>
+
+#include <stddef.h>
+#include <stdint.h>
+
+ZIX_BEGIN_DECLS
+
+/**
+   @defgroup zix_rank_tree RankTree
+   @ingroup zix_data_structures
+   @{
+*/
+
+/**
+   @defgroup zix_rank_tree_types Types
+   @{
+*/
+
+/**
+   A "rank tree", an efficient B-tree with a vector-like interface.
+
+   This is internally structured like a B-tree, but rather than storing ordered
+   elements, presents a simple vector-like interface where elements can be
+   retrieved by "rank" (0-based index). This scales more gracefully than an
+   array-based vector (by avoiding relocation), and is packed more efficiently
+   than a generic B-tree (the tree is always left-complete and nodes are filled
+   entirely with either child pointers or values with zero overhead).
+
+   The tree stores opaque pointer-sized values, and is structured so that
+   retrieving an element by index is as fast as possible: nearly branchless,
+   with only a few memory accesses.
+*/
+typedef struct ZixRankTreeImpl ZixRankTree;
+
+/// Function to destroy a RankTree element
+typedef void (*ZixRankTreeDestroyFunc)(uintptr_t             value,
+                                       void* ZIX_UNSPECIFIED user_data);
+
+/**
+   @}
+   @defgroup zix_rank_tree_setup Setup
+   @{
+*/
+
+/**
+   Create a new empty RankTree.
+
+   This allocates the only the returned structure, no nodes are allocated until
+   elements are inserted.
+
+   @param allocator Allocator which is used for the returned structure, and
+   later used to allocate tree nodes.
+*/
+ZIX_API ZIX_NODISCARD ZixRankTree* ZIX_ALLOCATED
+zix_rank_tree_new(ZixAllocator* ZIX_NULLABLE allocator);
+
+/**
+   Free `t` and all the nodes it contains.
+
+   @param t The tree to free.
+
+   @param destroy Function to call once for every element in the tree.  This
+   can be used to free elements if they are dynamically allocated.
+
+   @param destroy_data Opaque user data pointer to pass to `destroy`.
+*/
+ZIX_API void
+zix_rank_tree_free(ZixRankTree* ZIX_NULLABLE           t,
+                   ZixRankTreeDestroyFunc ZIX_NULLABLE destroy,
+                   void* ZIX_NULLABLE                  destroy_data);
+
+/**
+   Clear everything from `t`, leaving it empty.
+
+   @param t The tree to clear.
+
+   @param destroy Function called exactly once for every element in the tree,
+   just before that element is removed from the tree.
+
+   @param destroy_data Opaque user data pointer to pass to `destroy`.
+*/
+ZIX_API void
+zix_rank_tree_clear(ZixRankTree* ZIX_NONNULL            t,
+                    ZixRankTreeDestroyFunc ZIX_NULLABLE destroy,
+                    void* ZIX_NULLABLE                  destroy_data);
+
+/**
+   Return the number of elements in `t`.
+
+   The returned size is by definition 1 greater than the greatest stored rank.
+*/
+ZIX_PURE_API size_t
+zix_rank_tree_size(const ZixRankTree* ZIX_NONNULL t);
+
+/**
+   Return the height of `t`.
+
+   A tree with a single root note (that is, a single level) has a height of
+   zero. The height is at most 7 on 64-bit systems, and 3 on 32-bit systems.
+*/
+ZIX_API uint8_t
+zix_rank_tree_height(const ZixRankTree* ZIX_NONNULL t);
+
+/**
+   @}
+   @defgroup zix_rank_tree_access Access
+   @{
+*/
+
+/**
+   Return an element of `t` by rank/index.
+
+   Note that this function returns zero if `rank` is out of range, so if this
+   isn't a sentinel value for the values stored in the tree, the caller is
+   responsible for first checking that the rank is valid.
+
+   @param t The tree to retrieve the element from.
+   @param rank The 0-based rank of the element.
+   @return The element at the given index, or zero if `rank` is out of range.
+*/
+ZIX_API uintptr_t
+zix_rank_tree_at(const ZixRankTree* ZIX_NONNULL t, size_t rank);
+
+/**
+   @}
+   @defgroup zix_rank_tree_modification Modification
+   @{
+*/
+
+/**
+   Append the element `e` to `t`.
+
+   @param t Tree to append a new element to.
+   @param e Opaque value of new element to store.
+   @return #ZIX_STATUS_SUCCESS, or #ZIX_STATUS_NO_MEM.
+*/
+ZIX_API ZixStatus
+zix_rank_tree_push(ZixRankTree* ZIX_NONNULL t, uintptr_t e);
+
+/**
+   Remove the element `e` from `t`.
+
+   @param t Tree to remove the last element from.
+   @return #ZIX_STATUS_SUCCESS, or #ZIX_STATUS_NOT_FOUND if `t` is empty.
+*/
+ZIX_API ZixStatus
+zix_rank_tree_pop(ZixRankTree* ZIX_NONNULL t);
+
+/**
+   @}
+   @}
+*/
+
+ZIX_END_DECLS
+
+#endif /* ZIX_RANK_TREE_H */
diff --git a/include/zix/zix.h b/include/zix/zix.h
index ceaadc0..65a3575 100644
--- a/include/zix/zix.h
+++ b/include/zix/zix.h
@@ -1,4 +1,4 @@
-// Copyright 2016-2024 David Robillard <d@drobilla.net>
+// Copyright 2016-2025 David Robillard <d@drobilla.net>
 // SPDX-License-Identifier: ISC
 
 #ifndef ZIX_ZIX_H
@@ -45,6 +45,7 @@
 
 #include <zix/btree.h>
 #include <zix/hash.h>
+#include <zix/rank_tree.h>
 #include <zix/ring.h>
 #include <zix/tree.h>
 
diff --git a/meson.build b/meson.build
index 7a8d68c..f6a4740 100644
--- a/meson.build
+++ b/meson.build
@@ -12,7 +12,7 @@ project(
   ],
   license: 'ISC',
   meson_version: '>= 0.56.0',
-  version: '0.6.3',
+  version: '0.7.0',
 )
 
 zix_src_root = meson.current_source_dir()
@@ -38,6 +38,7 @@ if cc.get_id() in ['clang', 'emscripten']
       '-Wno-declaration-after-statement',
       '-Wno-implicit-fallthrough', # Really for clang < 12
       '-Wno-padded',
+      '-Wno-pre-c11-compat',
       '-Wno-switch-default',
       '-Wno-unsafe-buffer-usage',
       '-Wno-unsafe-buffer-usage-in-libc-call',
@@ -337,6 +338,7 @@ c_headers = files(
   'include/zix/filesystem.h',
   'include/zix/hash.h',
   'include/zix/path.h',
+  'include/zix/rank_tree.h',
   'include/zix/ring.h',
   'include/zix/sem.h',
   'include/zix/status.h',
@@ -355,6 +357,7 @@ sources = files(
   'src/filesystem.c',
   'src/hash.c',
   'src/path.c',
+  'src/rank_tree.c',
   'src/ring.c',
   'src/status.c',
   'src/string_view.c',
@@ -435,7 +438,7 @@ libzix = library(
   versioned_name,
   sources,
   c_args: c_suppressions + library_c_args,
-  darwin_versions: ['0.6.0', meson.project_version()],
+  darwin_versions: ['0.7.0', meson.project_version()],
   dependencies: dependencies,
   gnu_symbol_visibility: 'hidden',
   implicit_include_directories: false,
diff --git a/src/.clang-tidy b/src/.clang-tidy
index b3b1960..d8c39bd 100644
--- a/src/.clang-tidy
+++ b/src/.clang-tidy
@@ -1,7 +1,8 @@
-# Copyright 2021-2022 David Robillard <d@drobilla.net>
+# Copyright 2021-2025 David Robillard <d@drobilla.net>
 # SPDX-License-Identifier: 0BSD OR ISC
 
 Checks: >
+  -*-macro-to-enum,
   -*-magic-numbers,
   -bugprone-easily-swappable-parameters,
   -bugprone-multi-level-implicit-pointer-conversion,
diff --git a/src/rank_tree.c b/src/rank_tree.c
new file mode 100644
index 0000000..20dea49
--- /dev/null
+++ b/src/rank_tree.c
@@ -0,0 +1,326 @@
+// Copyright 2011-2025 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#include <zix/rank_tree.h>
+
+#include <zix/allocator.h>
+#include <zix/status.h>
+
+#include <assert.h>
+#include <stdint.h>
+#include <string.h>
+
+#define ZIX_RANK_TREE_PAGE_SIZE 4096U
+#define ZIX_RANK_TREE_FANOUT \
+  ((uint16_t)(ZIX_RANK_TREE_PAGE_SIZE / sizeof(void*)))
+
+#if UINTPTR_MAX > UINT32_MAX // 64-bit
+#  define ZIX_RANK_TREE_INDEX_BITS 9U
+#  define ZIX_RANK_TREE_INDEX_MASK 0x1FFU
+#  define ZIX_RANK_TREE_MAX_HEIGHT 7U
+#  define ZIX_RANK_TREE_MAX_LEVELS 8U
+#else // 32-bit
+#  define ZIX_RANK_TREE_INDEX_BITS 10U
+#  define ZIX_RANK_TREE_INDEX_MASK 0x3FFU
+#  define ZIX_RANK_TREE_MAX_HEIGHT 3U
+#  define ZIX_RANK_TREE_MAX_LEVELS 4U
+#endif
+
+typedef uint16_t ChildIndex;
+typedef uint8_t  TreeHeight;
+
+typedef union ZixRankTreeNodeImpl ZixRankTreeNode;
+
+typedef struct {
+  ChildIndex indices[ZIX_RANK_TREE_MAX_LEVELS];
+} ZixRankTreePath;
+
+struct ZixRankTreeImpl {
+  ZixAllocator*    allocator; ///< Allocator for this structure and nodes
+  ZixRankTreeNode* root;      ///< Pointer to root node
+  size_t           size;      ///< Total number of elements in tree
+  TreeHeight       height;    ///< Height where 0 has one node (the root)
+};
+
+union ZixRankTreeNodeImpl {
+  uintptr_t        vals[ZIX_RANK_TREE_FANOUT];     ///< Elements (leaf)
+  ZixRankTreeNode* children[ZIX_RANK_TREE_FANOUT]; ///< Children (internal)
+};
+
+#if ((defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112L) || \
+     (defined(__cplusplus) && __cplusplus >= 201103L))
+static_assert(sizeof(ZixRankTree) <= ZIX_RANK_TREE_PAGE_SIZE, "");
+static_assert(sizeof(ZixRankTreeNode) == ZIX_RANK_TREE_PAGE_SIZE, "");
+#endif
+
+static ZixRankTreePath
+zix_rank_tree_parse_rank(const size_t rank)
+{
+  ZixRankTreePath path      = {{0U}};
+  size_t          remaining = rank;
+  for (unsigned i = 0U; i < ZIX_RANK_TREE_MAX_LEVELS; ++i) {
+    path.indices[ZIX_RANK_TREE_MAX_HEIGHT - i] =
+      remaining & ZIX_RANK_TREE_INDEX_MASK;
+    remaining = remaining >> ZIX_RANK_TREE_INDEX_BITS;
+  }
+
+  return path;
+}
+
+static ZixRankTreeNode*
+zix_rank_tree_node_new(ZixAllocator* const allocator)
+{
+  ZixRankTreeNode* const node = (ZixRankTreeNode*)zix_aligned_alloc(
+    allocator, ZIX_RANK_TREE_PAGE_SIZE, ZIX_RANK_TREE_PAGE_SIZE);
+
+  if (node) {
+    memset(node, 0, ZIX_RANK_TREE_PAGE_SIZE);
+  }
+
+  return node;
+}
+
+ZixRankTree*
+zix_rank_tree_new(ZixAllocator* const allocator)
+{
+#if !((defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112L) || \
+      (defined(__cplusplus) && __cplusplus >= 201103L))
+  assert(sizeof(ZixRankTree) <= ZIX_RANK_TREE_PAGE_SIZE);
+  assert(sizeof(ZixRankTreeNode) == ZIX_RANK_TREE_PAGE_SIZE);
+#endif
+
+  ZixRankTree* const t =
+    (ZixRankTree*)zix_malloc(allocator, sizeof(ZixRankTree));
+
+  if (t) {
+    t->allocator = allocator;
+    t->root      = NULL;
+    t->size      = 0U;
+    t->height    = 0U;
+  }
+
+  return t;
+}
+
+static void
+zix_rank_tree_free_children(ZixRankTree* const           t,
+                            ZixRankTreePath              this_path,
+                            const ZixRankTreePath        last_path,
+                            const unsigned               height,
+                            ZixRankTreeNode* const       n,
+                            const ZixRankTreeDestroyFunc destroy,
+                            void* const                  destroy_user_data)
+{
+  if (height) {
+    // Recursively free children of internal node
+    for (ChildIndex i = 0U; i < ZIX_RANK_TREE_FANOUT; ++i) {
+      this_path.indices[ZIX_RANK_TREE_MAX_HEIGHT - height] = i;
+
+      ZixRankTreeNode* const child = n->children[i];
+      if (child) {
+        zix_rank_tree_free_children(t,
+                                    this_path,
+                                    last_path,
+                                    height - 1U,
+                                    child,
+                                    destroy,
+                                    destroy_user_data);
+        zix_aligned_free(t->allocator, child);
+      }
+    }
+  } else if (destroy) {
+    // Determine how many elements are in this leaf
+    unsigned n_vals = last_path.indices[ZIX_RANK_TREE_MAX_HEIGHT] + 1U;
+    for (unsigned i = 1U; i <= t->height; ++i) {
+      if (this_path.indices[ZIX_RANK_TREE_MAX_HEIGHT - i] <
+          last_path.indices[ZIX_RANK_TREE_MAX_HEIGHT - i]) {
+        n_vals = ZIX_RANK_TREE_FANOUT;
+        break;
+      }
+    }
+
+    // Destroy values in leaf node
+    for (unsigned i = 0U; i < n_vals; ++i) {
+      destroy(n->vals[i], destroy_user_data);
+    }
+  }
+}
+
+void
+zix_rank_tree_free(ZixRankTree* const           t,
+                   const ZixRankTreeDestroyFunc destroy,
+                   void* const                  destroy_user_data)
+{
+  if (t) {
+    zix_rank_tree_clear(t, destroy, destroy_user_data);
+    zix_free(t->allocator, t);
+  }
+}
+
+void
+zix_rank_tree_clear(ZixRankTree* const           t,
+                    const ZixRankTreeDestroyFunc destroy,
+                    void* const                  destroy_user_data)
+{
+  assert(t);
+
+  if (t->size) {
+    const ZixRankTreePath first_path = {0U};
+    const ZixRankTreePath last_path  = zix_rank_tree_parse_rank(t->size - 1U);
+    zix_rank_tree_free_children(
+      t, first_path, last_path, t->height, t->root, destroy, destroy_user_data);
+
+    zix_aligned_free(t->allocator, t->root);
+    t->root   = NULL;
+    t->size   = 0U;
+    t->height = 0U;
+  }
+}
+
+size_t
+zix_rank_tree_size(const ZixRankTree* const t)
+{
+  assert(t);
+  return t->size;
+}
+
+uint8_t
+zix_rank_tree_height(const ZixRankTree* const t)
+{
+  assert(t);
+  return t->height;
+}
+
+uintptr_t
+zix_rank_tree_at(const ZixRankTree* const t, const size_t rank)
+{
+  assert(t);
+  if (rank >= t->size) {
+    return 0U;
+  }
+
+  const ZixRankTreePath path       = zix_rank_tree_parse_rank(rank);
+  const unsigned        root_level = ZIX_RANK_TREE_MAX_HEIGHT - t->height;
+  ZixRankTreeNode*      node       = t->root;
+  for (unsigned i = root_level; i < ZIX_RANK_TREE_MAX_HEIGHT; ++i) {
+    assert(node->children[path.indices[i]]);
+    node = node->children[path.indices[i]];
+  }
+
+  return node->vals[path.indices[ZIX_RANK_TREE_MAX_HEIGHT]];
+}
+
+ZixStatus
+zix_rank_tree_push(ZixRankTree* const t, const uintptr_t e)
+{
+  assert(t);
+  assert(t->height < ZIX_RANK_TREE_MAX_HEIGHT);
+
+  if (!t->root) {
+    assert(!t->size);
+    if (!(t->root = zix_rank_tree_node_new(t->allocator))) {
+      return ZIX_STATUS_NO_MEM;
+    }
+
+    t->root->vals[0] = e;
+    ++t->size;
+    return ZIX_STATUS_SUCCESS;
+  }
+
+  const size_t          rank        = t->size;
+  const ZixRankTreePath path        = zix_rank_tree_parse_rank(rank);
+  const unsigned        n_levels    = t->height + 1U;
+  const unsigned        height_bits = n_levels * ZIX_RANK_TREE_INDEX_BITS;
+  const unsigned        height_max  = ((1U << height_bits) - 1U);
+
+  if (rank > height_max) {
+    // Add a new root to grow upwards
+    ZixRankTreeNode* const root = zix_rank_tree_node_new(t->allocator);
+    if (!root) {
+      return ZIX_STATUS_NO_MEM;
+    }
+
+    root->children[0] = t->root;
+    t->height         = (TreeHeight)(t->height + !!t->root);
+    t->root           = root;
+  }
+
+  // Walk down to the appropriate leaf
+  const unsigned   root_level = ZIX_RANK_TREE_MAX_HEIGHT - t->height;
+  ZixRankTreeNode* node       = t->root;
+  for (unsigned i = root_level; i < ZIX_RANK_TREE_MAX_HEIGHT; ++i) {
+    const ChildIndex index = path.indices[i];
+    ZixRankTreeNode* child = node->children[index];
+    if (!child) {
+      child = zix_rank_tree_node_new(t->allocator);
+      if (!child) {
+        return ZIX_STATUS_NO_MEM;
+      }
+
+      node->children[index] = child;
+    }
+
+    node = child;
+  }
+
+  node->vals[path.indices[ZIX_RANK_TREE_MAX_HEIGHT]] = e;
+
+  ++t->size;
+  return ZIX_STATUS_SUCCESS;
+}
+
+ZixStatus
+zix_rank_tree_pop(ZixRankTree* const t)
+{
+  assert(t);
+  if (!t->size) {
+    return ZIX_STATUS_NOT_FOUND;
+  }
+
+  // Decrease size, and handle now-empty case by clearing
+  const size_t rank = --t->size;
+  if (!rank) {
+    zix_aligned_free(t->allocator, t->root);
+    t->root = NULL;
+    return ZIX_STATUS_SUCCESS;
+  }
+
+  // Parse the rank to get the path and walk down to the leaf
+  const ZixRankTreePath path = zix_rank_tree_parse_rank(rank);
+  ZixRankTreeNode*      parents[ZIX_RANK_TREE_MAX_LEVELS] = {NULL};
+  ZixRankTreeNode*      node                              = t->root;
+  const unsigned        root_level = ZIX_RANK_TREE_MAX_HEIGHT - t->height;
+  for (unsigned i = root_level; i < ZIX_RANK_TREE_MAX_HEIGHT; ++i) {
+    parents[i] = node;
+    node       = parents[i]->children[path.indices[i]];
+  }
+
+  // Reset the element entry in the leaf
+  node->vals[path.indices[ZIX_RANK_TREE_MAX_HEIGHT]] = 0U;
+
+  if (!path.indices[ZIX_RANK_TREE_MAX_HEIGHT]) {
+    // Leaf is now empty, walk up deleting now-empty nodes as necessary
+    for (int i = ZIX_RANK_TREE_MAX_HEIGHT - 1U; i >= (int)root_level; --i) {
+      ZixRankTreeNode* const parent = parents[i];
+      const ChildIndex       index  = path.indices[i];
+
+      assert(parent->children[index]);
+      zix_aligned_free(t->allocator, parent->children[index]);
+      parent->children[index] = NULL;
+      if (index) {
+        break;
+      }
+    }
+
+    if (t->height && !t->root->children[1U]) {
+      // Root has only one child left, make it the new root
+      ZixRankTreeNode* const new_root = t->root->children[0U];
+      assert(new_root);
+      zix_aligned_free(t->allocator, t->root);
+      t->root = new_root;
+      --t->height;
+    }
+  }
+
+  return ZIX_STATUS_SUCCESS;
+}
diff --git a/test/cpp/test_headers_cpp.cpp b/test/cpp/test_headers_cpp.cpp
index fe367ad..ea4cc44 100644
--- a/test/cpp/test_headers_cpp.cpp
+++ b/test/cpp/test_headers_cpp.cpp
@@ -1,4 +1,4 @@
-// Copyright 2022 David Robillard <d@drobilla.net>
+// Copyright 2022-2025 David Robillard <d@drobilla.net>
 // SPDX-License-Identifier: ISC
 
 #ifdef _WIN32
@@ -14,6 +14,7 @@
 #include <zix/filesystem.h>     // IWYU pragma: keep
 #include <zix/hash.h>           // IWYU pragma: keep
 #include <zix/path.h>           // IWYU pragma: keep
+#include <zix/rank_tree.h>      // IWYU pragma: keep
 #include <zix/ring.h>           // IWYU pragma: keep
 #include <zix/sem.h>            // IWYU pragma: keep
 #include <zix/status.h>         // IWYU pragma: keep
diff --git a/test/headers/test_headers.c b/test/headers/test_headers.c
index f10d05f..519c8bd 100644
--- a/test/headers/test_headers.c
+++ b/test/headers/test_headers.c
@@ -1,4 +1,4 @@
-// Copyright 2022 David Robillard <d@drobilla.net>
+// Copyright 2022-2025 David Robillard <d@drobilla.net>
 // SPDX-License-Identifier: ISC
 
 #include <zix/allocator.h>      // IWYU pragma: keep
@@ -10,6 +10,7 @@
 #include <zix/filesystem.h>     // IWYU pragma: keep
 #include <zix/hash.h>           // IWYU pragma: keep
 #include <zix/path.h>           // IWYU pragma: keep
+#include <zix/rank_tree.h>      // IWYU pragma: keep
 #include <zix/ring.h>           // IWYU pragma: keep
 #include <zix/sem.h>            // IWYU pragma: keep
 #include <zix/status.h>         // IWYU pragma: keep
diff --git a/test/meson.build b/test/meson.build
index 0db182c..20003be 100644
--- a/test/meson.build
+++ b/test/meson.build
@@ -47,6 +47,11 @@ sequential_tests = {
   'filesystem': {'': files('../README.md')},
   'hash': {'': []},
   'path': {'': []},
+  'rank_tree': {
+    '': [],
+    '_small': ['4'],
+    '_large': ['1000000'],
+  },
   'status': {'': []},
   'string_view': {'': []},
   'tree': {
@@ -74,6 +79,9 @@ bad_tests = {
   'btree': {
     '_extra': ['4', '1337'],
   },
+  'rank_tree': {
+    '_extra': ['4', '1337'],
+  },
   'ring': {
     '_extra': ['4', '1024', '1337'],
   },
diff --git a/test/test_rank_tree.c b/test/test_rank_tree.c
new file mode 100644
index 0000000..b0ef03d
--- /dev/null
+++ b/test/test_rank_tree.c
@@ -0,0 +1,182 @@
+// Copyright 2011-2025 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#undef NDEBUG
+
+#include "failing_allocator.h"
+#include "test_args.h"
+
+#include <zix/rank_tree.h>
+#include <zix/status.h>
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+static void
+test_new_failed_alloc(void)
+{
+  ZixFailingAllocator allocator = zix_failing_allocator();
+
+  // Successfully allocate a itree to count the number of allocations
+  ZixRankTree* const tree = zix_rank_tree_new(&allocator.base);
+  assert(tree);
+  assert(!zix_rank_tree_size(tree));
+  assert(!zix_rank_tree_height(tree));
+  zix_rank_tree_free(tree, NULL, NULL);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_new_allocs = zix_failing_allocator_reset(&allocator, 0);
+  for (size_t i = 0U; i < n_new_allocs; ++i) {
+    zix_failing_allocator_reset(&allocator, i);
+    assert(!zix_rank_tree_new(&allocator.base));
+  }
+}
+
+static void
+test_push_failed_alloc(void)
+{
+  static const size_t n_elems = 1024U;
+
+  ZixFailingAllocator allocator = zix_failing_allocator();
+
+  ZixRankTree* const tree = zix_rank_tree_new(&allocator.base);
+  assert(tree);
+
+  // Successfully push elements to count the number of allocations
+  for (uintptr_t i = 0U; i < n_elems; ++i) {
+    assert(!zix_rank_tree_push(tree, i));
+  }
+
+  zix_rank_tree_clear(tree, NULL, NULL);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_new_allocs = zix_failing_allocator_reset(&allocator, 0);
+  for (size_t i = 0U; i < n_new_allocs; ++i) {
+    zix_failing_allocator_reset(&allocator, i);
+
+    for (uintptr_t j = 0U; j < n_elems; ++j) {
+      const ZixStatus st = zix_rank_tree_push(tree, j);
+      if (st) {
+        assert(st == ZIX_STATUS_NO_MEM);
+        break;
+      }
+    }
+  }
+
+  zix_rank_tree_free(tree, NULL, NULL);
+}
+
+static void
+test_push_pop(const size_t n_elems)
+{
+  // Create a new tree and check that no elements are accessible
+  ZixRankTree* const tree = zix_rank_tree_new(NULL);
+  assert(tree);
+  assert(!zix_rank_tree_at(tree, 0U));
+  assert(zix_rank_tree_pop(tree) == ZIX_STATUS_NOT_FOUND);
+
+  // Push elements and check that they're accessible as we go
+  for (uintptr_t i = 0U; i < n_elems; ++i) {
+    assert(!zix_rank_tree_push(tree, i));
+    assert(zix_rank_tree_size(tree) == i + 1);
+    assert(zix_rank_tree_at(tree, i) == i);
+  }
+
+  // Check that all those elements are present in the final tree
+  for (uintptr_t i = 0U; i < n_elems; ++i) {
+    assert(zix_rank_tree_at(tree, i) == i);
+  }
+
+  // Check that the tree has the expected size
+  assert(zix_rank_tree_size(tree) == n_elems);
+  assert(!zix_rank_tree_at(tree, n_elems + 1U));
+
+  // Pop elements
+  for (uintptr_t i = 0U; i < n_elems; ++i) {
+    const size_t rank = n_elems - i;
+    assert(!zix_rank_tree_pop(tree));
+    assert(zix_rank_tree_size(tree) == rank - 1U);
+    assert(!zix_rank_tree_at(tree, rank));
+  }
+
+  // Check that the tree is empty again
+  assert(!zix_rank_tree_size(tree));
+  assert(!zix_rank_tree_height(tree));
+  assert(!zix_rank_tree_at(tree, 0U));
+
+  zix_rank_tree_free(tree, NULL, NULL);
+}
+
+static void
+destroy(const uintptr_t val, void* const user_data)
+{
+  size_t* const count = (size_t*)user_data;
+  assert(val == *count);
+  ++*count;
+}
+
+static void
+test_clear(const size_t n_elems)
+{
+  ZixRankTree* const tree = zix_rank_tree_new(NULL);
+  assert(tree);
+
+  // Push elements
+  for (uintptr_t i = 0U; i < n_elems; ++i) {
+    assert(!zix_rank_tree_push(tree, i));
+  }
+
+  // Clear tree and record number of destructions
+  size_t destroy_count = 0U;
+  zix_rank_tree_clear(tree, destroy, &destroy_count);
+
+  // Check that the tree is empty
+  assert(!zix_rank_tree_size(tree));
+  assert(!zix_rank_tree_height(tree));
+  assert(destroy_count == n_elems);
+
+  zix_rank_tree_free(tree, NULL, NULL);
+}
+
+static void
+test_free(void)
+{
+  ZixRankTree* const tree = zix_rank_tree_new(NULL);
+  assert(tree);
+
+  // Test that the destroy function isn't called for an empty tree
+  size_t destroy_count = 0U;
+  zix_rank_tree_free(tree, destroy, &destroy_count);
+  assert(!destroy_count);
+
+  // Test that free handles null gracefully
+  zix_rank_tree_free(NULL, NULL, NULL);
+  zix_rank_tree_free(NULL, destroy, &destroy_count);
+  zix_rank_tree_free(NULL, destroy, NULL);
+  zix_rank_tree_free(NULL, NULL, &destroy_count);
+  assert(!destroy_count);
+}
+
+int
+main(int argc, char** argv)
+{
+  if (argc > 2) {
+    fprintf(stderr, "Usage: %s [N_ELEMS]\n", argv[0]);
+    return EXIT_FAILURE;
+  }
+
+  const char* const size_arg = (argc > 1) ? argv[1] : "262145";
+  const size_t      n_elems  = zix_test_size_arg(size_arg, 1U, 1U << 30U);
+
+  printf("Running tests with %zu elements\n", n_elems);
+
+  test_new_failed_alloc();
+  test_free();
+  test_push_failed_alloc();
+  test_push_pop(n_elems);
+  test_clear(n_elems);
+  return 0;
+}