summaryrefslogtreecommitdiffstats
path: root/src/btree.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/btree.c')
-rw-r--r--src/btree.c90
1 files changed, 50 insertions, 40 deletions
diff --git a/src/btree.c b/src/btree.c
index 7970796..dabd406 100644
--- a/src/btree.c
+++ b/src/btree.c
@@ -1,7 +1,11 @@
-// Copyright 2011-2021 David Robillard <d@drobilla.net>
+// Copyright 2011-2024 David Robillard <d@drobilla.net>
// SPDX-License-Identifier: ISC
-#include "zix/btree.h"
+#include <zix/btree.h>
+
+#include <zix/allocator.h>
+#include <zix/attributes.h>
+#include <zix/status.h>
#include <assert.h>
#include <stdint.h>
@@ -10,9 +14,9 @@
// #define ZIX_BTREE_SORTED_CHECK 1
// Define ZixShort as an integer type half the size of a pointer
-#if UINTPTR_MAX >= UINT32_MAX
+#if UINTPTR_MAX > UINT32_MAX // 64-bit
typedef uint32_t ZixShort;
-#else
+#else // 32-bit
typedef uint16_t ZixShort;
#endif
@@ -78,8 +82,7 @@ zix_btree_node_new(ZixAllocator* const allocator, const bool leaf)
return node;
}
-ZIX_PURE_FUNC
-static ZixBTreeNode*
+ZIX_PURE_FUNC static ZixBTreeNode*
zix_btree_child(const ZixBTreeNode* const node, const unsigned i)
{
assert(!node->is_leaf);
@@ -99,23 +102,15 @@ zix_btree_new(ZixAllocator* const allocator,
assert(cmp);
- 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_aligned_free(allocator, t);
- return NULL;
+ ZixBTree* const t = (ZixBTree*)zix_malloc(allocator, sizeof(ZixBTree));
+ if (t) {
+ t->allocator = allocator;
+ t->root = NULL;
+ t->cmp = cmp;
+ t->cmp_data = cmp_data;
+ t->size = 0U;
}
- t->allocator = allocator;
- t->cmp = cmp;
- t->cmp_data = cmp_data;
- t->size = 0U;
-
return t;
}
@@ -154,20 +149,22 @@ zix_btree_free(ZixBTree* const t,
if (t) {
zix_btree_clear(t, destroy, destroy_user_data);
zix_aligned_free(t->allocator, t->root);
- zix_aligned_free(t->allocator, t);
+ zix_free(t->allocator, t);
}
}
void
-zix_btree_clear(ZixBTree* const t,
- ZixBTreeDestroyFunc destroy,
- const void* destroy_user_data)
+zix_btree_clear(ZixBTree* const t,
+ const ZixBTreeDestroyFunc destroy,
+ const void* const destroy_user_data)
{
- zix_btree_free_children(t, t->root, destroy, destroy_user_data);
+ if (t->root) {
+ zix_btree_free_children(t, t->root, destroy, destroy_user_data);
+ zix_aligned_free(t->allocator, t->root);
+ t->root = NULL;
+ }
- memset(t->root, 0U, sizeof(ZixBTreeNode));
- t->root->is_leaf = true;
- t->size = 0U;
+ t->size = 0U;
}
size_t
@@ -196,7 +193,7 @@ zix_btree_ainsert(void** const array,
const unsigned i,
void* const e)
{
- memmove(array + i + 1U, array + i, (n - i) * sizeof(e));
+ memmove(array + i + 1U, array + i, ((size_t)n - i) * sizeof(e));
array[i] = e;
}
@@ -205,7 +202,7 @@ static void*
zix_btree_aerase(void** const array, const unsigned n, const unsigned i)
{
void* const ret = array[i];
- memmove(array + i, array + i + 1U, (n - i) * sizeof(ret));
+ memmove(array + i, array + i + 1U, ((size_t)n - i) * sizeof(ret));
return ret;
}
@@ -221,7 +218,7 @@ zix_btree_split_child(ZixAllocator* const allocator,
assert(i < n->n_vals + 1U);
assert(zix_btree_child(n, i) == lhs);
- const ZixShort max_n_vals = zix_btree_max_vals(lhs);
+ const unsigned max_n_vals = zix_btree_max_vals(lhs);
ZixBTreeNode* rhs = zix_btree_node_new(allocator, lhs->is_leaf);
if (!rhs) {
return NULL;
@@ -247,7 +244,7 @@ zix_btree_split_child(ZixAllocator* const allocator,
rhs->n_vals * sizeof(void*));
memcpy(rhs->data.inode.children,
lhs->data.inode.children + lhs->n_vals + 1U,
- (rhs->n_vals + 1U) * sizeof(ZixBTreeNode*));
+ ((size_t)rhs->n_vals + 1U) * sizeof(ZixBTreeNode*));
// Move middle value up to parent
zix_btree_ainsert(
@@ -394,14 +391,14 @@ zix_btree_leaf_find(const ZixBTree* const t,
t->cmp, t->cmp_data, n->data.leaf.vals, n->n_vals, e, equal);
}
-static inline bool
+ZIX_PURE_FUNC static inline bool
zix_btree_can_remove_from(const ZixBTreeNode* const n)
{
assert(n->n_vals >= zix_btree_min_vals(n));
return n->n_vals > zix_btree_min_vals(n);
}
-static inline bool
+ZIX_PURE_FUNC static inline bool
zix_btree_is_full(const ZixBTreeNode* const n)
{
assert(n->n_vals <= zix_btree_max_vals(n));
@@ -433,8 +430,13 @@ zix_btree_insert(ZixBTree* const t, void* const e)
ZixStatus st = ZIX_STATUS_SUCCESS;
- // Grow up if necessary to ensure the root is not full
- if (zix_btree_is_full(t->root)) {
+ if (!t->root) {
+ // Empty tree, create a new leaf root
+ if (!(t->root = zix_btree_node_new(t->allocator, true))) {
+ return ZIX_STATUS_NO_MEM;
+ }
+ } else if (zix_btree_is_full(t->root)) {
+ // Grow up if necessary to ensure the root is not full
if ((st = zix_btree_grow_up(t))) {
return st;
}
@@ -490,8 +492,9 @@ zix_btree_insert(ZixBTree* const t, void* const e)
static void
zix_btree_iter_set_frame(ZixBTreeIter* const ti,
ZixBTreeNode* const n,
- const ZixShort i)
+ const unsigned i)
{
+ assert(i <= UINT16_MAX);
ti->nodes[ti->level] = n;
ti->indexes[ti->level] = (uint16_t)i;
}
@@ -617,7 +620,7 @@ zix_btree_merge(ZixBTree* const t, ZixBTreeNode* const n, const unsigned i)
rhs->n_vals * sizeof(void*));
memcpy(lhs->data.inode.children + lhs->n_vals,
rhs->data.inode.children,
- (rhs->n_vals + 1U) * sizeof(void*));
+ ((size_t)rhs->n_vals + 1U) * sizeof(void*));
}
lhs->n_vals += rhs->n_vals;
@@ -677,6 +680,7 @@ zix_btree_fatten_child(ZixBTree* const t, ZixBTreeIter* const iter)
assert(n);
assert(!n->is_leaf);
+ assert(n->n_vals);
ZixBTreeNode* const* const children = n->data.inode.children;
if (i > 0U && zix_btree_can_remove_from(children[i - 1U])) {
@@ -825,6 +829,9 @@ zix_btree_find(const ZixBTree* const t,
ZixBTreeNode* n = t->root;
*ti = zix_btree_end_iter;
+ if (!n) {
+ return ZIX_STATUS_NOT_FOUND;
+ }
while (!n->is_leaf) {
bool equal = false;
@@ -866,6 +873,9 @@ zix_btree_lower_bound(const ZixBTree* const t,
ZixBTreeNode* n = t->root; // Current node
uint16_t found_level = 0U; // Lowest level a match was found at
bool found = false; // True if a match was ever found
+ if (!n) {
+ return ZIX_STATUS_SUCCESS;
+ }
// Search down until we reach a leaf
while (!n->is_leaf) {
@@ -959,7 +969,7 @@ zix_btree_end(const ZixBTree* const t)
bool
zix_btree_iter_equals(const ZixBTreeIter lhs, const ZixBTreeIter rhs)
{
- const size_t indexes_size = (lhs.level + 1U) * sizeof(uint16_t);
+ const size_t indexes_size = ((size_t)lhs.level + 1U) * sizeof(uint16_t);
return (lhs.level == rhs.level) && (lhs.nodes[0U] == rhs.nodes[0U]) &&
(!lhs.nodes[0U] || !memcmp(lhs.indexes, rhs.indexes, indexes_size));
generated by cgit v1.2.1 (git 2.18.0) at 2025-07-04 09:36:00 +0000