Why I get unexpected pointer address when I try to find node and the node's pointer from my linked list node?

help
1

I implemented a linked list. I want to check the heap address where the nodes are stored.

use spin::Mutex;

#[derive(Debug)]
struct ListNode {
    next: Option<&'static mut ListNode>,
    val: Option<usize>,
}

#[derive(Debug)]
struct Head {
    list_head: Option<&'static mut ListNode>,
}

static HEAD: Mutex<Head> = Mutex::new(Head { list_head: None });

impl Head {
    // Input test data
    unsafe fn init(&mut self) {
        for i in 0..3 {
            let ptr = Box::into_raw(Box::new([ListNode::new(0)])) as *mut ListNode;
            let n = ListNode {
                next: self.list_head.take(),
                val: Some(10 * (i + 1)),
            };
            println!("ptr: {:x?} val: {:?}", ptr, n.val);
            ptr.write(n);
            self.list_head = Some(&mut *ptr);
        }
    }

    // find ListNode having val. Show the pointer if found the ListNode.
    fn find(&self, val: usize) -> &Option<&'static mut ListNode> {
        let mut n = &self.list_head;
        while n.is_none() || n.as_ref().unwrap().val != Some(val) {
            n = &n.as_ref().unwrap().next;
        }
        if n.is_some() && n.as_ref().unwrap().val == Some(val) {
            println!("Found {:?} at {:p}", val, n);
            return n;
        }
        unreachable!();
    }
}

impl ListNode {
    fn new(val: usize) -> Self {
        ListNode {
            next: None,
            val: Some(val),
        }
    }
}

fn main() {
    unsafe {
        HEAD.lock().init();
        println!("{:?}", HEAD.lock());
    }
    HEAD.lock().find(10);
    HEAD.lock().find(20);
    HEAD.lock().find(30);
}

Here is the output.
However, it is an unexpected result because the address where each node is stored doesn't match the address which is the result of find(val).

ptr: 0x55f43e63cba0 val: Some(10)
ptr: 0x55f43e63cbc0 val: Some(20)
ptr: 0x55f43e63cbe0 val: Some(30)
Head { list_head: Some(ListNode { next: Some(ListNode { next: Some(ListNode { next: None, val: Some(10) }), val: Some(20) }), val: Some(30) }) }
Found 10 at 0x55f43e63cbc0   <<<--- I expect Some(20) is stored at this address.
Found 20 at 0x55f43e63cbe0   <<<--- I expect Some(30) is soored at this address.
Found 30 at 0x55f43cdba038   <<<--- What is this address ???

In my understanding, The result should be like below...

ptr: 0x55f43e63cba0 val: Some(10)
ptr: 0x55f43e63cbc0 val: Some(20)
ptr: 0x55f43e63cbe0 val: Some(30)
Head { list_head: Some(ListNode { next: Some(ListNode { next: Some(ListNode { next: None, val: Some(10) }), val: Some(20) }), val: Some(30) }) }
Found 10 at 0x55f43e63cba0
Found 20 at 0x55f43e63cbc0
Found 30 at 0x55f43e63cbe0

Could you tell me why this result happened, please?

Since I'm a beginner at Rust, I suspect I may or not overlook some basic things...

Thank you

2

Your n is not a pointer to the node itself, but has type &Option<&'static mut ListNode>. When you print that as a pointer, you're printing the address of the next field (or list_head) that points to the node you actually want.

Each of your n.as_ref().unwrap() calls will give you &&'static mut ListNode, so you could dereference that once to get the actual node pointer. A little more directly, n.as_deref().unwrap() will dereference the inner type to give you &ListNode.

3 Likes
3

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.