hashbrown
hashbrown copied to clipboard
rust-lang
Consider implementing `entries(&mut self) -> impl Iterator<Item = OccupiedEntryRef>`
See my comment here for the motivation: https://github.com/rust-lang/rust/issues/59618#issuecomment-1520583112 .
Unfortunately, the impl can't just be added. hashbrown's EntryRefs are currently Send, which means that they can't be allowed to co-exist. Allowing this API would require removing the Send impls on those types. Before someone starts with the implementation, is that something the crate would consider? The tradeoff is pretty clearly well-motivated imo, especially since the entry types already have lifetimes and so aren't exactly likely to be sent across threads much.
That doesn't work due to the way the Iterator trait works: the value returned by next() is not tied to the lifetime of the iterator, which means you can call it multiple times and end up with multiple OccupiedEntryRef at the same time. This is unsound since they each hold a mutable reference to the underlying HashMap.
@Amanieu sure, but that's fixable by just... Not doing that, right? We can have them hold a *mut HashMap and a pointer to their bucket or something like that
The problem is in the Item type on the Iterator trait: it has to contain a lifetime but this lifetime cannot refer to the lifetime of the iterator itself. Consider IterMut of Vec for example, it returns &'a mut T but you can call .next mutliple times on it to obtain multiple mutable references to distinct elements at the same time.
I understand that. My point is that we should allow OccupiedEntryRefs to coexist - that's a feature. I don't think there's any reason that can't be implemented outside of needing to make them non-Send
This exposes too much of the implementation details of the current hash table implementation. For example, the previous implementation (before hashbrown) would shift adjacent entries on deletion. This would invalidate references to other elements in the table.
Is that comment from the pov of std or the pov of hashbrown? Putting std aside for a minute, would hashbrown consider this API?
No, I would like to keep the high-level HashMap/HashSet independent of the underlying implementation. Of course this is not the case for RawTable which directly exposes implementation details.