star-line

commit 1595ab0d1d3b57c732d75e007e1e0fdec7ec0bed
parent 9f49170cb0f0823ffb52de36afe6291e6dc2f8e0
Author: Vincent Forest <vincent.forest@meso-star.com>
Date:   Tue,  7 Apr 2026 15:26:57 +0200

Update the stack size for tree-building routines

The size of the stack depends on the maximum depth of the tree and the
algorithm. Therefore, there is no longer a single constant defining an
absolute stack size, but rather a set of constants defined on a
per-function basis, depending on the maximum depth of the tree - which is
set once and for all - and the algorithm in which the stack is declared.

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

1 file changed, 45 insertions(+), 23 deletions(-)
diff --git a/src/sln_tree_build.c b/src/sln_tree_build.c
@@ -28,12 +28,7 @@
 /* Maximum number of lines per leaf */
 #define MAX_NLINES_PER_LEAF 1
 
-/* 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
- *
- * FIXME the previous comment is not true with a tree whose arity is not 2 */
-#define STACK_SIZE 64
+#define TREE_DEPTH_MAX 64
 
 /*******************************************************************************
  * Helper functions
@@ -379,14 +374,21 @@ error:
 static res_T
 build_polylines(struct sln_tree* tree)
 {
-  size_t stack[STACK_SIZE*2];
+  /* Stack */
+  #define STACK_SIZE (TREE_DEPTH_MAX*2/*tree arity*/)
+  size_t stack[STACK_SIZE];
   size_t istack = 0;
-  size_t inode = 0;
+
+  /* Progress */
   size_t nnodes_total = 0;
   size_t nnodes_processed = 0;
   int progress = 0;
+
+  /* Miscellaneous */
+  size_t inode = 0;
   res_T res = RES_OK;
-  ASSERT(tree);
+
+  ASSERT(tree); /* Pre-condition */
 
   #define LOG_MSG "Meshing: %3d%%\n"
   #define NODE(Id) (darray_node_data_get(&tree->nodes) + (Id))
@@ -420,12 +422,8 @@ build_polylines(struct sln_tree* tree)
 
         /* Build the polyline of the current node by merging the polylines of
          * its children */
-#if 0
         res = merge_node_polylines
           (tree, NODE(ichild0), NODE(ichild1), NODE(inode));
-#else
-        res = merge_children_polylines(tree, inode);
-#endif
         if(res != RES_OK) goto error;
         inode = stack[--istack];
 
@@ -461,6 +459,7 @@ build_polylines(struct sln_tree* tree)
   #undef NODE
   #undef IS_LEAF
   #undef LOG_MSG
+  #undef STACK_SIZE
 
 exit:
   return res;
@@ -471,13 +470,20 @@ error:
 static res_T
 build_polylines2(struct sln_tree* tree)
 {
-  size_t stack[STACK_SIZE*2];
+  /* Stack */
+  #define STACK_SIZE (TREE_DEPTH_MAX*SLN_TREE_ARITY_MAX)
+  size_t stack[STACK_SIZE];
   size_t istack = 0;
-  size_t inode = 0;
+
+  /* Progress */
   size_t nnodes_total = 0;
   size_t nnodes_processed = 0;
   int progress = 0;
+
+  /* Miscellaneous */
+  size_t inode = 0;
   res_T res = RES_OK;
+
   ASSERT(tree);
 
   #define LOG_MSG "Meshing: %3d%%\n"
@@ -557,6 +563,7 @@ build_polylines2(struct sln_tree* tree)
   #undef NODE
   #undef IS_LEAF
   #undef LOG_MSG
+  #undef STACK_SIZE
 
 exit:
   return res;
@@ -567,16 +574,23 @@ error:
 static res_T
 partition_lines(struct sln_tree* tree)
 {
+  /* Stack */
+  #define STACK_SIZE TREE_DEPTH_MAX
   size_t stack[STACK_SIZE];
   size_t istack = 0;
-  size_t inode = 0;
+
+  /* Progress */
   size_t nlines = 0;
   size_t nlines_total = 0;
   size_t nlines_processed = 0;
   int progress = 0;
+
+  /* Miscellaneous */
+  size_t inode = 0;
   res_T res = RES_OK;
 
-  ASSERT(tree);
+  ASSERT(tree); /* Pre-condition */
+
   SHTR(line_list_get_size(tree->args.lines, &nlines));
 
   nlines_total = nlines;
@@ -660,7 +674,7 @@ partition_lines(struct sln_tree* tree)
 
   #undef NODE
   #undef CREATE_NODE
-
+  #undef STACK_SIZE
 exit:
   return res;
 error:
@@ -671,20 +685,25 @@ error:
 static res_T
 partition_lines2(struct sln_tree* tree)
 {
+  /* Stack */
+  #define STACK_SIZE (TREE_DEPTH_MAX*(SLN_TREE_ARITY_MAX-1))
   size_t stack[STACK_SIZE];
   size_t istack = 0;
-  size_t inode = 0;
+
+  /* Progress */
   size_t nlines = 0;
   size_t nlines_total = 0;
   size_t nlines_processed = 0;
   int progress = 0;
-  unsigned arity = 0;
+
+  /* Miscellaneous */
+  size_t inode = 0;
   res_T res = RES_OK;
 
-  ASSERT(tree);
+  ASSERT(tree); /* Pre-condition */
+
   SHTR(line_list_get_size(tree->args.lines, &nlines));
 
-  arity = tree->args.arity;
   nlines_total = nlines;
   nlines_processed = 0;
 
@@ -744,7 +763,7 @@ partition_lines2(struct sln_tree* tree)
       /* Calculate the index of the first child */
       size_t ichildren = darray_node_size_get(&tree->nodes);
 
-      ASSERT(nchildren <= arity);
+      ASSERT(nchildren <= tree->args.arity);
       ASSERT(ichildren > inode);
 
       node_range[0] = NODE(inode)->range[0];
@@ -778,6 +797,8 @@ partition_lines2(struct sln_tree* tree)
       NODE(ichildren + nchildren - 1)->range[1] = node_range[1];
 
       inode = ichildren; /* Make the first child the current node */
+
+      ASSERT(istack < STACK_SIZE - 1/*1st child*/);
       FOR_EACH(i, 1, nchildren) {
         stack[istack++] = ichildren + i; /* Push the other children */
       }
@@ -787,6 +808,7 @@ partition_lines2(struct sln_tree* tree)
 
   #undef NODE
   #undef CREATE_NODE
+  #undef STACK_SIZE
 exit:
   return res;
 error: