Trying to implement heapless, singly-linked list. Struggling to keep everything in stack. Everytime I use a node in if statement it drops my node

help
#1

i been trying to implement a singly linked list on a microcontroller, so cant use use heap, cant use heapless crate due to my list size is unknown. solution i thought is everytime i need a node i will create it in bottom function stack, and everywhere else i will use reference to it. implementation is somewhat like this.

struct Node<'a, T>{
    object: RefCell<T>,
    next: Option<&'a Node<'a, T>>
}
struct List{
    head: Option<&'a Node<'a, T>>
}
impl<'a, T:Object> List<'a, T>{
    pub fn push(&mut self, node: &'a Node<'a, T>){
   ¦   self.head = Some(node)
}

Now in main function i am creating Node and pushing a reference to that node to List, like

let head = None;
let node = Node{ RefCell::new(object), next: None};
head.push(&node);

Until this everything is working fine, but the problem is when i conditionals or loops, i have problem like let say i want to create 5 nodes then if i create those nodes inside of for loop then at the end of the loop nodes will be dropped and cant have dangling pointers.

i failed to find workaround this, any help?
if any way i can use conditionals without dropping my Nodes at the end of block.
ex:

            let node;
            if node_count > 0{
                node = Node::new(
                    Object::new(..<some values>..),
                    node_list.head.take()
                    );
               // Here i get borrowed value does not live long enough
                node_list.push(&enemy);
            };

I have to find a way to it, its a dead end for my personal project :worried:

#2

If you don’t have access to an allocator, you must decide in advance how much memory to use for everything and hardcode that into your program. You probably want a heapless::Vec— The capacity you give it is the maximum number of elements, but it can store fewer (or even zero).

To make the stack do what you’re trying to here, you need a new stack frame for each item you’re adding, and that means using recursion instead of loops. You’ll also need to use the list from within the innermost recursive function call, because each function’s memory is released as soon as it returns, and the corresponding list node with it.

This is technically possible, but will be extremely tricky to pull off and produce nigh-incomprehensible code.

2 Likes
#3

I suspect that you do actually know the size of your linked list.

You certainly know the maximum size it can be, it's whatever few KB of RAM your micro-controller has. Presumably you don't want your micro-controller application to crash when it runs out of RAM trying to create a linked list of unbounded size, so you will be putting some limit on size in place.

Ergo you know the size your linked list will be because you define it.

As you have noticed creating items on the stack is not the way to go given that the disappear when leaving the scope they were created in. This is true of other languages typically used in micro-controller, C, C++, Ada, whatever.

So use the heapless ::Vec.

Or create your linked list as a bunch of nodes in a Vec and use their indices within the Vec as the "references" forming the list, instead of using actual references. As discussed here: When is a linked list not a linked list?

Such a linked-list inside a Vec could save you valuable RAM space. Those "next" indices in the nodes only need be a byte for a list of up to 256 elements. Or perhaps 16 bits.

1 Like