How to get around BorrowFrom inadequacies?

[TyOverby]

I’m using the HashMap find_equiv to look up elements in a hashmap without having to reproduce all of the object that I’m using as a key.

My example is this:

I have a struct that contains lots of metadata and only one field that is hashed or checked for equality.

pub struct Node<'a, N: 'a, C: 'a> {
    pub state: RefCell<Option<N>>, // ONLY HASH AND EQ THIS FIELD
    pub parent: RefCell<Option<&'a Node<'a, N, C>>>,
    pub open: RefCell<bool>,
    pub cost: RefCell<C>,
    pub cost_with_heuristic: RefCell<C>
}

I have a large hashmap that contains these Nodes as keys.

But when I want to see if a certain state is in the map, I wrap it up in a “Dummy Node” that looks like this:

pub struct DumbNode<'b, N: 'b>(pub &'b N);

impl <'a, 'b, N: PartialEq, C> Equiv<&'a Node<'a, N, C>> for DumbNode<'b, N> {
    fn equiv(&self, other: &&Node<'a, N, C>) -> bool {
        let DumbNode(x) = *self;
        x.eq(other.state.borrow().deref().as_ref().unwrap())
    }
}

Notice the use of Equiv which lets me not have to include all of the metadata that is inside of Node.

Now with find_equiv being depricated, I’m not sure how I’ll get around this! I can’t afford to create full Node instances for every single query into the hash table. My current solution is to copy-paste the code from HashTable so that I can keep using it after it has been removed.

[TyOverby]

For the curious, the project that I’m working on is a generic A* implementation. You can see my usage of Equiv in state.rs

TyOverby/astar

[comex]

First off, I don’t really understand your usage pattern. In the repository you linked, the only hash map you use find_equiv on is seen, which maps references solely to themselves. If you only need to use the hash table as a ‘set’ of seen values, you could avoid redundancy by using HashSet. However, in this case, why not use a reference to state as the key, making things more explicit and avoiding the need to do anything special with Equiv or BorrowFrom?

(Also, you should probably try to refactor the code to not require wrapping every single field in its own RefCell.)

Second, if you do want to use BorrowFrom for some reason, I suppose you could create a wrapper struct for the field(s) that form the key, and use this struct inside Node. Then implement BorrowFrom<Node> for the wrapper.

edit: also, this question belongs on Stack Overflow or whatever.

[TyOverby]

If you only need to use the hash table as a ‘set’ of seen values, you could avoid redundancy by using HashSet

I had to use hashmap because hashset doesn’t have find_equiv.

However, in this case, why not use a reference to state as the key

The state needs to be owned by the Node.

Also, you should probably try to refactor the code to not require wrapping every single field in its own RefCell

I’m pretty sure that fine-grained RefCell usage is idiomatic

Second, if you do want to use BorrowFrom for some reason…

If you implement BorrowFrom then I’d need to create an entire Node (with metadata) when I only want access to the inner state.

[cgaebel]

Totally off topic to your main point:

Regarding the “idiomacy” of RefCell-ing every field: if N and C are both uint, you’ll have 6 words of data in your node (48 bytes on x86_64) and 12 words of RefCell overhead (96 bytes on x86_64). If you move the refcells up a level (use RefCell instead of Node), your nodes are 64 bytes large, and take up one cache line instead of 3. I think using less cache lines is more idiomatic rust, but then again, I’m crazy. (:

[Gankro]

Okay so I pulled down your repo to see what was really the issue. Other than the fact that you were using PartialEq as a bound when you presumably really want Eq, the problem is that Ref from the RefCell can’t be returned by the BorrowFrom fn by-reference, and the &N can’t outlive the Ref it’s taken out of.

[Gankro]

Could you go into detail on why you want interior mutability here? I skimmed a few files and nothing jumped out at me.

[TyOverby]

Gankro: thanks for taking a look! The reason that I want interior mutability is because I want to be able to update the cost, cost+heuristic, and parent nodes if I find a better path. This happens inside of the astar function inside of lib.rs.

I’m playing around with a solution which I’ve pushed here: https://github.com/TyOverby/astar/blob/master/src/state.rs but I needed some unsafe transmutes between references that I’ll try to resolve later.

What I ended up doing was using the DummyNode struct as the key to access the same state that Node wraps around.

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.