Lines Matching refs:hole
22823 // remaining hole. This is a good method.
22828 // hole. This method is very good. Benchmarks demonstrated slightly better
22834 // Intermediate state of the insertion process is always tracked by `hole`, which
22837 // 2. Fills the remaining hole in `v` in the end.
22841 // If `is_less` panics at any point during the process, `hole` will get dropped and
22842 // fill the hole in `v` with `tmp`, thus ensuring that `v` still holds every object it
22844 let mut hole = InsertionHole { src: &mut *tmp, dest: &mut v[1] };
22852 hole.dest = &mut v[i];
22854 // `hole` gets dropped and thus copies `tmp` into the remaining hole in `v`.
22894 // hole in `v`.
22896 // Intermediate state of the process is always tracked by `hole`, which serves two purposes:
22898 // 2. Fills the remaining hole in `v` if the longer run gets consumed first.
22902 // If `is_less` panics at any point during the process, `hole` will get dropped and fill the
22903 // hole in `v` with the unconsumed range in `buf`, thus ensuring that `v` still holds every
22905 let mut hole;
22911 hole = MergeHole { start: buf, end: buf.add(mid), dest: v };
22915 let left = &mut hole.start;
22917 let out = &mut hole.dest;
22919 while *left < hole.end && right < v_end {
22935 hole = MergeHole { start: buf, end: buf.add(len - mid), dest: v_mid };
22939 let left = &mut hole.dest;
22940 let right = &mut hole.end;
22956 // Finally, `hole` gets dropped. If the shorter run was not fully consumed, whatever remains of
22957 // it will now be copied into the hole in `v`.
41548 // When finished, the remaining data will be copied back to cover the hole,
44791 // hole), shift along the others and move the removed element back into the
44792 // vector at the final location of the hole.
44794 // the hole is filled back at the end of its scope, even on panic.
44795 // Using a hole reduces the constant factor compared to using swaps,
44802 // Take out the value at `pos` and create a hole.
44804 let mut hole = unsafe { Hole::new(&mut self.data, pos) };
44806 while hole.pos() > start {
44807 let parent = (hole.pos() - 1) / 2;
44809 // SAFETY: hole.pos() > start >= 0, which means hole.pos() > 0
44810 // and so hole.pos() - 1 can't underflow.
44811 // This guarantees that parent < hole.pos() so
44812 // it's a valid index and also != hole.pos().
44813 if hole.element() <= unsafe { hole.get(parent) } {
44818 unsafe { hole.move_to(parent) };
44821 hole.pos()
44832 let mut hole = unsafe { Hole::new(&mut self.data, pos) };
44833 let mut child = 2 * hole.pos() + 1;
44835 // Loop invariant: child == 2 * hole.pos() + 1.
44840 // child == 2 * hole.pos() + 1 != hole.pos() and
44841 // child + 1 == 2 * hole.pos() + 2 != hole.pos().
44842 // FIXME: 2 * hole.pos() + 1 or 2 * hole.pos() + 2 could overflow
44844 child += unsafe { hole.get(child) <= hole.get(child + 1) } as usize;
44848 // We already proven that both are < self.len() and != hole.pos()
44849 if hole.element() >= unsafe { hole.get(child) } {
44854 unsafe { hole.move_to(child) };
44855 child = 2 * hole.pos() + 1;
44860 if child == end - 1 && hole.element() < unsafe { hole.get(child) } {
44862 // child == 2 * hole.pos() + 1 != hole.pos().
44863 unsafe { hole.move_to(child) };
44891 let mut hole = unsafe { Hole::new(&mut self.data, pos) };
44892 let mut child = 2 * hole.pos() + 1;
44894 // Loop invariant: child == 2 * hole.pos() + 1.
44898 // child == 2 * hole.pos() + 1 != hole.pos() and
44899 // child + 1 == 2 * hole.pos() + 2 != hole.pos().
44900 // FIXME: 2 * hole.pos() + 1 or 2 * hole.pos() + 2 could overflow
44902 child += unsafe { hole.get(child) <= hole.get(child + 1) } as usize;
44905 unsafe { hole.move_to(child) };
44906 child = 2 * hole.pos() + 1;
44911 // and child == 2 * hole.pos() + 1 != hole.pos().
44912 unsafe { hole.move_to(child) };
44914 pos = hole.pos();
44915 drop(hole);
44917 // SAFETY: pos is the position in the hole and was already proven
45381 /// Hole represents a hole in a slice i.e., an index without valid value
45383 /// In drop, `Hole` will restore the slice by filling the hole
45424 /// Move hole to new location
45444 // fill the hole again
46683 // I.e. the marker does not depend on lifetimes of user-supplied types. Modulo the Copy hole, which
48088 let hole = self.as_mut_ptr().add(index);
48090 ptr::replace(hole, last)
48274 // SAFETY: `deleted_cnt` > 0, so the hole slot must not overlap with current element.
48548 // the hole, and the vector length is restored to the new length.