compiler/rustc_data_structures/src/vec_linked_list.rs

   1 use rustc_index::vec::{Idx, IndexVec};
   2
   3 pub fn iter<Ls>(
   4     first: Option<Ls::LinkIndex>,
   5     links: &Ls,
   6 ) -> impl Iterator<Item = Ls::LinkIndex> + '_
   7 where
   8     Ls: Links,
   9 {
  10     VecLinkedListIterator { links, current: first }
  11 }
  12
  13 pub struct VecLinkedListIterator<Ls>
  14 where
  15     Ls: Links,
  16 {
  17     links: Ls,
  18     current: Option<Ls::LinkIndex>,
  19 }
  20
  21 impl<Ls> Iterator for VecLinkedListIterator<Ls>
  22 where
  23     Ls: Links,
  24 {
  25     type Item = Ls::LinkIndex;
  26
  27     fn next(&mut self) -> Option<Ls::LinkIndex> {
  28         if let Some(c) = self.current {
  29             self.current = <Ls as Links>::next(&self.links, c);
  30             Some(c)
  31         } else {
  32             None
  33         }
  34     }
  35 }
  36
  37 pub trait Links {
  38     type LinkIndex: Copy;
  39
  40     fn next(links: &Self, index: Self::LinkIndex) -> Option<Self::LinkIndex>;
  41 }
  42
  43 impl<Ls> Links for &Ls
  44 where
  45     Ls: Links,
  46 {
  47     type LinkIndex = Ls::LinkIndex;
  48
  49     fn next(links: &Self, index: Ls::LinkIndex) -> Option<Ls::LinkIndex> {
  50         <Ls as Links>::next(links, index)
  51     }
  52 }
  53
  54 pub trait LinkElem {
  55     type LinkIndex: Copy;
  56
  57     fn next(elem: &Self) -> Option<Self::LinkIndex>;
  58 }
  59
  60 impl<L, E> Links for IndexVec<L, E>
  61 where
  62     E: LinkElem<LinkIndex = L>,
  63     L: Idx,
  64 {
  65     type LinkIndex = L;
  66
  67     fn next(links: &Self, index: L) -> Option<L> {
  68         <E as LinkElem>::next(&links[index])
  69     }
  70 }