slab
slab copied to clipboard
Multiple calls to vacant_entry / self referential entries.
TLDR: I want to be able to allocate multiple entries of a slab in a single go so I can have the entries reference each other.
Imagine you want to keep a value and a reference to another slab entry inside a slab.
Slab<(SomeValue, usize)>
So your the instance of your slab might contain something along the lines of this:
// slab[0] = (MyFirstValue, 1)
// slab[1] = (MySecondValue, 0)
There's currently no way to create two referencing entries inside a slab because we can't make multiple calls to vacant_entry
.
let first_entry = slab.vacant_entry();
let second_entry = slab.vacant_entry();
// use the entry.key() from each vacant_entry to insert references to the other.
The only way for me to accomplish something like this right now is to update the entries using get_mut
with the correct keys once I've already inserted the values.
Is this too a complex a feature request for this library? Is there another, better way to do this?
The only way to do this safely would be to have a way to get N vacant entries atomically.
This could be implemented without allocating for the N entries by having an iterator that produce the keys that future insert()
s will use. It wouldn't be completely foolproof as removing an element would invalidate the returned keys, but it doesn't require unsafe
either.
It could be used as
let (first, second) = {
let mut keys = slab.next_keys();
(keys.next().unwrap(), keys.next().unwrap())
};
slab.insert(second);
slab.insert(first);
or
let keys = slab.next_keys().take(4).collect::<Vec<usize>>();
for key in keys {
// ...
}
I've implemented this here and can open a pull request if anybody is interested.
@tormol Interesting thought.
I'm a little uncomfortable with that strategy as can issue other operations on the slab that would invalidate the promised keys. For example, if you remove an entry before using a promised key, that changes things.
Yes, after removing something then one will always get the wrong key, so any bug, if not immediately discovered, will at least be easy to reproduce. I could add an example showing what happens if it's used wrong.
In general, I prefer opting for APIs that are hard (impossible) to misuse.