Simulating a HashMap<K, V> where the key is not K

help
1

The topic sounds a bit weird but let me explain.

Roughly, I'm implementing a struct like this:

struct MyStruct<T> {
    // other stuff
    arena: Arena<Box<T>>,
    map: HashMap<MyWrapper<T>, Index>,
}

MyWrapper<T> does the internal de-referencing to the entries in the arena (basically its a *const T).
Switching Box an MyWrapper doesn't solve the problem. Code that correctly inserts and removes elements is written.

The idea is to build a collection that can be both accessed by index and by hashing. Therefore, I'd like to give users of MyStruct an API similar to a normal HashMap, e.g.

impl<T>  MyStruct<T> {
    fn get<'a, Q>(&'a self, key: &Q) -> Option<&'a T>
    where
        T: Borrow<Q>,
        Q: ?Sized + Eq + Hash,
    { ... }
}

The obvious way would be to impl<T, Q> Borrow<Q> for MyWrapper<T>. However, this conflicts with the impl<T> Borrow<T> for T in the std/core crate. I also rely on the Borrow<Q> bound so going for a simpler signature with only key: &T is not an option.

Has anyone a solution or at least some inspiration for me?

2

Why not? That at least fixes the Borrow impl?

3

Not sure if you'd consider using unsafe?

use std::{borrow::Borrow, collections::HashMap, hash::Hash};

#[derive(Hash, PartialEq, Eq)]
struct MyWrapper<T>(T);

fn get<T, Q>(map: &HashMap<MyWrapper<T>, ()>, v: &Q)
where
    T: Borrow<Q> + Eq + Hash,
    Q: Eq + Hash,
{
    #[derive(Hash, PartialEq, Eq)]
    #[repr(transparent)]
    struct BorrowWrapper<T: ?Sized>(T);
    
    impl<T: ?Sized> BorrowWrapper<T> {
        fn from_ref(r: &T) -> &Self {
            unsafe { &*(r as *const T as *const BorrowWrapper<T>) }
        }
    }
    
    impl<T, Q> Borrow<BorrowWrapper<Q>> for MyWrapper<T>
    where
        T: Borrow<Q>,
    {
        fn borrow(&self) -> &BorrowWrapper<Q> {
            BorrowWrapper::from_ref(self.0.borrow())
        }
    }

    map.get(BorrowWrapper::from_ref(v));
}
3 Likes
4

This doesn't work because Box is only impl<T> Borrow<T> for Box<T> and not impl<T, Q> Borrow<Q> for Box<T> where T: Borrow<Q>. This means that the following won't compile:

let mut map = HashSet::new();
map.insert(Box::new("foo".to_owned()));
map.get("foo");

Maybe this should be implemented in the std crate? (Also for other types like Box, e.g. Rc and so on)

5

This looks promising I'll give it a try.

6

This worked! Thank you very much! I don't think I could've come up with this solution on my own.

However, I'm not sure if I understood the from_ref() function correctly. For me it looks like a &BorrowWrapper<T> is actually only a type level construct for a &T which is required to implement the Borrow<Q> outside of the restrictions of the std/core crate.

7

By using repr(transparent) we've created a type that has the same memory representation as the inner type, but at the type level it's different from the inner type. That allows us to implement the trait we need as the compiler can prove the blanket impl will never apply, unless we implement traits matching the blanket constraints in our own crate, which we don't.

2 Likes
8

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.