Thanks for using Compiler Explorer
Sponsors
Jakt
C++
Ada
Algol68
Analysis
Android Java
Android Kotlin
Assembly
C
C3
Carbon
C with Coccinelle
C++ with Coccinelle
C++ (Circle)
CIRCT
Clean
CMake
CMakeScript
COBOL
C++ for OpenCL
MLIR
Cppx
Cppx-Blue
Cppx-Gold
Cpp2-cppfront
Crystal
C#
CUDA C++
D
Dart
Elixir
Erlang
Fortran
F#
GLSL
Go
Haskell
HLSL
Hook
Hylo
IL
ispc
Java
Julia
Kotlin
LLVM IR
LLVM MIR
Modula-2
Mojo
Nim
Numba
Nix
Objective-C
Objective-C++
OCaml
Odin
OpenCL C
Pascal
Pony
PTX
Python
Racket
Raku
Ruby
Rust
Sail
Snowball
Scala
Slang
Solidity
Spice
SPIR-V
Swift
LLVM TableGen
Toit
Triton
TypeScript Native
V
Vala
Visual Basic
Vyper
WASM
Zig
Javascript
GIMPLE
Ygen
sway
rust source #1
Output
Compile to binary object
Link to binary
Execute the code
Intel asm syntax
Demangle identifiers
Verbose demangling
Filters
Unused labels
Library functions
Directives
Comments
Horizontal whitespace
Debug intrinsics
Compiler
mrustc (master)
rustc 1.0.0
rustc 1.1.0
rustc 1.10.0
rustc 1.11.0
rustc 1.12.0
rustc 1.13.0
rustc 1.14.0
rustc 1.15.1
rustc 1.16.0
rustc 1.17.0
rustc 1.18.0
rustc 1.19.0
rustc 1.2.0
rustc 1.20.0
rustc 1.21.0
rustc 1.22.0
rustc 1.23.0
rustc 1.24.0
rustc 1.25.0
rustc 1.26.0
rustc 1.27.0
rustc 1.27.1
rustc 1.28.0
rustc 1.29.0
rustc 1.3.0
rustc 1.30.0
rustc 1.31.0
rustc 1.32.0
rustc 1.33.0
rustc 1.34.0
rustc 1.35.0
rustc 1.36.0
rustc 1.37.0
rustc 1.38.0
rustc 1.39.0
rustc 1.4.0
rustc 1.40.0
rustc 1.41.0
rustc 1.42.0
rustc 1.43.0
rustc 1.44.0
rustc 1.45.0
rustc 1.45.2
rustc 1.46.0
rustc 1.47.0
rustc 1.48.0
rustc 1.49.0
rustc 1.5.0
rustc 1.50.0
rustc 1.51.0
rustc 1.52.0
rustc 1.53.0
rustc 1.54.0
rustc 1.55.0
rustc 1.56.0
rustc 1.57.0
rustc 1.58.0
rustc 1.59.0
rustc 1.6.0
rustc 1.60.0
rustc 1.61.0
rustc 1.62.0
rustc 1.63.0
rustc 1.64.0
rustc 1.65.0
rustc 1.66.0
rustc 1.67.0
rustc 1.68.0
rustc 1.69.0
rustc 1.7.0
rustc 1.70.0
rustc 1.71.0
rustc 1.72.0
rustc 1.73.0
rustc 1.74.0
rustc 1.75.0
rustc 1.76.0
rustc 1.77.0
rustc 1.78.0
rustc 1.79.0
rustc 1.8.0
rustc 1.80.0
rustc 1.81.0
rustc 1.82.0
rustc 1.83.0
rustc 1.84.0
rustc 1.85.0
rustc 1.86.0
rustc 1.87.0
rustc 1.88.0
rustc 1.89.0
rustc 1.9.0
rustc beta
rustc nightly
rustc-cg-gcc (master)
x86-64 GCCRS (GCC master)
x86-64 GCCRS (GCCRS master)
x86-64 GCCRS 14.1 (GCC assertions)
x86-64 GCCRS 14.1 (GCC)
x86-64 GCCRS 14.2 (GCC assertions)
x86-64 GCCRS 14.2 (GCC)
x86-64 GCCRS 14.3 (GCC assertions)
x86-64 GCCRS 14.3 (GCC)
x86-64 GCCRS 15.1 (GCC assertions)
x86-64 GCCRS 15.1 (GCC)
x86-64 GCCRS 15.2 (GCC assertions)
x86-64 GCCRS 15.2 (GCC)
Options
Source code
use std::mem::{swap, ManuallyDrop}; use std::ops::{Deref, DerefMut}; use std::ptr; pub struct BinaryHeap<T> { data: Vec<T>, } pub struct PeekMut<'a, T: 'a + Ord> { heap: &'a mut BinaryHeap<T>, sift: bool, } impl<T: Ord> Drop for PeekMut<'_, T> { fn drop(&mut self) { if self.sift { self.heap.sift_down(0); } } } impl<T: Ord> Deref for PeekMut<'_, T> { type Target = T; fn deref(&self) -> &T { debug_assert!(!self.heap.is_empty()); // SAFE: PeekMut is only instantiated for non-empty heaps unsafe { self.heap.data.get_unchecked(0) } } } impl<T: Ord> DerefMut for PeekMut<'_, T> { fn deref_mut(&mut self) -> &mut T { debug_assert!(!self.heap.is_empty()); self.sift = true; // SAFE: PeekMut is only instantiated for non-empty heaps unsafe { self.heap.data.get_unchecked_mut(0) } } } impl<'a, T: Ord> PeekMut<'a, T> { pub fn pop(mut this: PeekMut<'a, T>) -> T { let value = this.heap.pop().unwrap(); this.sift = false; value } } impl<T: Ord> BinaryHeap<T> { pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T>> { if self.is_empty() { None } else { Some(PeekMut { heap: self, sift: false }) } } pub fn pop(&mut self) -> Option<T> { self.data.pop().map(|mut item| { if !self.is_empty() { swap(&mut item, &mut self.data[0]); self.sift_down_to_bottom(0); } item }) } fn sift_up(&mut self, start: usize, pos: usize) -> usize { unsafe { // Take out the value at `pos` and create a hole. let mut hole = Hole::new(&mut self.data, pos); while hole.pos() > start { let parent = (hole.pos() - 1) / 2; if hole.element() <= hole.get(parent) { break; } hole.move_to(parent); } hole.pos() } } /// Take an element at `pos` and move it down the heap, /// while its children are larger. fn sift_down_range(&mut self, pos: usize, end: usize) { unsafe { let mut hole = Hole::new(&mut self.data, pos); let mut child = 2 * pos + 1; while child < end { let right = child + 1; // compare with the greater of the two children if right < end && hole.get(child) <= hole.get(right) { child = right; } // if we are already in order, stop. if hole.element() >= hole.get(child) { break; } hole.move_to(child); child = 2 * hole.pos() + 1; } } } fn sift_down(&mut self, pos: usize) { let len = self.len(); self.sift_down_range(pos, len); } fn sift_down_to_bottom(&mut self, mut pos: usize) { let end = self.len(); let start = pos; unsafe { let mut hole = Hole::new(&mut self.data, pos); let mut child = 2 * pos + 1; while child < end { let right = child + 1; // compare with the greater of the two children if right < end && hole.get(child) <= hole.get(right) { child = right; } hole.move_to(child); child = 2 * hole.pos() + 1; } pos = hole.pos; } self.sift_up(start, pos); } } impl<T> BinaryHeap<T> { pub fn len(&self) -> usize { self.data.len() } pub fn is_empty(&self) -> bool { self.len() == 0 } } /// Hole represents a hole in a slice i.e., an index without valid value /// (because it was moved from or duplicated). /// In drop, `Hole` will restore the slice by filling the hole /// position with the value that was originally removed. struct Hole<'a, T: 'a> { data: &'a mut [T], elt: ManuallyDrop<T>, pos: usize, } impl<'a, T> Hole<'a, T> { #[inline] unsafe fn new(data: &'a mut [T], pos: usize) -> Self { debug_assert!(pos < data.len()); // SAFE: pos should be inside the slice let elt = unsafe { ptr::read(data.get_unchecked(pos)) }; Hole { data, elt: ManuallyDrop::new(elt), pos } } #[inline] fn pos(&self) -> usize { self.pos } #[inline] fn element(&self) -> &T { &self.elt } #[inline] unsafe fn get(&self, index: usize) -> &T { debug_assert!(index != self.pos); debug_assert!(index < self.data.len()); unsafe { self.data.get_unchecked(index) } } #[inline] unsafe fn move_to(&mut self, index: usize) { debug_assert!(index != self.pos); debug_assert!(index < self.data.len()); unsafe { let index_ptr: *const _ = self.data.get_unchecked(index); let hole_ptr = self.data.get_unchecked_mut(self.pos); ptr::copy_nonoverlapping(index_ptr, hole_ptr, 1); } self.pos = index; } } impl<T> Drop for Hole<'_, T> { #[inline] fn drop(&mut self) { // fill the hole again unsafe { let pos = self.pos; ptr::copy_nonoverlapping(&*self.elt, self.data.get_unchecked_mut(pos), 1); } } } pub fn push_if_below_max(heap: &mut BinaryHeap<i32>, x: i32) { if let Some(mut max) = heap.peek_mut() { if x < *max { *max = x; } } }
Become a Patron
Sponsor on GitHub
Donate via PayPal
Compiler Explorer Shop
Source on GitHub
Mailing list
Installed libraries
Wiki
Report an issue
How it works
Contact the author
CE on Mastodon
CE on Bluesky
Statistics
Changelog
Version tree