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::marker::PhantomData;
  13 use std::mem;
  14 use std::ops::{Deref, DerefMut, Range};
  15 use bitslice::{BitSlice, Word};
  16 use bitslice::{bitwise, Union, Subtract};
  17 use indexed_vec::Idx;
  18
  19 /// Represents a set (or packed family of sets), of some element type
  20 /// E, where each E is identified by some unique index type `T`.
  21 ///
  22 /// In other words, `T` is the type used to index into the bitvector
  23 /// this type uses to represent the set of object it holds.
  24 pub struct IdxSetBuf<T: Idx> {
  25     _pd: PhantomData<fn(&T)>,
  26     bits: Vec<Word>,
  27 }
  28
  29 impl<T: Idx> Clone for IdxSetBuf<T> {
  30     fn clone(&self) -> Self {
  31         IdxSetBuf { _pd: PhantomData, bits: self.bits.clone() }
  32     }
  33 }
  34
  35 // pnkfelix wants to have this be `IdxSet<T>([Word]) and then pass
  36 // around `&mut IdxSet<T>` or `&IdxSet<T>`.
  37 //
  38 // WARNING: Mapping a `&IdxSetBuf<T>` to `&IdxSet<T>` (at least today)
  39 // requires a transmute relying on representation guarantees that may
  40 // not hold in the future.
  41
  42 /// Represents a set (or packed family of sets), of some element type
  43 /// E, where each E is identified by some unique index type `T`.
  44 ///
  45 /// In other words, `T` is the type used to index into the bitslice
  46 /// this type uses to represent the set of object it holds.
  47 pub struct IdxSet<T: Idx> {
  48     _pd: PhantomData<fn(&T)>,
  49     bits: [Word],
  50 }
  51
  52 impl<T: Idx> fmt::Debug for IdxSetBuf<T> {
  53     fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { self.bits.fmt(w) }
  54 }
  55
  56 impl<T: Idx> fmt::Debug for IdxSet<T> {
  57     fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { self.bits.fmt(w) }
  58 }
  59
  60 impl<T: Idx> IdxSetBuf<T> {
  61     fn new(init: Word, universe_size: usize) -> Self {
  62         let bits_per_word = mem::size_of::<Word>() * 8;
  63         let num_words = (universe_size + (bits_per_word - 1)) / bits_per_word;
  64         IdxSetBuf {
  65             _pd: Default::default(),
  66             bits: vec![init; num_words],
  67         }
  68     }
  69
  70     /// Creates set holding every element whose index falls in range 0..universe_size.
  71     pub fn new_filled(universe_size: usize) -> Self {
  72         Self::new(!0, universe_size)
  73     }
  74
  75     /// Creates set holding no elements.
  76     pub fn new_empty(universe_size: usize) -> Self {
  77         Self::new(0, universe_size)
  78     }
  79 }
  80
  81 impl<T: Idx> IdxSet<T> {
  82     unsafe fn from_slice(s: &[Word]) -> &Self {
  83         mem::transmute(s) // (see above WARNING)
  84     }
  85
  86     unsafe fn from_slice_mut(s: &mut [Word]) -> &mut Self {
  87         mem::transmute(s) // (see above WARNING)
  88     }
  89 }
  90
  91 impl<T: Idx> Deref for IdxSetBuf<T> {
  92     type Target = IdxSet<T>;
  93     fn deref(&self) -> &IdxSet<T> {
  94         unsafe { IdxSet::from_slice(&self.bits) }
  95     }
  96 }
  97
  98 impl<T: Idx> DerefMut for IdxSetBuf<T> {
  99     fn deref_mut(&mut self) -> &mut IdxSet<T> {
 100         unsafe { IdxSet::from_slice_mut(&mut self.bits) }
 101     }
 102 }
 103
 104 impl<T: Idx> IdxSet<T> {
 105     pub fn to_owned(&self) -> IdxSetBuf<T> {
 106         IdxSetBuf {
 107             _pd: Default::default(),
 108             bits: self.bits.to_owned(),
 109         }
 110     }
 111
 112     /// Removes `elem` from the set `self`; returns true iff this changed `self`.
 113     pub fn remove(&mut self, elem: &T) -> bool {
 114         self.bits.clear_bit(elem.index())
 115     }
 116
 117     /// Adds `elem` to the set `self`; returns true iff this changed `self`.
 118     pub fn add(&mut self, elem: &T) -> bool {
 119         self.bits.set_bit(elem.index())
 120     }
 121
 122     pub fn range(&self, elems: &Range<T>) -> &Self {
 123         let elems = elems.start.index()..elems.end.index();
 124         unsafe { Self::from_slice(&self.bits[elems]) }
 125     }
 126
 127     pub fn range_mut(&mut self, elems: &Range<T>) -> &mut Self {
 128         let elems = elems.start.index()..elems.end.index();
 129         unsafe { Self::from_slice_mut(&mut self.bits[elems]) }
 130     }
 131
 132     /// Returns true iff set `self` contains `elem`.
 133     pub fn contains(&self, elem: &T) -> bool {
 134         self.bits.get_bit(elem.index())
 135     }
 136
 137     pub fn words(&self) -> &[Word] {
 138         &self.bits
 139     }
 140
 141     pub fn words_mut(&mut self) -> &mut [Word] {
 142         &mut self.bits
 143     }
 144
 145     pub fn clone_from(&mut self, other: &IdxSet<T>) {
 146         self.words_mut().clone_from_slice(other.words());
 147     }
 148
 149     pub fn union(&mut self, other: &IdxSet<T>) -> bool {
 150         bitwise(self.words_mut(), other.words(), &Union)
 151     }
 152
 153     pub fn subtract(&mut self, other: &IdxSet<T>) -> bool {
 154         bitwise(self.words_mut(), other.words(), &Subtract)
 155     }
 156
 157     /// Calls `f` on each index value held in this set, up to the
 158     /// bound `max_bits` on the size of universe of indexes.
 159     pub fn each_bit<F>(&self, max_bits: usize, f: F) where F: FnMut(T) {
 160         each_bit(self, max_bits, f)
 161     }
 162
 163     /// Removes all elements from this set.
 164     pub fn reset_to_empty(&mut self) {
 165         for word in self.words_mut() { *word = 0; }
 166     }
 167
 168     pub fn elems(&self, universe_size: usize) -> Elems<T> {
 169         Elems { i: 0, set: self, universe_size: universe_size }
 170     }
 171 }
 172
 173 pub struct Elems<'a, T: Idx> { i: usize, set: &'a IdxSet<T>, universe_size: usize }
 174
 175 impl<'a, T: Idx> Iterator for Elems<'a, T> {
 176     type Item = T;
 177     fn next(&mut self) -> Option<T> {
 178         if self.i >= self.universe_size { return None; }
 179         let mut i = self.i;
 180         loop {
 181             if i >= self.universe_size {
 182                 self.i = i; // (mark iteration as complete.)
 183                 return None;
 184             }
 185             if self.set.contains(&T::new(i)) {
 186                 self.i = i + 1; // (next element to start at.)
 187                 return Some(T::new(i));
 188             }
 189             i = i + 1;
 190         }
 191     }
 192 }
 193
 194 fn each_bit<T: Idx, F>(words: &IdxSet<T>, max_bits: usize, mut f: F) where F: FnMut(T) {
 195     let usize_bits: usize = mem::size_of::<usize>() * 8;
 196
 197     for (word_index, &word) in words.words().iter().enumerate() {
 198         if word != 0 {
 199             let base_index = word_index * usize_bits;
 200             for offset in 0..usize_bits {
 201                 let bit = 1 << offset;
 202                 if (word & bit) != 0 {
 203                     // NB: we round up the total number of bits
 204                     // that we store in any given bit set so that
 205                     // it is an even multiple of usize::BITS. This
 206                     // means that there may be some stray bits at
 207                     // the end that do not correspond to any
 208                     // actual value; that's why we first check
 209                     // that we are in range of bits_per_block.
 210                     let bit_index = base_index + offset as usize;
 211                     if bit_index >= max_bits {
 212                         return;
 213                     } else {
 214                         f(Idx::new(bit_index));
 215                     }
 216                 }
 217             }
 218         }
 219     }
 220 }