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, Jan 04 '21 at 03:44
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, Jan 04 '21 at 03:46
So I still need to `Box` things and send both `List` and `HashMap` the boxed type? — Jason Siefken, Jan 04 '21 at 04:15

Lambda Fairy · Accepted Answer · 2021-01-04T04:52:42.700

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 Answers1