star-line

commit 25fde8e4d6c6fa72c4981c96fc435d49d875c1e0
parent 968865d1a43c05f9c6722a84c99b9d035c971047
Author: Vincent Forest <vincent.forest@meso-star.com>
Date:   Tue,  7 Apr 2026 12:55:56 +0200

Compute the number of children

This allows to handle cases where the arity of the tree is not
necessarily equal to two. The number of children of a node might then
differ from the tree's arity, but it can be computed based on the
number of nodes to be partitioned and the partitioning strategy.
This is why the 'node_child_count' function was designed.

Diffstat:
M
src/sln_tree_build.c
 | 
44
++++++++++++++++++++++++++++++++++++++++----

1 file changed, 40 insertions(+), 4 deletions(-)
diff --git a/src/sln_tree_build.c b/src/sln_tree_build.c
@@ -96,6 +96,39 @@ eval_ka
   return ka;
 }
 
+static INLINE size_t
+node_child_count(const struct sln_tree* tree, const size_t inode)
+{
+  const struct sln_node* node = NULL;
+  size_t nlines = 0; /* #lines in the node */
+  size_t nlines_child =  0; /* #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_child = (nlines + tree->args.arity-1/*ceil*/)/tree->args.arity;
+
+  /* From the previous line repartition, compute the number of children */
+  nchildren = (nlines + nlines_child-1/*ceil*/)/nlines_child;
+  ASSERT(nchildren >= 2);
+
+  return nchildren;
+}
+
 static res_T
 merge_node_polylines
   (struct sln_tree* tree,
@@ -204,6 +237,7 @@ merge_children_polylines
   size_t nvertices = 0;
 
   /* Miscellaneous */
+  size_t nchildren = 0;
   unsigned i = 0;
   res_T res = RES_OK;
 
@@ -214,10 +248,12 @@ merge_children_polylines
 
   #define NODE(Id) (darray_node_data_get(&tree->nodes) + (Id))
 
+  nchildren = node_child_count(tree, inode);
+
   /* Compute the number of vertices to be merged,
    * i.e., the sum of vertices of the children */
   nvertices = 0;
-  FOR_EACH(i, 0, tree->args.arity) {
+  FOR_EACH(i, 0, nchildren) {
     const size_t ichild = inode + NODE(inode)->offset + i;
     nvertices += NODE(ichild)->nvertices;
   }
@@ -237,7 +273,7 @@ merge_children_polylines
   /* Initialize the vertex index list. For each child, the initial value
    * corresponds to the index of its first vertex. This index will be
    * incremented as vertices are merged into the parent polyline. */
-  FOR_EACH(i, 0, tree->args.arity) {
+  FOR_EACH(i, 0, nchildren) {
     const size_t ichild = inode + NODE(inode)->offset + i;
     children_ivtx[i] = NODE(ichild)->ivertex;
   }
@@ -254,7 +290,7 @@ merge_children_polylines
 
     /* Find the minimum wave number among the vertices of the child vertices
      * that are candidates for merging */
-    FOR_EACH(i, 0, tree->args.arity) {
+    FOR_EACH(i, 0, nchildren) {
       const size_t child_ivtx = children_ivtx[i];
       if(child_ivtx != NO_MORE_VERTEX) {
         nu = MMIN(nu, vertices[child_ivtx].wavenumber);
@@ -263,7 +299,7 @@ merge_children_polylines
     ASSERT(nu != INF); /* At least one vertex must have been found */
 
     /* Compute the value of ka at the wave number determined above */
-    FOR_EACH(i, 0, tree->args.arity) {
+    FOR_EACH(i, 0, nchildren) {
       const size_t child_ivtx = children_ivtx[i];
       const struct sln_node* child = NODE(inode + NODE(inode)->offset + i);