equal
deleted
inserted
replaced
11 //! - By *relative heads* of a collection of revision numbers (`Revision`), we |
11 //! - By *relative heads* of a collection of revision numbers (`Revision`), we |
12 //! mean those revisions that have no children among the collection. |
12 //! mean those revisions that have no children among the collection. |
13 //! - Similarly *relative roots* of a collection of `Revision`, we mean those |
13 //! - Similarly *relative roots* of a collection of `Revision`, we mean those |
14 //! whose parents, if any, don't belong to the collection. |
14 //! whose parents, if any, don't belong to the collection. |
15 use super::{Graph, GraphError, Revision, NULL_REVISION}; |
15 use super::{Graph, GraphError, Revision, NULL_REVISION}; |
16 use crate::ancestors::AncestorsIterator; |
16 use crate::{ancestors::AncestorsIterator, BaseRevision}; |
17 use std::collections::{BTreeSet, HashSet}; |
17 use std::collections::{BTreeSet, HashSet}; |
18 |
18 |
19 fn remove_parents<S: std::hash::BuildHasher>( |
19 fn remove_parents<S: std::hash::BuildHasher>( |
20 graph: &impl Graph, |
20 graph: &impl Graph, |
21 rev: Revision, |
21 rev: Revision, |
74 // mutating |
74 // mutating |
75 let as_vec: Vec<Revision> = revs.iter().cloned().collect(); |
75 let as_vec: Vec<Revision> = revs.iter().cloned().collect(); |
76 for rev in as_vec { |
76 for rev in as_vec { |
77 if rev != NULL_REVISION { |
77 if rev != NULL_REVISION { |
78 remove_parents(graph, rev, revs)?; |
78 remove_parents(graph, rev, revs)?; |
|
79 } |
|
80 } |
|
81 Ok(()) |
|
82 } |
|
83 |
|
84 /// Optimized version of `retain_heads` that expects an zeroed array of the size |
|
85 /// of the graph, to act as a faster but less space-efficient `HashSet`. |
|
86 /// |
|
87 /// # Panics |
|
88 /// |
|
89 /// Can panic if `not_heads` is shorten than the length of graph. |
|
90 pub fn retain_heads_fast( |
|
91 graph: &impl Graph, |
|
92 not_heads: &mut [bool], |
|
93 filtered_revs: &HashSet<Revision>, |
|
94 ) -> Result<(), GraphError> { |
|
95 for idx in (0..not_heads.len()).rev() { |
|
96 let rev = Revision(idx as BaseRevision); |
|
97 if !not_heads[idx] && filtered_revs.contains(&rev) { |
|
98 not_heads[idx] = true; |
|
99 continue; |
|
100 } |
|
101 for parent in graph.parents(rev)?.iter() { |
|
102 if *parent != NULL_REVISION { |
|
103 not_heads[parent.0 as usize] = true; |
|
104 } |
79 } |
105 } |
80 } |
106 } |
81 Ok(()) |
107 Ok(()) |
82 } |
108 } |
83 |
109 |