Looking for advice on extending BTreeMap's Entry API

[pmarcelll]

Someone asked about a specific functionality on Reddit around Christmas (described here), and I’ve been thinking about a possible implementation.

My plan/design:

Calling entry() on a BTreeMap gives a view into a single entry, but doesn’t make it possible to reach other key/value pairs from there. The main problem is, that the enty() method mutably borrows the map, so similarly to a Vec, a mutable reference to one of the elements locks the whole container. Despite these constraints, it is impossible to change the key in the Entry after it was constructed (unless of course the tricks described in BTreeMap’s documentation are used, e.g. interior mutability). Every method in the Entry API, that causes modification of pointers in the B-tree consumes the Entry object. These conditions make it possible to construct a method that gives mutable access to the Entry object (so the key can be accessed and/or the value can be modified) and also gives access to the rest of the elements in the map. I called this mehod environment (because it gives access to the surrounding elements/environment of the entry). This is probably not a good name but a couldn’t come up with a better one, maybe the native English speakers here can.

This is how it looks like (Self is Entry here):

    pub fn environment<F>(self, mut f: F) -> Self
        where F: FnMut(&mut Self, (RangeMut<K, V>, RangeMut<K, V>))
    {
        ...
    }

Basically, the user has to provide a closure that has two arguments:

• a mutable borrow to the Entry object
• a tuple that contains two ranges: one for the preceding elements is the map, and one for the following elements (with intervals: [first, act) and (act, last])

Based on the intervals, this also works if the key is not in the map, it even makes it possible to split the map it two (or three, if the key is in the map) based on any provided key.

What do you think about this design? Do you think it has a place in the standard library? Can you find anything that is fundamentally wrong with it?

Implementation

I went through the source code of BTreeMap and managed to understand the important parts. I tried to implement my method, first with everything mutable, then immutable, and 90% of the required stuff is already implemented, but the Handle based design is intentionally restrictive to avoid dangling pointers, and I couldn’t figure out a way to implement it without modifying the internals of the codebase too much.

The algorithm: first we need to find the first leaf edge and the last leaf edge for the start of the first range and the end of the second range. If the Entry is Occupied, take the internal Handle, turn it into a NodeRef, run two range_searches with the NodeRef as the root of the search, one with (Unbounded, Excluded(entry.key())) RangeArgument, the other with (Excluded(entry.key()), Unbounded)). These should give the correct positions for the two ranges, and searching is necessary, because ranges can only be constructed from Handles that point to an edge in a leaf node. And if the Entry is Vacant, the internal Handle already points to the correct place and is good for both ranges.

[Amanieu]

It seems to me that a better solution would be to just do the same thing C++ does and return a cursor to the newly added element. This is what RBTree::insert does in intrusive-collections.

I’ve said this quite a few times in the past, but I really think that the standard collections need to implement a cursor API. It enables many code patterns that are difficult or impossible with the current API.

[bluss]

If not submitting a pull request yourself, you could mentor someone to do it. Your expression of what needs to be done reminds me of some of mine, and those where I realize I care enough about it has to be me that fixes it. But mentoring seems like a good way to get others involved too.

[pmarcelll]

I have an implementation that seems to be working, but the method has 6 ptr::read()s in it, because it is basically the BTreeMap’s version of split_at_mut(). I’ll clean it up a bit, test it properly and submit a PR.

I also looked at the API of RBTree and it might be possible to extend the Entry API to act as a Cursor, an Option<OccupiedEntry> is similar to a CursorMut, the only part missing is some kind of immutableOccupiedEntryView. I’ll mention this option in the PR.