commit b89669a93bdad47130865e4fb457a2783fb40e0f
parent c126c34e04bbcd6541ec7e392d5529c17b6247b5
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Thu, 2 Apr 2026 13:52:35 +0200
Prepares to make the tree's arity configurable
The tree's arity is now defined by the caller at the time of creation.
Currently, the arity can only be 2, as defined by the new symbolic
constant SLN_TREE_ARITY_MAX (which is effectively set to 2).
However, this commit also introduces a new procedure for merging
polylines that is independent of the tree's arity. Thus, once the
maximum limit on the tree's arity is relaxed, this function will be able
to accommodate it. The tree constructed with this new merging function
is strictly the same (bit-to-bit) as the one constructed with the
previous function that, by design, only handles the merging of two nodes
(as required by a binary tree).
Finally, note that this commit allows both merging functions to coexist
in order to facilitate future testing.
Diffstat:
4 files changed, 179 insertions(+), 1 deletion(-)
diff --git a/src/sln.h b/src/sln.h
@@ -43,6 +43,9 @@
#define SLN(Func) sln_ ## Func
#endif
+/* Maximum arity of a tree */
+#define SLN_TREE_ARITY_MAX 2
+
/* Forward declaration of external data structures */
struct logger;
struct mem_allocator;
@@ -105,6 +108,9 @@ struct sln_tree_create_args {
* coarser the mesh */
double mesh_decimation_err; /* > 0 */
enum sln_mesh_type mesh_type; /* Type of mesh to generate */
+
+ /* Maximum number of children per node */
+ unsigned arity;
};
#define SLN_TREE_CREATE_ARGS_DEFAULT__ { \
NULL, /* metadata */ \
@@ -116,6 +122,7 @@ struct sln_tree_create_args {
16, /* #vertices hint */ \
0.01f, /* Mesh decimation error */ \
SLN_MESH_UPPER, /* Mesh type */ \
+ 2 /* Arity */ \
}
static const struct sln_tree_create_args SLN_TREE_CREATE_ARGS_DEFAULT =
SLN_TREE_CREATE_ARGS_DEFAULT__;
@@ -162,9 +169,10 @@ struct sln_tree_desc {
size_t nlines;
size_t nvertices;
size_t nnodes;
+ unsigned arity;
};
#define SLN_TREE_DESC_NULL__ { \
- 0, 0, SLN_MESH_TYPES_COUNT__, SLN_LINE_PROFILES_COUNT__, 0, 0, 0, 0, 0, 0 \
+ 0, 0, SLN_MESH_TYPES_COUNT__, SLN_LINE_PROFILES_COUNT__, 0, 0, 0, 0, 0, 0, 0 \
}
static const struct sln_tree_desc SLN_TREE_DESC_NULL = SLN_TREE_DESC_NULL__;
diff --git a/src/sln_tree.c b/src/sln_tree.c
@@ -223,6 +223,12 @@ check_sln_tree_create_args
return RES_BAD_ARG;
}
+ if(args->arity < 2 || args->arity > SLN_TREE_ARITY_MAX) {
+ ERROR(sln, "%s: invalid arity %u. It must be in [2, %d]\n",
+ caller, args->arity, SLN_TREE_ARITY_MAX);
+ return RES_BAD_ARG;
+ }
+
res = check_molecules(sln, caller, args);
if(res != RES_OK) return res;
@@ -505,6 +511,7 @@ sln_tree_read
READ(&tree->args.nvertices_hint, 1);
READ(&tree->args.mesh_decimation_err, 1);
READ(&tree->args.mesh_type, 1);
+ READ(&tree->args.arity, 1);
#undef READ
exit:
@@ -548,6 +555,7 @@ sln_tree_get_desc(const struct sln_tree* tree, struct sln_tree_desc* desc)
desc->nvertices = darray_vertex_size_get(&tree->vertices);
desc->pressure = tree->args.pressure; /* [atm] */
desc->temperature = tree->args.temperature; /* [K] */
+ desc->arity = tree->args.arity;
SHTR(line_list_get_size(tree->args.lines, &desc->nlines));
nlines_adjusted = round_up_pow2(desc->nlines);
@@ -753,6 +761,7 @@ sln_tree_write
WRITE(&tree->args.nvertices_hint, 1);
WRITE(&tree->args.mesh_decimation_err, 1);
WRITE(&tree->args.mesh_type, 1);
+ WRITE(&tree->args.arity, 1);
#undef WRITE
exit:
diff --git a/src/sln_tree_build.c b/src/sln_tree_build.c
@@ -187,6 +187,154 @@ error:
}
static res_T
+merge_children_polylines
+ (struct sln_tree* tree,
+ const size_t inode)
+{
+ /* Helper constant */
+ static const size_t NO_MORE_VERTEX = SIZE_MAX;
+
+ /* Polyline vertices */
+ size_t children_ivtx[SLN_TREE_ARITY_MAX] = {0};
+ size_t vertices_range[2] = {0,0};
+ struct sln_vertex* vertices = NULL;
+ size_t ivtx = 0;
+ size_t nvertices = 0;
+
+ /* Miscellaneous */
+ unsigned i = 0;
+ res_T res = RES_OK;
+
+ /* Pre-conditions */
+ ASSERT(tree && inode < darray_node_size_get(&tree->nodes));
+ ASSERT(tree->args.arity >= 2);
+ ASSERT(tree->args.arity <= SLN_TREE_ARITY_MAX);
+
+ #define NODE(Id) (darray_node_data_get(&tree->nodes) + (Id))
+
+ /* 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) {
+ const size_t ichild = inode + NODE(inode)->offset + i;
+ nvertices += NODE(ichild)->nvertices;
+ }
+
+ /* Define the vertices range of the merged polyline */
+ vertices_range[0] = darray_vertex_size_get(&tree->vertices);
+ vertices_range[1] = vertices_range[0] + nvertices - 1/*inclusive bound*/;
+
+ /* Allocate the memory space to store the new polyline */
+ res = darray_vertex_resize(&tree->vertices, vertices_range[1]+1);
+ if(res != RES_OK) {
+ ERROR(tree->sln, "Error in merging polylines -- %s.\n", res_to_cstr(res));
+ goto error;
+ }
+ vertices = darray_vertex_data_get(&tree->vertices);
+
+ /* 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) {
+ const size_t ichild = inode + NODE(inode)->offset + i;
+ children_ivtx[i] = NODE(ichild)->ivertex;
+ }
+
+ FOR_EACH(ivtx, vertices_range[0], vertices_range[1]+1/*inclusive bound*/) {
+ double ka = 0;
+ double nu = INF;
+
+ /* The number of vertices corresponding to the current wave number for which
+ * the parent ka is calculated. It is at least equal to one, since this nu
+ * is defined by the child vertices, but may be greater if multiple children
+ * share the same vertex, i.e., a ka value calculated for the same nu */
+ unsigned nvertices_merged = 0;
+
+ /* Find the minimum wave number among the vertices of the child vertices
+ * that are candidates for merging */
+ FOR_EACH(i, 0, tree->args.arity) {
+ const size_t child_ivtx = children_ivtx[i];
+ if(child_ivtx != NO_MORE_VERTEX) {
+ nu = MMIN(nu, vertices[child_ivtx].wavenumber);
+ }
+ }
+ 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) {
+ const size_t child_ivtx = children_ivtx[i];
+ const struct sln_node* child = NODE(inode + NODE(inode)->offset + i);
+
+ if(child_ivtx == NO_MORE_VERTEX
+ || nu != vertices[child_ivtx].wavenumber) {
+ /* The wave number does not correspond to a vertex in the current
+ * child's mesh. Therefore, its contribution to the parent node's ka is
+ * computed */
+ ka += eval_ka(tree, child, nu);
+
+ } else {
+ /* The wave number is the one for which the child node stores a ka
+ * value. Add it to the parent node's ka value and designate the child's
+ * next vertex as a candidate for merging into the parent. The exception
+ * is when all vertices of the child have already been merged. In this
+ * case, report that the child no longer has any candidate vertices */
+ ka += vertices[child_ivtx].ka;
+ ++children_ivtx[i];
+ if(children_ivtx[i] >= child->ivertex + child->nvertices) {
+ children_ivtx[i] = NO_MORE_VERTEX;
+ }
+ ++nvertices_merged; /* Record that a vertex has been merged */
+ }
+ }
+
+ /* Setup the parent vertex */
+ vertices[ivtx].wavenumber = (float)nu;
+ vertices[ivtx].ka = (float)ka;
+
+ /* If multiple child vertices have been merged, then a single wave number
+ * corresponds to a vertex with multiple children. The number of parent
+ * vertices is therefore no longer the sum of the number of its children's
+ * vertices, since some vertices are duplicated. Hence the following
+ * adjustment, which removes the duplicate vertices. */
+ vertices_range[1] -= (nvertices_merged-1);
+ }
+
+ /* Decimate the resulting polyline */
+ res = polyline_decimate(tree->sln, darray_vertex_data_get(&tree->vertices),
+ vertices_range, (float)tree->args.mesh_decimation_err, tree->args.mesh_type);
+ if(res != RES_OK) goto error;
+
+ /* Shrink the size of the vertices */
+ darray_vertex_resize(&tree->vertices, vertices_range[1] + 1);
+
+ /* Setup the node polyline */
+ NODE(inode)->ivertex = vertices_range[0];
+ NODE(inode)->nvertices = ui64_to_ui32(vertices_range[1] - vertices_range[0] + 1);
+
+ /* It is necessary to ensure that the recorded vertices define a polyline
+ * along which any value (calculated by linear interpolation) is well above
+ * the sum of the corresponding values of the polylines to be merged. However,
+ * although this is guaranteed by definition for the vertices of the polyline,
+ * numerical uncertainty may nevertheless introduce errors that violate this
+ * criterion. Hence the following adjustment, which slightly increases the ka
+ * of the mesh so as to guarantee this constraint between the mesh of a node
+ * and that of its children */
+ if(tree->args.mesh_type == SLN_MESH_UPPER) {
+ FOR_EACH(ivtx, vertices_range[0], vertices_range[1]+1/*inclusive bound*/) {
+ const double ka = vertices[ivtx].ka;
+ vertices[ivtx].ka = (float)(ka + MMAX(ka*1e-2, 1e-6));
+ }
+ }
+
+ #undef NODE
+
+exit:
+ return res;
+error:
+ goto exit;
+}
+
+static res_T
build_polylines(struct sln_tree* tree)
{
size_t stack[STACK_SIZE*2];
@@ -230,8 +378,12 @@ 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];
diff --git a/src/test_sln_tree.c b/src/test_sln_tree.c
@@ -183,6 +183,7 @@ test_tree
CHK(desc.depth == (unsigned)log2i((int)round_up_pow2(desc.nlines)));
CHK(desc.pressure == tree_args.pressure);
CHK(desc.temperature == tree_args.temperature);
+ CHK(desc.arity == tree_args.arity);
CHK(node = sln_tree_get_root(tree));
CHK(node != NULL);
@@ -307,7 +308,15 @@ check_tree_equality
CHK(sln_tree_get_desc(tree2, &desc2) == RES_OK);
CHK(desc1.max_nlines_per_leaf == desc2.max_nlines_per_leaf);
CHK(desc1.mesh_decimation_err == desc2.mesh_decimation_err);
+ CHK(desc1.mesh_type == desc2.mesh_type);
CHK(desc1.line_profile == desc2.line_profile);
+ CHK(desc1.pressure == desc2.pressure);
+ CHK(desc1.temperature == desc2.temperature);
+ CHK(desc1.depth == desc2.depth);
+ CHK(desc1.nlines == desc2.nlines);
+ CHK(desc1.nvertices == desc2.nvertices);
+ CHK(desc1.nnodes == desc2.nnodes);
+ CHK(desc1.arity == desc2.arity);
stack[istack++] = NULL;
stack[istack++] = NULL;
