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 array_vec::ArrayVec;
  12 use std::fmt;
  13 use std::iter;
  14 use std::marker::PhantomData;
  15 use std::mem;
  16 use std::slice;
  17 use bitslice::{BitSlice, Word};
  18 use bitslice::{bitwise, Union, Subtract, Intersect};
  19 use indexed_vec::Idx;
  20 use rustc_serialize;
  21
  22 /// This is implemented by all the index sets so that IdxSet::union() can be
  23 /// passed any type of index set.
  24 pub trait UnionIntoIdxSet<T: Idx> {
  25     // Performs `other = other | self`.
  26     fn union_into(&self, other: &mut IdxSet<T>) -> bool;
  27 }
  28
  29 /// This is implemented by all the index sets so that IdxSet::subtract() can be
  30 /// passed any type of index set.
  31 pub trait SubtractFromIdxSet<T: Idx> {
  32     // Performs `other = other - self`.
  33     fn subtract_from(&self, other: &mut IdxSet<T>) -> bool;
  34 }
  35
  36 /// Represents a set of some element type E, where each E is identified by some
  37 /// unique index type `T`.
  38 ///
  39 /// In other words, `T` is the type used to index into the bitvector
  40 /// this type uses to represent the set of object it holds.
  41 ///
  42 /// The representation is dense, using one bit per possible element.
  43 #[derive(Eq, PartialEq)]
  44 pub struct IdxSet<T: Idx> {
  45     _pd: PhantomData<fn(&T)>,
  46     bits: Vec<Word>,
  47 }
  48
  49 impl<T: Idx> Clone for IdxSet<T> {
  50     fn clone(&self) -> Self {
  51         IdxSet { _pd: PhantomData, bits: self.bits.clone() }
  52     }
  53 }
  54
  55 impl<T: Idx> rustc_serialize::Encodable for IdxSet<T> {
  56     fn encode<E: rustc_serialize::Encoder>(&self,
  57                                      encoder: &mut E)
  58                                      -> Result<(), E::Error> {
  59         self.bits.encode(encoder)
  60     }
  61 }
  62
  63 impl<T: Idx> rustc_serialize::Decodable for IdxSet<T> {
  64     fn decode<D: rustc_serialize::Decoder>(d: &mut D) -> Result<IdxSet<T>, D::Error> {
  65         let words: Vec<Word> = rustc_serialize::Decodable::decode(d)?;
  66
  67         Ok(IdxSet {
  68             _pd: PhantomData,
  69             bits: words,
  70         })
  71     }
  72 }
  73
  74 const BITS_PER_WORD: usize = mem::size_of::<Word>() * 8;
  75
  76 impl<T: Idx> fmt::Debug for IdxSet<T> {
  77     fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
  78         w.debug_list()
  79          .entries(self.iter())
  80          .finish()
  81     }
  82 }
  83
  84 impl<T: Idx> IdxSet<T> {
  85     fn new(init: Word, domain_size: usize) -> Self {
  86         let num_words = (domain_size + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
  87         IdxSet {
  88             _pd: Default::default(),
  89             bits: vec![init; num_words],
  90         }
  91     }
  92
  93     /// Creates set holding every element whose index falls in range 0..domain_size.
  94     pub fn new_filled(domain_size: usize) -> Self {
  95         let mut result = Self::new(!0, domain_size);
  96         result.trim_to(domain_size);
  97         result
  98     }
  99
 100     /// Creates set holding no elements.
 101     pub fn new_empty(domain_size: usize) -> Self {
 102         Self::new(0, domain_size)
 103     }
 104
 105     /// Duplicates as a hybrid set.
 106     pub fn to_hybrid(&self) -> HybridIdxSet<T> {
 107         // This domain_size may be slightly larger than the one specified
 108         // upon creation, due to rounding up to a whole word. That's ok.
 109         let domain_size = self.bits.len() * BITS_PER_WORD;
 110
 111         // Note: we currently don't bother trying to make a Sparse set.
 112         HybridIdxSet::Dense(self.to_owned(), domain_size)
 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     /// Sets all elements up to `domain_size`
 123     pub fn set_up_to(&mut self, domain_size: usize) {
 124         for b in &mut self.bits {
 125             *b = !0;
 126         }
 127         self.trim_to(domain_size);
 128     }
 129
 130     /// Clear all elements above `domain_size`.
 131     fn trim_to(&mut self, domain_size: usize) {
 132         // `trim_block` is the first block where some bits have
 133         // to be cleared.
 134         let trim_block = domain_size / BITS_PER_WORD;
 135
 136         // all the blocks above it have to be completely cleared.
 137         if trim_block < self.bits.len() {
 138             for b in &mut self.bits[trim_block+1..] {
 139                 *b = 0;
 140             }
 141
 142             // at that block, the `domain_size % BITS_PER_WORD` LSBs
 143             // should remain.
 144             let remaining_bits = domain_size % BITS_PER_WORD;
 145             let mask = (1<<remaining_bits)-1;
 146             self.bits[trim_block] &= mask;
 147         }
 148     }
 149
 150     /// Removes `elem` from the set `self`; returns true iff this changed `self`.
 151     pub fn remove(&mut self, elem: &T) -> bool {
 152         self.bits.clear_bit(elem.index())
 153     }
 154
 155     /// Adds `elem` to the set `self`; returns true iff this changed `self`.
 156     pub fn add(&mut self, elem: &T) -> bool {
 157         self.bits.set_bit(elem.index())
 158     }
 159
 160     /// Returns true iff set `self` contains `elem`.
 161     pub fn contains(&self, elem: &T) -> bool {
 162         self.bits.get_bit(elem.index())
 163     }
 164
 165     pub fn words(&self) -> &[Word] {
 166         &self.bits
 167     }
 168
 169     pub fn words_mut(&mut self) -> &mut [Word] {
 170         &mut self.bits
 171     }
 172
 173     /// Efficiently overwrite `self` with `other`. Panics if `self` and `other`
 174     /// don't have the same length.
 175     pub fn overwrite(&mut self, other: &IdxSet<T>) {
 176         self.words_mut().clone_from_slice(other.words());
 177     }
 178
 179     /// Set `self = self | other` and return true if `self` changed
 180     /// (i.e., if new bits were added).
 181     pub fn union(&mut self, other: &impl UnionIntoIdxSet<T>) -> bool {
 182         other.union_into(self)
 183     }
 184
 185     /// Set `self = self - other` and return true if `self` changed.
 186     /// (i.e., if any bits were removed).
 187     pub fn subtract(&mut self, other: &impl SubtractFromIdxSet<T>) -> bool {
 188         other.subtract_from(self)
 189     }
 190
 191     /// Set `self = self & other` and return true if `self` changed.
 192     /// (i.e., if any bits were removed).
 193     pub fn intersect(&mut self, other: &IdxSet<T>) -> bool {
 194         bitwise(self.words_mut(), other.words(), &Intersect)
 195     }
 196
 197     pub fn iter(&self) -> Iter<T> {
 198         Iter {
 199             cur: None,
 200             iter: self.words().iter().enumerate(),
 201             _pd: PhantomData,
 202         }
 203     }
 204 }
 205
 206 impl<T: Idx> UnionIntoIdxSet<T> for IdxSet<T> {
 207     fn union_into(&self, other: &mut IdxSet<T>) -> bool {
 208         bitwise(other.words_mut(), self.words(), &Union)
 209     }
 210 }
 211
 212 impl<T: Idx> SubtractFromIdxSet<T> for IdxSet<T> {
 213     fn subtract_from(&self, other: &mut IdxSet<T>) -> bool {
 214         bitwise(other.words_mut(), self.words(), &Subtract)
 215     }
 216 }
 217
 218 pub struct Iter<'a, T: Idx> {
 219     cur: Option<(Word, usize)>,
 220     iter: iter::Enumerate<slice::Iter<'a, Word>>,
 221     _pd: PhantomData<fn(&T)>,
 222 }
 223
 224 impl<'a, T: Idx> Iterator for Iter<'a, T> {
 225     type Item = T;
 226
 227     fn next(&mut self) -> Option<T> {
 228         loop {
 229             if let Some((ref mut word, offset)) = self.cur {
 230                 let bit_pos = word.trailing_zeros() as usize;
 231                 if bit_pos != BITS_PER_WORD {
 232                     let bit = 1 << bit_pos;
 233                     *word ^= bit;
 234                     return Some(T::new(bit_pos + offset))
 235                 }
 236             }
 237
 238             let (i, word) = self.iter.next()?;
 239             self.cur = Some((*word, BITS_PER_WORD * i));
 240         }
 241     }
 242 }
 243
 244 const SPARSE_MAX: usize = 8;
 245
 246 /// A sparse index set with a maximum of SPARSE_MAX elements. Used by
 247 /// HybridIdxSet; do not use directly.
 248 ///
 249 /// The elements are stored as an unsorted vector with no duplicates.
 250 #[derive(Clone, Debug)]
 251 pub struct SparseIdxSet<T: Idx>(ArrayVec<[T; SPARSE_MAX]>);
 252
 253 impl<T: Idx> SparseIdxSet<T> {
 254     fn new() -> Self {
 255         SparseIdxSet(ArrayVec::new())
 256     }
 257
 258     fn len(&self) -> usize {
 259         self.0.len()
 260     }
 261
 262     fn contains(&self, elem: &T) -> bool {
 263         self.0.contains(elem)
 264     }
 265
 266     fn add(&mut self, elem: &T) -> bool {
 267         // Ensure there are no duplicates.
 268         if self.0.contains(elem) {
 269             false
 270         } else {
 271             self.0.push(*elem);
 272             true
 273         }
 274     }
 275
 276     fn remove(&mut self, elem: &T) -> bool {
 277         if let Some(i) = self.0.iter().position(|e| e == elem) {
 278             // Swap the found element to the end, then pop it.
 279             let len = self.0.len();
 280             self.0.swap(i, len - 1);
 281             self.0.pop();
 282             true
 283         } else {
 284             false
 285         }
 286     }
 287
 288     fn to_dense(&self, domain_size: usize) -> IdxSet<T> {
 289         let mut dense = IdxSet::new_empty(domain_size);
 290         for elem in self.0.iter() {
 291             dense.add(elem);
 292         }
 293         dense
 294     }
 295
 296     fn iter(&self) -> SparseIter<T> {
 297         SparseIter {
 298             iter: self.0.iter(),
 299         }
 300     }
 301 }
 302
 303 impl<T: Idx> UnionIntoIdxSet<T> for SparseIdxSet<T> {
 304     fn union_into(&self, other: &mut IdxSet<T>) -> bool {
 305         let mut changed = false;
 306         for elem in self.iter() {
 307             changed |= other.add(&elem);
 308         }
 309         changed
 310     }
 311 }
 312
 313 impl<T: Idx> SubtractFromIdxSet<T> for SparseIdxSet<T> {
 314     fn subtract_from(&self, other: &mut IdxSet<T>) -> bool {
 315         let mut changed = false;
 316         for elem in self.iter() {
 317             changed |= other.remove(&elem);
 318         }
 319         changed
 320     }
 321 }
 322
 323 pub struct SparseIter<'a, T: Idx> {
 324     iter: slice::Iter<'a, T>,
 325 }
 326
 327 impl<'a, T: Idx> Iterator for SparseIter<'a, T> {
 328     type Item = T;
 329
 330     fn next(&mut self) -> Option<T> {
 331         self.iter.next().map(|e| *e)
 332     }
 333 }
 334
 335 /// Like IdxSet, but with a hybrid representation: sparse when there are few
 336 /// elements in the set, but dense when there are many. It's especially
 337 /// efficient for sets that typically have a small number of elements, but a
 338 /// large `domain_size`, and are cleared frequently.
 339 #[derive(Clone, Debug)]
 340 pub enum HybridIdxSet<T: Idx> {
 341     Sparse(SparseIdxSet<T>, usize),
 342     Dense(IdxSet<T>, usize),
 343 }
 344
 345 impl<T: Idx> HybridIdxSet<T> {
 346     pub fn new_empty(domain_size: usize) -> Self {
 347         HybridIdxSet::Sparse(SparseIdxSet::new(), domain_size)
 348     }
 349
 350     pub fn clear(&mut self) {
 351         let domain_size = match *self {
 352             HybridIdxSet::Sparse(_, size) => size,
 353             HybridIdxSet::Dense(_, size) => size,
 354         };
 355         *self = HybridIdxSet::new_empty(domain_size);
 356     }
 357
 358     /// Returns true iff set `self` contains `elem`.
 359     pub fn contains(&self, elem: &T) -> bool {
 360         match self {
 361             HybridIdxSet::Sparse(sparse, _) => sparse.contains(elem),
 362             HybridIdxSet::Dense(dense, _) => dense.contains(elem),
 363         }
 364     }
 365
 366     /// Adds `elem` to the set `self`.
 367     pub fn add(&mut self, elem: &T) -> bool {
 368         match self {
 369             HybridIdxSet::Sparse(sparse, _) if sparse.len() < SPARSE_MAX => {
 370                 // The set is sparse and has space for `elem`.
 371                 sparse.add(elem)
 372             }
 373             HybridIdxSet::Sparse(sparse, _) if sparse.contains(elem) => {
 374                 // The set is sparse and does not have space for `elem`, but
 375                 // that doesn't matter because `elem` is already present.
 376                 false
 377             }
 378             HybridIdxSet::Sparse(_, _) => {
 379                 // The set is sparse and full. Convert to a dense set.
 380                 //
 381                 // FIXME: This code is awful, but I can't work out how else to
 382                 //        appease the borrow checker.
 383                 let dummy = HybridIdxSet::Sparse(SparseIdxSet::new(), 0);
 384                 match mem::replace(self, dummy) {
 385                     HybridIdxSet::Sparse(sparse, domain_size) => {
 386                         let mut dense = sparse.to_dense(domain_size);
 387                         let changed = dense.add(elem);
 388                         assert!(changed);
 389                         mem::replace(self, HybridIdxSet::Dense(dense, domain_size));
 390                         changed
 391                     }
 392                     _ => panic!("impossible"),
 393                 }
 394             }
 395
 396             HybridIdxSet::Dense(dense, _) => dense.add(elem),
 397         }
 398     }
 399
 400     /// Removes `elem` from the set `self`.
 401     pub fn remove(&mut self, elem: &T) -> bool {
 402         // Note: we currently don't bother going from Dense back to Sparse.
 403         match self {
 404             HybridIdxSet::Sparse(sparse, _) => sparse.remove(elem),
 405             HybridIdxSet::Dense(dense, _) => dense.remove(elem),
 406         }
 407     }
 408
 409     /// Converts to a dense set, consuming itself in the process.
 410     pub fn to_dense(self) -> IdxSet<T> {
 411         match self {
 412             HybridIdxSet::Sparse(sparse, domain_size) => sparse.to_dense(domain_size),
 413             HybridIdxSet::Dense(dense, _) => dense,
 414         }
 415     }
 416
 417     /// Iteration order is unspecified.
 418     pub fn iter(&self) -> HybridIter<T> {
 419         match self {
 420             HybridIdxSet::Sparse(sparse, _) => HybridIter::Sparse(sparse.iter()),
 421             HybridIdxSet::Dense(dense, _) => HybridIter::Dense(dense.iter()),
 422         }
 423     }
 424 }
 425
 426 impl<T: Idx> UnionIntoIdxSet<T> for HybridIdxSet<T> {
 427     fn union_into(&self, other: &mut IdxSet<T>) -> bool {
 428         match self {
 429             HybridIdxSet::Sparse(sparse, _) => sparse.union_into(other),
 430             HybridIdxSet::Dense(dense, _) => dense.union_into(other),
 431         }
 432     }
 433 }
 434
 435 impl<T: Idx> SubtractFromIdxSet<T> for HybridIdxSet<T> {
 436     fn subtract_from(&self, other: &mut IdxSet<T>) -> bool {
 437         match self {
 438             HybridIdxSet::Sparse(sparse, _) => sparse.subtract_from(other),
 439             HybridIdxSet::Dense(dense, _) => dense.subtract_from(other),
 440         }
 441     }
 442 }
 443
 444 pub enum HybridIter<'a, T: Idx> {
 445     Sparse(SparseIter<'a, T>),
 446     Dense(Iter<'a, T>),
 447 }
 448
 449 impl<'a, T: Idx> Iterator for HybridIter<'a, T> {
 450     type Item = T;
 451
 452     fn next(&mut self) -> Option<T> {
 453         match self {
 454             HybridIter::Sparse(sparse) => sparse.next(),
 455             HybridIter::Dense(dense) => dense.next(),
 456         }
 457     }
 458 }
 459
 460 #[test]
 461 fn test_trim_to() {
 462     use std::cmp;
 463
 464     for i in 0..256 {
 465         let mut idx_buf: IdxSet<usize> = IdxSet::new_filled(128);
 466         idx_buf.trim_to(i);
 467
 468         let elems: Vec<usize> = idx_buf.iter().collect();
 469         let expected: Vec<usize> = (0..cmp::min(i, 128)).collect();
 470         assert_eq!(elems, expected);
 471     }
 472 }
 473
 474 #[test]
 475 fn test_set_up_to() {
 476     for i in 0..128 {
 477         for mut idx_buf in
 478             vec![IdxSet::new_empty(128), IdxSet::new_filled(128)]
 479             .into_iter()
 480         {
 481             idx_buf.set_up_to(i);
 482
 483             let elems: Vec<usize> = idx_buf.iter().collect();
 484             let expected: Vec<usize> = (0..i).collect();
 485             assert_eq!(elems, expected);
 486         }
 487     }
 488 }
 489
 490 #[test]
 491 fn test_new_filled() {
 492     for i in 0..128 {
 493         let idx_buf = IdxSet::new_filled(i);
 494         let elems: Vec<usize> = idx_buf.iter().collect();
 495         let expected: Vec<usize> = (0..i).collect();
 496         assert_eq!(elems, expected);
 497     }
 498 }