{"push_id":678208608,"size":2,"distinct_size":0,"ref":"refs/heads/tmp","head":"efebe45cc0f3265ee8bb6396952e93a2004128c8","before":"621a10e7f32d790c39a0b4528369cf7959dd7d34","commits":[{"sha":"5249cbb7fa31ea2e6e8d77b49bfda386215b1ce7","author":{"email":"dc76e9f0c0006e8f919e0c515c66dbba3982f785@localhost","name":"Ulrik Sverdrup"},"message":"collections: Make BinaryHeap panic safe in sift_up / sift_down\n\nUse a struct called Hole that keeps track of an invalid location\nin the vector and fills the hole on drop.\n\nI include a run-pass test that the current BinaryHeap fails, and the new\none passes.\n\nFixes #25842","distinct":false,"url":"https://api.github.com/repos/rust-lang/rust/commits/5249cbb7fa31ea2e6e8d77b49bfda386215b1ce7"},{"sha":"efebe45cc0f3265ee8bb6396952e93a2004128c8","author":{"email":"3a2c29237f73c7cf88424b80e427b1884f346b35@rust-lang.org","name":"bors"},"message":"Auto merge of #25856 - bluss:binary-heap-hole, r=Gankro\n\ncollections: Make BinaryHeap panic safe in sift_up / sift_down\r\n\r\nUse a struct called Hole that keeps track of an invalid location\r\nin the vector and fills the hole on drop.\r\n\r\nI include a run-pass test that the current BinaryHeap fails, and the new\r\none passes.\r\n\r\nNOTE: The BinaryHeap will still be inconsistent after a comparison fails. It will\r\nnot have the heap property. What we fix is just that elements will be valid\r\nvalues.\r\n\r\nThis is actually a performance win -- the new code does not bother to write in `zeroed()`\r\nvalues in the holes, it just leaves them as they were.\r\n\r\nNet result is something like a 5% decrease in runtime for `BinaryHeap::from_vec`. This\r\ncan be further improved by using unchecked indexing (I confirmed it makes a difference,\r\nnot a surprise with the non-sequential access going on), but let's leave that for another PR.\r\nSafety first :wink: \r\n\r\nFixes #25842","distinct":false,"url":"https://api.github.com/repos/rust-lang/rust/commits/efebe45cc0f3265ee8bb6396952e93a2004128c8"}]}