ObjectIdOwnerMap.java

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

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Fast, efficient map for {@link org.eclipse.jgit.lib.ObjectId} subclasses in
 * only one map.
 * <p>
 * To use this map type, applications must have their entry value type extend
 * from {@link org.eclipse.jgit.lib.ObjectIdOwnerMap.Entry}, which itself
 * extends from ObjectId.
 * <p>
 * Object instances may only be stored in <b>ONE</b> ObjectIdOwnerMap. This
 * restriction exists because the map stores internal map state within each
 * object instance. If an instance is be placed in another ObjectIdOwnerMap it
 * could corrupt one or both map's internal state.
 * <p>
 * If an object instance must be in more than one map, applications may use
 * ObjectIdOwnerMap for one of the maps, and
 * {@link org.eclipse.jgit.lib.ObjectIdSubclassMap} for the other map(s). It is
 * encouraged to use ObjectIdOwnerMap for the map that is accessed most often,
 * as this implementation runs faster than the more general ObjectIdSubclassMap
 * implementation.
 *
 * @param <V>
 *            type of subclass of ObjectId that will be stored in the map.
 */
public class ObjectIdOwnerMap<V extends ObjectIdOwnerMap.Entry>
        implements Iterable<V>, ObjectIdSet {
    /** Size of the initial directory, will grow as necessary. */
    private static final int INITIAL_DIRECTORY = 1024;

    /** Number of bits in a segment's index. Segments are 2^11 in size. */
    private static final int SEGMENT_BITS = 11;

    private static final int SEGMENT_SHIFT = 32 - SEGMENT_BITS;

    /**
     * Top level directory of the segments.
     * <p>
     * The low {@link #bits} of the SHA-1 are used to select the segment from
     * this directory. Each segment is constant sized at 2^SEGMENT_BITS.
     */
    V[][] directory;

    /** Total number of objects in this map. */
    int size;

    /** The map doubles in capacity when {@link #size} reaches this target. */
    private int grow;

    /** Number of low bits used to form the index into {@link #directory}. */
    int bits;

    /** Low bit mask to index into {@link #directory}, {@code 2^bits-1}. */
    private int mask;

    /**
     * Create an empty map.
     */
    @SuppressWarnings("unchecked")
    public ObjectIdOwnerMap() {
        bits = 0;
        mask = 0;
        grow = computeGrowAt(bits);

        directory = (V[][]) new Entry[INITIAL_DIRECTORY][];
        directory[0] = newSegment();
    }

    /**
     * Remove all entries from this map.
     */
    public void clear() {
        size = 0;

        for (V[] tbl : directory) {
            if (tbl == null)
                break;
            Arrays.fill(tbl, null);
        }
    }

    /**
     * Lookup an existing mapping.
     *
     * @param toFind
     *            the object identifier to find.
     * @return the instance mapped to toFind, or null if no mapping exists.
     */
    @SuppressWarnings("unchecked")
    public V get(AnyObjectId toFind) {
        if (toFind == null) {
            return null;
        }
        int h = toFind.w1;
        V obj = directory[h & mask][h >>> SEGMENT_SHIFT];
        for (; obj != null; obj = (V) obj.next)
            if (equals(obj, toFind))
                return obj;
        return null;
    }

    /**
     * {@inheritDoc}
     * <p>
     * Returns true if this map contains the specified object.
     */
    @Override
    public boolean contains(AnyObjectId toFind) {
        return get(toFind) != null;
    }

    /**
     * Store an object for future lookup.
     * <p>
     * An existing mapping for <b>must not</b> be in this map. Callers must
     * first call {@link #get(AnyObjectId)} to verify there is no current
     * mapping prior to adding a new mapping, or use {@link #addIfAbsent(Entry)}.
     *
     * @param newValue
     *            the object to store.
     */
    public <Q extends V> void add(Q newValue) {
        if (++size == grow)
            grow();

        int h = newValue.w1;
        V[] table = directory[h & mask];
        h >>>= SEGMENT_SHIFT;

        newValue.next = table[h];
        table[h] = newValue;
    }

    /**
     * Store an object for future lookup.
     * <p>
     * Stores {@code newValue}, but only if there is not already an object for
     * the same object name. Callers can tell if the value is new by checking
     * the return value with reference equality:
     *
     * <pre>
     * V obj = ...;
     * boolean wasNew = map.addIfAbsent(obj) == obj;
     * </pre>
     *
     * @param newValue
     *            the object to store.
     * @return {@code newValue} if stored, or the prior value already stored and
     *         that would have been returned had the caller used
     *         {@code get(newValue)} first.
     */
    @SuppressWarnings("unchecked")
    public <Q extends V> V addIfAbsent(Q newValue) {
        int h = newValue.w1;
        V[] table = directory[h & mask];
        h >>>= SEGMENT_SHIFT;

        for (V obj = table[h]; obj != null; obj = (V) obj.next)
            if (equals(obj, newValue))
                return obj;

        newValue.next = table[h];
        table[h] = newValue;

        if (++size == grow)
            grow();
        return newValue;
    }

    /**
     * Get number of objects in this map.
     *
     * @return number of objects in this map.
     */
    public int size() {
        return size;
    }

    /**
     * Whether this map is empty
     *
     * @return true if {@link #size()} is 0.
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /** {@inheritDoc} */
    @Override
    public Iterator<V> iterator() {
        return new Iterator<V>() {
            private int found;
            private int dirIdx;
            private int tblIdx;
            private V next;

            @Override
            public boolean hasNext() {
                return found < size;
            }

            @Override
            public V next() {
                if (next != null)
                    return found(next);

                for (;;) {
                    V[] table = directory[dirIdx];
                    if (tblIdx == table.length) {
                        if (++dirIdx >= (1 << bits))
                            throw new NoSuchElementException();
                        table = directory[dirIdx];
                        tblIdx = 0;
                    }

                    while (tblIdx < table.length) {
                        V v = table[tblIdx++];
                        if (v != null)
                            return found(v);
                    }
                }
            }

            @SuppressWarnings("unchecked")
            private V found(V v) {
                found++;
                next = (V) v.next;
                return v;
            }

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

    @SuppressWarnings("unchecked")
    private void grow() {
        final int oldDirLen = 1 << bits;
        final int s = 1 << bits;

        bits++;
        mask = (1 << bits) - 1;
        grow = computeGrowAt(bits);

        // Quadruple the directory if it needs to expand. Expanding the
        // directory is expensive because it generates garbage, so try
        // to avoid doing it often.
        //
        final int newDirLen = 1 << bits;
        if (directory.length < newDirLen) {
            V[][] newDir = (V[][]) new Entry[newDirLen << 1][];
            System.arraycopy(directory, 0, newDir, 0, oldDirLen);
            directory = newDir;
        }

        // For every bucket of every old segment, split the chain between
        // the old segment and the new segment's corresponding bucket. To
        // select between them use the lowest bit that was just added into
        // the mask above. This causes the table to double in capacity.
        //
        for (int dirIdx = 0; dirIdx < oldDirLen; dirIdx++) {
            final V[] oldTable = directory[dirIdx];
            final V[] newTable = newSegment();

            for (int i = 0; i < oldTable.length; i++) {
                V chain0 = null;
                V chain1 = null;
                V next;

                for (V obj = oldTable[i]; obj != null; obj = next) {
                    next = (V) obj.next;

                    if ((obj.w1 & s) == 0) {
                        obj.next = chain0;
                        chain0 = obj;
                    } else {
                        obj.next = chain1;
                        chain1 = obj;
                    }
                }

                oldTable[i] = chain0;
                newTable[i] = chain1;
            }

            directory[oldDirLen + dirIdx] = newTable;
        }
    }

    @SuppressWarnings("unchecked")
    private final V[] newSegment() {
        return (V[]) new Entry[1 << SEGMENT_BITS];
    }

    private static final int computeGrowAt(int bits) {
        return 1 << (bits + SEGMENT_BITS);
    }

    private static final boolean equals(AnyObjectId firstObjectId,
            AnyObjectId secondObjectId) {
        return firstObjectId.w2 == secondObjectId.w2
                && firstObjectId.w3 == secondObjectId.w3
                && firstObjectId.w4 == secondObjectId.w4
                && firstObjectId.w5 == secondObjectId.w5
                && firstObjectId.w1 == secondObjectId.w1;
    }

    /** Type of entry stored in the {@link ObjectIdOwnerMap}. */
    public abstract static class Entry extends ObjectId {
        transient Entry next;

        /**
         * Initialize this entry with a specific ObjectId.
         *
         * @param id
         *            the id the entry represents.
         */
        public Entry(AnyObjectId id) {
            super(id);
        }
    }
}