commit dbfa2759749944ec0871c2a3f2210629e4e6d144
parent 1595ab0d1d3b57c732d75e007e1e0fdec7ec0bed
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Wed, 8 Apr 2026 09:00:33 +0200
Add the constant SLN_TREE_DEPTH_MAX
The maximum depth of a tree is now a symbolic constant provided directly
by the Star-Line API. It replaces the constants defined elsewhere.
Diffstat:
5 files changed, 28 insertions(+), 27 deletions(-)
diff --git a/src/sln.h b/src/sln.h
@@ -43,8 +43,8 @@
#define SLN(Func) sln_ ## Func
#endif
-/* Maximum arity of a tree */
-#define SLN_TREE_ARITY_MAX 2
+#define SLN_TREE_DEPTH_MAX 64 /* Maximum depth of a tree */
+#define SLN_TREE_ARITY_MAX 2 /* Maximum arity of a tree */
/* Forward declaration of external data structures */
struct logger;
diff --git a/src/sln_get.c b/src/sln_get.c
@@ -26,16 +26,6 @@
#include <unistd.h>
-/* The maximum depth of a tree is 63, which is greater than the number of
- * lines that could actually be managed. Indeed, with such a depth, assuming
- * that there is a maximum of one line per leaf, it would be possible to
- * structure up to 2^63 lines. The problem would then be memory usage well
- * before this maximum depth.
- *
- * In fact, this limit is dictated by the number of bits used to encode the
- * descent masks, i.e., on a 64-bit integer. */
-#define MAX_DEPTH 64
-
enum child { LEFT, RIGHT };
enum output_type {
@@ -110,9 +100,10 @@ tree_descent
uint64_t mask = 0;
ASSERT(args);
- if(nlevels == 0 || args->depth >= MAX_DEPTH) return; /* Nothing to descent */
+ if(nlevels == 0 || args->depth >= SLN_TREE_DEPTH_MAX)
+ return; /* Nothing to descent */
- if(nlevels > 64) {
+ if(nlevels > SLN_TREE_DEPTH_MAX) {
/* The mask can encode up to 64 levels of descent. Thus, if the number of
* levels is greater than or equal to 64, all bits of the mask are
* activated. */
@@ -131,7 +122,7 @@ tree_descent
case RIGHT: args->descent_rmask |= mask; break;
default: FATAL("Unreachable code\n"); break;
}
- args->depth = MMIN(args->depth + nlevels, MAX_DEPTH);
+ args->depth = MMIN(args->depth + nlevels, SLN_TREE_DEPTH_MAX);
}
static res_T
@@ -309,7 +300,10 @@ static res_T
print_level_descriptor(const struct cmd* cmd)
{
/* Stack for visiting the tree depth-first */
- struct { const struct sln_node* node; unsigned level; } stack[MAX_DEPTH];
+ struct {
+ const struct sln_node* node;
+ unsigned level;
+ } stack[SLN_TREE_DEPTH_MAX];
int istack = 0;
/* Node data */
diff --git a/src/sln_tree.c b/src/sln_tree.c
@@ -560,7 +560,10 @@ sln_tree_get_desc(const struct sln_tree* tree, struct sln_tree_desc* desc)
SHTR(line_list_get_size(tree->args.lines, &desc->nlines));
nlines_adjusted = round_up_pow2(desc->nlines);
- for(depth=0; depth<64 && !(BIT_U64(depth) & nlines_adjusted); ++depth);
+ for(depth=0;
+ depth<SLN_TREE_DEPTH_MAX && !(BIT_U64(depth) & nlines_adjusted);
+ ++depth);
+
desc->depth = depth;
#ifndef NDEBUG
@@ -599,7 +602,7 @@ sln_node_is_leaf(const struct sln_node* node)
const struct sln_node*
sln_node_get_child(const struct sln_node* node, const unsigned ichild)
{
- ASSERT(node && ichild <= 1);
+ ASSERT(node && ichild < SLN_TREE_ARITY_MAX);
ASSERT(!sln_node_is_leaf(node));
return node + node->offset + ichild;
}
diff --git a/src/sln_tree_build.c b/src/sln_tree_build.c
@@ -25,11 +25,6 @@
#include <rsys/cstr.h>
-/* Maximum number of lines per leaf */
-#define MAX_NLINES_PER_LEAF 1
-
-#define TREE_DEPTH_MAX 64
-
/*******************************************************************************
* Helper functions
******************************************************************************/
@@ -375,7 +370,7 @@ static res_T
build_polylines(struct sln_tree* tree)
{
/* Stack */
- #define STACK_SIZE (TREE_DEPTH_MAX*2/*tree arity*/)
+ #define STACK_SIZE (SLN_TREE_DEPTH_MAX*2/*tree arity*/)
size_t stack[STACK_SIZE];
size_t istack = 0;
@@ -471,7 +466,7 @@ static res_T
build_polylines2(struct sln_tree* tree)
{
/* Stack */
- #define STACK_SIZE (TREE_DEPTH_MAX*SLN_TREE_ARITY_MAX)
+ #define STACK_SIZE (SLN_TREE_DEPTH_MAX*SLN_TREE_ARITY_MAX)
size_t stack[STACK_SIZE];
size_t istack = 0;
@@ -575,7 +570,7 @@ static res_T
partition_lines(struct sln_tree* tree)
{
/* Stack */
- #define STACK_SIZE TREE_DEPTH_MAX
+ #define STACK_SIZE SLN_TREE_DEPTH_MAX
size_t stack[STACK_SIZE];
size_t istack = 0;
@@ -686,7 +681,7 @@ static res_T
partition_lines2(struct sln_tree* tree)
{
/* Stack */
- #define STACK_SIZE (TREE_DEPTH_MAX*(SLN_TREE_ARITY_MAX-1))
+ #define STACK_SIZE (SLN_TREE_DEPTH_MAX*(SLN_TREE_ARITY_MAX-1))
size_t stack[STACK_SIZE];
size_t istack = 0;
diff --git a/src/sln_tree_c.h b/src/sln_tree_c.h
@@ -25,6 +25,9 @@
#include <rsys/dynamic_array.h>
#include <rsys/ref_count.h>
+/* Maximum number of lines per leaf */
+#define MAX_NLINES_PER_LEAF 1
+
/* Current version of the serialized tree data. One should increment it and
* perform a version management onto serialized tree when these data are
* updated. */
@@ -70,4 +73,10 @@ extern LOCAL_SYM res_T
tree_build
(struct sln_tree* tree);
+extern LOCAL_SYM size_t
+node_child_count
+ (const struct sln_tree* tree,
+ const size_t inode,
+ size_t* out_nlines_per_child); /* Max #lines per child. May be NULL */
+
#endif /* SLN_TREE_C_H */
