Weak Heap implementation in Rust

code review
1

Hello there!

Today I published the first version of the crate, in which I implemented a weak heap data structure, and I want to share this with you. One of the criteria of my work was interface identity with BinaryHeap from std. What do you think about implementing various "exotic" data structures in Rust, how useful is it? And what do you think about the quality of my code? :face_with_peeking_eye:

2

You have a lot of unsafe code. Are you sure you need that much? A did a few spot checks and noted the following comment on line 507:

// SAFETY: `start <= ancestor < pos < self.len()`

However it is unclear why this should be the case. Why can't ancestor be less than start?

I was also confused about the sift boolean on WeakHeapPeekMut. Why would you sift it down if the user has accessed the element mutably, but not otherwise?

Besides that, I would move the tests.rs file to a tests folder.

1 Like
3

Thank you for the feedback!

  • I use unsafe code to optimize frequently used functions. It is used here mainly to skip vector boundary checks when accessing elements, this is also quite common in std.
  • I really made an inaccuracy in the comment, it was worth writing 0 instead of start.
  • Usually, mutable access to an element is used to change it, after which the algorithm is obliged to restore the heap property in order to guarantee the correctness of the program. In the case of reading access, the value doesn`t change, and therefore nothing needs to be done.
4

Ah, fair point about changing its value. By the way, in your unsafe code, have you taken into account that the value might do stuff like returning a random boolean when you ask which of two elements is smaller, making the ordering inconsistent? You can't trigger UB even if that happens.

5

Why can a random boolean value be returned there? The boundaries of the vector are observed, and the elements by convention implement the Ord trait.

6

Ord is a safe trait, so it's not allowed for your (or anyone else's) unsafe code to rely on it being implemented correctly for the purpose of memory safety. Your code has to stay sound even if an incorrect/inconsistent/adversarial Ord impl is supplied.

3 Likes
7

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.