4

What would be a good Rusty way to implement a data structure providing "handles" to its elements to allow their later manipulation? A prime example would be a binary heap implementation where you want to decrease element keys and remove elements.

(My particular motivation are Fibonacci and other heaps, e.g. for Dijkstra's algorithm.)

Unlike this related question I do not mind writing unsafe code as long as I can provide a safe interface with safe element references.

I can think of several directions:

  • Index the elements of the data structure by some unique key and always access it via this key. In a heap, this means an additional structure. This also complicates the internal structure quite a bit.

  • Wrap every node in an Rc, using weak refs for parent pointers. Every "element handle" returned is actually a wrapped Rc. This can be completely safe Rust, but I do not like this solution for all the runtime checks and using refcounting everywhere not being a really good design.

  • Return handles with references or pointers lifetime-bound to the main structure. This option would likely not allow deleting individual elements before dropping the main structure. I am not sure about the details or options.

I would like to ask for help with the last option, or more generally if there are any other approaches I am missing. I know that "you can not have everything" ... I am asking for the right and most Rusty approach here.

Community
  • 1
  • 1
Tomáš Gavenčiak
  • 470
  • 5
  • 9
  • This question feels far too broad for Stack Overflow. – Shepmaster Mar 11 '17 at 15:11
  • 2
    I agree with Shepmaster. This by no means that I do not find your question intriguing and interesting! I do feel, however, that an answer would require a *discussion*, which Stack Overflow is ill-equipped to host. I advise you to ask this question on either r/rust (reddit) or the Rust Users forum. (Note: you may also need to specify some bits; for example can the heap change while people have handles? If it can, maintaining indices to elements is going to be tough...) – Matthieu M. Mar 11 '17 at 15:43
  • There is a good discussion at this at https://github.com/contain-rs/discuss/issues/11 also mentioning other ways to implement stable handles. One notable example is to reuse but never (in the struct lifetime) deallocate the Node data structures and provide "version number" passed around in the handles. If a handle points to a reused Node, the version numbers will not match. – Tomáš Gavenčiak Mar 23 '17 at 19:42

1 Answers1

2

The Entry API of HashMap in the standard library is a good example of your third idea.

If you study the source code a bit, you find that instances of Entry include a mutable reference to the HashMap they came from, plus some metadata needed to avoid redundantly searching the hash table a second time.

Because an Entry contains a mutable reference to its HashMap, only one such Entry can exist at a time, and concurrent modification of the HashMap while the Entry exists is impossible. This is probably what you want.

Rust's built-in slice type is another example of your third idea. Unusually, the split_at_mut() method can be used to obtain multiple simultaneous mutable views of the same array, provided they don't overlap. This is perhaps a good example of benefiting from carefully chosen unsafe code.

In my opinion, these designs work well, and I would imitate them.

apt1002
  • 969
  • 6
  • 15
  • A great example -- thanks for pointing out the `Entry` API. I guess to have multiple "handles" with mutability, I cold use a `RefCell`. – Tomáš Gavenčiak Mar 19 '17 at 09:04
  • Hmm, adding mutability to "handles" would be more complicated than just using a `RefCell`: I still do not know how to *safely* modify the structure (esp. remove elements) while holding some handles elsewhere. I understand that this is unsafe in general (except withr `Rc` or GC) and have to set the right level of "unsafeness". – Tomáš Gavenčiak Mar 19 '17 at 09:14