FanoutBucket.java

/*
 * Copyright (C) 2010, 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.notes;

import static org.eclipse.jgit.lib.FileMode.TREE;

import java.io.IOException;
import java.util.Iterator;
import java.util.NoSuchElementException;

import org.eclipse.jgit.lib.AbbreviatedObjectId;
import org.eclipse.jgit.lib.AnyObjectId;
import org.eclipse.jgit.lib.MutableObjectId;
import org.eclipse.jgit.lib.ObjectId;
import org.eclipse.jgit.lib.ObjectInserter;
import org.eclipse.jgit.lib.ObjectReader;
import org.eclipse.jgit.lib.TreeFormatter;

/**
 * A note tree holding only note subtrees, each named using a 2 digit hex name.
 *
 * The fanout buckets/trees contain on average 256 subtrees, naming the subtrees
 * by a slice of the ObjectId contained within them, from "00" through "ff".
 *
 * Each fanout bucket has a {@link #prefixLen} that defines how many digits it
 * skips in an ObjectId before it gets to the digits matching {@link #table}.
 *
 * The root tree has {@code prefixLen == 0}, and thus does not skip any digits.
 * For ObjectId "c0ffee...", the note (if it exists) will be stored within the
 * bucket {@code table[0xc0]}.
 *
 * The first level tree has {@code prefixLen == 2}, and thus skips the first two
 * digits. For the same example "c0ffee..." object, its note would be found
 * within the {@code table[0xff]} bucket (as first 2 digits "c0" are skipped).
 *
 * Each subtree is loaded on-demand, reducing startup latency for reads that
 * only need to examine a few objects. However, due to the rather uniform
 * distribution of the SHA-1 hash that is used for ObjectIds, accessing 256
 * objects is very likely to load all of the subtrees into memory.
 *
 * A FanoutBucket must be parsed from a tree object by {@link NoteParser}.
 */
class FanoutBucket extends InMemoryNoteBucket {
    /**
     * Fan-out table similar to the PackIndex structure.
     *
     * Notes for an object are stored within the sub-bucket that is held here as
     * {@code table[ objectId.getByte( prefixLen / 2 ) ]}. If the slot is null
     * there are no notes with that prefix.
     */
    private final NoteBucket[] table;

    /** Number of non-null slots in {@link #table}. */
    private int cnt;

    FanoutBucket(int prefixLen) {
        super(prefixLen);
        table = new NoteBucket[256];
    }

    void setBucket(int cell, ObjectId id) {
        table[cell] = new LazyNoteBucket(id);
        cnt++;
    }

    void setBucket(int cell, InMemoryNoteBucket bucket) {
        table[cell] = bucket;
        cnt++;
    }

    @Override
    Note getNote(AnyObjectId objId, ObjectReader or) throws IOException {
        NoteBucket b = table[cell(objId)];
        return b != null ? b.getNote(objId, or) : null;

    }

    NoteBucket getBucket(int cell) {
        return table[cell];
    }

    static InMemoryNoteBucket loadIfLazy(NoteBucket b, AnyObjectId prefix,
            ObjectReader or) throws IOException {
        if (b == null)
            return null;
        if (b instanceof InMemoryNoteBucket)
            return (InMemoryNoteBucket) b;
        return ((LazyNoteBucket) b).load(prefix, or);
    }

    @Override
    Iterator<Note> iterator(AnyObjectId objId, final ObjectReader reader)
            throws IOException {
        final MutableObjectId id = new MutableObjectId();
        id.fromObjectId(objId);

        return new Iterator<>() {
            private int cell;

            private Iterator<Note> itr;

            @Override
            public boolean hasNext() {
                if (itr != null && itr.hasNext())
                    return true;

                for (; cell < table.length; cell++) {
                    NoteBucket b = table[cell];
                    if (b == null)
                        continue;

                    try {
                        id.setByte(prefixLen >> 1, cell);
                        itr = b.iterator(id, reader);
                    } catch (IOException err) {
                        throw new RuntimeException(err);
                    }

                    if (itr.hasNext()) {
                        cell++;
                        return true;
                    }
                }
                return false;
            }

            @Override
            public Note next() {
                if (hasNext()) {
                    return itr.next();
                }
                throw new NoSuchElementException();
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }

    @Override
    int estimateSize(AnyObjectId noteOn, ObjectReader or) throws IOException {
        // If most of this fan-out is full, estimate it should still be split.
        if (LeafBucket.MAX_SIZE * 3 / 4 <= cnt)
            return 1 + LeafBucket.MAX_SIZE;

        // Due to the uniform distribution of ObjectIds, having less nodes full
        // indicates a good chance the total number of children below here
        // is less than the MAX_SIZE split point. Get a more accurate count.

        MutableObjectId id = new MutableObjectId();
        id.fromObjectId(noteOn);

        int sz = 0;
        for (int cell = 0; cell < 256; cell++) {
            NoteBucket b = table[cell];
            if (b == null)
                continue;

            id.setByte(prefixLen >> 1, cell);
            sz += b.estimateSize(id, or);
            if (LeafBucket.MAX_SIZE < sz)
                break;
        }
        return sz;
    }

    @Override
    InMemoryNoteBucket set(AnyObjectId noteOn, AnyObjectId noteData,
            ObjectReader or) throws IOException {
        int cell = cell(noteOn);
        NoteBucket b = table[cell];

        if (b == null) {
            if (noteData == null) {
                return this;
            }

            LeafBucket n = new LeafBucket(prefixLen + 2);
            table[cell] = n.set(noteOn, noteData, or);
            cnt++;
            return this;

        }
        NoteBucket n = b.set(noteOn, noteData, or);
        if (n == null) {
            table[cell] = null;
            cnt--;

            if (cnt == 0) {
                return null;
            }

            return contractIfTooSmall(noteOn, or);

        } else if (n != b) {
            table[cell] = n;
        }
        return this;
    }

    InMemoryNoteBucket contractIfTooSmall(AnyObjectId noteOn, ObjectReader or)
            throws IOException {
        if (estimateSize(noteOn, or) < LeafBucket.MAX_SIZE) {
            // We are small enough to just contract to a single leaf.
            InMemoryNoteBucket r = new LeafBucket(prefixLen);
            for (Iterator<Note> i = iterator(noteOn, or); i.hasNext();)
                r = r.append(i.next());
            r.nonNotes = nonNotes;
            return r;
        }

        return this;
    }

    private static final byte[] hexchar = { '0', '1', '2', '3', '4', '5', '6',
            '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };

    @Override
    ObjectId writeTree(ObjectInserter inserter) throws IOException {
        return inserter.insert(build(true, inserter));
    }

    @Override
    ObjectId getTreeId() {
        try (ObjectInserter.Formatter f = new ObjectInserter.Formatter()) {
            return f.idFor(build(false, null));
        } catch (IOException e) {
            // should never happen as we are not inserting
            throw new RuntimeException(e);
        }
    }

    private TreeFormatter build(boolean insert, ObjectInserter inserter)
            throws IOException {
        byte[] nameBuf = new byte[2];
        TreeFormatter fmt = new TreeFormatter(treeSize());
        NonNoteEntry e = nonNotes;

        for (int cell = 0; cell < 256; cell++) {
            NoteBucket b = table[cell];
            if (b == null)
                continue;

            nameBuf[0] = hexchar[cell >>> 4];
            nameBuf[1] = hexchar[cell & 0x0f];

            while (e != null && e.pathCompare(nameBuf, 0, 2, TREE) < 0) {
                e.format(fmt);
                e = e.next;
            }

            ObjectId id;
            if (insert) {
                id = b.writeTree(inserter);
            } else {
                id = b.getTreeId();
            }
            fmt.append(nameBuf, 0, 2, TREE, id);
        }

        for (; e != null; e = e.next)
            e.format(fmt);
        return fmt;
    }

    private int treeSize() {
        int sz = cnt * TreeFormatter.entrySize(TREE, 2);
        for (NonNoteEntry e = nonNotes; e != null; e = e.next)
            sz += e.treeEntrySize();
        return sz;
    }

    @Override
    InMemoryNoteBucket append(Note note) {
        int cell = cell(note);
        InMemoryNoteBucket b = (InMemoryNoteBucket) table[cell];

        if (b == null) {
            LeafBucket n = new LeafBucket(prefixLen + 2);
            table[cell] = n.append(note);
            cnt++;

        } else {
            InMemoryNoteBucket n = b.append(note);
            if (n != b)
                table[cell] = n;
        }
        return this;
    }

    private int cell(AnyObjectId id) {
        return id.getByte(prefixLen >> 1);
    }

    private class LazyNoteBucket extends NoteBucket {
        private final ObjectId treeId;

        LazyNoteBucket(ObjectId treeId) {
            this.treeId = treeId;
        }

        @Override
        Note getNote(AnyObjectId objId, ObjectReader or) throws IOException {
            return load(objId, or).getNote(objId, or);
        }

        @Override
        Iterator<Note> iterator(AnyObjectId objId, ObjectReader reader)
                throws IOException {
            return load(objId, reader).iterator(objId, reader);
        }

        @Override
        int estimateSize(AnyObjectId objId, ObjectReader or) throws IOException {
            return load(objId, or).estimateSize(objId, or);
        }

        @Override
        InMemoryNoteBucket set(AnyObjectId noteOn, AnyObjectId noteData,
                ObjectReader or) throws IOException {
            return load(noteOn, or).set(noteOn, noteData, or);
        }

        @Override
        ObjectId writeTree(ObjectInserter inserter) {
            return treeId;
        }

        @Override
        ObjectId getTreeId() {
            return treeId;
        }

        private InMemoryNoteBucket load(AnyObjectId prefix, ObjectReader or)
                throws IOException {
            AbbreviatedObjectId p = prefix.abbreviate(prefixLen + 2);
            InMemoryNoteBucket self = NoteParser.parse(p, treeId, or);
            table[cell(prefix)] = self;
            return self;
        }
    }
}