The CommitGraph is a supplemental data structure that accelerates commit graph walks.

If a user downgrades or disables the core.commitGraph config setting, then the existing object database is sufficient.

It stores the commit graph structure along with some extra metadata to speed up graph walks. By listing commit OIDs in lexicographic order, we can identify an integer position for each commit and refer to the parents of a commit using those integer positions. We use binary search to find initial commits and then use the integer positions for fast lookups during the walk.

Nested and Inner Type Summary

Modifier and Type	Class and Description
public static interface	CommitGraph.CommitData Metadata of a commit in commit data chunk.

Field Summary

Modifier and Type	Field and Description
public static final CommitGraph	EMPTY Empty `CommitGraph` with no results.

Method Summary

Modifier and Type	Method and Description
public int	Returns: the commit-graph position or -1 if the object was not found. findGraphPosition(AnyObjectId the commit for which the commit-graph position will be found. commit) Find the position in the commit-graph of the commit.
public ChangedPathFilter	Returns: the bloom filter or null if it's not found. getChangedPathFilter(int the position in the commit-graph of the object. graphPos) Get the changed path filter of the object at the commit-graph position.
public long	Returns: number of commits in this commit-graph. getCommitCnt() Obtain the total number of commits described by this commit-graph.
public CommitGraph.CommitData	Returns: the metadata of a commit or null if it's not found. getCommitData(int the position in the commit-graph of the object. graphPos) Get the metadata of a commit。 This function runs in time O(1).
public ObjectId	Returns: the ObjectId or null if it's not found. getObjectId(int the position in the commit-graph of the object. graphPos) Get the object at the commit-graph position.

Field Detail

EMPTY	back to summary
public static final CommitGraph EMPTY Empty `CommitGraph` with no results.

Method Detail

findGraphPosition	back to summary
public int findGraphPosition(AnyObjectId commit) Find the position in the commit-graph of the commit. The position can only be used within the CommitGraph Instance you got it from. That's because the graph position of the same commit may be different in CommitGraph obtained at different times (eg., regenerated new commit-graph). Parameters commit:AnyObjectId the commit for which the commit-graph position will be found. Returns:int the commit-graph position or -1 if the object was not found.

findGraphPosition

back to summary

public int findGraphPosition(AnyObjectId commit)

Find the position in the commit-graph of the commit.

The position can only be used within the CommitGraph Instance you got it from. That's because the graph position of the same commit may be different in CommitGraph obtained at different times (eg., regenerated new commit-graph).

Parameters

commit:AnyObjectId: the commit for which the commit-graph position will be found.

Returns:int

the commit-graph position or -1 if the object was not found.

getChangedPathFilter	back to summary
public ChangedPathFilter getChangedPathFilter(int graphPos) Get the changed path filter of the object at the commit-graph position. Parameters graphPos:int the position in the commit-graph of the object. Returns:ChangedPathFilter the bloom filter or null if it's not found.

getChangedPathFilter

back to summary

public ChangedPathFilter getChangedPathFilter(int graphPos)

Get the changed path filter of the object at the commit-graph position.

Parameters

graphPos:int: the position in the commit-graph of the object.

Returns:ChangedPathFilter

the bloom filter or null if it's not found.

getCommitCnt	back to summary
public long getCommitCnt() Obtain the total number of commits described by this commit-graph. Returns:long number of commits in this commit-graph.

getCommitCnt

back to summary

public long getCommitCnt()

Obtain the total number of commits described by this commit-graph.

Returns:long: number of commits in this commit-graph.

getCommitData back to summary

getCommitData	back to summary
public CommitGraph.CommitData getCommitData(int graphPos) Get the metadata of a commit。 This function runs in time O(1). In the process of commit history traversal, `CommitData#getParents()` makes us get the graphPos of the commit's parents in advance, so that we can avoid O(logN) lookup and use O(1) lookup instead. Parameters graphPos:int the position in the commit-graph of the object. Returns:CommitGraph.CommitData the metadata of a commit or null if it's not found.

public CommitGraph.CommitData getCommitData(int graphPos)

Get the metadata of a commit。

This function runs in time O(1).

In the process of commit history traversal, CommitData#getParents() makes us get the graphPos of the commit's parents in advance, so that we can avoid O(logN) lookup and use O(1) lookup instead.

Parameters

graphPos:int: the position in the commit-graph of the object.

Returns:CommitGraph.CommitData

the metadata of a commit or null if it's not found.

getObjectId	back to summary
public ObjectId getObjectId(int graphPos) Get the object at the commit-graph position. Parameters graphPos:int the position in the commit-graph of the object. Returns:ObjectId the ObjectId or null if it's not found.

getObjectId

back to summary

public ObjectId getObjectId(int graphPos)

Get the object at the commit-graph position.

Parameters

graphPos:int: the position in the commit-graph of the object.

Returns:ObjectId

the ObjectId or null if it's not found.

org.eclipse.jgit.internal.storage.commitgraph back to summary

public Interface CommitGraph.CommitData

Known Direct Implementers: org.eclipse.jgit.internal.storage.commitgraph.GraphCommitData.CommitDataImpl

Metadata of a commit in commit data chunk.

Method Summary

Modifier and Type	Method and Description
public long	Returns: the commit time in seconds since EPOCH. getCommitTime() Time from the "committer" line.
public int	Returns: the generation number or `org.eclipse.jgit.lib.Constants#COMMIT_GENERATION_NOT_COMPUTED` if the writer didn't calculate it. getGeneration() Get the generation number (the distance from the root) of the commit.
public int[]	Returns: the array of parents. getParents() Obtain an array of all parents.
public ObjectId	Returns: tree of this commit. getTree() Get a reference to this commit's tree.

Method Detail

getCommitTime	back to summary
public long getCommitTime() Time from the "committer" line. Returns:long the commit time in seconds since EPOCH.

getCommitTime

back to summary

public long getCommitTime()

Time from the "committer" line.

Returns:long: the commit time in seconds since EPOCH.

getGeneration back to summary

getGeneration	back to summary
public int getGeneration() Get the generation number (the distance from the root) of the commit. Returns:int the generation number or `org.eclipse.jgit.lib.Constants#COMMIT_GENERATION_NOT_COMPUTED` if the writer didn't calculate it.

public int getGeneration()

Get the generation number (the distance from the root) of the commit.

Returns:int: the generation number or org.eclipse.jgit.lib.Constants#COMMIT_GENERATION_NOT_COMPUTED if the writer didn't calculate it.

getParents back to summary

getParents	back to summary
public int[] getParents() Obtain an array of all parents. The method only provides the graph positions of parents in commit-graph, call `CommitGraph#getObjectId(int)` to get the real objectId. Returns:int[] the array of parents.

public int[] getParents()

Obtain an array of all parents.

The method only provides the graph positions of parents in commit-graph, call CommitGraph#getObjectId(int) to get the real objectId.

Returns:int[]: the array of parents.

getTree	back to summary
public ObjectId getTree() Get a reference to this commit's tree. Returns:ObjectId tree of this commit.

getTree

back to summary

public ObjectId getTree()

Get a reference to this commit's tree.

Returns:ObjectId: tree of this commit.