in org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackObjectSizeIndexWriter.java [67:285]
public abstract void write(List<? extends PackedObjectInfo> objs)
throws IOException;
/**
* Object size index v1.
*
* Store position (in the main index) to size as parallel arrays.
*
* <p>Positions in the main index fit well in unsigned 24 bits (16M) for most
* repositories, but some outliers have even more objects, so we need to
* store also 32 bits positions.
*
* <p>Sizes are stored as a first array parallel to positions. If a size
* doesn't fit in an element of that array, then we encode there a position
* on the next-size array. This "overflow" array doesn't have entries for
* all positions.
*
* <pre>
*
* positions [10, 500, 1000, 1001]
* sizes (32bits) [15MB, -1, 6MB, -2]
* ___/ ______/
* / /
* sizes (64 bits) [3GB, 6GB]
* </pre>
*
* <p>For sizes we use 32 bits as the first level and 64 for the rare objects
* over 2GB.
*
* <p>A 24/32/64 bits hierarchy of arrays saves space if we have a lot of small
* objects, but wastes space if we have only big ones. The min size to index is
* controlled by conf and in principle we want to index only rather
* big objects (e.g. > 10MB). We could support more dynamics read/write of sizes
* (e.g. 24 only if the threshold will include many of those objects) but it
* complicates a lot code and spec. If needed it could go for a v2 of the protocol.
*
* <p>Format:
*
* <li>A header with the magic number (4 bytes)
* <li>The index version (1 byte)
* <li>The minimum object size (4 bytes)
* <li>Total count of objects indexed (C, 4 bytes)
* (if count == 0, stop here)
*
* Blocks of
* <li>Size per entry in bits (1 byte, either 24 (0x18) or 32 (0x20))
* <li>Count of entries (4 bytes) (c, as a signed int)
* <li>positions encoded in s bytes each (i.e s*c bytes)
*
* <li>0 (as a "size-per-entry = 0", marking end of the section)
*
* <li>32 bit sizes (C * 4 bytes). Negative size means
* nextLevel[abs(size)-1]
* <li>Count of 64 bit sizes (s64) (or 0 if no more indirections)
* <li>64 bit sizes (s64 * 8 bytes)
* <li>0 (end)
*/
static class PackObjectSizeWriterV1 extends PackObjectSizeIndexWriter {
private final OutputStream os;
private final int minObjSize;
private final byte[] intBuffer = new byte[4];
PackObjectSizeWriterV1(OutputStream os, int minSize) {
this.os = new BufferedOutputStream(os);
this.minObjSize = minSize;
}
@Override
public void write(List<? extends PackedObjectInfo> allObjects)
throws IOException {
os.write(HEADER);
writeUInt8(1); // Version
writeInt32(minObjSize);
PackedObjectStats stats = countIndexableObjects(allObjects);
int[] indexablePositions = findIndexablePositions(allObjects,
stats.indexableObjs);
writeInt32(indexablePositions.length); // Total # of objects
if (indexablePositions.length == 0) {
os.flush();
return;
}
// Positions that fit in 3 bytes
if (stats.pos24Bits > 0) {
writeUInt8(24);
writeInt32(stats.pos24Bits);
applyToRange(indexablePositions, 0, stats.pos24Bits,
this::writeInt24);
}
// Positions that fit in 4 bytes
// We only use 31 bits due to sign,
// but that covers 2 billion objs
if (stats.pos31Bits > 0) {
writeUInt8(32);
writeInt32(stats.pos31Bits);
applyToRange(indexablePositions, stats.pos24Bits,
stats.pos24Bits + stats.pos31Bits, this::writeInt32);
}
writeUInt8(0);
writeSizes(allObjects, indexablePositions, stats.sizeOver2GB);
os.flush();
}
private void writeUInt8(int i) throws IOException {
if (i > 255) {
throw new IllegalStateException(
JGitText.get().numberDoesntFit);
}
NB.encodeInt32(intBuffer, 0, i);
os.write(intBuffer, 3, 1);
}
private void writeInt24(int i) throws IOException {
NB.encodeInt24(intBuffer, 1, i);
os.write(intBuffer, 1, 3);
}
private void writeInt32(int i) throws IOException {
NB.encodeInt32(intBuffer, 0, i);
os.write(intBuffer);
}
private void writeSizes(List<? extends PackedObjectInfo> allObjects,
int[] indexablePositions, int objsBiggerThan2Gb)
throws IOException {
if (indexablePositions.length == 0) {
writeInt32(0);
return;
}
byte[] sizes64bits = new byte[8 * objsBiggerThan2Gb];
int s64 = 0;
for (int i = 0; i < indexablePositions.length; i++) {
PackedObjectInfo info = allObjects.get(indexablePositions[i]);
if (info.getFullSize() < Integer.MAX_VALUE) {
writeInt32((int) info.getFullSize());
} else {
// Size needs more than 32 bits. Store -1 * offset in the
// next table as size.
writeInt32(-1 * (s64 + 1));
NB.encodeInt64(sizes64bits, s64 * 8, info.getFullSize());
s64++;
}
}
if (objsBiggerThan2Gb > 0) {
writeInt32(objsBiggerThan2Gb);
os.write(sizes64bits);
}
writeInt32(0);
}
private int[] findIndexablePositions(
List<? extends PackedObjectInfo> allObjects,
int indexableObjs) {
int[] positions = new int[indexableObjs];
int positionIdx = 0;
for (int i = 0; i < allObjects.size(); i++) {
PackedObjectInfo o = allObjects.get(i);
if (!shouldIndex(o)) {
continue;
}
positions[positionIdx++] = i;
}
return positions;
}
private PackedObjectStats countIndexableObjects(
List<? extends PackedObjectInfo> objs) {
PackedObjectStats stats = new PackedObjectStats();
for (int i = 0; i < objs.size(); i++) {
PackedObjectInfo o = objs.get(i);
if (!shouldIndex(o)) {
continue;
}
stats.indexableObjs++;
if (o.getFullSize() > Integer.MAX_VALUE) {
stats.sizeOver2GB++;
}
if (i <= MAX_24BITS_UINT) {
stats.pos24Bits++;
} else {
stats.pos31Bits++;
// i is a positive int, cannot be bigger than this
}
}
return stats;
}
private boolean shouldIndex(PackedObjectInfo o) {
return (o.getType() == Constants.OBJ_BLOB)
&& (o.getFullSize() >= minObjSize);
}
private static class PackedObjectStats {
int indexableObjs;
int pos24Bits;
int pos31Bits;
int sizeOver2GB;
}
@FunctionalInterface
interface IntEncoder {
void encode(int i) throws IOException;
}
private static void applyToRange(int[] allPositions, int start, int end,
IntEncoder encoder) throws IOException {
for (int i = start; i < end; i++) {
encoder.encode(allPositions[i]);
}
}
}