Mutable references in several containers?

Let's start with a use case, we are going to create a disk cache. For each cached block there is a struct, in the struct there is information such as which block on the disk it represent, where it is cached in RAM, time last used, time last written to, if the block was written to. For fast lookup this struct is put in a tree or hashmap with disk block as key. Also this struct is put last on a list/queue when being accessed, just some form of last recently used tracking. If the block was written to the struct is also put on another list/queue for blocks that are going to be committed to disk. The structures needs to preallocated in order to be fast and will live as long the disk cache runs.

In C or C++ this implementation would be pretty straight forward and also simple. I would start just start allocating an array with the structs. When the disk cache starts, it starts to pick structs from the array, and I would just take a pointer of the struct in that array and put it on the appropriate list/hashmap depending on operation. If this would be C/C++ I would also use intrusive containers which would make the memory fragmentation zero but let's leave that out for this example. In C++ simplest would be list<DiskCacheStruct*> and map<BlockNr, DiskCacheStruct*> for example. During the operations, you would basically just move the struct around these there containers and also update the struct.

Now, the same functionality with Rust. I have read a book about Rust cover to cover but I'm still unable to solve this. Let's start with the structs, that part is easy, just make a vector of the structs. Then the difficulties starts, taking mutable references from the vector and put it in those hashmaps/lists will not work as the compiler starts to complaining about multiple mutable references in the wild. That will of course not work. Some of you might say, just store the index of the struct in the vector instead. Yes, that might work, however let's say you want to expand you disk cache with more structs. In C++ you could just allocate a new array and start to work with those immediately, the containers will not know the difference as they work with pointers. Another possibility is to use reference counted structs instead, however, I know that the structs will live forever (we don't shrink the cache), so increasing and decreasing a reference count is kind of unnecessary but perhaps the most viable solution.

The use case I'm describing is a common pattern i systems programming, I often find myself doing versions of it. In C/C++ this type of implementations are simple and works often nicely and working with raw pointers have its benefits. Rust is marketed as a systems programming language how could the same functionality be made there?

I would you solve this?

If I understood all of that correctly, fundamentally I believe your options are:

  • Use unsafe raw pointers just like C/C++, but ensure there's a DiskCache type fully owning both the list and the map so it can expose a safe API
  • Use indices, with all the downsides you described
  • Use Arc/Rcs in both the list and map (or Arc/Rcs in one and Weaks in the other). This should only affect edit performance, not lookup performance, and it sounds like you're more concerned about the latter.

It's worth stating explicitly that C/C++ provide exactly the same fundamental tradeoff. They just don't make it as obvious that the raw pointers have a safety cost, C is missing Rc/Arc/Weak, and C++ is missing Rc.

Most simple way will be to use raw pointers with unsafe code, as long as the code is functionally correct I don't see a problem using unsafe code where it makes sense and keep things simpler.