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 int
private boolean
private final int
Number of low bits to discard from a key to indextable
.private Edit
private static final int
private static final int
private final int
private int[]
Forptr
,next[ptr - ptrShift]
has subsequent index.private int
Value to subtract from element indexes to keynext
array.private static final int
private static final int
private static final int
private static final int
private int
Number of elements inrecs
; also is the unique element count.private int[]
For elementptr
in A, index of the record inrecs
array.private long[]
Describes a unique element in sequence A.private final Edit
private final int[]
Keyed byhash(HashedSequence, int)
forrecs
index. -
Constructor Summary
ConstructorsConstructorDescriptionHistogramDiffIndex
(int maxChainLength, HashedSequenceComparator<S> cmp, HashedSequence<S> a, HashedSequence<S> b, Edit r) -
Method Summary
Modifier and TypeMethodDescription(package private) Edit
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)
-
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)
forrecs
index. -
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
, as0
would 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 elementptr
in A, index of the record inrecs
array. 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 keynext
array. -
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)
-