Merge remote-tracking branch 'origin/master' into gen

[rust.git] / src / librustc_data_structures / indexed_set.rs

diff --git a/src/librustc_data_structures/indexed_set.rs b/src/librustc_data_structures/indexed_set.rs
index cc56289a5633467998551c93a0a27facc6ee7b99..47fa21e3bf0b2bf6a1e47f4d6c78b94c1aca9246 100644 (file)
--- a/src/librustc_data_structures/indexed_set.rs
+++ b/src/librustc_data_structures/indexed_set.rs
@@ -171,6 +171,70 @@ pub fn iter(&self) -> Iter<T> {
             _pd: PhantomData,
         }
     }
+
+    /// Calls `f` on each index value held in this set, up to the
+    /// bound `max_bits` on the size of universe of indexes.
+    pub fn each_bit<F>(&self, max_bits: usize, f: F) where F: FnMut(T) {
+        each_bit(self, max_bits, f)
+    }
+
+    /// Removes all elements from this set.
+    pub fn reset_to_empty(&mut self) {
+        for word in self.words_mut() { *word = 0; }
+    }
+
+    pub fn elems(&self, universe_size: usize) -> Elems<T> {
+        Elems { i: 0, set: self, universe_size: universe_size }
+    }
+}
+
+pub struct Elems<'a, T: Idx> { i: usize, set: &'a IdxSet<T>, universe_size: usize }
+
+impl<'a, T: Idx> Iterator for Elems<'a, T> {
+    type Item = T;
+    fn next(&mut self) -> Option<T> {
+        if self.i >= self.universe_size { return None; }
+        let mut i = self.i;
+        loop {
+            if i >= self.universe_size {
+                self.i = i; // (mark iteration as complete.)
+                return None;
+            }
+            if self.set.contains(&T::new(i)) {
+                self.i = i + 1; // (next element to start at.)
+                return Some(T::new(i));
+            }
+            i = i + 1;
+        }
+    }
+}
+
+fn each_bit<T: Idx, F>(words: &IdxSet<T>, max_bits: usize, mut f: F) where F: FnMut(T) {
+    let usize_bits: usize = mem::size_of::<usize>() * 8;
+
+    for (word_index, &word) in words.words().iter().enumerate() {
+        if word != 0 {
+            let base_index = word_index * usize_bits;
+            for offset in 0..usize_bits {
+                let bit = 1 << offset;
+                if (word & bit) != 0 {
+                    // NB: we round up the total number of bits
+                    // that we store in any given bit set so that
+                    // it is an even multiple of usize::BITS. This
+                    // means that there may be some stray bits at
+                    // the end that do not correspond to any
+                    // actual value; that's why we first check
+                    // that we are in range of bits_per_block.
+                    let bit_index = base_index + offset as usize;
+                    if bit_index >= max_bits {
+                        return;
+                    } else {
+                        f(Idx::new(bit_index));
+                    }
+                }
+            }
+        }
+    }
 }
 
 pub struct Iter<'a, T: Idx> {