From a13354bea05968799a5be5521691322274fa6a9e Mon Sep 17 00:00:00 2001 From: Rémy Rakic Date: Tue, 7 Jan 2025 15:19:05 +0000 Subject: rename `BitSet` to `DenseBitSet` This should make it clearer that this bitset is dense, with the advantages and disadvantages that it entails. --- .../rustc_data_structures/src/graph/implementation/mod.rs | 8 ++++---- compiler/rustc_data_structures/src/graph/iterate/mod.rs | 14 +++++++------- compiler/rustc_data_structures/src/stable_hasher.rs | 4 ++-- compiler/rustc_data_structures/src/stable_hasher/tests.rs | 6 +++--- compiler/rustc_data_structures/src/work_queue.rs | 6 +++--- 5 files changed, 19 insertions(+), 19 deletions(-) (limited to 'compiler/rustc_data_structures/src') diff --git a/compiler/rustc_data_structures/src/graph/implementation/mod.rs b/compiler/rustc_data_structures/src/graph/implementation/mod.rs index 43fdfe6ee0d..7724e9347d8 100644 --- a/compiler/rustc_data_structures/src/graph/implementation/mod.rs +++ b/compiler/rustc_data_structures/src/graph/implementation/mod.rs @@ -22,7 +22,7 @@ use std::fmt::Debug; -use rustc_index::bit_set::BitSet; +use rustc_index::bit_set::DenseBitSet; use tracing::debug; #[cfg(test)] @@ -214,7 +214,7 @@ impl Graph { direction: Direction, entry_node: NodeIndex, ) -> Vec { - let mut visited = BitSet::new_empty(self.len_nodes()); + let mut visited = DenseBitSet::new_empty(self.len_nodes()); let mut stack = vec![]; let mut result = Vec::with_capacity(self.len_nodes()); let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| { @@ -287,7 +287,7 @@ impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> { pub struct DepthFirstTraversal<'g, N, E> { graph: &'g Graph, stack: Vec, - visited: BitSet, + visited: DenseBitSet, direction: Direction, } @@ -297,7 +297,7 @@ impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> { start_node: NodeIndex, direction: Direction, ) -> Self { - let mut visited = BitSet::new_empty(graph.len_nodes()); + let mut visited = DenseBitSet::new_empty(graph.len_nodes()); visited.insert(start_node.node_id()); DepthFirstTraversal { graph, stack: vec![start_node], visited, direction } } diff --git a/compiler/rustc_data_structures/src/graph/iterate/mod.rs b/compiler/rustc_data_structures/src/graph/iterate/mod.rs index cbc6664d853..ecda7d3fba8 100644 --- a/compiler/rustc_data_structures/src/graph/iterate/mod.rs +++ b/compiler/rustc_data_structures/src/graph/iterate/mod.rs @@ -1,6 +1,6 @@ use std::ops::ControlFlow; -use rustc_index::bit_set::BitSet; +use rustc_index::bit_set::DenseBitSet; use rustc_index::{IndexSlice, IndexVec}; use super::{DirectedGraph, StartNode, Successors}; @@ -78,7 +78,7 @@ where { graph: G, stack: Vec, - visited: BitSet, + visited: DenseBitSet, } impl DepthFirstSearch @@ -86,7 +86,7 @@ where G: DirectedGraph + Successors, { pub fn new(graph: G) -> Self { - Self { stack: vec![], visited: BitSet::new_empty(graph.num_nodes()), graph } + Self { stack: vec![], visited: DenseBitSet::new_empty(graph.num_nodes()), graph } } /// Version of `push_start_node` that is convenient for chained @@ -207,8 +207,8 @@ where { graph: &'graph G, stack: Vec>, - visited: BitSet, - settled: BitSet, + visited: DenseBitSet, + settled: DenseBitSet, } impl<'graph, G> TriColorDepthFirstSearch<'graph, G> @@ -219,8 +219,8 @@ where TriColorDepthFirstSearch { graph, stack: vec![], - visited: BitSet::new_empty(graph.num_nodes()), - settled: BitSet::new_empty(graph.num_nodes()), + visited: DenseBitSet::new_empty(graph.num_nodes()), + settled: DenseBitSet::new_empty(graph.num_nodes()), } } diff --git a/compiler/rustc_data_structures/src/stable_hasher.rs b/compiler/rustc_data_structures/src/stable_hasher.rs index 0872bd2c9ac..9cd0cc499ca 100644 --- a/compiler/rustc_data_structures/src/stable_hasher.rs +++ b/compiler/rustc_data_structures/src/stable_hasher.rs @@ -3,7 +3,7 @@ use std::marker::PhantomData; use std::mem; use std::num::NonZero; -use rustc_index::bit_set::{self, BitSet}; +use rustc_index::bit_set::{self, DenseBitSet}; use rustc_index::{Idx, IndexSlice, IndexVec}; use smallvec::SmallVec; @@ -544,7 +544,7 @@ where } } -impl HashStable for BitSet { +impl HashStable for DenseBitSet { fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) { ::std::hash::Hash::hash(self, hasher); } diff --git a/compiler/rustc_data_structures/src/stable_hasher/tests.rs b/compiler/rustc_data_structures/src/stable_hasher/tests.rs index aab50a13af0..635f241847c 100644 --- a/compiler/rustc_data_structures/src/stable_hasher/tests.rs +++ b/compiler/rustc_data_structures/src/stable_hasher/tests.rs @@ -17,9 +17,9 @@ fn hash>(t: &T) -> Hash128 { // Check that bit set hash includes the domain size. #[test] fn test_hash_bit_set() { - use rustc_index::bit_set::BitSet; - let a: BitSet = BitSet::new_empty(1); - let b: BitSet = BitSet::new_empty(2); + use rustc_index::bit_set::DenseBitSet; + let a: DenseBitSet = DenseBitSet::new_empty(1); + let b: DenseBitSet = DenseBitSet::new_empty(2); assert_ne!(a, b); assert_ne!(hash(&a), hash(&b)); } diff --git a/compiler/rustc_data_structures/src/work_queue.rs b/compiler/rustc_data_structures/src/work_queue.rs index ca052e2eac6..815756edfeb 100644 --- a/compiler/rustc_data_structures/src/work_queue.rs +++ b/compiler/rustc_data_structures/src/work_queue.rs @@ -1,7 +1,7 @@ use std::collections::VecDeque; use rustc_index::Idx; -use rustc_index::bit_set::BitSet; +use rustc_index::bit_set::DenseBitSet; /// A work queue is a handy data structure for tracking work left to /// do. (For example, basic blocks left to process.) It is basically a @@ -11,14 +11,14 @@ use rustc_index::bit_set::BitSet; /// and also use a bit set to track occupancy. pub struct WorkQueue { deque: VecDeque, - set: BitSet, + set: DenseBitSet, } impl WorkQueue { /// Creates a new work queue that starts empty, where elements range from (0..len). #[inline] pub fn with_none(len: usize) -> Self { - WorkQueue { deque: VecDeque::with_capacity(len), set: BitSet::new_empty(len) } + WorkQueue { deque: VecDeque::with_capacity(len), set: DenseBitSet::new_empty(len) } } /// Attempt to enqueue `element` in the work queue. Returns false if it was already present. -- cgit 1.4.1-3-g733a5