star-line

commit 345d66bad759bd3b7ddbe6fc76740655ab30f1c4
parent e3c0d4d325b0b561bb9baa61dec0d11b7f1dba96
Author: Vincent Forest <vincent.forest@meso-star.com>
Date:   Wed, 27 Apr 2022 11:22:36 +0200

Test tree data

Diffstat:
M
src/test_sln_tree.c
 | 
125
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 125 insertions(+), 0 deletions(-)
diff --git a/src/test_sln_tree.c b/src/test_sln_tree.c
@@ -17,7 +17,10 @@
  * along with this program. If not, see <http://www.gnu.org/licenses/>. */
 
 #include "sln.h"
+
 #include <star/shtr.h>
+
+#include <rsys/algorithm.h>
 #include <rsys/math.h>
 #include <rsys/mem_allocator.h>
 
@@ -195,6 +198,112 @@ write_shtr_lines
 /*******************************************************************************
  * Helper function
  ******************************************************************************/
+static int
+cmp_line(const void* key, const void* item)
+{
+  const struct shtr_line* line0 = key;
+  const struct shtr_line* line1 = item;
+  CHK(key && item);
+       if(line0->wavenumber < line1->wavenumber) return -1;
+  else if(line0->wavenumber > line1->wavenumber) return +1;
+  else return 0;
+}
+
+/* Return the index of the line in the lines_list or SIZE_MAX if the line does
+ * not exist */
+static INLINE size_t
+find_line
+  (const struct shtr_lines_list* lines_list,
+   const struct shtr_line* line)
+{
+  const struct shtr_line* list = NULL;
+  const struct shtr_line* found = NULL;
+  size_t iline, nlines;
+
+  CHK(shtr_lines_list_get(lines_list, &list) == RES_OK);
+  CHK(shtr_lines_list_get_size(lines_list, &nlines) == RES_OK);
+
+  /* Dichotomous search wrt the wavenumber of lines */
+  found = search_lower_bound
+    (line, list, nlines, sizeof(struct shtr_line), cmp_line);
+  if(!found) return SIZE_MAX;
+
+  /* Find a line with the same wavenumber as the one searched for and whose
+   * other member variables are also equal to those of the line searched for */
+  CHK(found >= list);
+  iline = (size_t)(found - list);
+  while(list[iline].wavenumber == line->wavenumber
+    && !shtr_line_eq(&list[iline], line)
+    && iline < nlines) {
+    ++iline;
+  }
+
+  if(shtr_line_eq(&list[iline], line)) {
+    return iline;
+  } else {
+    return SIZE_MAX;
+  }
+}
+
+static void
+check_tree
+  (const struct sln_tree* tree,
+   const size_t nlines_per_leaf,
+   struct shtr_lines_list* lines_list)
+{
+  #define STACK_SIZE 64
+  const struct shtr_line* list = NULL;
+  const struct sln_node* stack[STACK_SIZE] = {NULL};
+  size_t istack = 0;
+  const struct sln_node* node = NULL;
+
+  char* found_lines = NULL;
+  size_t found_nlines = 0;
+  size_t lines_list_sz;
+
+  CHK(shtr_lines_list_get_size(lines_list, &lines_list_sz) == RES_OK);
+  CHK(shtr_lines_list_get(lines_list, &list) == RES_OK);
+
+  CHK(found_lines = mem_calloc(lines_list_sz, sizeof(char)));
+
+  node = sln_tree_get_root(tree);
+  while(node) {
+    if(!sln_node_is_leaf(node)) {
+      CHK(sln_node_get_lines_count(node) > nlines_per_leaf);
+
+      ASSERT(istack < STACK_SIZE);
+      stack[istack++] = sln_node_get_child(node, 1); /* Push the child 1 */
+      node = sln_node_get_child(node, 0); /* Handle the child 0 */
+
+    } else {
+      size_t iline, nlines;
+
+      nlines = sln_node_get_lines_count(node);
+      CHK(nlines <= nlines_per_leaf);
+      FOR_EACH(iline, 0, nlines) {
+        const struct shtr_line* line = NULL;
+        size_t found_iline = 0;
+        CHK(sln_leaf_get_line(tree, node, iline, &line) == RES_OK);
+        found_iline = find_line(lines_list, line);
+        CHK(found_iline != SIZE_MAX); /* Line is found */
+
+        if(!found_lines[found_iline]) {
+          found_nlines += 1;
+          found_lines[found_iline] = 1;
+        }
+      }
+
+      node = istack ? stack[--istack] : NULL; /* Pop the next node */
+    }
+  }
+
+  /* Check that all lines are found */
+  CHK(found_nlines == lines_list_sz);
+
+  mem_rm(found_lines);
+  #undef STACK_SIZE
+}
+
 static void
 test_tree
   (struct sln_device* sln,
@@ -203,6 +312,8 @@ test_tree
 {
   struct sln_tree_create_args tree_args = SLN_TREE_CREATE_ARGS_DEFAULT;
   struct sln_tree* tree = NULL;
+  const struct sln_node* node = NULL;
+  const struct shtr_line* line = NULL;
 
   tree_args.metadata = metadata;
   tree_args.lines = lines_list;
@@ -226,6 +337,20 @@ test_tree
   tree_args.max_nlines_per_leaf = 1;
   CHK(sln_tree_create(sln, &tree_args, &tree) == RES_OK);
 
+  CHK(node = sln_tree_get_root(tree));
+  while(!sln_node_is_leaf(node)) {
+    node = sln_node_get_child(node, 0);
+  }
+  CHK(sln_node_get_lines_count(node) <= tree_args.max_nlines_per_leaf);
+  CHK(sln_leaf_get_line(NULL, node, 0, &line) == RES_BAD_ARG);
+  CHK(sln_leaf_get_line(tree, NULL, 0, &line) == RES_BAD_ARG);
+  CHK(sln_leaf_get_line(tree, node, tree_args.max_nlines_per_leaf+1, &line)
+    == RES_BAD_ARG);
+  CHK(sln_leaf_get_line(tree, node, 0, NULL) == RES_BAD_ARG);
+  CHK(sln_leaf_get_line(tree, node, 0, &line) == RES_OK);
+
+  check_tree(tree, tree_args.max_nlines_per_leaf, lines_list);
+
   CHK(sln_tree_ref_get(NULL) == RES_BAD_ARG);
   CHK(sln_tree_ref_get(tree) == RES_OK);
   CHK(sln_tree_ref_put(NULL) == RES_BAD_ARG);