Struct cranelift_egraph::UnionFind

pub struct UnionFind { /* private fields */ }

A union-find data structure. The data structure can allocate Ids, indicating eclasses, and can merge eclasses together.

Implementations

impl UnionFind

pub fn new() -> Self

Create a new UnionFind.

pub fn with_capacity(cap: usize) -> Self

Create a new UnionFind with the given capacity.

pub fn add(&mut self, id: Id)

Add an Id to the UnionFind, with its own equivalence class initially. All Ids must be added before being queried or unioned.

pub fn find(&self, node: Id) -> Id

Find the canonical Id of a given Id.

pub fn find_and_update(&mut self, node: Id) -> Id

Find the canonical Id of a given Id, updating the data structure in the process so that future queries for this Id (and others in its chain up to the root of the equivalence class) will be faster.

pub fn union(&mut self, a: Id, b: Id)

Merge the equivalence classes of the two Ids.

pub fn equiv_id_mut(&mut self, a: Id, b: Id) -> bool

Determine if two Ids are equivalent, after canonicalizing. Update union-find data structure during our canonicalization to make future lookups faster.

pub fn hash_id_mut<H: Hasher>(&mut self, hash: &mut H, id: Id)

Hash an Id after canonicalizing it. Update union-find data structure to make future lookups/hashing faster.

Trait Implementations

impl Clone for UnionFind

fn clone(&self) -> UnionFind

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for UnionFind

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

Formats the value using the given formatter.