Top Description Fields Constructors Methods
org.eclipse.jgit.diff

pack-priv final Class HistogramDiffIndex<S extends Sequence>

extends Object
Class Inheritance
Type Parameters
<S>
type of the base sequence.
Imports
org.eclipse.jgit.internal.JGitText
Support HistogramDiff by computing occurrence counts of elements.

Each element in the range being considered is put into a hash table, tracking the number of times that distinct element appears in the sequence. Once all elements have been inserted from sequence A, each element of sequence B is probed in the hash table and the longest common subsequence with the lowest occurrence count in A is used as the result.

Field Summary

Modifier and TypeField and Description
private final HashedSequence<S>
a

private final HashedSequence<S>
b

private final HashedSequenceComparator<S>
cmp

private int
cnt

private boolean
hasCommon

private final int
keyShift

Number of low bits to discard from a key to index table.

private Edit
lcs

private static final int
MAX_CNT

private static final int
MAX_PTR

private final int
maxChainLength

private int[]
next

For ptr, next[ptr - ptrShift] has subsequent index.

private int
ptrShift

Value to subtract from element indexes to key next array.

private static final int
REC_CNT_MASK

private static final int
REC_NEXT_SHIFT

private static final int
REC_PTR_MASK

private static final int
REC_PTR_SHIFT

private int
recCnt

Number of elements in recs; also is the unique element count.

private int[]
recIdx

For element ptr in A, index of the record in recs array.

private long[]
recs

Describes a unique element in sequence A.

private final Edit
region

private final int[]
table

Keyed by hash(HashedSequence, int) for recs index.

Constructor Summary

AccessConstructor and Description
pack-priv
HistogramDiffIndex(int maxChainLength, HashedSequenceComparator<S> cmp, HashedSequence<S> a, HashedSequence<S> b, Edit r)

Method Summary

Modifier and TypeMethod and Description
pack-priv Edit
findLongestCommonSequence()

private int
hash(HashedSequence<S> s, int idx)

private static int
recCnt(long rec)

private static long
recCreate(int next, int ptr, int cnt)

private static int
recNext(long rec)

private static int
recPtr(long rec)

private boolean
scanA()

private static int
tableBits(int sz)

private int
tryLongestCommonSequence(int bPtr)

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

aback to summary
private final HashedSequence<S> a
bback to summary
private final HashedSequence<S> b
cmpback to summary
private final HashedSequenceComparator<S> cmp
cntback to summary
private int cnt
hasCommonback to summary
private boolean hasCommon
keyShiftback to summary
private final int keyShift

Number of low bits to discard from a key to index table.

lcsback to summary
private Edit lcs
MAX_CNTback to summary
private static final int MAX_CNT
MAX_PTRback to summary
private static final int MAX_PTR
maxChainLengthback to summary
private final int maxChainLength
nextback to summary
private int[] next

For ptr, next[ptr - ptrShift] has subsequent index. For the sequence element ptr, the value stored at location next[ptr - ptrShift] is the next occurrence of the exact same element in the sequence. Chains always run from the lowest index to the largest index. Therefore the array will store next[1] = 2, but never next[2] = 1. This allows a chain to terminate with 0, as 0 would never be a valid next element. The array is sized to be region.getLengthA() and element indexes are converted to array indexes by subtracting ptrShift, which is just a cached version of region.beginA.

ptrShiftback to summary
private int ptrShift

Value to subtract from element indexes to key next array.

REC_CNT_MASKback to summary
private static final int REC_CNT_MASK
REC_NEXT_SHIFTback to summary
private static final int REC_NEXT_SHIFT
REC_PTR_MASKback to summary
private static final int REC_PTR_MASK
REC_PTR_SHIFTback to summary
private static final int REC_PTR_SHIFT
recCntback to summary
private int recCnt

Number of elements in recs; also is the unique element count.

recIdxback to summary
private int[] recIdx

For element ptr in A, index of the record in recs array. The record at recs[recIdx[ptr - ptrShift]] is the record describing all occurrences of the element appearing in sequence A at position ptr. The record is needed to get the occurrence count of the element, or to locate all other occurrences of that element within sequence A. This index provides constant-time access to the record, and avoids needing to scan the hash chain.

recsback to summary
private long[] recs

Describes a unique element in sequence A. The records in this table are actually 3-tuples of:

  • index of next record in this table that has same hash code
  • index of first element in this occurrence chain
  • occurrence count for this element (length of locs list)
The occurrence count is capped at MAX_CNT, as the field is only a few bits wide. Elements that occur more frequently will have their count capped.
regionback to summary
private final Edit region
tableback to summary
private final int[] table

Keyed by hash(HashedSequence, int) for recs index.

Constructor Detail

HistogramDiffIndexback to summary
pack-priv HistogramDiffIndex(int maxChainLength, HashedSequenceComparator<S> cmp, HashedSequence<S> a, HashedSequence<S> b, Edit r)

Method Detail

findLongestCommonSequenceback to summary
pack-priv Edit findLongestCommonSequence()
hashback to summary
private int hash(HashedSequence<S> s, int idx)
recCntback to summary
private static int recCnt(long rec)
recCreateback to summary
private static long recCreate(int next, int ptr, int cnt)
recNextback to summary
private static int recNext(long rec)
recPtrback to summary
private static int recPtr(long rec)
scanAback to summary
private boolean scanA()
tableBitsback to summary
private static int tableBits(int sz)
tryLongestCommonSequenceback to summary
private int tryLongestCommonSequence(int bPtr)