Trying Arena DoublyLinkedList. Borrow checker problems

help
1

Hello people,

I am trying to implement a doubly linked list by using arena allocation. So I want to save all the data in a Vec.
If I want to delete some Nodes, I want save their index in a another Vec, so I can fill the gap up by the next addition.

Currently I am stuck with the burrow checker during the implementation of the addNode() function.

here is the code:

struct DoublyLinkedList<T> {
    Arena : Vec<ListE<T>>,
    ArenaLastEntry : usize,
    Gap : Vec<Option<usize>>,
    GapLastEntry : usize,
    Head : Option<usize>,
    Tail : Option<usize>
}

enum ListE<T> {
    Null,
    Node{Value: T, Next : usize, Prev : usize}
}

impl<T> ListE<T> {
    fn null() -> ListE<T> {
        ListE::Null
    }

    fn node(value : T, next : usize, prev : usize) -> ListE<T> {
        ListE::Node{
            Value : value,
            Next : next,
            Prev : prev
        }
    }
}

impl<T> DoublyLinkedList<T> {

    fn new() -> DoublyLinkedList<T> {
        DoublyLinkedList{
            Arena : Vec::new(),
            ArenaLastEntry : 0,
            Gap : Vec::new(),
            GapLastEntry : 0,
            Head : Option::None,
            Tail : Option::None
        }
    }

    fn addNode(&mut self, value : T) {
        let mut a = 0;
        if self.GapLastEntry < 0 {
            match self.Arena[self.ArenaLastEntry] {
                ListE::Node{Value,Next,Prev} => {
                   
                }
                ListE::Null =>  {
                    a = 0;
                }
            }
        }
    }

}

fn main() {
    let dblyLnkdLst : DoublyLinkedList<char> = DoublyLinkedList::new();
    println!("Hello,a world!");
}

Compiler:

-- mode: cargo-process; default-directory: "~/Dropbox/programming/rust/bisschien/DoublyLinkedList/DoublyLinkedList/src/" --
Cargo-Process started at Sat Dec 31 22:11:21

cargo build
Compiling DoublyLinkedList v0.1.0 (file:///home/ahmed/Dropbox/programming/rust/bisschien/DoublyLinkedList/DoublyLinkedList)
error[E0308]: mismatched types
--> main.rs:55:17
|
55 | ListE::Node{Value,Next,Prev} => {
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected reference, found enum ListE
|
= note: expected type &_
= note: found type ListE<_>

error[E0308]: mismatched types
--> main.rs:59:17
|
59 | ListE::Null => {
| ^^^^^^^^^^^ expected reference, found enum ListE
|
= note: expected type &_
= note: found type ListE<_>

error: aborting due to 2 previous errors

error: Could not compile DoublyLinkedList.

To learn more, run the command again with --verbose.

Cargo-Process exited abnormally with code 101 at Sat Dec 31 22:11:22

2

For this particular error, change match self.Arena[self.ArenaLastEntry] to match *self.Arena[self.ArenaLastEntry]

3

Now I get this error:

-- mode: cargo-process; default-directory: "~/Dropbox/programming/rust/bisschien/DoublyLinkedList/DoublyLinkedList/src/" --
Cargo-Process started at Sun Jan 1 00:47:12

cargo build
Compiling DoublyLinkedList v0.1.0 (file:///home/ahmed/Dropbox/programming/rust/bisschien/DoublyLinkedList/DoublyLinkedList)
error: type ListE<T> cannot be dereferenced
--> main.rs:54:19
|
54 | match *self.Arena[self.ArenaLastEntry] {
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error: aborting due to previous error

error: Could not compile DoublyLinkedList.

To learn more, run the command again with --verbose.

Cargo-Process exited abnormally with code 101 at Sun Jan 1 00:47:12

4

Ah sorry, misread the snippet. How about this (without the deref that I mentioned earlier):

[code]match self.Arena[self.ArenaLastEntry] {
ListE::Node{ref Value,ref Next,ref Prev} => {

            }
            ListE::Null =>  {
                a = 0;
            }
        }[/code]
5

That has worked, can you explain me why?

6

The index operator on a Vec returns a reference to the element - that's what the original error was: the match arms had a ListE type rather than a reference to a ListE. So, in your match arm for ListE::Node, you need to capture Value by ref so it's not moved; the other two fields don't actually need to be captured by ref since they're Copy. Does that make sense?

7

Now, yes! Thanks for the explanation. Do you got a linked about when something is moved in ruts?

Greets

Ahmed

8

I can recommend reading this about linked lists in Rust Learning Rust With Entirely Too Many Linked Lists

9

Thanks, I've already checked this. Honestly, I did it a bit superficially. However I still remember, that it isn't explained well enough "when data is moved". This I think, one of the most problems I have with rust. The Ownership model is special. So moving data is not always safe. So I want to know, when data is moved.

10

Rust moves by default. So unless you are working with references, objects are moved. An exception is Copy types, where a copy will be made instead of a move.

In the match case in this thread, you were using a destructuring pattern in one of your match arms to capture the inner fields of the ListE::Node variant. If you don't want to move a field you're capturing there, you'd need to add "ref" to the pattern to take a reference to the field.

11

I will mind it

12

Ok I have now problem. Now it is "second burrow". I've changed my Code a bit:

use std::mem;

struct DoublyLinkedList<T> {
    Arena : Vec<ListE<T>>,
    ArenaLastEntry : usize,
    Gap : Vec<Option<usize>>,
    GapLastEntry : usize,
    Head : Option<usize>,
    Tail : Option<usize>
}

/*
struct Node<T> {
    Value : T,
    Next : usize,
    Prev : usize
}

 */

enum ListE<T> {
    Null,
    Node{Value: T, Next : Option<usize>, Prev : Option<usize>}
}

impl<T> ListE<T> {
    fn null() -> ListE<T> {
        ListE::Null
    }

    fn node(value : T, next : Option<usize>, prev : Option<usize>) -> ListE<T> {
        ListE::Node{
            Value : value,
            Next : next,
            Prev : prev
        }
    }
}

impl<T> DoublyLinkedList<T> {

    fn new() -> DoublyLinkedList<T> {
        DoublyLinkedList{
            Arena : Vec::new(),
            ArenaLastEntry : 0,
            Gap : Vec::new(),
            GapLastEntry : 0,
            Head : Option::None,
            Tail : Option::None
        }
    }

    fn addNode(&mut self, value : T) {
        if self.GapLastEntry < 0 {
            match self.Arena[self.ArenaLastEntry] {
                ListE::Node{ref mut Value, ref mut Next, ref mut Prev} => {
                    mem::replace(Next, Option::Some(self.ArenaLastEntry + 1));
                    self.Arena.push(ListE::Node{Value : value, Next : None,Prev : Some(self.ArenaLastEntry)});
                    /*
                    let newNode : ListE<T> = ListE::Node{Value : value,
                                                         Next : Option::None,
                                                         Prev : Some(self.ArenaLastEntry)}
                    */
                }
                ListE::Null =>  {
                }
            }
        }
    }

}

fn main() {
    let dblyLnkdLst : DoublyLinkedList<char> = DoublyLinkedList::new();
    println!("Hello,a world!");
}

Compiler:

-- mode: cargo-process; default-directory: "~/Dropbox/programming/rust/bisschien/DoublyLinkedList/DoublyLinkedList/src/" --
Cargo-Process started at Mon Jan 2 00:32:57

cargo build
Compiling DoublyLinkedList v0.1.0 (file:///home/ahmed/Dropbox/programming/rust/bisschien/DoublyLinkedList/DoublyLinkedList)
error[E0499]: cannot borrow self.Arena as mutable more than once at a time
--> main.rs:58:21
|
55 | match self.Arena[self.ArenaLastEntry] {
| ---------- first mutable borrow occurs here
...
58 | self.Arena.push(ListE::Node{Value : value, Next : None,Prev : Some(self.ArenaLastEntry)});
| ^^^^^^^^^^ second mutable borrow occurs here
...
67 | }
| - first borrow ends here

error: aborting due to previous error

error: Could not compile DoublyLinkedList.

To learn more, run the command again with --verbose.

Cargo-Process exited abnormally with code 101 at Mon Jan 2 00:32:58

How do I solve this problem. Or do I solve such problems in general?

13

I believe this is lexical borrow in play. One easy way around this is to move the vec::push operation after the end of the match statement (and make ListE::Null case return out of the function) to allow the borrow to "expire", like so:

           match self.Arena[self.ArenaLastEntry] {
                ListE::Node{ref mut Value, ref mut Next, ref mut Prev} => {
                    mem::replace(Next, Option::Some(self.ArenaLastEntry + 1));
                }
                ListE::Null =>  { return; }
            }
            self.Arena.push(ListE::Node{Value : value, Next : None,Prev : Some(self.ArenaLastEntry)});
14

I understand what you saying:
So I just let these Branches, let's say, manipulate the future inner values, but at the very end I push the node with the values?