Generic trait for SecondaryMaps #51
Merged
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
@zrho You may have comments on this. |
Merged
- Renames the old SecondaryMap struct as "UnmanagedMap" - Implements SecondaryMap for BitVec - Uses the trait in Dominators to avoid wasting memory when doing partial traversals.
aborgna-q
force-pushed
the
feature/secondarymap-trait
branch
from
f06febf to
a2fbad8
Compare
ss2165
requested changes
May 30, 2023
| @@ -127,13 +140,13 @@ impl<'graph> TopoSort<'graph> { | |||
| // Mark all the candidate ports as visited, so we don't visit them again. | |||
| for node in candidate_nodes.iter() { | |||
| for port in graph.ports(*node, direction.reverse()) { | |||
| remaining_ports.set(port.index(), false); | |||
| visited_ports.set(port, true); | |||
There was a problem hiding this comment.
is there an assumption here that the default value of Map is always false or is that guranteed?
There was a problem hiding this comment.
Yes, that is part of the definition of SecondaryMap:
/// A map from keys to values that does not manage it's indices.
///
/// Querying a key that has not been set returns a default value.
(and default_value returns false for BitVec)
There was a problem hiding this comment.
right but that doesn't stop me using a struct for Map that returns true for default_value right? Might need a debug assert at least?
There was a problem hiding this comment.
Added the check to toposort. If the default value is true it initializes everything (and states so in the docs).
|
Looks good to me.
|
Yes, perhaps
👍 |
zrho
approved these changes
May 30, 2023
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This is a big breaking change that will give us more flexibility when managing secondary data on a portgraph.
It adds a
SecondaryMaptrait that encapsulates the common interfaces we use when managing node and port data.We can then implement that trait on different structures like the old
SecondaryMap(now renamedUnmanagedMap), bit vec for boolean storage, and any {Hash,BTree}{Set,Map}. This closes #46.With this, we can add a
Mapgeneric parameter toDominatorTreeandTopoSortthat lets us use more efficient structures when we do not traverse the full graph. This closes #31.Also:
There's a TODO to implement SecondaryMap for sparse containers (hash and BTree), but those can be done in another non-breaking PR.
Note that
unmanaged.rsis mostly the old contents ofsecondary.rs, but git didn't pick up the renaming.