Linked list in Rust with nodes owned by HashMap

Question

I am trying to construct a bunch of linked-list data-structure in Rust, but different than other examples I've seen, I'd like the actual nodes to be owned by a HashMap. It seems like if a HashMap owns the nodes, then lifetimes shouldn't be an issue and this should allow me to reference the next element in my list by Option<&List> rather than Box<List> (as done in Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time ). However, I am getting mutable/immutable borrow errors.

My minimal example is:

use std::collections::HashMap;

#[derive(Debug, Default)]
struct List<'a> {
    data: i32,
    child: Option<&'a List<'a>>,
}

fn main() {
    let mut map = HashMap::<i32, List>::new();

    let data = vec![(1, None), (2, Some(1))];

    for (data, child) in data.iter() {
        println!("Inserting {:?} with child {:?}", data, child);
        let new_node = map.entry(*data).or_insert(List {
            data: *data,
            child: None,
        });
        match child {
            Some(child_data) => {
                map.get(child_data).map(|child_node| {
                    new_node.child = Some(child_node);
                });
            }
            None => {}
        }
    }

    println!("Data: {:?}", map);
}

Which gives the error

error[E0502]: cannot borrow `map` as mutable because it is also borrowed as immutable
  --> src/main.rs:16:24
   |
16 |         let new_node = map.entry(*data).or_insert(List {
   |                        ^^^^^^^^^^^^^^^^ mutable borrow occurs here
...
22 |                 map.get(child_data).map(|child_node| {
   |                 --- immutable borrow occurs here

error[E0502]: cannot borrow `map` as immutable because it is also borrowed as mutable
  --> src/main.rs:22:17
   |
16 |         let new_node = map.entry(*data).or_insert(List {
   |                        --- mutable borrow occurs here
...
22 |                 map.get(child_data).map(|child_node| {
   |                 ^^^ immutable borrow occurs here
23 |                     new_node.child = Some(child_node);
   |                     -------- mutable borrow later captured here by closure

My question is, is this error a result of me not setting up the List struct correctly, a result of the way I am using HashMap, and how can I fix it?

The error is correct. If you have a node that points to itself (e.g. (1, Some(1)), then new_node and map.get(...) will alias. — Lambda Fairy
Also, HashMap is backed by a growable array. Every time the hashtable fills up, it will reallocate and invalidate all existing references. So what you're doing is fundamentally impossible. — Lambda Fairy
So I still need to Box things and send both List and HashMap the boxed type? — Jason Siefken

Lambda Fairy Lambda Fairy · Accepted Answer · 2021-01-04T04:35:38

The error is correct:

If you have a node that refers to itself (e.g. (1, Some(1))), then new_node and child_node will point to the same value. This is illegal as new_node is a mutable (read: exclusive) reference.
HashMap, like Vec, is backed by an array. When the HashMap fills up, it will reallocate this array, invalidating all existing references.
HashMap lets you delete entries. This will cause dangling pointers if a deleted entry is referenced elsewhere.

Here are a few solutions to this problem:

Store the index instead. This is the simplest solution, and is recommended most of the time.
```
struct List {
  data: i32,
  child: Option<i32>,
}
```

Use an append-only collection like elsa::FrozenMap. This only solves problem 3, but Box and Cell should handle the rest:

use elsa::FrozenMap;

struct List<'a> {
  data: i32,
  child: Cell<Option<&'a List<'a>>>,
}

fn main() {
  let map = FrozenMap::<i32, Box<List>>::new();

  // ...
}

Linked list in Rust with nodes owned by HashMap

1 Answers