commit c610024b4cddb5d0297e4254dbd701b6f5224d1c
parent 2d684ecd4658629d1503e4e2ea9f3b1b8a992b46
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Thu, 2 Apr 2026 21:46:40 +0200
Addition of a tree arity-agnostic partitioning
Following commit b89669a, this new function partitions nodes based on
the tree's arity, which is no longer assumed to be two. Currently,
since the arity can only be 2, both functions construct the same
bit-by-bit tree as before. This serves, in a way, as a validation of the
new function.
Note that the previous function is retained to simplify future testing
when the caller will be able to define an arity other than 2.
Diffstat:
| M | src/sln_tree_build.c | | | 131 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- |
1 file changed, 129 insertions(+), 2 deletions(-)
diff --git a/src/sln_tree_build.c b/src/sln_tree_build.c
@@ -30,7 +30,9 @@
/* STACK_SIZE is set to the maximum depth of the partitioning tree generated by
* the tree_build function. This is actually the maximum stack size where tree
- * nodes are pushed by the recursive build process */
+ * nodes are pushed by the recursive build process
+ *
+ * FIXME the previous comment is not true with a tree whose arity is not 2 */
#define STACK_SIZE 64
/*******************************************************************************
@@ -530,6 +532,131 @@ error:
goto exit;
}
+static res_T
+partition_lines2(struct sln_tree* tree)
+{
+ size_t stack[STACK_SIZE];
+ size_t istack = 0;
+ size_t inode = 0;
+ size_t nlines = 0;
+ size_t nlines_total = 0;
+ size_t nlines_processed = 0;
+ int progress = 0;
+ unsigned arity = 0;
+ res_T res = RES_OK;
+
+ ASSERT(tree);
+ SHTR(line_list_get_size(tree->args.lines, &nlines));
+
+ arity = tree->args.arity;
+ nlines_total = nlines;
+ nlines_processed = 0;
+
+ #define LOG_MSG "Partitioning: %3d%%\n"
+ #define NODE(Id) (darray_node_data_get(&tree->nodes) + (Id))
+ #define CREATE_NODE { \
+ res = darray_node_push_back(&tree->nodes, &SLN_NODE_NULL); \
+ if(res != RES_OK) goto error; \
+ } (void)0
+
+ CREATE_NODE; /* Alloc the root node */
+
+ /* Setup the root node */
+ NODE(0)->range[0] = 0;
+ NODE(0)->range[1] = nlines - 1;
+
+ /* Push back SIZE_MAX which, once pop up, will mark the end of recursion */
+ stack[istack++] = SIZE_MAX;
+
+ /* Print that although nothing has been done yet,
+ * the calculation is nevertheless in progress */
+ INFO(tree->sln, LOG_MSG, progress);
+
+ inode = 0; /* Root node */
+ while(inode != SIZE_MAX) {
+ /* #lines into the node */
+ nlines = NODE(inode)->range[1] - NODE(inode)->range[0] + 1;
+
+ /* Make a leaf */
+ if(nlines <= MAX_NLINES_PER_LEAF) {
+ int pcent = 0;
+
+ NODE(inode)->offset = 0;
+ inode = stack[--istack]; /* Pop the next node */
+
+ ASSERT(nlines_processed + nlines <= nlines_total);
+ nlines_processed += nlines;
+
+ /* Print progress update */
+ pcent = (int)((double)nlines_processed*100.0/(double)nlines_total+0.5);
+ if(pcent/10 > progress/10) {
+ progress = pcent;
+ INFO(tree->sln, LOG_MSG, progress);
+ }
+
+ /* Split the node */
+ } else {
+ size_t node_range[2] = {0,0};
+ size_t i = 0;
+
+ /* Compute how the lines of a node are distributed among its children,
+ * as well as the number of children that node has */
+ const size_t nlines_child = (nlines + arity/2/*ceil*/)/arity;
+ const size_t nchildren = (nlines + nlines_child/2/*ceil*/)/nlines_child;
+
+ /* Calculate the index of the first child */
+ size_t ichildren = darray_node_size_get(&tree->nodes);
+
+ ASSERT(nchildren <= arity);
+ ASSERT(ichildren > inode);
+
+ node_range[0] = NODE(inode)->range[0];
+ node_range[1] = NODE(inode)->range[1];
+
+ /* Define the offset from the current node to its children */
+ NODE(inode)->offset = ui64_to_ui32((uint64_t)(ichildren - inode));
+
+ FOR_EACH(i, 0, nchildren) {
+ 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_child*(i+0);
+ NODE(ichildren+i)->range[1] = node_range[0] + nlines_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]);
+ }
+ /* 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 */
+ FOR_EACH(i, 1, nchildren) {
+ stack[istack++] = ichildren + i; /* Push the other children */
+ }
+ }
+ }
+ ASSERT(nlines_processed == nlines_total);
+
+ #undef NODE
+ #undef CREATE_NODE
+exit:
+ return res;
+error:
+ darray_node_clear(&tree->nodes);
+ goto exit;
+}
+
/*******************************************************************************
* Local functions
******************************************************************************/
@@ -538,7 +665,7 @@ tree_build(struct sln_tree* tree)
{
res_T res = RES_OK;
- if((res = partition_lines(tree)) != RES_OK) goto error;
+ if((res = partition_lines2(tree)) != RES_OK) goto error;
if((res = build_polylines(tree)) != RES_OK) goto error;
exit:
