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.
final class HistogramDiffIndex<S extends Sequence> extends java.lang.Object
SupportHistogramDiff
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
Fields Modifier and Type Field Description private HashedSequence<S>
a
private HashedSequence<S>
b
private HashedSequenceComparator<S>
cmp
private int
cnt
private boolean
hasCommon
private int
keyShift
Number of low bits to discard from a key to indextable
.private Edit
lcs
private static int
MAX_CNT
private static int
MAX_PTR
private int
maxChainLength
private int[]
next
Forptr
,next[ptr - ptrShift]
has subsequent index.private int
ptrShift
Value to subtract from element indexes to keynext
array.private static int
REC_CNT_MASK
private static int
REC_NEXT_SHIFT
private static int
REC_PTR_MASK
private static int
REC_PTR_SHIFT
private int
recCnt
Number of elements inrecs
; also is the unique element count.private int[]
recIdx
For elementptr
in A, index of the record inrecs
array.private long[]
recs
Describes a unique element in sequence A.private Edit
region
private int[]
table
Keyed byhash(HashedSequence, int)
forrecs
index.
-
Constructor Summary
Constructors Constructor Description HistogramDiffIndex(int maxChainLength, HashedSequenceComparator<S> cmp, HashedSequence<S> a, HashedSequence<S> b, Edit r)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) 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)
-
-
-
Field Detail
-
REC_NEXT_SHIFT
private static final int REC_NEXT_SHIFT
- See Also:
- Constant Field Values
-
REC_PTR_SHIFT
private static final int REC_PTR_SHIFT
- See Also:
- Constant Field Values
-
REC_PTR_MASK
private static final int REC_PTR_MASK
- See Also:
- Constant Field Values
-
REC_CNT_MASK
private static final int REC_CNT_MASK
- See Also:
- Constant Field Values
-
MAX_PTR
private static final int MAX_PTR
- See Also:
- Constant Field Values
-
MAX_CNT
private static final int MAX_CNT
- See Also:
- Constant Field Values
-
maxChainLength
private final int maxChainLength
-
cmp
private final HashedSequenceComparator<S extends Sequence> cmp
-
a
private final HashedSequence<S extends Sequence> a
-
b
private final HashedSequence<S extends Sequence> b
-
region
private final Edit region
-
table
private final int[] table
Keyed byhash(HashedSequence, int)
forrecs
index.
-
keyShift
private final int keyShift
Number of low bits to discard from a key to indextable
.
-
recs
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)
MAX_CNT
, as the field is only a few bits wide. Elements that occur more frequently will have their count capped.
-
recCnt
private int recCnt
Number of elements inrecs
; also is the unique element count.
-
next
private int[] next
Forptr
,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[] recIdx
For 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 ptrShift
Value to subtract from element indexes to keynext
array.
-
lcs
private Edit lcs
-
cnt
private int cnt
-
hasCommon
private boolean hasCommon
-
-
Constructor Detail
-
HistogramDiffIndex
HistogramDiffIndex(int maxChainLength, HashedSequenceComparator<S> cmp, HashedSequence<S> a, HashedSequence<S> b, Edit r)
-
-
Method Detail
-
findLongestCommonSequence
Edit findLongestCommonSequence()
-
scanA
private boolean scanA()
-
tryLongestCommonSequence
private int tryLongestCommonSequence(int bPtr)
-
hash
private int hash(HashedSequence<S> s, int idx)
-
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)
-
-