gix_revwalk/
lib.rs

1//! Utility types for traversing the git commit-graph.
2//!
3//! This crate considers itself very much *plumbing* and is meant for consumption by other plumbing crates.
4#![deny(missing_docs, rust_2018_idioms)]
5#![forbid(unsafe_code)]
6
7/// A graph of commits which additionally allows to associate data with commits.
8///
9/// It starts empty, but each access may fill it with commit information.
10/// Note that the traversal can be accelerated if a [commit-graph][gix_commitgraph::Graph] is also made available.
11///
12/// ### About replacements
13///
14/// Object replacements is an object database feature to substitute one object with another. We assume that this is transparently
15/// implemented by the `find` function that returns objects. Also we assume that the commitgraph as been written with replacements
16/// active to provide a consistent view.
17///
18/// ### Odb or `find` configuration
19///
20/// The `find` handle should be setup to *quickly determine if an object exists or not* to assure quick operation *on shallow repositories*.
21/// This typically means that it should not re-read the odb if there is an object miss.
22///
23/// Most usage of the Graph will benefit from fast ODB lookups, so setting up an object cache will be beneficial. If that's not the case,
24/// the method docs will inform about that.
25///
26/// Additionally, and only if `T` is [`Commit<T>`][graph::Commit], there is *no need for an object cache* as we keep track of
27/// everything related to commit traversal in our own hashmap.
28pub struct Graph<'find, 'cache, T> {
29    /// A way to resolve a commit from the object database.
30    find: Box<dyn gix_object::Find + 'find>,
31    /// A way to speedup commit access, essentially a multi-file commit database.
32    cache: Option<&'cache gix_commitgraph::Graph>,
33    /// The set of cached commits that we have seen once, along with data associated with them.
34    map: graph::IdMap<T>,
35    /// A buffer for writing commit data into.
36    buf: Vec<u8>,
37    /// Another buffer we typically use to store parents.
38    parent_buf: Vec<u8>,
39}
40
41///
42pub mod graph;
43
44/// A utility type implementing a queue which can be used to automatically sort data by its time in ascending order.
45///
46/// Note that the performance of this queue is very relevant to overall algorithm performance of many graph-walking algorithms,
47/// and as it stands our implementation is about 6% slower in practice, probably also depending on the size of the stored data.
48#[derive(Default)]
49pub struct PriorityQueue<K: Ord, T>(std::collections::BinaryHeap<queue::Item<K, T>>);
50mod queue;
gix_revwalk/lib.rs

gix_revwalk/
lib.rs
