Package org.eclipse.jgit.diff
Class HistogramDiffIndex<S extends Sequence>
java.lang.Object
org.eclipse.jgit.diff.HistogramDiffIndex<S>
- Type Parameters:
S- type of the base sequence.
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
FieldsModifier and TypeFieldDescriptionprivate final HashedSequence<S>private final HashedSequence<S>private final HashedSequenceComparator<S>private intprivate booleanprivate final intNumber of low bits to discard from a key to indextable.private Editprivate static final intprivate static final intprivate final intprivate int[]Forptr,next[ptr - ptrShift]has subsequent index.private intValue to subtract from element indexes to keynextarray.private static final intprivate static final intprivate static final intprivate static final intprivate intNumber of elements inrecs; also is the unique element count.private int[]For elementptrin A, index of the record inrecsarray.private long[]Describes a unique element in sequence A.private final Editprivate final int[]Keyed byhash(HashedSequence, int)forrecsindex. -
Constructor Summary
ConstructorsConstructorDescriptionHistogramDiffIndex(int maxChainLength, HashedSequenceComparator<S> cmp, HashedSequence<S> a, HashedSequence<S> b, Edit r) -
Method Summary
Modifier and TypeMethodDescription(package private) Editprivate inthash(HashedSequence<S> s, int idx) private static intrecCnt(long rec) private static longrecCreate(int next, int ptr, int cnt) private static intrecNext(long rec) private static intrecPtr(long rec) private booleanscanA()private static inttableBits(int sz) private inttryLongestCommonSequence(int bPtr)
-
Field Details
-
REC_NEXT_SHIFT
private static final int REC_NEXT_SHIFT- See Also:
-
REC_PTR_SHIFT
private static final int REC_PTR_SHIFT- See Also:
-
REC_PTR_MASK
private static final int REC_PTR_MASK- See Also:
-
REC_CNT_MASK
private static final int REC_CNT_MASK- See Also:
-
MAX_PTR
private static final int MAX_PTR- See Also:
-
MAX_CNT
private static final int MAX_CNT- See Also:
-
maxChainLength
private final int maxChainLength -
cmp
-
a
-
b
-
region
-
table
private final int[] tableKeyed byhash(HashedSequence, int)forrecsindex. -
keyShift
private final int keyShiftNumber of low bits to discard from a key to indextable. -
recs
private long[] recsDescribes 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)
MAX_CNT, as the field is only a few bits wide. Elements that occur more frequently will have their count capped. -
recCnt
private int recCntNumber of elements inrecs; also is the unique element count. -
next
private int[] nextForptr,next[ptr - ptrShift]has subsequent index. For the sequence elementptr, the value stored at locationnext[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 storenext[1] = 2, but nevernext[2] = 1. This allows a chain to terminate with0, as0would never be a valid next element. The array is sized to beregion.getLengthA()and element indexes are converted to array indexes by subtractingptrShift, which is just a cached version ofregion.beginA. -
recIdx
private int[] recIdxFor elementptrin A, index of the record inrecsarray. The record atrecs[recIdx[ptr - ptrShift]]is the record describing all occurrences of the element appearing in sequence A at positionptr. 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. -
ptrShift
private int ptrShiftValue to subtract from element indexes to keynextarray. -
lcs
-
cnt
private int cnt -
hasCommon
private boolean hasCommon
-
-
Constructor Details
-
HistogramDiffIndex
HistogramDiffIndex(int maxChainLength, HashedSequenceComparator<S> cmp, HashedSequence<S> a, HashedSequence<S> b, Edit r)
-
-
Method Details
-
findLongestCommonSequence
Edit findLongestCommonSequence() -
scanA
private boolean scanA() -
tryLongestCommonSequence
private int tryLongestCommonSequence(int bPtr) -
hash
-
recCreate
private static long recCreate(int next, int ptr, int cnt) -
recNext
private static int recNext(long rec) -
recPtr
private static int recPtr(long rec) -
recCnt
private static int recCnt(long rec) -
tableBits
private static int tableBits(int sz)
-