Warning

This post was published 135 days ago. The information described in this article may have changed.

Info

This post is auto-generated from RSS feed The Rust Programming Language Forum - Latest topics. Source: Internal mutability of objects in containers

p.s. I tried to read may topics on this but can't seem to figure out. ( lot of code below )

Background: I am implementing a HashGraph<K, V> data structure (so entry to graph is O(1))

• I am using a custom FixedSizeHashMap<K, V> that is implemented internally using Vec<Slot<K, V>> that allows me to get &V/&mut V using both K and the usize index into the Vec.
• In my HashGraph, I store the graph as FixedSizeHashMap<K, Node<V>>
• I use indexes rather than K to point to connected nodes as I can avoid repeated hash calculations and save memory when K is huge. Anyway, for my issue it is not relevant as the problem occurs either ways.
• I have successfully implemented methods such as insert(&'a mut self, key_value: (K, V), connections: Vec<(K, V)>) , and connect(&mut self, k: &K, to_keys: Vec<&K>) however, I'm having the dreaded [E0499] errors when I try to implement remove which should disconnect the edges and removes the node.

The issue is: I need to mutate multiple objects in the same collection 'simultaneously' and of course the borrow checker cant be sure they are not same nodes

here's the code:

struct Node<V> {
    _value: V,
    _connected_to: FixedSizeHashMap<usize, u32>, // stores index (into _hash_map) of nodes and weights that I connect to 
    _connected_from: FixedSizeHashSet<usize>, // stores index (into _hash_map) nodes that connect to me
}

struct FixedSizeHashGraph<K, V> {
    _hash_map: FixedSizeHashMap<K, Node<V>,
    ....
}

impl <K, V> FixedSizeHashGraph<K, V> {
....
    fn remove(&mut self, key: &K) {
        // mut borrow occurs on node being removed     vvvvvvvvvvvvvv
        let Some((node, index)) = self._hash_map._get_mut_value_and_index_of(key) else {
            return
        };

        // remove all the connections/edges
        for (to_index, _) in node._connected_to.iter_head() {
            // mut borrow occurs on connected_to nodes   vvvvvvvvvvvvvv [E0499]
            let Some(to_node) = self._hash_map._get_mut_value_at(*to_index) else {
                continue;
            };
            to_node._connected_from.remove(&index);
        }

        for (from_index, _) in node._connected_from.iter_head() {
            // mut borrow occurs on connected_from nodes   vvvvvvvvvvvvvv [E0499]
            let Some(from_node) = self._hash_map._get_mut_value_at(*from_index) else {
                continue;
            };
            from_node._connected_to.remove(&index);
        }

        // finally remove the node
        self._hash_map.remove(&key);
    }
....

Workaround: I have found the following workaround where I copy all the indexes of the nodes I need manipulate and then do the actual work. Here is what works, but this seems like a huge overhead to make "unnecessary" copies of data and unnecessary iterations:

    fn remove(&mut self, key: &K) {
        // collect all the indexes into _hash_map to nodes we will update
        let (index, to_indexes, from_indexes): (usize, Vec<usize>, Vec<usize>) =
            match self._hash_map._get_mut_value_and_index_of(key) {
                Some((node, index)) => {
                    (
                        index,
                        node._connected_to.iter_head().map(|kv| *kv.0).collect(),
                        node._connected_from.iter_head().map(|kv| *kv.0).collect()
                    )
                },
                None => return,
            };
        // update nodes to remove all connections/edges
        for to_index in to_indexes {
            let Some(to_node) = self._hash_map._get_mut_value_at(to_index) else {
                continue;
            };
            to_node._connected_from.remove(&index);
        }

        for from_index in from_indexes {
            let Some(from_node) = self._hash_map._get_mut_value_at(from_index) else {
                continue;
            };
            from_node._connected_to.remove(&index);
        }

        //finally remove the node
        self._hash_map.remove(&key);
    }

Question: is there a better faster/more memory efficient way to do this? I'm not sure how and if RefCell can help and what's the overhead.

2 posts - 2 participants

Read full topic

🏷️ rust_feed