- // We just need any empty iterator. We don't even want to
- // yield the element that surrounds this position, nor do
- // any splitting.
- &mut []
- } else {
- // Make sure we got a clear beginning
- let mut first_idx = self.find_offset(offset);
- if self.split_index(first_idx, offset) {
- // The newly created 2nd element is ours
- first_idx += 1;
- }
- let first_idx = first_idx; // no more mutation
- // Find our end. Linear scan, but that's ok because the iteration
- // is doing the same linear scan anyway -- no increase in complexity.
- // We combine this scan with a scan for duplicates that we can merge, to reduce
- // the number of elements.
- // We stop searching after the first "block" of size 1, to avoid spending excessive
- // amounts of time on the merging.
- let mut equal_since_idx = first_idx;
- // Once we see too many non-mergeable blocks, we stop.
- // The initial value is chosen via... magic. Benchmarking and magic.
- let mut successful_merge_count = 3usize;
- let mut end_idx = first_idx; // when the loop is done, this is the first excluded element.
- loop {
- // Compute if `end` is the last element we need to look at.
- let done = self.v[end_idx].range.end >= offset+len;
- // We definitely need to include `end`, so move the index.
- end_idx += 1;
- debug_assert!(done || end_idx < self.v.len(), "iter_mut: end-offset {} is out-of-bounds", offset+len);
- // see if we want to merge everything in `equal_since..end` (exclusive at the end!)
- if successful_merge_count > 0 {
- if done || self.v[end_idx].data != self.v[equal_since_idx].data {
- // Everything in `equal_since..end` was equal. Make them just one element covering
- // the entire range.
- let removed_elems = end_idx - equal_since_idx - 1; // number of elements that we would remove
- if removed_elems > 0 {
- // Adjust the range of the first element to cover all of them.
- let equal_until = self.v[end_idx - 1].range.end; // end of range of last of the equal elements
- self.v[equal_since_idx].range.end = equal_until;
- // Delete the rest of them.
- self.v.splice(equal_since_idx+1..end_idx, std::iter::empty());
- // Adjust `end_idx` because we made the list shorter.
- end_idx -= removed_elems;
- // Adjust the count for the cutoff.
- successful_merge_count += removed_elems;
- } else {
- // Adjust the count for the cutoff.
- successful_merge_count -= 1;
- }
- // Go on scanning for the next block starting here.
- equal_since_idx = end_idx;
+ // We just need any empty iterator. We don't even want to
+ // yield the element that surrounds this position, nor do
+ // any splitting.
+ &mut []
+ } else {
+ // Make sure we got a clear beginning
+ let mut first_idx = self.find_offset(offset);
+ if self.split_index(first_idx, offset) {
+ // The newly created 2nd element is ours
+ first_idx += 1;
+ }
+ // No more mutation.
+ let first_idx = first_idx;
+ // Find our end. Linear scan, but that's ok because the iteration
+ // is doing the same linear scan anyway -- no increase in complexity.
+ // We combine this scan with a scan for duplicates that we can merge, to reduce
+ // the number of elements.
+ // We stop searching after the first "block" of size 1, to avoid spending excessive
+ // amounts of time on the merging.
+ let mut equal_since_idx = first_idx;
+ // Once we see too many non-mergeable blocks, we stop.
+ // The initial value is chosen via... magic. Benchmarking and magic.
+ let mut successful_merge_count = 3usize;
+ // When the loop is done, this is the first excluded element.
+ let mut end_idx = first_idx;
+ loop {
+ // Compute if `end` is the last element we need to look at.
+ let done = self.v[end_idx].range.end >= offset + len;
+ // We definitely need to include `end`, so move the index.
+ end_idx += 1;
+ debug_assert!(
+ done || end_idx < self.v.len(),
+ "iter_mut: end-offset {} is out-of-bounds",
+ offset + len
+ );
+ // see if we want to merge everything in `equal_since..end` (exclusive at the end!)
+ if successful_merge_count > 0 {
+ if done || self.v[end_idx].data != self.v[equal_since_idx].data {
+ // Everything in `equal_since..end` was equal. Make them just one element covering
+ // the entire range.
+ let removed_elems = end_idx - equal_since_idx - 1; // number of elements that we would remove
+ if removed_elems > 0 {
+ // Adjust the range of the first element to cover all of them.
+ let equal_until = self.v[end_idx - 1].range.end; // end of range of last of the equal elements
+ self.v[equal_since_idx].range.end = equal_until;
+ // Delete the rest of them.
+ self.v.splice(equal_since_idx + 1..end_idx, std::iter::empty());
+ // Adjust `end_idx` because we made the list shorter.
+ end_idx -= removed_elems;
+ // Adjust the count for the cutoff.
+ successful_merge_count += removed_elems;
+ } else {
+ // Adjust the count for the cutoff.
+ successful_merge_count -= 1;