Arena Allocated Doubly Linked List PANIC


#1

I have tried implementing a doubly linked list. To avoid lifetime issues, I am starting the arena allocated way.

Currently, I have just finished the addNode() function which adds the Node a the very last position in the list (not arena).

However I experience panic in the very beginning of the runtime of the program, which is nevertheless just a for loop of adding usize elements to the list. I have tried BACKTRACE=1, but I haven’t understand the information. Can you help me please?

use std::mem;

struct DoublyLinkedList<T> {
    arena : Vec<ListE<T>>,
    arena_size : usize,
    gap : Vec<Option<usize>>,
    gape_size : usize,
    gap_iterator : usize,
    gap_gap_iterator : usize,
    list_size : usize,
    head : Option<usize>,
    tail : Option<usize>
}

enum ListE<T> {
    Null,
    Node{value : T, next : Option<usize>, previous : Option<usize>}
}

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

    fn node(val : T, nxt : Option<usize>, prv : Option<usize>) -> ListE<T> {
        ListE::Node{
            value : val,
            next : nxt,
            previous : prv
        }
    }
}

impl<T> DoublyLinkedList<T> {

    fn new() -> DoublyLinkedList<T> {
        DoublyLinkedList{
            arena : Vec::new(),
            arena_size : 0,
            gap : Vec::new(),
            gape_size : 0,
            gap_iterator : 0,
            gap_gap_iterator : 0,
            list_size : 0,
            head : None,
            tail : None
       }
    }

    fn addNode(&mut self, val : T) {
        let mut arena_id : usize = 0;
        let mut new_entry : bool = false;
        let mut prv : Option<usize> = None;
        match self.tail {
            Some(tail_id) => {
                match self.gap[self.gap_iterator] {
                    Some(gap_id) => {
                        arena_id = gap_id;
                        new_entry = false;
                        prv = Some(tail_id);
                        match self.arena[tail_id] {
                            ListE::Node{ref value, ref mut next, ref previous} => {
                                mem::replace(next, Some(gap_id));
                                self.tail = Some(gap_id);
                            }
                            ListE::Null => {
                            }
                        }
                        self.gap[self.gap_iterator] = None;
                        self.gap_iterator = self.gap_iterator + 1;
                    }
                    None => {
                        arena_id = self.list_size;
                        new_entry = true;
                        prv = None;
                        match self.arena[tail_id] {
                            ListE::Node{ref value, ref mut next, ref previous} => {
                                mem::replace(next, Some(self.list_size));
                                self.tail = Some(self.list_size);
                        }
                            ListE::Null => {
                            }
                        }
                    }
                }
            }
            None => {
                arena_id = 0;
                prv = Some(0);
                self.head = Some(0);
                self.tail = Some(0);
            }
        }
        if new_entry {
            self.arena.push(ListE::Node{value : val, next : None, previous : prv});
            self.arena_size = self.arena_size + 1;
        }
        else {
            self.arena[arena_id] = ListE::Node{value : val, next : None, previous : prv};
        }
        self.tail = Some(arena_id);
        self.list_size = self.list_size + 1;
    }

}

fn main() {
    let mut dblyLnkdLst : DoublyLinkedList<usize> = DoublyLinkedList::new();
    for i in 0..10 {
        dblyLnkdLst.addNode(i);
    }
    match dblyLnkdLst.head {
        Some(mut node_id) => {
            while true {
                match dblyLnkdLst.arena[node_id] {
                    ListE::Node{ref mut value, ref mut next, ref mut previous} => {
                        match *next {
                            Some(next_id) => {
                                match *previous {
                                    Some(prev_id) => {
                                        print!("<-{}-{}-{}->", prev_id, value, next_id);
                                    }
                                    None => {
                                        print!("{}-{}->", value, next_id);
                                    }
                                }
                                node_id = next_id;
                            }
                            None => {
                                match *previous {
                                    Some(prev_id) => {
                                        print!("<-{}-{}", prev_id, value);
                                    }
                                    None => {
                                        print!("{}", value);
                                    }
                                }
                                break;
                            }
                        }
                    }
                    ListE::Null => {
                        break;
                    }
                }
            }
        }
        None =>{
            
        }
    }
}

#2

Reducing your code to

let mut dblyLnkdLst : DoublyLinkedList<usize> = DoublyLinkedList::new();
dblyLnkdLst.addNode(0);

reproduces the same panic, so I suggest starting there.

In particular, it looks like new_entry never gets set to true when there’s no tail, which seems like a clear problem to me.


#3

I have looked at the code and I found some mistakes. So this is the new one:

use std::mem;

struct DoublyLinkedList<T> {
    arena : Vec<ListE<T>>,
    arena_size : usize,
    gap : Vec<Option<usize>>,
    gape_size : usize,
    gap_iterator : usize,
    gap_gap_iterator : usize,
    list_size : usize,
    head : Option<usize>,
    tail : Option<usize>
}

enum ListE<T> {
    Null,
    Node{value : T, next : Option<usize>, previous : Option<usize>}
}

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

    fn node(val : T, nxt : Option<usize>, prv : Option<usize>) -> ListE<T> {
        ListE::Node{
            value : val,
            next : nxt,
            previous : prv
        }
    }
}

impl<T> DoublyLinkedList<T> {

    fn new() -> DoublyLinkedList<T> {
        DoublyLinkedList{
            arena : Vec::new(),
            arena_size : 0,
            gap : Vec::new(),
            gape_size : 0,
            gap_iterator : 0,
            gap_gap_iterator : 0,
            list_size : 0,
            head : None,
            tail : None
       }
    }

    fn addNode(&mut self, val : T) {
        let mut arena_id : usize = 0;
        let mut new_entry : bool = false;
        let mut prv : Option<usize> = None;
        match self.tail {
            Some(tail_id) => {
                match self.gap[self.gap_iterator] {
                    Some(gap_id) => {
                        arena_id = gap_id;
                        new_entry = false;
                        prv = Some(tail_id);
                        match self.arena[tail_id] {
                            ListE::Node{ref value, ref mut next, ref previous} => {
                                mem::replace(next, Some(gap_id));
                                self.tail = Some(gap_id);
                            }
                            ListE::Null => {
                            }
                        }
                        self.gap[self.gap_iterator] = None;
                        self.gap_iterator = self.gap_iterator + 1;
                    }
                    None => {
                        arena_id = self.list_size;
                        new_entry = true;
                        prv = Some(tail_id);
                        match self.arena[tail_id] {
                            ListE::Node{ref value, ref mut next, ref previous} => {
                                mem::replace(next, Some(self.list_size));
                                self.tail = Some(self.list_size);
                        }
                            ListE::Null => {
                            }
                        }
                    }
                }
            }
            None => {
                new_entry = true;
                arena_id = 0;
                prv = Some(0);
                self.head = Some(0);
                self.tail = Some(0);
            }
        }
        if new_entry {
            let new_node : ListE<T> = ListE::Node{value : val, next : None, previous : prv};
            self.arena.push(new_node);
            self.arena_size = self.arena_size + 1;
        }
        else {
            let new_node : ListE<T> = ListE::Node{value : val, next : None, previous : prv};
            self.arena[arena_id] = new_node;
        }
        self.tail = Some(arena_id);
        self.list_size = self.list_size + 1;
    }

}

fn main() {
    let mut dblyLnkdLst : DoublyLinkedList<usize> = DoublyLinkedList::new();
    dblyLnkdLst.addNode(42);
    /*
    for i in 0..10 {
        dblyLnkdLst.addNode(i);
    }
    */
}

Now the first Addition does work:

dblyLnkdLst.addNode(42);

However when I add the other statement:

    dblyLnkdLst.addNode(42);
    for i in 0..10 {
        dblyLnkdLst.addNode(i);
    }

The Compiler says this:

-- mode: cargo-process; default-directory: “~/Dropbox/programming/rust/bisschien/DoublyLinkedList/current/DoublyLinkedList/src/” --
Cargo-Process started at Mon Jan 9 01:06:07

cargo run
Finished debug [unoptimized + debuginfo] target(s) in 0.0 secs
Running /home/ahmed/Dropbox/programming/rust/bisschien/DoublyLinkedList/current/DoublyLinkedList/target/debug/DoublyLinkedList
thread ‘main’ panicked at ‘index out of bounds: the len is 0 but the index is 0’, …/src/libcollections/vec.rs:1307
note: Run with RUST_BACKTRACE=1 for a backtrace.

Cargo-Process exited abnormally with code 101 at Mon Jan 9 01:06:07

Excuse me: When the first statement now works, but the vec-size is still 0. Why function dosn’t the element to the list?
Please help me understand this!


#4

This fails because the gap vector is empty. If you paste the output of running with RUST_BACKTRACE=1 I can try to explain how to read it so you can make better progress debugging these failures on your own.


#5

The Backtrace output:

thread 'main' panicked at 'index out of bounds: the len is 0 but the index is 0', ../src/libcollections/vec.rs:1307
stack backtrace:
   1:     0x559afb40ee4f - std::sys::backtrace::tracing::imp::write::h6f1d53a70916b90d
   2:     0x559afb4118fd - std::panicking::default_hook::{{closure}}::h137e876f7d3b5850
   3:     0x559afb410e5a - std::panicking::default_hook::h0ac3811ec7cee78c
   4:     0x559afb4113a8 - std::panicking::rust_panic_with_hook::hc303199e04562edf
   5:     0x559afb411242 - std::panicking::begin_panic::h6ed03353807cf54d
   6:     0x559afb411180 - std::panicking::begin_panic_fmt::hc321cece241bb2f5
   7:     0x559afb411101 - rust_begin_unwind
   8:     0x559afb44636f - core::panicking::panic_fmt::h27224b181f9f037f
   9:     0x559afb446313 - core::panicking::panic_bounds_check::h19e9bbc59320a57e
  10:     0x559afb40a025 - <collections::vec::Vec<T> as core::ops::Index<usize>>::index::hffb41cb21bf4c363
                        at /buildslave/rust-buildbot/slave/stable-dist-rustc-linux/build/obj/../src/libcollections/vec.rs:1307
  11:     0x559afb40a3d8 - <DoublyLinkedList::DoublyLinkedList<T>>::addNode::hc23737b7997775dc
                        at /home/ahmed/Dropbox/programming/rust/bisschien/DoublyLinkedList/current/DoublyLinkedList/src/main.rs:56
  12:     0x559afb40aa28 - DoublyLinkedList::main::he12cee50056235b4
                        at /home/ahmed/Dropbox/programming/rust/bisschien/DoublyLinkedList/current/DoublyLinkedList/src/main.rs:115
  13:     0x559afb4193c6 - __rust_maybe_catch_panic
  14:     0x559afb4106d1 - std::rt::lang_start::h538f8960e7644c80
  15:     0x559afb40aab3 - main
  16:     0x7f273fe32290 - __libc_start_main
  17:     0x559afb408909 - _start
                        at ../sysdeps/x86_64/start.S:120

#6

Ok i got. i think I have understood the output of the backtrace. It gives me the sequential execution of the rust statements and mention the related line number. And yes it is an index bound of exception.

thanks for the help!