ReftableWriter.java

/*
 * Copyright (C) 2017, Google Inc. and others
 *
 * This program and the accompanying materials are made available under the
 * terms of the Eclipse Distribution License v. 1.0 which is available at
 * https://www.eclipse.org/org/documents/edl-v10.php.
 *
 * SPDX-License-Identifier: BSD-3-Clause
 */

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.
 * <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 OutputStream outputStream;
    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.
     *
     * @param os
     *            output stream.
     */
    public ReftableWriter(OutputStream os) {
        this(new ReftableConfig(), os);
        lastRef = null;
        lastLog = null;
    }

    /**
     * Initialize a writer with a configuration.
     *
     * @param cfg
     *            configuration for the writer
     * @param os
     *            output stream.
     */
    public ReftableWriter(ReftableConfig cfg, OutputStream os) {
        config = cfg;
        outputStream = os;
    }

    /**
     * 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.
     *
     * @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.
     *
     * @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. Should be called only once. Call this
     * if a stream was passed to the constructor.
     *
     * @return {@code this}
     */
    public ReftableWriter begin() {
        if (out != null) {
            throw new IllegalStateException("begin() called twice.");//$NON-NLS-1$
        }

        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(outputStream, 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.
     * The input refs may not have duplicate names.
     *
     * @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();
        RefEntry last = null;
        while (itr.hasNext()) {
            RefEntry entry = itr.next();
            if (last != null && Entry.compare(last, entry) == 0) {
                throwIllegalEntry(last, entry);
            }

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

    /**
     * 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.
     * <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.
     * <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.
     *
     * <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
     *
     * @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.
     *
     * @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.
     *
     * @return statistics of the last written reftable.
     */
    public Stats getStats() {
        return stats;
    }

    /** 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;
        }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        /**
         * @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;
        }
    }
}