Struct cargo::util::DependencyQueue
source · pub struct DependencyQueue<N: Hash + Eq, E: Hash + Eq, V> {
dep_map: HashMap<N, (HashSet<(N, E)>, V)>,
reverse_dep_map: HashMap<N, HashMap<E, HashSet<N>>>,
priority: HashMap<N, usize>,
cost: HashMap<N, usize>,
}
Fields§
§dep_map: HashMap<N, (HashSet<(N, E)>, V)>
A list of all known keys to build.
The value of the hash map is list of dependencies which still need to be built before the package can be built. Note that the set is dynamically updated as more dependencies are built.
reverse_dep_map: HashMap<N, HashMap<E, HashSet<N>>>
A reverse mapping of a package to all packages that depend on that package.
This map is statically known and does not get updated throughout the lifecycle of the DependencyQueue.
This is sort of like a HashMap<(N, E), HashSet<N>>
map, but more
easily indexable with just an N
priority: HashMap<N, usize>
The relative priority of this package. Higher values should be scheduled sooner.
cost: HashMap<N, usize>
An expected cost for building this package. Used to determine priority.
Implementations§
source§impl<N: Hash + Eq, E: Hash + Eq, V> DependencyQueue<N, E, V>
impl<N: Hash + Eq, E: Hash + Eq, V> DependencyQueue<N, E, V>
sourcepub fn new() -> DependencyQueue<N, E, V>
pub fn new() -> DependencyQueue<N, E, V>
Creates a new dependency queue with 0 packages.
source§impl<N: Hash + Eq + Clone, E: Eq + Hash + Clone, V> DependencyQueue<N, E, V>
impl<N: Hash + Eq + Clone, E: Eq + Hash + Clone, V> DependencyQueue<N, E, V>
sourcepub fn queue(
&mut self,
key: N,
value: V,
dependencies: impl IntoIterator<Item = (N, E)>,
cost: usize
)
pub fn queue( &mut self, key: N, value: V, dependencies: impl IntoIterator<Item = (N, E)>, cost: usize )
Adds a new node and its dependencies to this queue.
The key
specified is a new node in the dependency graph, and the node
depend on all the dependencies iterated by dependencies
. Each
dependency is a node/edge pair, where edges can be thought of as
productions from nodes (aka if it’s just ()
it’s just waiting for the
node to finish).
An optional value
can also be associated with key
which is reclaimed
when the node is ready to go.
The cost parameter can be used to hint at the relative cost of building this node. This implementation does not care about the units of this value, so the calling code is free to use whatever they’d like. In general, higher cost nodes are expected to take longer to build.
sourcepub fn queue_finished(&mut self)
pub fn queue_finished(&mut self)
All nodes have been added, calculate some internal metadata and prepare
for dequeue
.
sourcepub fn dequeue(&mut self) -> Option<(N, V, usize)>
pub fn dequeue(&mut self) -> Option<(N, V, usize)>
Dequeues a package that is ready to be built.
A package is ready to be built when it has 0 un-built dependencies. If
None
is returned then no packages are ready to be built.
sourcepub fn finish(&mut self, node: &N, edge: &E) -> Vec<&N>
pub fn finish(&mut self, node: &N, edge: &E) -> Vec<&N>
Indicate that something has finished.
Calling this function indicates that the node
has produced edge
. All
remaining work items which only depend on this node/edge pair are now
candidates to start their job.
Returns the nodes that are now allowed to be dequeued as a result of finishing this node.
Trait Implementations§
Auto Trait Implementations§
impl<N, E, V> RefUnwindSafe for DependencyQueue<N, E, V>where E: RefUnwindSafe, N: RefUnwindSafe, V: RefUnwindSafe,
impl<N, E, V> Send for DependencyQueue<N, E, V>where E: Send, N: Send, V: Send,
impl<N, E, V> Sync for DependencyQueue<N, E, V>where E: Sync, N: Sync, V: Sync,
impl<N, E, V> Unpin for DependencyQueue<N, E, V>where E: Unpin, N: Unpin, V: Unpin,
impl<N, E, V> UnwindSafe for DependencyQueue<N, E, V>where E: UnwindSafe, N: UnwindSafe, V: UnwindSafe,
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> Instrument for T
impl<T> Instrument for T
source§fn instrument(self, span: Span) -> Instrumented<Self>
fn instrument(self, span: Span) -> Instrumented<Self>
source§fn in_current_span(self) -> Instrumented<Self>
fn in_current_span(self) -> Instrumented<Self>
source§impl<T> WithSubscriber for T
impl<T> WithSubscriber for T
source§fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>where
S: Into<Dispatch>,
fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>where S: Into<Dispatch>,
source§fn with_current_subscriber(self) -> WithDispatch<Self>
fn with_current_subscriber(self) -> WithDispatch<Self>
Layout§
Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...)
attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.
Size: 192 bytes