src/librustc_data_structures/indexed_set.rs

   1 // Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use std::fmt;
  12 use std::iter;
  13 use std::marker::PhantomData;
  14 use std::mem;
  15 use std::ops::{Deref, DerefMut, Range};
  16 use std::slice;
  17 use bitslice::{BitSlice, Word};
  18 use bitslice::{bitwise, Union, Subtract};
  19 use indexed_vec::Idx;
  20
  21 /// Represents a set (or packed family of sets), of some element type
  22 /// E, where each E is identified by some unique index type `T`.
  23 ///
  24 /// In other words, `T` is the type used to index into the bitvector
  25 /// this type uses to represent the set of object it holds.
  26 #[derive(Eq, PartialEq)]
  27 pub struct IdxSetBuf<T: Idx> {
  28     _pd: PhantomData<fn(&T)>,
  29     bits: Vec<Word>,
  30 }
  31
  32 impl<T: Idx> Clone for IdxSetBuf<T> {
  33     fn clone(&self) -> Self {
  34         IdxSetBuf { _pd: PhantomData, bits: self.bits.clone() }
  35     }
  36 }
  37
  38 // pnkfelix wants to have this be `IdxSet<T>([Word]) and then pass
  39 // around `&mut IdxSet<T>` or `&IdxSet<T>`.
  40 //
  41 // WARNING: Mapping a `&IdxSetBuf<T>` to `&IdxSet<T>` (at least today)
  42 // requires a transmute relying on representation guarantees that may
  43 // not hold in the future.
  44
  45 /// Represents a set (or packed family of sets), of some element type
  46 /// E, where each E is identified by some unique index type `T`.
  47 ///
  48 /// In other words, `T` is the type used to index into the bitslice
  49 /// this type uses to represent the set of object it holds.
  50 pub struct IdxSet<T: Idx> {
  51     _pd: PhantomData<fn(&T)>,
  52     bits: [Word],
  53 }
  54
  55 impl<T: Idx> fmt::Debug for IdxSetBuf<T> {
  56     fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { self.bits.fmt(w) }
  57 }
  58
  59 impl<T: Idx> fmt::Debug for IdxSet<T> {
  60     fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { self.bits.fmt(w) }
  61 }
  62
  63 impl<T: Idx> IdxSetBuf<T> {
  64     fn new(init: Word, universe_size: usize) -> Self {
  65         let bits_per_word = mem::size_of::<Word>() * 8;
  66         let num_words = (universe_size + (bits_per_word - 1)) / bits_per_word;
  67         IdxSetBuf {
  68             _pd: Default::default(),
  69             bits: vec![init; num_words],
  70         }
  71     }
  72
  73     /// Creates set holding every element whose index falls in range 0..universe_size.
  74     pub fn new_filled(universe_size: usize) -> Self {
  75         Self::new(!0, universe_size)
  76     }
  77
  78     /// Creates set holding no elements.
  79     pub fn new_empty(universe_size: usize) -> Self {
  80         Self::new(0, universe_size)
  81     }
  82 }
  83
  84 impl<T: Idx> IdxSet<T> {
  85     unsafe fn from_slice(s: &[Word]) -> &Self {
  86         mem::transmute(s) // (see above WARNING)
  87     }
  88
  89     unsafe fn from_slice_mut(s: &mut [Word]) -> &mut Self {
  90         mem::transmute(s) // (see above WARNING)
  91     }
  92 }
  93
  94 impl<T: Idx> Deref for IdxSetBuf<T> {
  95     type Target = IdxSet<T>;
  96     fn deref(&self) -> &IdxSet<T> {
  97         unsafe { IdxSet::from_slice(&self.bits) }
  98     }
  99 }
 100
 101 impl<T: Idx> DerefMut for IdxSetBuf<T> {
 102     fn deref_mut(&mut self) -> &mut IdxSet<T> {
 103         unsafe { IdxSet::from_slice_mut(&mut self.bits) }
 104     }
 105 }
 106
 107 impl<T: Idx> IdxSet<T> {
 108     pub fn to_owned(&self) -> IdxSetBuf<T> {
 109         IdxSetBuf {
 110             _pd: Default::default(),
 111             bits: self.bits.to_owned(),
 112         }
 113     }
 114
 115     /// Removes all elements
 116     pub fn clear(&mut self) {
 117         for b in &mut self.bits {
 118             *b = 0;
 119         }
 120     }
 121
 122     /// Removes `elem` from the set `self`; returns true iff this changed `self`.
 123     pub fn remove(&mut self, elem: &T) -> bool {
 124         self.bits.clear_bit(elem.index())
 125     }
 126
 127     /// Adds `elem` to the set `self`; returns true iff this changed `self`.
 128     pub fn add(&mut self, elem: &T) -> bool {
 129         self.bits.set_bit(elem.index())
 130     }
 131
 132     pub fn range(&self, elems: &Range<T>) -> &Self {
 133         let elems = elems.start.index()..elems.end.index();
 134         unsafe { Self::from_slice(&self.bits[elems]) }
 135     }
 136
 137     pub fn range_mut(&mut self, elems: &Range<T>) -> &mut Self {
 138         let elems = elems.start.index()..elems.end.index();
 139         unsafe { Self::from_slice_mut(&mut self.bits[elems]) }
 140     }
 141
 142     /// Returns true iff set `self` contains `elem`.
 143     pub fn contains(&self, elem: &T) -> bool {
 144         self.bits.get_bit(elem.index())
 145     }
 146
 147     pub fn words(&self) -> &[Word] {
 148         &self.bits
 149     }
 150
 151     pub fn words_mut(&mut self) -> &mut [Word] {
 152         &mut self.bits
 153     }
 154
 155     pub fn clone_from(&mut self, other: &IdxSet<T>) {
 156         self.words_mut().clone_from_slice(other.words());
 157     }
 158
 159     pub fn union(&mut self, other: &IdxSet<T>) -> bool {
 160         bitwise(self.words_mut(), other.words(), &Union)
 161     }
 162
 163     pub fn subtract(&mut self, other: &IdxSet<T>) -> bool {
 164         bitwise(self.words_mut(), other.words(), &Subtract)
 165     }
 166
 167     pub fn iter(&self) -> Iter<T> {
 168         Iter {
 169             cur: None,
 170             iter: self.words().iter().enumerate(),
 171             _pd: PhantomData,
 172         }
 173     }
 174 }
 175
 176 pub struct Iter<'a, T: Idx> {
 177     cur: Option<(Word, usize)>,
 178     iter: iter::Enumerate<slice::Iter<'a, Word>>,
 179     _pd: PhantomData<fn(&T)>,
 180 }
 181
 182 impl<'a, T: Idx> Iterator for Iter<'a, T> {
 183     type Item = T;
 184
 185     fn next(&mut self) -> Option<T> {
 186         let word_bits = mem::size_of::<Word>() * 8;
 187         loop {
 188             if let Some((ref mut word, offset)) = self.cur {
 189                 let bit_pos = word.trailing_zeros() as usize;
 190                 if bit_pos != word_bits {
 191                     let bit = 1 << bit_pos;
 192                     *word ^= bit;
 193                     return Some(T::new(bit_pos + offset))
 194                 }
 195             }
 196
 197             match self.iter.next() {
 198                 Some((i, word)) => self.cur = Some((*word, word_bits * i)),
 199                 None => return None,
 200             }
 201         }
 202     }
 203 }