Creating a linearized tree with inlined arrays

[cognominal]

I am brand new to rust but was proficient in C.
I want to generate wasm from rust but that is probably not
the problem here. I want to create on the fly a linearized relocatable tree data structure created of
chunks, themselves mostly constituted of inlined arrays. The catch: I know the size of arrays only at time creation of a chunk. I guess the rest I can figure out.
Once created the tree and its content are read only.
In the pseudo code below, I restrict myself to one array per chunk.

Next, I will need to traverse these trees from JavaScript.
But I guess I must go thru Implementing Life - Rust and WebAssembly
to be capable to post any sensible question on that second issue.

use std::alloc::{alloc, dealloc, Layout};

Struct {
  U32 offset_sibling;
  U32 offset parent;
  U32 array1[sizearray1];
}

let layout = Layout::new::<u16>();
let tree root = alloc(layout);


fn create_son_node(u32 parent_offset, u32 sizearray1 ) { …  }
fn create_sibling(u32 sibling_offset, u32 sizearray1) { … }

If the tree grows too big, I will use a realloc but the whole
structure is connex.
If someone can give me the code for create_son_node
I would be unstuck. or better even point me to the relevant docs. Thx.

[H2CO3]

I don't see any pertinent implementation in the snippet you posted – what is it you have written so far, and in what way didn't it work?

[cognominal]

This is pseudo code to explain the data structures. I even mistakenly typed vars with C syntax.

Probably the following page address my problem : creating
a struct instance with an array of size known only at
creation time.

Exotically Sized Types - The Rustonomicon

[cognominal]

rust permits to directly address memory.
So is not because I initially thought I could implement it using structs
à la C that it had to be done that way.
Anyway, I already gave a hint how I would expose the result as an API.

This is a classic case of, I have a problem, I will use that (regex, structs, whatever), now I have two problems.

[kornel]

Do I understand correctly that you want to emulate C's "flexible array member"?

struct foo {
   int head;
   int data[];
}

If so, then Rust can do it, but it's not easy.

You have two options:

1. Dynaically sized types

2. Use allocator directly, as you're trying here. The last field will have to be array1: [u32/*node type*/; 0], but you won't be able to use it directly due to 0 size. Use pointer arithmetic to get the rest. Be careful about moves truncating it - I suggest wrapping it in a newtype that holds a raw pointer to data. You will also need to store the length (sizearray1) in the struct, because freeing needs the length.

Anyway, it's a lot of work. From the not-quite-correct syntax of your post I assume you're new to Rust. I do not recommend trying to do this until you're more experienced. It will be a lot of hassle, require advanced features, and result will be complex, full of unsafe code, and not even fast or efficient as you hope.

A practical and easy solution is to use something like:

struct Node {
  sibling: u32, parent: u32,
}

struct Tree {
   nodes: Vec<Node>,
}

so that the offsets everywhere all point to nodes at the root, rather than their own field. You will have only one contiguous allocation, instead of allocation per node. That saves you even more allocations! And has even better locality.

If you want node's children stored together in the node, then this also works:

struct Node {
  sibling: u32, parent: u32,
  child_nodes: Vec<Node>, 
}

Note that this makes one allocation, not two. That's because child_nodes: Vec<Node> stores Node by value, not as Vec<Box<Node>>, so the total number of allocations is the same or even smaller than your solution! (smaller, because empty Vec at leaf nodes does not allocate).

[cognominal]

Thx for the information. So far I never wrote any rust code so starting by dealing with complex data structures in wasm is a stretch.
At this point I am exploring the options. Rust support for wasm seems interesting. But I am not sure everything is supported with the wasm backend.