Changing BTreeMap key while iterating

help
1

I have a situation where I am iterating using BTreeMap::range_mut, which allows me to mutate values but not the key. I'd like to mutate the key rather than remove and re-insert, I know the change does not affect the ordering.

I don't think there is a clean solution. I was wondering if there is a "dirty" solution ( doesn't mean I am going to use it ), in the form of unsafely somehow re-casting the immutable reference I have to the key to a mutable reference, to mutate the key value ( which is a u64 ). Is that possible? Is it sound?

Code is here: wmap.rs - source

2

Do not try to cast an immutable reference to mutable -- this is always immediate UB.

A safe way would be to use a new key type that wraps Cell<u64> or AtomicU64, depending on whether you need it to be thread-safe.

5 Likes
3

I thought of using AtomicU64, but that means a performance hit from synchronisation, I guess. I also thought of using Cell, but that seemed to cause a problem with my struct being Send. I am probably not going to do anything at all, I was just curious if there is a potential solution or not ( short of making my own implementation of BTreeMap!!! ).

Edit ( correction ): the problem was the Cell was making my struct not Sync, rather than not Send.

5

One may use UnsafeCell, but you must make sure you know what you're doing. Litmus test: using UnsafeCell is like using Mutex, exclusively by doing .try_lock().unwrap(), and where if there is contention instead of it panicking like .try_lock().unwrap() would it just causes instant undefined-behavior.

1 Like
6

If you don't mind could you post the problem you're having? Just curious since the Cell is contained in a map which I assume is contained in a Sync wrapper such as a Mutex.

7

FYI relaxed atomic load/store operations compile to the same assembly as normal load/stores on most hardware. The only performance hit is only from missed compiler optimizations.

2 Likes
8

It is a trait bound, my Storage trait has Send + Sync for convenience with async, and one of my structs which implements Storage has a WMap. So using Cell is not practical for me. It's ok, I didn't expect to find a solution, and the insert/remove sequence (when mutating the key would be ideal) is perfectly acceptable in practical terms, it was more a matter of curiosity. I suspect the UB solution would probably work, but I am not going there!

9

I don't believe there's a reasonable and sound way without synchronization (or losing Sync) in this case, currently. One unreasonable way would be implementing your own BTreeMap (perhaps via a newtype), basically. But what you really want is for BTreeMap itself to offer a way to get &mut Keys.

As it turns out, there are a few proposals for that floating around.

I didn't see a proposal for such, but if any of those land, an iterator that somehow allows key mutation without interior mutability also seems reasonable to me.

2 Likes
10

For the Cell solution:

If you wrap your BTreeMap in a struct S that only allows mutating the cell when you have &mut self, then you can soundly add unsafe impl Sync for S {}. This is similar to the reasoning behind Exclusive.

1 Like
11

Well I made a start on my own BTreeMap. It is very much experimental at this stage, and all I have done with it so far is a simple unit test. I think it has all the functionality I need.

[ Edit: I am not using it in RustDb, and it seems to now be working. Whether it is faster or slower than the standard BTreeMap for my purposes I don't yet know. ]

12

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.