org.eclipse.jgit/org.eclipse.jgit/5.5.0.201909110433-r : org/eclipse/jgit/internal/storage/reftable/ReftableWriter.java

ReftableWriter
http://www.eclipse.org/jgit//org.eclipse.jgit: Repository access and algorithms (Eclipse JGit Project)
Eclipse Distribution License (New BSD License)
Andrey Loskutov
Christian Halstrick
Dave Borowitz
David Pursehouse
Gunnar Wagenknecht
Jonathan Nieder
Jonathan Tan
Matthias Sohn
Sasa Zivkov
Terry Parker
Thomas Wolf
/*
 * Copyright (C) 2017, Google Inc.
 * and other copyright owners as documented in the project's IP log.
 *
 * This program and the accompanying materials are made available
 * under the terms of the Eclipse Distribution License v1.0 which
 * accompanies this distribution, is reproduced below, and is
 * available at http://www.eclipse.org/org/documents/edl-v10.php
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or
 * without modification, are permitted provided that the following
 * conditions are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 *
 * - Redistributions in binary form must reproduce the above
 *   copyright notice, this list of conditions and the following
 *   disclaimer in the documentation and/or other materials provided
 *   with the distribution.
 *
 * - Neither the name of the Eclipse Foundation, Inc. nor the
 *   names of its contributors may be used to endorse or promote
 *   products derived from this software without specific prior
 *   written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package org.eclipse.jgit.internal.storage.reftable;

import static java.lang.Math.log;
import static java.nio.charset.StandardCharsets.UTF_8;
import static org.eclipse.jgit.internal.storage.reftable.BlockWriter.padBetweenBlocks;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_FOOTER_LEN;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_HEADER_LEN;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_HEADER_MAGIC;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.INDEX_BLOCK_TYPE;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.LOG_BLOCK_TYPE;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.MAX_BLOCK_SIZE;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.MAX_RESTARTS;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.OBJ_BLOCK_TYPE;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.REF_BLOCK_TYPE;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VERSION_1;
import static org.eclipse.jgit.lib.Constants.OBJECT_ID_LENGTH;

import java.io.IOException;
import java.io.OutputStream;
import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.zip.CRC32;

import org.eclipse.jgit.annotations.Nullable;
import org.eclipse.jgit.internal.JGitText;
import org.eclipse.jgit.internal.storage.reftable.BlockWriter.DeleteLogEntry;
import org.eclipse.jgit.internal.storage.reftable.BlockWriter.Entry;
import org.eclipse.jgit.internal.storage.reftable.BlockWriter.IndexEntry;
import org.eclipse.jgit.internal.storage.reftable.BlockWriter.LogEntry;
import org.eclipse.jgit.internal.storage.reftable.BlockWriter.ObjEntry;
import org.eclipse.jgit.internal.storage.reftable.BlockWriter.RefEntry;
import org.eclipse.jgit.lib.AbbreviatedObjectId;
import org.eclipse.jgit.lib.AnyObjectId;
import org.eclipse.jgit.lib.ObjectId;
import org.eclipse.jgit.lib.ObjectIdOwnerMap;
import org.eclipse.jgit.lib.ObjectIdSubclassMap;
import org.eclipse.jgit.lib.PersonIdent;
import org.eclipse.jgit.lib.Ref;
import org.eclipse.jgit.util.LongList;
import org.eclipse.jgit.util.NB;

Writes a reftable formatted file.
 A reftable can be written in a streaming fashion, provided the caller sorts all references. A ReftableWriter is single-use, and not thread-safe. /**
 * Writes a reftable formatted file.
 * <p>
 * A reftable can be written in a streaming fashion, provided the caller sorts
 * all references. A
 * {@link org.eclipse.jgit.internal.storage.reftable.ReftableWriter} is
 * single-use, and not thread-safe.
 */
public class ReftableWriter {
	private ReftableConfig config;
	private int refBlockSize;
	private int logBlockSize;
	private int restartInterval;
	private int maxIndexLevels;
	private boolean alignBlocks;
	private boolean indexObjects;

	private long minUpdateIndex;
	private long maxUpdateIndex;

	private ReftableOutputStream out;
	private ObjectIdSubclassMap<RefList> obj2ref;

	private BlockWriter.Entry lastRef;
	private BlockWriter.Entry lastLog;
	private BlockWriter cur;
	private Section refs;
	private Section objs;
	private Section logs;
	private int objIdLen;
	private Stats stats;

	Initialize a writer with a default configuration.
/**
	 * Initialize a writer with a default configuration.
	 */
	public ReftableWriter() {
		this(new ReftableConfig());
		lastRef = null;
		lastLog = null;
	}

	Initialize a writer with a specific configuration.
Params: cfg – 
           configuration for the writer./**
	 * Initialize a writer with a specific configuration.
	 *
	 * @param cfg
	 *            configuration for the writer.
	 */
	public ReftableWriter(ReftableConfig cfg) {
		config = cfg;
	}

	Set configuration for the writer.
Params: cfg – 
           configuration for the writer.
Returns: this/**
	 * Set configuration for the writer.
	 *
	 * @param cfg
	 *            configuration for the writer.
	 * @return {@code this}
	 */
	public ReftableWriter setConfig(ReftableConfig cfg) {
		this.config = cfg != null ? cfg : new ReftableConfig();
		return this;
	}

	Set the minimum update index for log entries that appear in this
reftable.
Params: min –  the minimum update index for log entries that appear in this reftable. This should be 1 higher than the prior reftable's maxUpdateIndex if this table will be used in a stack.
Returns: this/**
	 * Set the minimum update index for log entries that appear in this
	 * reftable.
	 *
	 * @param min
	 *            the minimum update index for log entries that appear in this
	 *            reftable. This should be 1 higher than the prior reftable's
	 *            {@code maxUpdateIndex} if this table will be used in a stack.
	 * @return {@code this}
	 */
	public ReftableWriter setMinUpdateIndex(long min) {
		minUpdateIndex = min;
		return this;
	}

	Set the maximum update index for log entries that appear in this
reftable.
Params: max –  the maximum update index for log entries that appear in this reftable. This should be at least 1 higher than the prior reftable's maxUpdateIndex if this table will be used in a stack.
Returns: this/**
	 * Set the maximum update index for log entries that appear in this
	 * reftable.
	 *
	 * @param max
	 *            the maximum update index for log entries that appear in this
	 *            reftable. This should be at least 1 higher than the prior
	 *            reftable's {@code maxUpdateIndex} if this table will be used
	 *            in a stack.
	 * @return {@code this}
	 */
	public ReftableWriter setMaxUpdateIndex(long max) {
		maxUpdateIndex = max;
		return this;
	}

	Begin writing the reftable.
Params: os –  stream to write the table to. Caller is responsible for closing the stream after invoking finish().
Throws: IOException – 
            if reftable header cannot be written.
Returns: this/**
	 * Begin writing the reftable.
	 *
	 * @param os
	 *            stream to write the table to. Caller is responsible for
	 *            closing the stream after invoking {@link #finish()}.
	 * @return {@code this}
	 * @throws java.io.IOException
	 *             if reftable header cannot be written.
	 */
	public ReftableWriter begin(OutputStream os) throws IOException {
		refBlockSize = config.getRefBlockSize();
		logBlockSize = config.getLogBlockSize();
		restartInterval = config.getRestartInterval();
		maxIndexLevels = config.getMaxIndexLevels();
		alignBlocks = config.isAlignBlocks();
		indexObjects = config.isIndexObjects();

		if (refBlockSize <= 0) {
			refBlockSize = 4 << 10;
		} else if (refBlockSize > MAX_BLOCK_SIZE) {
			throw new IllegalArgumentException();
		}
		if (logBlockSize <= 0) {
			logBlockSize = 2 * refBlockSize;
		}
		if (restartInterval <= 0) {
			restartInterval = refBlockSize < (60 << 10) ? 16 : 64;
		}

		out = new ReftableOutputStream(os, refBlockSize, alignBlocks);
		refs = new Section(REF_BLOCK_TYPE);
		if (indexObjects) {
			obj2ref = new ObjectIdSubclassMap<>();
		}
		writeFileHeader();
		return this;
	}

	Sort a collection of references and write them to the reftable.
Params: refsToPack – 
           references to sort and write.
Throws: IOException – 
            if reftable cannot be written.
Returns: this/**
	 * Sort a collection of references and write them to the reftable.
	 *
	 * @param refsToPack
	 *            references to sort and write.
	 * @return {@code this}
	 * @throws java.io.IOException
	 *             if reftable cannot be written.
	 */
	public ReftableWriter sortAndWriteRefs(Collection<Ref> refsToPack)
			throws IOException {
		Iterator<RefEntry> itr = refsToPack.stream()
				.map(r -> new RefEntry(r, maxUpdateIndex - minUpdateIndex))
				.sorted(Entry::compare)
				.iterator();
		while (itr.hasNext()) {
			RefEntry entry = itr.next();
			long blockPos = refs.write(entry);
			indexRef(entry.ref, blockPos);
		}
		return this;
	}

	Write one reference to the reftable.

References must be passed in sorted order.
Params: ref – 
           the reference to store.
Throws: IOException – 
            if reftable cannot be written./**
	 * Write one reference to the reftable.
	 * <p>
	 * References must be passed in sorted order.
	 *
	 * @param ref
	 *            the reference to store.
	 * @throws java.io.IOException
	 *             if reftable cannot be written.
	 */
	public void writeRef(Ref ref) throws IOException {
		writeRef(ref, maxUpdateIndex);
	}

	Write one reference to the reftable.

References must be passed in sorted order.
Params: ref – 
           the reference to store.
updateIndex –  the updateIndex that modified this reference. Must be >= minUpdateIndex for this file.
Throws: IOException – 
            if reftable cannot be written./**
	 * Write one reference to the reftable.
	 * <p>
	 * References must be passed in sorted order.
	 *
	 * @param ref
	 *            the reference to store.
	 * @param updateIndex
	 *            the updateIndex that modified this reference. Must be
	 *            {@code >= minUpdateIndex} for this file.
	 * @throws java.io.IOException
	 *             if reftable cannot be written.
	 */
	public void writeRef(Ref ref, long updateIndex) throws IOException {
		if (updateIndex < minUpdateIndex) {
			throw new IllegalArgumentException();
		}
		long d = updateIndex - minUpdateIndex;
		RefEntry entry = new RefEntry(ref, d);
		if (lastRef != null && Entry.compare(lastRef, entry) >= 0) {
			throwIllegalEntry(lastRef, entry);
		}
		lastRef = entry;

		long blockPos = refs.write(entry);
		indexRef(ref, blockPos);
	}

	private void throwIllegalEntry(Entry last, Entry now) {
		throw new IllegalArgumentException(MessageFormat.format(
				JGitText.get().refTableRecordsMustIncrease,
				new String(last.key, UTF_8), new String(now.key, UTF_8)));
	}

	private void indexRef(Ref ref, long blockPos) {
		if (indexObjects && !ref.isSymbolic()) {
			indexId(ref.getObjectId(), blockPos);
			indexId(ref.getPeeledObjectId(), blockPos);
		}
	}

	private void indexId(ObjectId id, long blockPos) {
		if (id != null) {
			RefList l = obj2ref.get(id);
			if (l == null) {
				l = new RefList(id);
				obj2ref.add(l);
			}
			l.addBlock(blockPos);
		}
	}

	Write one reflog entry to the reftable.
 Reflog entries must be written in reference name and descending updateIndex (highest first) order. 
Params: ref – 
           name of the reference.
updateIndex –  identifier of the transaction that created the log record. The updateIndex must be unique within the scope of ref, and must be within the bounds defined by minUpdateIndex <= updateIndex <= maxUpdateIndex.
who – 
           committer of the reflog entry.
oldId –  prior id; pass ObjectId.zeroId() for creations.
newId –  new id; pass ObjectId.zeroId() for deletions.
message – 
           optional message (may be null).
Throws: IOException – 
            if reftable cannot be written./**
	 * Write one reflog entry to the reftable.
	 * <p>
	 * Reflog entries must be written in reference name and descending
	 * {@code updateIndex} (highest first) order.
	 *
	 * @param ref
	 *            name of the reference.
	 * @param updateIndex
	 *            identifier of the transaction that created the log record. The
	 *            {@code updateIndex} must be unique within the scope of
	 *            {@code ref}, and must be within the bounds defined by
	 *            {@code minUpdateIndex <= updateIndex <= maxUpdateIndex}.
	 * @param who
	 *            committer of the reflog entry.
	 * @param oldId
	 *            prior id; pass {@link org.eclipse.jgit.lib.ObjectId#zeroId()}
	 *            for creations.
	 * @param newId
	 *            new id; pass {@link org.eclipse.jgit.lib.ObjectId#zeroId()}
	 *            for deletions.
	 * @param message
	 *            optional message (may be null).
	 * @throws java.io.IOException
	 *             if reftable cannot be written.
	 */
	public void writeLog(String ref, long updateIndex, PersonIdent who,
			ObjectId oldId, ObjectId newId, @Nullable String message)
					throws IOException {
		String msg = message != null ? message : ""; //$NON-NLS-1$
		beginLog();
		LogEntry entry = new LogEntry(ref, updateIndex, who, oldId, newId, msg);
		if (lastLog != null && Entry.compare(lastLog, entry) >= 0) {
			throwIllegalEntry(lastLog, entry);
		}
		lastLog = entry;
		logs.write(entry);
	}

	Record deletion of one reflog entry in this reftable.
 The deletion can shadow an entry stored in a lower table in the stack. This is useful for refs/stash and dropping an entry from its reflog. 
 Deletion must be properly interleaved in sorted updateIndex order with any other logs written by writeLog(String, long, PersonIdent, ObjectId, ObjectId, String). 
Params: ref – 
           the ref to delete (hide) a reflog entry from.
updateIndex – 
           the update index that must be hidden.
Throws: IOException – 
            if reftable cannot be written./**
	 * Record deletion of one reflog entry in this reftable.
	 *
	 * <p>
	 * The deletion can shadow an entry stored in a lower table in the stack.
	 * This is useful for {@code refs/stash} and dropping an entry from its
	 * reflog.
	 * <p>
	 * Deletion must be properly interleaved in sorted updateIndex order with
	 * any other logs written by
	 * {@link #writeLog(String, long, PersonIdent, ObjectId, ObjectId, String)}.
	 *
	 * @param ref
	 *            the ref to delete (hide) a reflog entry from.
	 * @param updateIndex
	 *            the update index that must be hidden.
	 * @throws java.io.IOException
	 *             if reftable cannot be written.
	 */
	public void deleteLog(String ref, long updateIndex) throws IOException {
		beginLog();
		logs.write(new DeleteLogEntry(ref, updateIndex));
	}

	private void beginLog() throws IOException {
		if (logs == null) {
			finishRefAndObjSections(); // close prior ref blocks and their index, if present.
			out.flushFileHeader();
			out.setBlockSize(logBlockSize);
			logs = new Section(LOG_BLOCK_TYPE);
		}
	}

	Get an estimate of the current size in bytes of the reftable
Returns: an estimate of the current size in bytes of the reftable, if it was finished right now. Estimate is only accurate if ReftableConfig.setIndexObjects(boolean) is false and ReftableConfig.setMaxIndexLevels(int) is 1./**
	 * Get an estimate of the current size in bytes of the reftable
	 *
	 * @return an estimate of the current size in bytes of the reftable, if it
	 *         was finished right now. Estimate is only accurate if
	 *         {@link org.eclipse.jgit.internal.storage.reftable.ReftableConfig#setIndexObjects(boolean)}
	 *         is {@code false} and
	 *         {@link org.eclipse.jgit.internal.storage.reftable.ReftableConfig#setMaxIndexLevels(int)}
	 *         is {@code 1}.
	 */
	public long estimateTotalBytes() {
		long bytes = out.size();
		if (bytes == 0) {
			bytes += FILE_HEADER_LEN;
		}
		if (cur != null) {
			long curBlockPos = out.size();
			int sz = cur.currentSize();
			bytes += sz;

			IndexBuilder idx = null;
			if (cur.blockType() == REF_BLOCK_TYPE) {
				idx = refs.idx;
			} else if (cur.blockType() == LOG_BLOCK_TYPE) {
				idx = logs.idx;
			}
			if (idx != null && shouldHaveIndex(idx)) {
				if (idx == refs.idx) {
					bytes += out.estimatePadBetweenBlocks(sz);
				}
				bytes += idx.estimateBytes(curBlockPos);
			}
		}
		bytes += FILE_FOOTER_LEN;
		return bytes;
	}

	Finish writing the reftable by writing its trailer.
Throws: IOException – 
            if reftable cannot be written.
Returns: this/**
	 * Finish writing the reftable by writing its trailer.
	 *
	 * @return {@code this}
	 * @throws java.io.IOException
	 *             if reftable cannot be written.
	 */
	public ReftableWriter finish() throws IOException {
		finishRefAndObjSections();
		finishLogSection();
		writeFileFooter();
		out.finishFile();

		stats = new Stats(this, out);
		out = null;
		obj2ref = null;
		cur = null;
		refs = null;
		objs = null;
		logs = null;
		return this;
	}

	private void finishRefAndObjSections() throws IOException {
		if (cur != null && cur.blockType() == REF_BLOCK_TYPE) {
			refs.finishSectionMaybeWriteIndex();
			if (indexObjects && !obj2ref.isEmpty() && refs.idx.bytes > 0) {
				writeObjBlocks();
			}
			obj2ref = null;
		}
	}

	private void writeObjBlocks() throws IOException {
		List<RefList> sorted = sortById(obj2ref);
		obj2ref = null;
		objIdLen = shortestUniqueAbbreviation(sorted);

		out.padBetweenBlocksToNextBlock();
		objs = new Section(OBJ_BLOCK_TYPE);
		objs.entryCnt = sorted.size();
		for (RefList l : sorted) {
			objs.write(new ObjEntry(objIdLen, l, l.blockPos));
		}
		objs.finishSectionMaybeWriteIndex();
	}

	private void finishLogSection() throws IOException {
		if (cur != null && cur.blockType() == LOG_BLOCK_TYPE) {
			logs.finishSectionMaybeWriteIndex();
		}
	}

	private boolean shouldHaveIndex(IndexBuilder idx) {
		int threshold;
		if (idx == refs.idx && alignBlocks) {
			threshold = 4;
		} else {
			threshold = 1;
		}
		return idx.entries.size() + (cur != null ? 1 : 0) > threshold;
	}

	private void writeFileHeader() {
		byte[] hdr = new byte[FILE_HEADER_LEN];
		encodeHeader(hdr);
		out.write(hdr, 0, FILE_HEADER_LEN);
	}

	private void encodeHeader(byte[] hdr) {
		System.arraycopy(FILE_HEADER_MAGIC, 0, hdr, 0, 4);
		int bs = alignBlocks ? refBlockSize : 0;
		NB.encodeInt32(hdr, 4, (VERSION_1 << 24) | bs);
		NB.encodeInt64(hdr, 8, minUpdateIndex);
		NB.encodeInt64(hdr, 16, maxUpdateIndex);
	}

	private void writeFileFooter() {
		int ftrLen = FILE_FOOTER_LEN;
		byte[] ftr = new byte[ftrLen];
		encodeHeader(ftr);

		NB.encodeInt64(ftr, 24, indexPosition(refs));
		NB.encodeInt64(ftr, 32, (firstBlockPosition(objs) << 5) | objIdLen);
		NB.encodeInt64(ftr, 40, indexPosition(objs));
		NB.encodeInt64(ftr, 48, firstBlockPosition(logs));
		NB.encodeInt64(ftr, 56, indexPosition(logs));

		CRC32 crc = new CRC32();
		crc.update(ftr, 0, ftrLen - 4);
		NB.encodeInt32(ftr, ftrLen - 4, (int) crc.getValue());

		out.write(ftr, 0, ftrLen);
	}

	private static long firstBlockPosition(@Nullable Section s) {
		return s != null ? s.firstBlockPosition : 0;
	}

	private static long indexPosition(@Nullable Section s) {
		return s != null && s.idx != null ? s.idx.rootPosition : 0;
	}

	Get statistics of the last written reftable.
Returns: statistics of the last written reftable./**
	 * Get statistics of the last written reftable.
	 *
	 * @return statistics of the last written reftable.
	 */
	public Stats getStats() {
		return stats;
	}

	Statistics about a written reftable. /** Statistics about a written reftable. */
	public static class Stats {
		private final int refBlockSize;
		private final int logBlockSize;
		private final int restartInterval;

		private final long minUpdateIndex;
		private final long maxUpdateIndex;

		private final long refCnt;
		private final long objCnt;
		private final int objIdLen;
		private final long logCnt;
		private final long refBytes;
		private final long objBytes;
		private final long logBytes;
		private final long paddingUsed;
		private final long totalBytes;

		private final int refIndexSize;
		private final int refIndexLevels;
		private final int objIndexSize;
		private final int objIndexLevels;

		Stats(ReftableWriter w, ReftableOutputStream o) {
			refBlockSize = w.refBlockSize;
			logBlockSize = w.logBlockSize;
			restartInterval = w.restartInterval;

			minUpdateIndex = w.minUpdateIndex;
			maxUpdateIndex = w.maxUpdateIndex;
			paddingUsed = o.paddingUsed();
			totalBytes = o.size();

			refCnt = w.refs.entryCnt;
			refBytes = w.refs.bytes;

			objCnt = w.objs != null ? w.objs.entryCnt : 0;
			objBytes = w.objs != null ? w.objs.bytes : 0;
			objIdLen = w.objIdLen;

			logCnt = w.logs != null ? w.logs.entryCnt : 0;
			logBytes = w.logs != null ? w.logs.bytes : 0;

			IndexBuilder refIdx = w.refs.idx;
			refIndexSize = refIdx.bytes;
			refIndexLevels = refIdx.levels;

			IndexBuilder objIdx = w.objs != null ? w.objs.idx : null;
			objIndexSize = objIdx != null ? objIdx.bytes : 0;
			objIndexLevels = objIdx != null ? objIdx.levels : 0;
		}

		Returns: number of bytes in a ref block./** @return number of bytes in a ref block. */
		public int refBlockSize() {
			return refBlockSize;
		}

		Returns: number of bytes to compress into a log block./** @return number of bytes to compress into a log block. */
		public int logBlockSize() {
			return logBlockSize;
		}

		Returns: number of references between binary search markers./** @return number of references between binary search markers. */
		public int restartInterval() {
			return restartInterval;
		}

		Returns: smallest update index contained in this reftable./** @return smallest update index contained in this reftable. */
		public long minUpdateIndex() {
			return minUpdateIndex;
		}

		Returns: largest update index contained in this reftable./** @return largest update index contained in this reftable. */
		public long maxUpdateIndex() {
			return maxUpdateIndex;
		}

		Returns: total number of references in the reftable./** @return total number of references in the reftable. */
		public long refCount() {
			return refCnt;
		}

		Returns: number of unique objects in the reftable./** @return number of unique objects in the reftable. */
		public long objCount() {
			return objCnt;
		}

		Returns: total number of log records in the reftable./** @return total number of log records in the reftable. */
		public long logCount() {
			return logCnt;
		}

		Returns: number of bytes for references, including ref index./** @return number of bytes for references, including ref index. */
		public long refBytes() {
			return refBytes;
		}

		Returns: number of bytes for objects, including object index./** @return number of bytes for objects, including object index. */
		public long objBytes() {
			return objBytes;
		}

		Returns: number of bytes for log, including log index./** @return number of bytes for log, including log index. */
		public long logBytes() {
			return logBytes;
		}

		Returns: total number of bytes in the reftable./** @return total number of bytes in the reftable. */
		public long totalBytes() {
			return totalBytes;
		}

		Returns: bytes of padding used to maintain block alignment./** @return bytes of padding used to maintain block alignment. */
		public long paddingBytes() {
			return paddingUsed;
		}

		Returns: number of bytes in the ref index; 0 if no index was used./** @return number of bytes in the ref index; 0 if no index was used. */
		public int refIndexSize() {
			return refIndexSize;
		}

		Returns: number of levels in the ref index./** @return number of levels in the ref index. */
		public int refIndexLevels() {
			return refIndexLevels;
		}

		Returns: number of bytes in the object index; 0 if no index./** @return number of bytes in the object index; 0 if no index. */
		public int objIndexSize() {
			return objIndexSize;
		}

		Returns: number of levels in the object index./** @return number of levels in the object index. */
		public int objIndexLevels() {
			return objIndexLevels;
		}

		Returns: number of bytes required to uniquely identify all objects in the reftable. Unique abbreviations in hex would be 2 * objIdLength()./**
		 * @return number of bytes required to uniquely identify all objects in
		 *         the reftable. Unique abbreviations in hex would be
		 *         {@code 2 * objIdLength()}.
		 */
		public int objIdLength() {
			return objIdLen;
		}
	}

	private static List<RefList> sortById(ObjectIdSubclassMap<RefList> m) {
		List<RefList> s = new ArrayList<>(m.size());
		for (RefList l : m) {
			s.add(l);
		}
		Collections.sort(s);
		return s;
	}

	private static int shortestUniqueAbbreviation(List<RefList> in) {
		// Estimate minimum number of bytes necessary for unique abbreviations.
		int bytes = Math.max(2, (int) (log(in.size()) / log(8)));
		Set<AbbreviatedObjectId> tmp = new HashSet<>((int) (in.size() * 0.75f));
		retry: for (;;) {
			int hexLen = bytes * 2;
			for (ObjectId id : in) {
				AbbreviatedObjectId a = id.abbreviate(hexLen);
				if (!tmp.add(a)) {
					if (++bytes >= OBJECT_ID_LENGTH) {
						return OBJECT_ID_LENGTH;
					}
					tmp.clear();
					continue retry;
				}
			}
			return bytes;
		}
	}

	private static class RefList extends ObjectIdOwnerMap.Entry {
		final LongList blockPos = new LongList(2);

		RefList(AnyObjectId id) {
			super(id);
		}

		void addBlock(long pos) {
			if (!blockPos.contains(pos)) {
				blockPos.add(pos);
			}
		}
	}

	private class Section {
		final IndexBuilder idx;
		final long firstBlockPosition;

		long entryCnt;
		long bytes;

		Section(byte keyType) {
			idx = new IndexBuilder(keyType);
			firstBlockPosition = out.size();
		}

		long write(BlockWriter.Entry entry) throws IOException {
			if (cur == null) {
				beginBlock(entry);
			} else if (!cur.tryAdd(entry)) {
				flushCurBlock();
				if (cur.padBetweenBlocks()) {
					out.padBetweenBlocksToNextBlock();
				}
				beginBlock(entry);
			}
			entryCnt++;
			return out.size();
		}

		private void beginBlock(BlockWriter.Entry entry)
				throws BlockSizeTooSmallException {
			byte blockType = entry.blockType();
			int bs = out.bytesAvailableInBlock();
			cur = new BlockWriter(blockType, idx.keyType, bs, restartInterval);
			cur.mustAdd(entry);
		}

		void flushCurBlock() throws IOException {
			idx.entries.add(new IndexEntry(cur.lastKey(), out.size()));
			cur.writeTo(out);
		}

		void finishSectionMaybeWriteIndex() throws IOException {
			flushCurBlock();
			cur = null;
			if (shouldHaveIndex(idx)) {
				idx.writeIndex();
			}
			bytes = out.size() - firstBlockPosition;
		}
	}

	private class IndexBuilder {
		final byte keyType;
		List<IndexEntry> entries = new ArrayList<>();
		long rootPosition;
		int bytes;
		int levels;

		IndexBuilder(byte kt) {
			keyType = kt;
		}

		int estimateBytes(long curBlockPos) {
			BlockWriter b = new BlockWriter(
					INDEX_BLOCK_TYPE, keyType,
					MAX_BLOCK_SIZE,
					Math.max(restartInterval, entries.size() / MAX_RESTARTS));
			try {
				for (Entry e : entries) {
					b.mustAdd(e);
				}
				if (cur != null) {
					b.mustAdd(new IndexEntry(cur.lastKey(), curBlockPos));
				}
			} catch (BlockSizeTooSmallException e) {
				return b.currentSize();
			}
			return b.currentSize();
		}

		void writeIndex() throws IOException {
			if (padBetweenBlocks(keyType)) {
				out.padBetweenBlocksToNextBlock();
			}
			long startPos = out.size();
			writeMultiLevelIndex(entries);
			bytes = (int) (out.size() - startPos);
			entries = null;
		}

		private void writeMultiLevelIndex(List<IndexEntry> keys)
				throws IOException {
			levels = 1;
			while (maxIndexLevels == 0 || levels < maxIndexLevels) {
				keys = writeOneLevel(keys);
				if (keys == null) {
					return;
				}
				levels++;
			}

			// When maxIndexLevels has restricted the writer, write one
			// index block with the entire remaining set of keys.
			BlockWriter b = new BlockWriter(
					INDEX_BLOCK_TYPE, keyType,
					MAX_BLOCK_SIZE,
					Math.max(restartInterval, keys.size() / MAX_RESTARTS));
			for (Entry e : keys) {
				b.mustAdd(e);
			}
			rootPosition = out.size();
			b.writeTo(out);
		}

		private List<IndexEntry> writeOneLevel(List<IndexEntry> keys)
				throws IOException {
			Section thisLevel = new Section(keyType);
			for (Entry e : keys) {
				thisLevel.write(e);
			}
			if (!thisLevel.idx.entries.isEmpty()) {
				thisLevel.flushCurBlock();
				if (cur.padBetweenBlocks()) {
					out.padBetweenBlocksToNextBlock();
				}
				cur = null;
				return thisLevel.idx.entries;
			}

			// The current block fit entire level; make it the root.
			rootPosition = out.size();
			cur.writeTo(out);
			cur = null;
			return null;
		}
	}
}
Params:	min – the minimum update index for log entries that appear in this reftable. This should be 1 higher than the prior reftable's `maxUpdateIndex` if this table will be used in a stack.
Returns:	`this`
Params:	max – the maximum update index for log entries that appear in this reftable. This should be at least 1 higher than the prior reftable's `maxUpdateIndex` if this table will be used in a stack.
Returns:	`this`
Params:	os – stream to write the table to. Caller is responsible for closing the stream after invoking `finish()`.
Throws:	IOException – if reftable header cannot be written.
Returns:	`this`
Params:	refsToPack – references to sort and write.
Throws:	IOException – if reftable cannot be written.
Returns:	`this`
Params:	ref – the reference to store.
Throws:	IOException – if reftable cannot be written.
Params:	ref – the reference to store. updateIndex – the updateIndex that modified this reference. Must be `>= minUpdateIndex` for this file.
Throws:	IOException – if reftable cannot be written.
Params:	ref – the ref to delete (hide) a reflog entry from. updateIndex – the update index that must be hidden.
Throws:	IOException – if reftable cannot be written.
/

org.eclipse.jgit/ org.eclipse.jgit/ 5.5.0.201909110433-r/ org/eclipse/jgit/internal/storage/reftable/ReftableWriter.java
