commit d85a0f7264fdc9915e857d550284603c4902fede
parent 7542ac561004749bfad51db1b9d83a6b0b171ee3
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Wed, 8 Apr 2026 09:16:18 +0200
Add of the sln_node_get_child_count function
It calculates the number of children of a node based on the tree's arity
and the number of lines that the parent node partitions. This is actually
the public interface for the internal function node_child_count.
This commit also updates the profile of the sln_node_get_child
function to add the tree as the first argument. This makes its profile
consistent with the aforementioned function, as both take the tree as an
argument, but also allows for an internal check to verify that the
provided child index is valid relative to the node.
Diffstat:
7 files changed, 83 insertions(+), 58 deletions(-)
diff --git a/src/sln.h b/src/sln.h
@@ -302,11 +302,17 @@ SLN_API int
sln_node_is_leaf
(const struct sln_node* node);
+SLN_API size_t
+sln_node_get_child_count
+ (const struct sln_tree* tree,
+ const struct sln_node* node);
+
/* The node must not be a leaf */
SLN_API const struct sln_node*
sln_node_get_child
- (const struct sln_node* node,
- const unsigned ichild); /* 0 or 1 */
+ (const struct sln_tree* tree,
+ const struct sln_node* node,
+ const unsigned ichild); /* 0 or #children */
SLN_API size_t
sln_node_get_line_count
diff --git a/src/sln_get.c b/src/sln_get.c
@@ -335,10 +335,10 @@ print_level_descriptor(const struct cmd* cmd)
++level;
/* Push the right child */
- stack[istack ].node = sln_node_get_child(node, 1);
+ stack[istack ].node = sln_node_get_child(cmd->tree, node, 1);
stack[istack++].level = level;
- node = sln_node_get_child(node, 0); /* Visit the left child */
+ node = sln_node_get_child(cmd->tree, node, 0); /* Visit the left child */
} else {
/* The queried level or a leaf is reached, update the descriptor */
@@ -379,9 +379,9 @@ get_node(const struct cmd* cmd, unsigned* node_depth/*can be NULL*/)
if(sln_node_is_leaf(node)) break;
if(mask & cmd->args.descent_lmask) {
- node = sln_node_get_child(node, 0);
+ node = sln_node_get_child(cmd->tree, node, 0);
} else if(mask & cmd->args.descent_rmask) {
- node = sln_node_get_child(node, 1);
+ node = sln_node_get_child(cmd->tree, node, 1);
} else {
FATAL("Unreachable code\n");
}
@@ -477,8 +477,8 @@ print_node_value(const struct cmd* cmd)
double val_mesh0 = 0;
double val_mesh1 = 0;
- child0 = sln_node_get_child(node, 0);
- child1 = sln_node_get_child(node, 1);
+ child0 = sln_node_get_child(cmd->tree, node, 0);
+ child1 = sln_node_get_child(cmd->tree, node, 1);
if((res = sln_node_get_mesh(cmd->tree, child0, &mesh0)) != RES_OK) goto error;
if((res = sln_node_get_mesh(cmd->tree, child1, &mesh1)) != RES_OK) goto error;
diff --git a/src/sln_slab.c b/src/sln_slab.c
@@ -337,8 +337,8 @@ sample_line
if(sln_node_is_leaf(node)) break;
- node0 = sln_node_get_child(node, 0);
- node1 = sln_node_get_child(node, 1);
+ node0 = sln_node_get_child(cmd->tree, node, 0);
+ node1 = sln_node_get_child(cmd->tree, node, 1);
SLN(node_get_mesh(cmd->tree, node0, &mesh0));
SLN(node_get_mesh(cmd->tree, node1, &mesh1));
diff --git a/src/sln_tree.c b/src/sln_tree.c
@@ -384,6 +384,46 @@ release_tree(ref_T* ref)
}
/*******************************************************************************
+ * Local function
+ ******************************************************************************/
+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 */
+{
+ const struct sln_node* node = NULL;
+ size_t nlines = 0; /* #lines in the node */
+ size_t nlines_per_child = 0; /* Max #lines in a child */
+ size_t nchildren = 0;
+
+ /* Pre-conditions */
+ ASSERT(tree && inode < darray_node_size_get(&tree->nodes));
+ ASSERT(MAX_NLINES_PER_LEAF == 1); /* Assume one line per leaf */
+
+ /* Retrieve the node data and compute the #lines it partitions */
+ node = darray_node_cdata_get(&tree->nodes) + inode;
+ nlines = node->range[1] - node->range[0] + 1;
+ ASSERT(nlines);
+
+ /* Based on the arity of the tree, calculate how the lines of the node are
+ * distributed among its children. The policy below prioritizes an equal
+ * distribution of rows among the children over maintaining the tree's arity.
+ * Thus, if a smaller number of children results in a more equitable
+ * distribution, this option is preferred over ensuring a number of children
+ * equal to the tree's arity. In other words, the tree's balance is
+ * prioritized. */
+ nlines_per_child = (nlines + tree->args.arity-1/*ceil*/)/tree->args.arity;
+
+ /* From the previous line repartition, compute the number of children */
+ nchildren = (nlines + nlines_per_child-1/*ceil*/)/nlines_per_child;
+ ASSERT(nchildren >= 2);
+
+ if(out_nlines_per_child) *out_nlines_per_child = nlines_per_child;
+ return nchildren;
+}
+
+/*******************************************************************************
* Exported symbols
******************************************************************************/
res_T
@@ -571,7 +611,7 @@ sln_tree_get_desc(const struct sln_tree* tree, struct sln_tree_desc* desc)
unsigned max_depth = 0;
const struct sln_node* node = sln_tree_get_root(tree);
while(!sln_node_is_leaf(node)) {
- node = sln_node_get_child(node, 0);
+ node = sln_node_get_child(tree, node, 0);
++max_depth;
}
CHK(max_depth == depth);
@@ -599,10 +639,26 @@ sln_node_is_leaf(const struct sln_node* node)
return node->offset == 0;
}
+size_t
+sln_node_get_child_count
+ (const struct sln_tree* tree,
+ const struct sln_node* node)
+{
+ size_t inode = 0;
+ ASSERT(tree && node);
+
+ inode = (size_t)(node - darray_node_cdata_get(&tree->nodes));
+ ASSERT(inode < darray_node_size_get(&tree->nodes));
+ return node_child_count(tree, inode, NULL);
+}
+
const struct sln_node*
-sln_node_get_child(const struct sln_node* node, const unsigned ichild)
+sln_node_get_child
+ (const struct sln_tree* tree,
+ const struct sln_node* node,
+ const unsigned ichild)
{
- ASSERT(node && ichild < SLN_TREE_ARITY_MAX);
+ ASSERT(node && ichild < sln_node_get_child_count(tree, node));
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
@@ -86,43 +86,6 @@ eval_ka
return ka;
}
-static INLINE 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 */
-{
- const struct sln_node* node = NULL;
- size_t nlines = 0; /* #lines in the node */
- size_t nlines_per_child = 0; /* Max #lines in a child */
- size_t nchildren = 0;
-
- /* Pre-conditions */
- ASSERT(tree && inode < darray_node_size_get(&tree->nodes));
- ASSERT(MAX_NLINES_PER_LEAF == 1); /* Assume one line per leaf */
-
- /* Retrieve the node data and compute the #lines it partitions */
- node = darray_node_cdata_get(&tree->nodes) + inode;
- nlines = node->range[1] - node->range[0] + 1;
- ASSERT(nlines);
-
- /* Based on the arity of the tree, calculate how the lines of the node are
- * distributed among its children. The policy below prioritizes an equal
- * distribution of rows among the children over maintaining the tree's arity.
- * Thus, if a smaller number of children results in a more equitable
- * distribution, this option is preferred over ensuring a number of children
- * equal to the tree's arity. In other words, the tree's balance is
- * prioritized. */
- nlines_per_child = (nlines + tree->args.arity-1/*ceil*/)/tree->args.arity;
-
- /* From the previous line repartition, compute the number of children */
- nchildren = (nlines + nlines_per_child-1/*ceil*/)/nlines_per_child;
- ASSERT(nchildren >= 2);
-
- if(out_nlines_per_child) *out_nlines_per_child = nlines_per_child;
- return nchildren;
-}
-
static res_T
merge_node_polylines
(struct sln_tree* tree,
diff --git a/src/sln_tree_c.h b/src/sln_tree_c.h
@@ -45,7 +45,7 @@ struct sln_node { /* 32 Bytes */
uint64_t range[2];
uint64_t ivertex; /* Index toward the 1st vertex */
uint32_t nvertices; /* #vertices */
- uint32_t offset; /* Offset toward the node's children (left then right) */
+ uint32_t offset; /* Offset toward the node's children */
};
#define SLN_NODE_NULL__ {{0,0},0,0,0}
static const struct sln_node SLN_NODE_NULL = SLN_NODE_NULL__;
diff --git a/src/test_sln_tree.c b/src/test_sln_tree.c
@@ -100,8 +100,8 @@ check_tree
CHK(sln_node_get_line_count(node) > desc.max_nlines_per_leaf);
ASSERT(istack < STACK_SIZE);
- stack[istack++] = sln_node_get_child(node, 1); /* Push the child 1 */
- node = sln_node_get_child(node, 0); /* Handle the child 0 */
+ stack[istack++] = sln_node_get_child(tree, node, 1); /* Push the child 1 */
+ node = sln_node_get_child(tree, node, 0); /* Handle the child 0 */
} else {
size_t iline, nlines;
@@ -196,7 +196,7 @@ test_tree
while(!sln_node_is_leaf(node)) {
struct sln_node_desc node_desc_next = SLN_NODE_DESC_NULL;
- node = sln_node_get_child(node, 0);
+ node = sln_node_get_child(tree, node, 0);
CHK(sln_node_get_desc(node, &node_desc_next) == RES_OK);
CHK(node_desc_next.nlines >= 1);
@@ -332,10 +332,10 @@ check_tree_equality
node2 = stack[--istack];
node1 = stack[--istack];
} else {
- stack[istack++] = sln_node_get_child(node1, 1);
- stack[istack++] = sln_node_get_child(node2, 1);
- node1 = sln_node_get_child(node1, 0);
- node2 = sln_node_get_child(node2, 0);
+ stack[istack++] = sln_node_get_child(tree1, node1, 1);
+ stack[istack++] = sln_node_get_child(tree2, node2, 1);
+ node1 = sln_node_get_child(tree1, node1, 0);
+ node2 = sln_node_get_child(tree2, node2, 0);
}
}
}
