star-line

commit ff95468f9c6fa72f95bdbf598df3dd7a73a7a0e1
parent 3c773e852fbc213e00b3c2309f3e1192d7006352
Author: Vincent Forest <vincent.forest@meso-star.com>
Date:   Fri, 22 Apr 2022 15:53:11 +0200

Fix invalid memory access in tree building

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

1 file changed, 23 insertions(+), 21 deletions(-)
diff --git a/src/sln_tree_build.c b/src/sln_tree_build.c
@@ -29,14 +29,15 @@ tree_build
    const struct sln_tree_create_args* args)
 {
   size_t stack[64];
-  struct node* node = NULL;
   size_t istack = 0;
+  size_t inode;
   size_t nlines;
   res_T res = RES_OK;
 
   ASSERT(tree && args);
   SHTR(lines_view_get_size(tree->lines_view, &nlines));
 
+  #define NODE(Id) (darray_node_data_get(&tree->nodes) + (Id))
   #define CREATE_NODE {                                                        \
     res = darray_node_push_back(&tree->nodes, &NODE_NULL);                     \
     if(res != RES_OK) goto error;                                              \
@@ -45,48 +46,49 @@ tree_build
   CREATE_NODE; /* Alloc the root node */
 
   /* Setup the root node */
-  node = darray_node_data_get(&tree->nodes);
-  node->range[0] = 0;
-  node->range[1] = nlines - 1;
+  NODE(0)->range[0] = 0;
+  NODE(0)->range[1] = nlines - 1;
+  inode = 0;
 
-  while(node) {
-    const size_t inode = (size_t)(node - darray_node_cdata_get(&tree->nodes));
-    nlines = node->range[1] - node->range[0] + 1; /* #lines into the node */
+  while(inode != SIZE_MAX) {
+    /* #lines into the node */
+    nlines = NODE(inode)->range[1] - NODE(inode)->range[0] + 1;
 
     /* Make a leaf */
-    if(nlines < args->max_nlines_per_leaf) {
-      node->offset = -1;
-      node = istack ? darray_node_data_get(&tree->nodes)+stack[--istack] : NULL;
+    if(nlines <= args->max_nlines_per_leaf) {
+      NODE(inode)->offset = -1;
+      inode = istack ? stack[--istack] : SIZE_MAX;
 
     /* Split the node  */
     } else {
       const size_t split = (nlines + 1/*ceil*/)/2; /* Median split */
-      struct node* children = NULL;
 
       /* Compute the index toward the 2 children (first is the left child,
        * followed by the righ child) */
       size_t ichildren = darray_node_size_get(&tree->nodes);
 
-      /* Define the offset from the current node to its children */
+      ASSERT(NODE(inode)->range[0] <= split);
+      ASSERT(NODE(inode)->range[1] >= split);
       ASSERT(ichildren > inode);
-      node->offset = (int64_t)(ichildren - inode);
+
+      /* Define the offset from the current node to its children */
+      NODE(inode)->offset = (int64_t)(ichildren - inode);
 
       CREATE_NODE; /* Alloc left child */
       CREATE_NODE; /* Alloc right child */
 
-      children = darray_node_data_get(&tree->nodes)+ichildren;
-
       /* Setup the left child  */
-      children[0].range[0] = node->range[0];
-      children[0].range[1] = split-1;
+      NODE(ichildren+0)->range[0] = NODE(inode)->range[0];
+      NODE(ichildren+0)->range[1] = split-1;
       /* Setup the right child */
-      children[1].range[0] = split;
-      children[1].range[1] = node->range[1];
+      NODE(ichildren+1)->range[0] = split;
+      NODE(ichildren+1)->range[1] = NODE(inode)->range[1];;
 
-      node = children + 0; /* Make left children the current node */
-      stack[istack] = ichildren + 1; /* Push the right children */
+      inode = ichildren + 0; /* Make the left child current node */
+      stack[istack] = ichildren + 1; /* Push the right child */
     }
   }
+  #undef NODE
   #undef CREATE_NODE
 
 exit: