commit 30f143c5a4add2934d5cf4fe9a47eb14b16c8d35
parent c213ff38c1900e95dfd261bca87b2f8111d04543
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Thu, 23 Apr 2026 14:55:29 +0200
Update to the distribution of lines among tree nodes
The number of children for a node was calculated to prioritize balancing
the tree over maintaining its arity. However, the number of lines
actually assigned to child nodes could result in a (significant)
imbalance.
This commit retains the same policy for calculating the number of
children of a node, but modifies the way lines are distributed among
them to optimize the tree’s balance. A fixed number of lines is assigned
to each child, and the remaining lines are distributed equally among the
first children.
Diffstat:
3 files changed, 31 insertions(+), 40 deletions(-)
diff --git a/src/sln_tree.c b/src/sln_tree.c
@@ -393,10 +393,7 @@ release_tree(ref_T* ref)
* Local function
******************************************************************************/
unsigned
-node_child_count
- (const struct sln_node* node,
- const unsigned tree_arity,
- size_t* out_nlines_per_child) /* Max #lines per child. May be NULL */
+node_child_count(const struct sln_node* node, const unsigned tree_arity)
{
size_t nlines = 0; /* #lines in the node */
size_t nlines_per_child = 0; /* Max #lines in a child */
@@ -422,8 +419,6 @@ node_child_count
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;
-
ASSERT(nchildren <= UINT_MAX);
return (unsigned)nchildren;
}
@@ -670,7 +665,7 @@ sln_node_get_child_count
if(sln_node_is_leaf(node)) {
return 0; /* No child */
} else {
- return node_child_count(node, tree->args.arity, NULL);
+ return node_child_count(node, tree->args.arity);
}
}
diff --git a/src/sln_tree_build.c b/src/sln_tree_build.c
@@ -749,7 +749,7 @@ build_polylines(struct sln_tree* tree)
} else {
const size_t ichild0 = inode + NODE(inode)->offset + 0;
const struct sln_node* node = darray_node_cdata_get(&tree->nodes)+inode;
- const unsigned nchildren = node_child_count(node, tree->args.arity, NULL);
+ const unsigned nchildren = node_child_count(node, tree->args.arity);
size_t i = 0;
/* Child nodes have their polyline created */
@@ -827,7 +827,6 @@ partition_lines(struct sln_tree* tree)
size_t istack = 0;
/* Progress */
- size_t nlines = 0;
size_t nlines_total = 0;
size_t nlines_processed = 0;
int progress = 0;
@@ -838,9 +837,7 @@ partition_lines(struct sln_tree* tree)
ASSERT(tree); /* Pre-condition */
- SHTR(line_list_get_size(tree->args.lines, &nlines));
-
- nlines_total = nlines;
+ SHTR(line_list_get_size(tree->args.lines, &nlines_total));
nlines_processed = 0;
#define LOG_MSG "Partitioning: %3d%%\n"
@@ -854,7 +851,7 @@ partition_lines(struct sln_tree* tree)
/* Setup the root node */
NODE(0)->range[0] = 0;
- NODE(0)->range[1] = nlines - 1;
+ NODE(0)->range[1] = nlines_total - 1;
/* Push back SIZE_MAX which, once pop up, will mark the end of recursion */
stack[istack++] = SIZE_MAX;
@@ -866,17 +863,17 @@ partition_lines(struct sln_tree* tree)
inode = 0; /* Root node */
while(inode != SIZE_MAX) {
/* #lines into the node */
- nlines = NODE(inode)->range[1] - NODE(inode)->range[0] + 1;
+ size_t nlines_node = NODE(inode)->range[1] - NODE(inode)->range[0] + 1;
/* Make a leaf */
- if(nlines <= tree->args.leaf_nlines) {
+ if(nlines_node <= tree->args.leaf_nlines) {
int pcent = 0;
NODE(inode)->offset = 0;
inode = stack[--istack]; /* Pop the next node */
- ASSERT(nlines_processed + nlines <= nlines_total);
- nlines_processed += nlines;
+ ASSERT(nlines_processed + nlines_node <= nlines_total);
+ nlines_processed += nlines_node;
/* Print progress update */
pcent = (int)((double)nlines_processed*100.0/(double)nlines_total+0.5);
@@ -888,17 +885,17 @@ partition_lines(struct sln_tree* tree)
/* Split the node */
} else {
size_t node_range[2] = {0,0};
- size_t nlines_per_child = 0;
+ size_t nlines_child_min = 0; /* Min #lines per child */
+ size_t nlines_remain = 0;
size_t nchildren = 0;
+ size_t iline = 0;
size_t i = 0;
/* Calculate the index of the first child */
size_t ichildren = darray_node_size_get(&tree->nodes);
- /* Compute how the lines of a node are distributed among its children,
- * as well as the number of children that node has */
- nchildren = node_child_count(darray_node_cdata_get(&tree->nodes)+inode,
- tree->args.arity, &nlines_per_child);
+ /* Compute how the number of children that node has */
+ nchildren = node_child_count(NODE(inode), tree->args.arity);
ASSERT(nchildren <= tree->args.arity);
ASSERT(ichildren > inode);
@@ -909,29 +906,29 @@ partition_lines(struct sln_tree* tree)
/* Define the offset from the current node to its children */
NODE(inode)->offset = ui64_to_ui32((uint64_t)(ichildren - inode));
+ nlines_child_min = nlines_node / nchildren;
+ nlines_remain = nlines_node % nchildren;
+
+ iline = node_range[0];
FOR_EACH(i, 0, nchildren) {
+ /* Compute the number of lines per child. Start by assigning the minimum
+ * number of lines to each child, then distribute the remaining lines
+ * among the first children */
+ size_t nlines_child = nlines_child_min + (i < nlines_remain);
+
CREATE_NODE;
/* Set the range of lines line for the newly created child. Note that
* the boundaries of the range are inclusive, which is why 1 is
* subtracted to the upper bound */
- NODE(ichildren+i)->range[0] = node_range[0] + nlines_per_child*(i+0);
- NODE(ichildren+i)->range[1] = node_range[0] + nlines_per_child*(i+1)-1;
-
- /* Check that the child's lines are a subset of the parent's lines. Note
- * that the upper bound of the child's line interval is not checked, as
- * it may temporarily exceed the parent's interval since, up to this
- * point, it is assumed that all children contain the same number of
- * lines. This is no longer true if the number of lines in the parent is
- * not a multiple of the computed number of lines per child. The upper
- * bound of the last child's range is therefore readjusted at the end of
- * the loop (see below) */
- ASSERT(NODE(ichildren+i)->range[0] <= node_range[1]);
+ NODE(ichildren+i)->range[0] = iline;
+ NODE(ichildren+i)->range[1] = iline + nlines_child - 1/*inclusive bound*/;
+ iline += nlines_child;
+
+ /* Check that the child's lines are a subset of the parent's lines */
+ ASSERT(NODE(ichildren+i)->range[0] >= node_range[0]);
+ ASSERT(NODE(ichildren+i)->range[1] <= node_range[1]);
}
- /* Readjust the upper bound of the last child to ensure that its line
- * interval is fully contained within its parent node. See above for an
- * explanation of why */
- NODE(ichildren + nchildren - 1)->range[1] = node_range[1];
inode = ichildren; /* Make the first child the current node */
diff --git a/src/sln_tree_c.h b/src/sln_tree_c.h
@@ -74,7 +74,6 @@ tree_build
extern LOCAL_SYM unsigned
node_child_count
(const struct sln_node* node,
- const unsigned tree_arity,
- size_t* out_nlines_per_child); /* Max #lines per child. May be NULL */
+ const unsigned tree_arity);
#endif /* SLN_TREE_C_H */
