sp_im/vector/
focus.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4
5use core::{
6  mem::{
7    replace,
8    swap,
9  },
10  ops::{
11    Range,
12    RangeBounds,
13  },
14  ptr::null,
15};
16
17use core::sync::atomic::{
18  AtomicPtr,
19  Ordering,
20};
21
22use crate::{
23  nodes::chunk::Chunk,
24  sync::Lock,
25  util::{
26    to_range,
27    PoolRef,
28    Ref,
29  },
30  vector::{
31    Iter,
32    IterMut,
33    RRBPool,
34    Vector,
35    VectorInner::{
36      Full,
37      Inline,
38      Single,
39    },
40    RRB,
41  },
42};
43
44/// Focused indexing over a [`Vector`][Vector].
45///
46/// By remembering the last tree node accessed through an index lookup and the
47/// path we took to get there, we can speed up lookups for adjacent indices
48/// tremendously. Lookups on indices in the same node are instantaneous, and
49/// lookups on sibling nodes are also very fast.
50///
51/// A `Focus` can also be used as a restricted view into a vector, using the
52/// [`narrow`][narrow] and [`split_at`][split_at] methods.
53///
54/// # When should I use a `Focus` for better performance?
55///
56/// `Focus` is useful when you need to perform a large number of index lookups
57/// that are more likely than not to be close to each other. It's usually worth
58/// using a `Focus` in any situation where you're batching a lot of index
59/// lookups together, even if they're not obviously adjacent - there's likely
60/// to be some performance gain for even completely random access.
61///
62/// If you're just iterating forwards or backwards over the [`Vector`][Vector]
63/// in order, you're better off with a regular iterator, which, in fact, is
64/// implemented using a `Focus`, but provides a simpler interface.
65///
66/// If you're just doing a very small number of index lookups, the setup cost
67/// for the `Focus` is probably not worth it.
68///
69/// A `Focus` is never faster than an index lookup on a small [`Vector`][Vector]
70/// with a length below the internal RRB tree's branching factor of 64.
71///
72/// # Examples
73///
74/// This example is contrived, as the better way to iterate forwards or
75/// backwards over a vector is with an actual iterator. Even so, the version
76/// using a `Focus` should run nearly an order of magnitude faster than the
77/// version using index lookups at a length of 1000. It should also be noted
78/// that [`vector::Iter`][Iter] is actually implemented using a `Focus` behind
79/// the scenes, so the performance of the two should be identical.
80///
81/// ```rust
82/// # #[macro_use] extern crate sp_im;
83/// # use sp_im::vector::Vector;
84/// # use std::iter::FromIterator;
85/// let mut vec: Vector<i64> = Vector::from_iter(0..1000);
86///
87/// // Summing a vector, the slow way:
88/// let mut sum = 0;
89/// for i in 0..1000 {
90///   sum += *vec.get(i).unwrap();
91/// }
92/// assert_eq!(499500, sum);
93///
94/// // Summing a vector faster using a Focus:
95/// let mut sum = 0;
96/// let mut focus = vec.focus();
97/// for i in 0..1000 {
98///   sum += *focus.get(i).unwrap();
99/// }
100/// assert_eq!(499500, sum);
101///
102/// // And the easy way, for completeness:
103/// let sum: i64 = vec.iter().sum();
104/// assert_eq!(499500, sum);
105/// ```
106///
107/// [Vector]: enum.Vector.html
108/// [Iter]: struct.Iter.html
109/// [narrow]: #method.narrow
110/// [split_at]: #method.split_at
111pub enum Focus<'a, A> {
112  #[doc(hidden)]
113  Single(&'a [A]),
114  #[doc(hidden)]
115  Full(TreeFocus<A>),
116}
117
118impl<'a, A> Focus<'a, A>
119where A: Clone + 'a
120{
121  /// Construct a `Focus` for a [`Vector`][Vector].
122  ///
123  /// [Vector]: enum.Vector.html
124  pub fn new(vector: &'a Vector<A>) -> Self {
125    match &vector.vector {
126      Inline(_, chunk) => Focus::Single(chunk),
127      Single(_, chunk) => Focus::Single(chunk),
128      Full(_, tree) => Focus::Full(TreeFocus::new(tree)),
129    }
130  }
131
132  /// Get the length of the focused [`Vector`][Vector].
133  ///
134  /// [Vector]: enum.Vector.html
135  pub fn len(&self) -> usize {
136    match self {
137      Focus::Single(chunk) => chunk.len(),
138      Focus::Full(tree) => tree.len(),
139    }
140  }
141
142  /// Test if the focused [`Vector`][Vector] is empty.
143  ///
144  /// [Vector]: enum.Vector.html
145  pub fn is_empty(&self) -> bool { self.len() == 0 }
146
147  /// Get a reference to the value at a given index.
148  pub fn get(&mut self, index: usize) -> Option<&A> {
149    match self {
150      Focus::Single(chunk) => chunk.get(index),
151      Focus::Full(tree) => tree.get(index),
152    }
153  }
154
155  /// Get a reference to the value at a given index.
156  ///
157  /// Panics if the index is out of bounds.
158  pub fn index(&mut self, index: usize) -> &A {
159    self.get(index).expect("index out of bounds")
160  }
161
162  /// Get the chunk for the given index.
163  ///
164  /// This gives you a reference to the leaf node that contains the index,
165  /// along with its start and end indices.
166  pub fn chunk_at(&mut self, index: usize) -> (Range<usize>, &[A]) {
167    let len = self.len();
168    if index >= len {
169      panic!("vector::Focus::chunk_at: index out of bounds");
170    }
171    match self {
172      Focus::Single(chunk) => (0..len, chunk),
173      Focus::Full(tree) => tree.get_chunk(index),
174    }
175  }
176
177  /// Narrow the focus onto a subslice of the vector.
178  ///
179  /// `Focus::narrow(range)` has the same effect as `&slice[range]`, without
180  /// actually modifying the underlying vector.
181  ///
182  /// Panics if the range isn't fully inside the current focus.
183  ///
184  /// ## Examples
185  ///
186  /// ```rust
187  /// # #[macro_use] extern crate sp_im;
188  /// # use sp_im::vector::Vector;
189  /// # use std::iter::FromIterator;
190  /// let vec = Vector::from_iter(0..1000);
191  /// let narrowed = vec.focus().narrow(100..200);
192  /// let narrowed_vec = narrowed.into_iter().cloned().collect();
193  /// assert_eq!(Vector::from_iter(100..200), narrowed_vec);
194  /// ```
195  ///
196  /// [slice::split_at]: https://doc.rust-lang.org/std/primitive.slice.html#method.split_at
197  /// [Vector::split_at]: enum.Vector.html#method.split_at
198  pub fn narrow<R>(self, range: R) -> Self
199  where R: RangeBounds<usize> {
200    let r = to_range(&range, self.len());
201    if r.start >= r.end || r.start >= self.len() {
202      panic!("vector::Focus::narrow: range out of bounds");
203    }
204    match self {
205      Focus::Single(chunk) => Focus::Single(&chunk[r]),
206      Focus::Full(tree) => Focus::Full(tree.narrow(r)),
207    }
208  }
209
210  /// Split the focus into two.
211  ///
212  /// Given an index `index`, consume the focus and produce two new foci, the
213  /// left onto indices `0..index`, and the right onto indices `index..N`
214  /// where `N` is the length of the current focus.
215  ///
216  /// Panics if the index is out of bounds.
217  ///
218  /// This is the moral equivalent of [`slice::split_at`][slice::split_at], in
219  /// that it leaves the underlying data structure unchanged, unlike
220  /// [`Vector::split_at`][Vector::split_at].
221  ///
222  /// ## Examples
223  ///
224  /// ```rust
225  /// # #[macro_use] extern crate sp_im;
226  /// # use sp_im::vector::Vector;
227  /// # use std::iter::FromIterator;
228  /// let vec = Vector::from_iter(0..1000);
229  /// let (left, right) = vec.focus().split_at(500);
230  /// let left_vec = left.into_iter().cloned().collect();
231  /// let right_vec = right.into_iter().cloned().collect();
232  /// assert_eq!(Vector::from_iter(0..500), left_vec);
233  /// assert_eq!(Vector::from_iter(500..1000), right_vec);
234  /// ```
235  ///
236  /// [slice::split_at]: https://doc.rust-lang.org/std/primitive.slice.html#method.split_at
237  /// [Vector::split_at]: enum.Vector.html#method.split_at
238  pub fn split_at(self, index: usize) -> (Self, Self) {
239    if index >= self.len() {
240      panic!("vector::Focus::split_at: index out of bounds");
241    }
242    match self {
243      Focus::Single(chunk) => {
244        let (left, right) = chunk.split_at(index);
245        (Focus::Single(left), Focus::Single(right))
246      }
247      Focus::Full(tree) => {
248        let (left, right) = tree.split_at(index);
249        (Focus::Full(left), Focus::Full(right))
250      }
251    }
252  }
253}
254
255impl<'a, A> IntoIterator for Focus<'a, A>
256where A: Clone + 'a
257{
258  type IntoIter = Iter<'a, A>;
259  type Item = &'a A;
260
261  fn into_iter(self) -> Self::IntoIter { Iter::from_focus(self) }
262}
263
264impl<'a, A> Clone for Focus<'a, A>
265where A: Clone + 'a
266{
267  fn clone(&self) -> Self {
268    match self {
269      Focus::Single(chunk) => Focus::Single(chunk),
270      Focus::Full(tree) => Focus::Full(tree.clone()),
271    }
272  }
273}
274
275pub struct TreeFocus<A> {
276  tree: RRB<A>,
277  view: Range<usize>,
278  middle_range: Range<usize>,
279  target_range: Range<usize>,
280  target_ptr: *const Chunk<A>,
281}
282
283impl<A> Clone for TreeFocus<A> {
284  fn clone(&self) -> Self {
285    let tree = self.tree.clone();
286    TreeFocus {
287      view: self.view.clone(),
288      middle_range: self.middle_range.clone(),
289      target_range: 0..0,
290      target_ptr: null(),
291      tree,
292    }
293  }
294}
295
296#[allow(unsafe_code)]
297#[cfg(threadsafe)]
298unsafe impl<A> Send for TreeFocus<A> {}
299#[allow(unsafe_code)]
300#[cfg(threadsafe)]
301unsafe impl<A> Sync for TreeFocus<A> {}
302
303#[inline]
304fn contains<A: Ord>(range: &Range<A>, index: &A) -> bool {
305  *index >= range.start && *index < range.end
306}
307
308impl<A> TreeFocus<A>
309where A: Clone
310{
311  fn new(tree: &RRB<A>) -> Self {
312    let middle_start = tree.outer_f.len() + tree.inner_f.len();
313    let middle_end = middle_start + tree.middle.len();
314    TreeFocus {
315      tree: tree.clone(),
316      view: 0..tree.length,
317      middle_range: middle_start..middle_end,
318      target_range: 0..0,
319      target_ptr: null(),
320    }
321  }
322
323  fn len(&self) -> usize { self.view.end - self.view.start }
324
325  fn narrow(self, mut view: Range<usize>) -> Self {
326    view.start += self.view.start;
327    view.end += self.view.start;
328    TreeFocus {
329      view,
330      middle_range: self.middle_range.clone(),
331      target_range: 0..0,
332      target_ptr: null(),
333      tree: self.tree,
334    }
335  }
336
337  fn split_at(self, index: usize) -> (Self, Self) {
338    let len = self.len();
339    let left = self.clone().narrow(0..index);
340    let right = self.narrow(index..len);
341    (left, right)
342  }
343
344  fn physical_index(&self, index: usize) -> usize {
345    debug_assert!(index < self.view.end);
346    self.view.start + index
347  }
348
349  fn logical_range(&self, range: &Range<usize>) -> Range<usize> {
350    (range.start - self.view.start)..(range.end - self.view.start)
351  }
352
353  fn set_focus(&mut self, index: usize) {
354    if index < self.middle_range.start {
355      let outer_len = self.tree.outer_f.len();
356      if index < outer_len {
357        self.target_range = 0..outer_len;
358        self.target_ptr = &*self.tree.outer_f;
359      }
360      else {
361        self.target_range = outer_len..self.middle_range.start;
362        self.target_ptr = &*self.tree.inner_f;
363      }
364    }
365    else if index >= self.middle_range.end {
366      let outer_start = self.middle_range.end + self.tree.inner_b.len();
367      if index < outer_start {
368        self.target_range = self.middle_range.end..outer_start;
369        self.target_ptr = &*self.tree.inner_b;
370      }
371      else {
372        self.target_range = outer_start..self.tree.length;
373        self.target_ptr = &*self.tree.outer_b;
374      }
375    }
376    else {
377      let tree_index = index - self.middle_range.start;
378      let (range, ptr) =
379        self.tree.middle.lookup_chunk(self.tree.middle_level, 0, tree_index);
380      self.target_range = (range.start + self.middle_range.start)
381        ..(range.end + self.middle_range.start);
382      self.target_ptr = ptr;
383    }
384  }
385
386  #[allow(unsafe_code)]
387  fn get_focus(&self) -> &Chunk<A> { unsafe { &*self.target_ptr } }
388
389  pub fn get(&mut self, index: usize) -> Option<&A> {
390    if index >= self.len() {
391      return None;
392    }
393    let phys_index = self.physical_index(index);
394    if !contains(&self.target_range, &phys_index) {
395      self.set_focus(phys_index);
396    }
397    let target_phys_index = phys_index - self.target_range.start;
398    Some(&self.get_focus()[target_phys_index])
399  }
400
401  pub fn get_chunk(&mut self, index: usize) -> (Range<usize>, &[A]) {
402    let phys_index = self.physical_index(index);
403    if !contains(&self.target_range, &phys_index) {
404      self.set_focus(phys_index);
405    }
406    let mut slice: &[A] = self.get_focus();
407    let mut left = 0;
408    let mut right = 0;
409    if self.target_range.start < self.view.start {
410      left = self.view.start - self.target_range.start;
411    }
412    if self.target_range.end > self.view.end {
413      right = self.target_range.end - self.view.end;
414    }
415    slice = &slice[left..(slice.len() - right)];
416    let phys_range =
417      (self.target_range.start + left)..(self.target_range.end - right);
418    (self.logical_range(&phys_range), slice)
419  }
420}
421
422/// A mutable version of [`Focus`][Focus].
423///
424/// See [`Focus`][Focus] for more details.
425///
426/// You can only build one `FocusMut` at a time for a vector, effectively
427/// keeping a lock on the vector until you're done with the focus, which relies
428/// on the structure of the vector not changing while it exists.
429///
430/// ```rust,compile_fail
431/// # #[macro_use] extern crate sp_im;
432/// # use sp_im::vector::Vector;
433/// # use std::iter::FromIterator;
434/// let mut vec = Vector::from_iter(0..1000);
435/// let focus1 = vec.focus_mut();
436/// // Fails here in 2015 edition because you're creating
437/// // two mutable references to the same thing.
438/// let focus2 = vec.focus_mut();
439/// // Fails here in 2018 edition because creating focus2
440/// // made focus1's lifetime go out of scope.
441/// assert_eq!(Some(&0), focus1.get(0));
442/// ```
443///
444/// On the other hand, you can split that one focus into multiple sub-focuses,
445/// which is safe because they can't overlap:
446///
447/// ```rust
448/// # #[macro_use] extern crate sp_im;
449/// # use sp_im::vector::Vector;
450/// # use std::iter::FromIterator;
451/// let mut vec = Vector::from_iter(0..1000);
452/// let focus = vec.focus_mut();
453/// let (mut left, mut right) = focus.split_at(500);
454/// assert_eq!(Some(&0), left.get(0));
455/// assert_eq!(Some(&500), right.get(0));
456/// ```
457///
458/// These sub-foci also work as a lock on the vector, even if the focus they
459/// were created from goes out of scope.
460///
461/// ```rust,compile_fail
462/// # #[macro_use] extern crate sp_im;
463/// # use sp_im::vector::Vector;
464/// # use std::iter::FromIterator;
465/// let mut vec = Vector::from_iter(0..1000);
466/// let (left, right) = {
467///     let focus = vec.focus_mut();
468///     focus.split_at(500)
469/// };
470/// // `left` and `right` are still in scope even if `focus` isn't, so we can't
471/// // create another focus:
472/// let focus2 = vec.focus_mut();
473/// assert_eq!(Some(&0), left.get(0));
474/// ```
475///
476/// [Focus]: enum.Focus.html
477pub enum FocusMut<'a, A> {
478  #[doc(hidden)]
479  Single(RRBPool<A>, &'a mut [A]),
480  #[doc(hidden)]
481  Full(RRBPool<A>, TreeFocusMut<'a, A>),
482}
483
484impl<'a, A> FocusMut<'a, A>
485where A: Clone + 'a
486{
487  /// Construct a `FocusMut` for a `Vector`.
488  pub fn new(vector: &'a mut Vector<A>) -> Self {
489    match &mut vector.vector {
490      Inline(pool, chunk) => FocusMut::Single(pool.clone(), chunk),
491      Single(pool, chunk) => FocusMut::Single(
492        pool.clone(),
493        PoolRef::make_mut(&pool.value_pool, chunk).as_mut_slice(),
494      ),
495      Full(pool, tree) => FocusMut::Full(pool.clone(), TreeFocusMut::new(tree)),
496    }
497  }
498
499  /// Get the length of the focused `Vector`.
500  pub fn len(&self) -> usize {
501    match self {
502      FocusMut::Single(_, chunk) => chunk.len(),
503      FocusMut::Full(_, tree) => tree.len(),
504    }
505  }
506
507  /// Test if the focused `Vector` is empty.
508  pub fn is_empty(&self) -> bool { self.len() == 0 }
509
510  /// Get a reference to the value at a given index.
511  pub fn get(&mut self, index: usize) -> Option<&A> {
512    self.get_mut(index).map(|r| &*r)
513  }
514
515  /// Get a mutable reference to the value at a given index.
516  pub fn get_mut(&mut self, index: usize) -> Option<&mut A> {
517    match self {
518      FocusMut::Single(_, chunk) => chunk.get_mut(index),
519      FocusMut::Full(pool, tree) => tree.get(pool, index),
520    }
521  }
522
523  /// Get a reference to the value at a given index.
524  ///
525  /// Panics if the index is out of bounds.
526  pub fn index(&mut self, index: usize) -> &A { &*self.index_mut(index) }
527
528  /// Get a mutable reference to the value at a given index.
529  ///
530  /// Panics if the index is out of bounds.
531  #[allow(clippy::should_implement_trait)] // would if I could
532  pub fn index_mut(&mut self, index: usize) -> &mut A {
533    self.get_mut(index).expect("index out of bounds")
534  }
535
536  /// Update the value at a given index.
537  ///
538  /// Returns `None` if the index is out of bounds, or the replaced value
539  /// otherwise.
540  pub fn set(&mut self, index: usize, value: A) -> Option<A> {
541    match self.get_mut(index) {
542      Some(ref mut pos) => Some(replace(pos, value)),
543      None => None,
544    }
545  }
546
547  /// Swap the values at two given indices.
548  ///
549  /// Panics if either index is out of bounds.
550  ///
551  /// If the indices are equal, this function returns without doing anything.
552  pub fn swap(&mut self, a: usize, b: usize) {
553    if a == b {
554      return;
555    }
556    self.pair(a, b, |left, right| swap(left, right));
557  }
558
559  /// Lookup two indices simultaneously and run a function over them.
560  ///
561  /// Useful because the borrow checker won't let you have more than one
562  /// mutable reference into the same data structure at any given time.
563  ///
564  /// Panics if either index is out of bounds, or if they are the same index.
565  ///
566  /// # Examples
567  ///
568  /// ```rust
569  /// # #[macro_use] extern crate sp_im;
570  /// # use sp_im::vector::Vector;
571  /// # use std::iter::FromIterator;
572  /// let mut vec = vector![1, 2, 3, 4, 5];
573  /// vec.focus_mut().pair(1, 3, |a, b| *a += *b);
574  /// assert_eq!(vector![1, 6, 3, 4, 5], vec);
575  /// ```
576  #[allow(unsafe_code)]
577  pub fn pair<F, B>(&mut self, a: usize, b: usize, mut f: F) -> B
578  where F: FnMut(&mut A, &mut A) -> B {
579    if a == b {
580      panic!("vector::FocusMut::pair: indices cannot be equal!");
581    }
582    let pa: *mut A = self.index_mut(a);
583    let pb: *mut A = self.index_mut(b);
584    unsafe { f(&mut *pa, &mut *pb) }
585  }
586
587  /// Lookup three indices simultaneously and run a function over them.
588  ///
589  /// Useful because the borrow checker won't let you have more than one
590  /// mutable reference into the same data structure at any given time.
591  ///
592  /// Panics if any index is out of bounds, or if any indices are equal.
593  ///
594  /// # Examples
595  ///
596  /// ```rust
597  /// # #[macro_use] extern crate sp_im;
598  /// # use sp_im::vector::Vector;
599  /// # use std::iter::FromIterator;
600  /// let mut vec = vector![1, 2, 3, 4, 5];
601  /// vec.focus_mut().triplet(0, 2, 4, |a, b, c| *a += *b + *c);
602  /// assert_eq!(vector![9, 2, 3, 4, 5], vec);
603  /// ```
604  #[allow(unsafe_code)]
605  pub fn triplet<F, B>(&mut self, a: usize, b: usize, c: usize, mut f: F) -> B
606  where F: FnMut(&mut A, &mut A, &mut A) -> B {
607    if a == b || b == c || a == c {
608      panic!("vector::FocusMut::triplet: indices cannot be equal!");
609    }
610    let pa: *mut A = self.index_mut(a);
611    let pb: *mut A = self.index_mut(b);
612    let pc: *mut A = self.index_mut(c);
613    unsafe { f(&mut *pa, &mut *pb, &mut *pc) }
614  }
615
616  /// Get the chunk for the given index.
617  ///
618  /// This gives you a reference to the leaf node that contains the index,
619  /// along with its start and end indices.
620  pub fn chunk_at(&mut self, index: usize) -> (Range<usize>, &mut [A]) {
621    let len = self.len();
622    if index >= len {
623      panic!("vector::FocusMut::chunk_at: index out of bounds");
624    }
625    match self {
626      FocusMut::Single(_, chunk) => (0..len, chunk),
627      FocusMut::Full(pool, tree) => {
628        let (range, chunk) = tree.get_chunk(pool, index);
629        (range, chunk)
630      }
631    }
632  }
633
634  /// Narrow the focus onto a subslice of the vector.
635  ///
636  /// `FocusMut::narrow(range)` has the same effect as `&slice[range]`, without
637  /// actually modifying the underlying vector.
638  ///
639  /// Panics if the range isn't fully inside the current focus.
640  ///
641  /// ## Examples
642  ///
643  /// ```rust
644  /// # #[macro_use] extern crate sp_im;
645  /// # use sp_im::vector::Vector;
646  /// # use std::iter::FromIterator;
647  /// let mut vec = Vector::from_iter(0..1000);
648  /// let narrowed = vec.focus_mut().narrow(100..200);
649  /// let narrowed_vec = narrowed.unmut().into_iter().cloned().collect();
650  /// assert_eq!(Vector::from_iter(100..200), narrowed_vec);
651  /// ```
652  ///
653  /// [slice::split_at]: https://doc.rust-lang.org/std/primitive.slice.html#method.split_at
654  /// [Vector::split_at]: enum.Vector.html#method.split_at
655  pub fn narrow<R>(self, range: R) -> Self
656  where R: RangeBounds<usize> {
657    let r = to_range(&range, self.len());
658    if r.start > r.end || r.start > self.len() {
659      panic!("vector::FocusMut::narrow: range out of bounds");
660    }
661    match self {
662      FocusMut::Single(pool, chunk) => FocusMut::Single(pool, &mut chunk[r]),
663      FocusMut::Full(pool, tree) => FocusMut::Full(pool, tree.narrow(r)),
664    }
665  }
666
667  /// Split the focus into two.
668  ///
669  /// Given an index `index`, consume the focus and produce two new foci, the
670  /// left onto indices `0..index`, and the right onto indices `index..N`
671  /// where `N` is the length of the current focus.
672  ///
673  /// Panics if the index is out of bounds.
674  ///
675  /// This is the moral equivalent of [`slice::split_at`][slice::split_at], in
676  /// that it leaves the underlying data structure unchanged, unlike
677  /// [`Vector::split_at`][Vector::split_at].
678  ///
679  /// ## Examples
680  ///
681  /// ```rust
682  /// # #[macro_use] extern crate sp_im;
683  /// # use sp_im::vector::Vector;
684  /// # use std::iter::FromIterator;
685  /// let mut vec = Vector::from_iter(0..1000);
686  /// {
687  ///   let (left, right) = vec.focus_mut().split_at(500);
688  ///   for ptr in left {
689  ///     *ptr += 100;
690  ///   }
691  ///   for ptr in right {
692  ///     *ptr -= 100;
693  ///   }
694  /// }
695  /// let expected = Vector::from_iter(100..600) + Vector::from_iter(400..900);
696  /// assert_eq!(expected, vec);
697  /// ```
698  ///
699  /// [slice::split_at]: https://doc.rust-lang.org/std/primitive.slice.html#method.split_at
700  /// [Vector::split_at]: enum.Vector.html#method.split_at
701  #[allow(clippy::redundant_clone)]
702  pub fn split_at(self, index: usize) -> (Self, Self) {
703    if index > self.len() {
704      panic!("vector::FocusMut::split_at: index out of bounds");
705    }
706    match self {
707      FocusMut::Single(pool, chunk) => {
708        let (left, right) = chunk.split_at_mut(index);
709        (FocusMut::Single(pool.clone(), left), FocusMut::Single(pool, right))
710      }
711      FocusMut::Full(pool, tree) => {
712        let (left, right) = tree.split_at(index);
713        (FocusMut::Full(pool.clone(), left), FocusMut::Full(pool, right))
714      }
715    }
716  }
717
718  /// Convert a `FocusMut` into a `Focus`.
719  pub fn unmut(self) -> Focus<'a, A> {
720    match self {
721      FocusMut::Single(_, chunk) => Focus::Single(chunk),
722      FocusMut::Full(_, mut tree) => Focus::Full(TreeFocus {
723        tree: {
724          let t = tree.tree.lock().unwrap();
725          (*t).clone()
726        },
727        view: tree.view.clone(),
728        middle_range: tree.middle_range.clone(),
729        target_range: 0..0,
730        target_ptr: null(),
731      }),
732    }
733  }
734}
735
736impl<'a, A> IntoIterator for FocusMut<'a, A>
737where A: Clone + 'a
738{
739  type IntoIter = IterMut<'a, A>;
740  type Item = &'a mut A;
741
742  fn into_iter(self) -> Self::IntoIter { IterMut::from_focus(self) }
743}
744
745impl<'a, A> Into<Focus<'a, A>> for FocusMut<'a, A>
746where A: Clone + 'a
747{
748  fn into(self) -> Focus<'a, A> { self.unmut() }
749}
750
751pub struct TreeFocusMut<'a, A> {
752  tree: Lock<&'a mut RRB<A>>,
753  view: Range<usize>,
754  middle_range: Range<usize>,
755  target_range: Range<usize>,
756  target_ptr: AtomicPtr<Chunk<A>>,
757}
758
759impl<'a, A> TreeFocusMut<'a, A>
760where A: Clone + 'a
761{
762  fn new(tree: &'a mut RRB<A>) -> Self {
763    let middle_start = tree.outer_f.len() + tree.inner_f.len();
764    let middle_end = middle_start + tree.middle.len();
765    TreeFocusMut {
766      view: 0..tree.length,
767      tree: Lock::new(tree),
768      middle_range: middle_start..middle_end,
769      target_range: 0..0,
770      target_ptr: AtomicPtr::default(),
771    }
772  }
773
774  fn len(&self) -> usize { self.view.end - self.view.start }
775
776  fn narrow(self, mut view: Range<usize>) -> Self {
777    view.start += self.view.start;
778    view.end += self.view.start;
779    TreeFocusMut {
780      view,
781      middle_range: self.middle_range.clone(),
782      target_range: 0..0,
783      target_ptr: AtomicPtr::default(),
784      tree: self.tree,
785    }
786  }
787
788  fn split_at(self, index: usize) -> (Self, Self) {
789    let len = self.len();
790    debug_assert!(index <= len);
791    #[allow(unsafe_code)]
792    let left = TreeFocusMut {
793      view: self.view.start..(self.view.start + index),
794      middle_range: self.middle_range.clone(),
795      target_range: 0..0,
796      target_ptr: AtomicPtr::default(),
797      tree: self.tree.clone(),
798    };
799    let right = TreeFocusMut {
800      view: (self.view.start + index)..(self.view.start + len),
801      middle_range: self.middle_range.clone(),
802      target_range: 0..0,
803      target_ptr: AtomicPtr::default(),
804      tree: self.tree,
805    };
806    (left, right)
807  }
808
809  fn physical_index(&self, index: usize) -> usize {
810    debug_assert!(index < self.view.end);
811    self.view.start + index
812  }
813
814  fn logical_range(&self, range: &Range<usize>) -> Range<usize> {
815    (range.start - self.view.start)..(range.end - self.view.start)
816  }
817
818  fn set_focus(&mut self, pool: &RRBPool<A>, index: usize) {
819    let mut tree = self.tree.lock().expect(
820      "sp_im::vector::Focus::set_focus: unable to acquire exclusive lock on \
821       Vector",
822    );
823    if index < self.middle_range.start {
824      let outer_len = tree.outer_f.len();
825      if index < outer_len {
826        self.target_range = 0..outer_len;
827        self.target_ptr.store(
828          PoolRef::make_mut(&pool.value_pool, &mut tree.outer_f),
829          Ordering::Relaxed,
830        );
831      }
832      else {
833        self.target_range = outer_len..self.middle_range.start;
834        self.target_ptr.store(
835          PoolRef::make_mut(&pool.value_pool, &mut tree.inner_f),
836          Ordering::Relaxed,
837        );
838      }
839    }
840    else if index >= self.middle_range.end {
841      let outer_start = self.middle_range.end + tree.inner_b.len();
842      if index < outer_start {
843        self.target_range = self.middle_range.end..outer_start;
844        self.target_ptr.store(
845          PoolRef::make_mut(&pool.value_pool, &mut tree.inner_b),
846          Ordering::Relaxed,
847        );
848      }
849      else {
850        self.target_range = outer_start..tree.length;
851        self.target_ptr.store(
852          PoolRef::make_mut(&pool.value_pool, &mut tree.outer_b),
853          Ordering::Relaxed,
854        );
855      }
856    }
857    else {
858      let tree_index = index - self.middle_range.start;
859      let level = tree.middle_level;
860      let middle = Ref::make_mut(&mut tree.middle);
861      let (range, ptr) = middle.lookup_chunk_mut(pool, level, 0, tree_index);
862      self.target_range = (range.start + self.middle_range.start)
863        ..(range.end + self.middle_range.start);
864      self.target_ptr.store(ptr, Ordering::Relaxed);
865    }
866  }
867
868  #[allow(unsafe_code)]
869  fn get_focus(&mut self) -> &mut Chunk<A> {
870    unsafe { &mut *self.target_ptr.load(Ordering::Relaxed) }
871  }
872
873  pub fn get(&mut self, pool: &RRBPool<A>, index: usize) -> Option<&mut A> {
874    if index >= self.len() {
875      return None;
876    }
877    let phys_index = self.physical_index(index);
878    if !contains(&self.target_range, &phys_index) {
879      self.set_focus(pool, phys_index);
880    }
881    let target_phys_index = phys_index - self.target_range.start;
882    Some(&mut self.get_focus()[target_phys_index])
883  }
884
885  pub fn get_chunk(
886    &mut self,
887    pool: &RRBPool<A>,
888    index: usize,
889  ) -> (Range<usize>, &mut [A]) {
890    let phys_index = self.physical_index(index);
891    if !contains(&self.target_range, &phys_index) {
892      self.set_focus(pool, phys_index);
893    }
894    let mut left = 0;
895    let mut right = 0;
896    if self.target_range.start < self.view.start {
897      left = self.view.start - self.target_range.start;
898    }
899    if self.target_range.end > self.view.end {
900      right = self.target_range.end - self.view.end;
901    }
902    let phys_range =
903      (self.target_range.start + left)..(self.target_range.end - right);
904    let log_range = self.logical_range(&phys_range);
905    let slice_len = self.get_focus().len();
906    let slice =
907      &mut (self.get_focus().as_mut_slice())[left..(slice_len - right)];
908    (log_range, slice)
909  }
910}
sp_im/vector/focus.rs

sp_im/vector/
focus.rs
