Enum swh_graph::collections::AdaptiveNodeSet

pub enum AdaptiveNodeSet {
    Sparse {
        max_items: usize,
        data: HashSet<NodeId>,
    },
    Dense {
        data: BitVec,
    },
}

Implementation of NodeSet that dynamically changes the underlying representation based on its content

The current implementation is initialized with a HashSet, but switches to [BitVec] once the data becomes dense.

This has the advantage of allocating little memory if there won’t be many elements, but avoiding the overhead of HashSet when there are.

let mut node_set = AdaptiveNodeSet::new(100);
assert_eq!(format!("{:?}", node_set), "Sparse { max_items: 100, data: {} }");
node_set.insert(10);
assert_eq!(format!("{:?}", node_set), "Sparse { max_items: 100, data: {10} }");
for i in 20..30 {
    node_set.insert(i);
}
assert_eq!(format!("{:?}", node_set), "Dense { data: BitVec { data: [1072694272, 0], len: 100 } }");

Variants

Sparse

Fields

max_items: usize

data: HashSet<NodeId>

Dense

Fields

data: BitVec

Implementations

impl AdaptiveNodeSet

pub fn new(max_items: usize) -> Self

Creates an empty AdaptiveNodeSet that may only store node ids from 0 to max_items-1

pub fn with_capacity(max_items: usize, capacity: usize) -> Self

Creates an empty AdaptiveNodeSet with at least the specified capacity

Trait Implementations

impl Debug for AdaptiveNodeSet

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl NodeSet for AdaptiveNodeSet

fn insert(&mut self, node: usize)

Adds a node to the set

Panics

If node is larger or equal to the max_items value passed to AdaptiveNodeSet::new.

fn contains(&self, node: usize) -> bool

Returns whether the node is part of the set

Panics

If node is larger or equal to the max_items value passed to AdaptiveNodeSet::new.