Yet another linked list: insert

help
1

I realize this is maybe a tired topic but I haven't yet seen a satisfactory solution for my problem. I've read that there are other approaches to take, arenas, etc etc. But my goal is to allocate my nodes in one thread then push them into another thread using a sync_channel, then add them, sometimes with insertion sort, into a list in another thread where I cannot allocate ["realtime" audio]. None of the other approaches I've seen help me there.

I've taken the fifth, double linked list, example from the too many lists blog post and extracted the node allocation from the push and now I want to do insert. I realize that it is problematic but I am not afraid to use unsafe, I'm just not exactly sure how:

https://github.com/x37v/rust-llist/blob/feature/insert/src/lib.rs#L72

I can get to the location I need to insert but as my reference isn't mutable I can't modify it, but if I to traverse with a mutable reference I cannot advance as I have to use the mutable reference to update the mutable reference.

It seems like what I have is almost there but I just need that last little bit of help. Do I need UnsafeCell to be able to update a link within my list? Is there some mem op I can do to traverse and keep my link mutable, or some sneaky unsafe cast I can do to take my immutable link and make it mutable?

2

std::mem::transmute() is very powerful and exceptionally dangerous (I wouldn't vouch for memory/data race safety of the following):

...
        } else {
            {   
                let mut cur = &self.head;
                while let &Some(ref node) = cur {
                    println!("TRAVERSE");
                    if func(&new_node, node) {
                        println!("INSERT HERE");
                        let node: &mut Box<Node<T>> = unsafe { std::mem::transmute(node as *const _) };
                        std::mem::swap(&mut new_node.elem, &mut node.elem);
                        std::mem::swap(&mut new_node.next, &mut node.next);
                        if self.tail == &mut **node as *mut _ {
                            self.tail = &mut *new_node as *mut _;
                        }
                        node.next = Some(new_node);
                        return;
                    }
                    cur = &node.next;
                }
            }
            println!("PUSH BACK FROM INSERT");
            self.push_back(new_node);
        }
...
2 Likes
3

Transmuting a & to &mut is considered UB, although there's some debate (I believe) about where exactly the UB steps in (at the point of transmuting or when writes are done through the reference). In this case, however, there's a write of node.next, which I think is UB on paper.

The good news is doing a mutable borrow, as @xnor wanted initially, works with NLL: playground

1 Like
4

Wow @inejge gave me what I think I was asking for, but @vitalyd gave me what I really wanted! FANTASTIC, thank you both.
I thought I might use NLL and actually tried it but I was trying to manipulate the link [cur] and not the node. Swapping the contents of the node and then pushing the swapped node behind the original one makes a lot of sense.

5

@vitalyd I'm curious. Was this insert not possible before NLL or was there another way to do it safely?

6

I don't think there was (is) a way to do it safely before NLL because borrowck does not track borrows coarsely enough (i.e. it's all lexical). Certainly just removing #![feature(nll)] from that code shows where the pre-NLL borrowck starts getting angry.

1 Like
7

Yeah, I started trying without NLL so I'm aware of the anger there :slight_smile: Thank you NLL! Thanks @vitalyd !