Extend Entry API with vacate/occupy

libs
1

Suppose you build a data structure that internally uses a HashMap. You wish to provide an Entry API that (by necessity) wraps the internal HashMap Entry API.

During this process there might be all sorts of reasons (e.g. cache invalidation) to end up in the scenario where an entry is occupied while you want it to be vacant, or vice versa. Right now there basically is no good way without extra lookups or unsafe code to provide this. Every removal/insertion operation on the Entry variants is 'the end of the line', and you lose the entry.

That's why I propose the addition of two functions:

impl<'a, K, V> OccupiedEntry<'a, K, V> {
    pub fn vacate(self) -> (V, VacantEntry<'a, K, V>);
}

impl<'a, K, V> VacantEntry<'a, K, V> {
    pub fn occupy(self, value: V) -> OccupiedEntry<'a, K, V>;
}

This gives the flexibility needed when wrapping Entry.

3 Likes
2

For OccupiedEntry::vacate, I proposed something like that to the hashbrown crate in rust-lang/hashbrown#189 and the results were Entry::and_replace_entry_with and OccupiedEntry::replace_entry_with, however they aren't present in the stdlib yet, not even as unstable methods.

For VacantEntry::occupy, you can already get that behaviour with Entry::Vacant(vacant_entry).insert(value) (although Entry::insert is unstable), however I don't think this is a good reason not to include a dedicate method. One thing I would change however is the name, I would prefer something like VacantEntry::insert_entry Edit: hashbrown already has a RustcVacantEntry::insert_entry method for the rustc entry api (you can see it defined here)

3

I don't think Entry::and_replace_entry_with or OccupiedEntry::replace_entry_with are a proper replacement for what I'm suggesting. They are higher level abstractions that add more unnecessary branches and checks (and could be implemented easily with my suggested methods).

Entry::Vacant(vacant_entry).insert(value) similarly feels wrong, as we throw away information (that we have a vacant entry) to then immediately check it in insert.

I don't mind calling it either vacate/occupy or remove_entry/insert_entry, that's just bikeshedding (although I do personally prefer the former). But they really should come as a pair and not just the one.

1 Like
4

Agreed, though I would be very surprised if the insert method on VacantEntry did any checks on it being "occupied" .

5

I wonder, is this really needed? Can't you keep an Option<(K, V)> on the side, or some other kind of „I want this state as the result“ through the algorithm, using that and only at the very end to „commit“ it into the entry?

6

Maybe (as I am not the OP) but from an API standpoint. It seems strange that there isn't a "remove" function.

8

You are misunderstanding this line:

Entry::Vacant(vacant_entry).insert(value)

Note that the insert being called here is Entry::insert, not VacantEntry::insert. VacantEntry::insert, unlike Entry::insert does not return an OccupiedEntry.

9

Yes I see now that I did. Though I still agree with you about these methods being missing.

10

What if the initial value is in the map? You would need to call HashMap::remove, use that value, then call HashMap::insert. It's definitely something you can already do in safe code, however it needs two query to the HashMap, which are more expensive than one. "But the entry API already provides a mutable reference to the data in the map!" yes, but this may limit your API if you're using it in a library. For example this came up when writing a grouping API for itertools (see the discussion)

11

To be clear, I'm not saying these methods wouldn't be useful from time to time. I'm just not convinced the need is so common to warrant further polluting the std API.

Furthermore, these are on the OccupiedEntry/VacantEntry, which means one has to match them first and they already have quite a lot of similar-looking methods...

Something on the Entry itself might be more useful. Insert already exists on that (though nighttly), if we added remove(self, key) -> (Option<V>, VacantEntry) on that, that would feel more appropriate (or making both insert and entry there take &mut Entry).

3 Likes
12

True, though (for myself at least). I thought that we were talking about Entry itself.

13

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