RevObjectList.java

/*
 * Copyright (C) 2009, Google Inc.
 * Copyright (C) 2009, Jonas Fonseca <fonseca@diku.dk>
 * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org> 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.revwalk;

import java.text.MessageFormat;
import java.util.AbstractList;

import org.eclipse.jgit.internal.JGitText;

/**
 * An ordered list of {@link org.eclipse.jgit.revwalk.RevObject} subclasses.
 *
 * @param <E>
 *            type of subclass of RevObject the list is storing.
 */
public class RevObjectList<E extends RevObject> extends AbstractList<E> {
    static final int BLOCK_SHIFT = 8;

    static final int BLOCK_SIZE = 1 << BLOCK_SHIFT;

    /**
     * Items stored in this list.
     * <p>
     * If {@link Block#shift} = 0 this block holds the list elements; otherwise
     * it holds pointers to other {@link Block} instances which use a shift that
     * is {@link #BLOCK_SHIFT} smaller.
     */
    protected Block contents = new Block(0);

    /** Current number of elements in the list. */
    protected int size = 0;

    /**
     * Create an empty object list.
     */
    public RevObjectList() {
        // Initialized above.
    }

    /** {@inheritDoc} */
    @Override
    public void add(int index, E element) {
        if (index != size)
            throw new UnsupportedOperationException(MessageFormat.format(
                    JGitText.get().unsupportedOperationNotAddAtEnd,
                    Integer.valueOf(index)));
        set(index, element);
        size++;
    }

    /** {@inheritDoc} */
    @Override
    @SuppressWarnings("unchecked")
    public E set(int index, E element) {
        Block s = contents;
        while (index >> s.shift >= BLOCK_SIZE) {
            s = new Block(s.shift + BLOCK_SHIFT);
            s.contents[0] = contents;
            contents = s;
        }
        while (s.shift > 0) {
            final int i = index >> s.shift;
            index -= i << s.shift;
            if (s.contents[i] == null)
                s.contents[i] = new Block(s.shift - BLOCK_SHIFT);
            s = (Block) s.contents[i];
        }
        final Object old = s.contents[index];
        s.contents[index] = element;
        return (E) old;
    }

    /** {@inheritDoc} */
    @Override
    @SuppressWarnings("unchecked")
    public E get(int index) {
        Block s = contents;
        if (index >> s.shift >= 1024)
            return null;
        while (s != null && s.shift > 0) {
            final int i = index >> s.shift;
            index -= i << s.shift;
            s = (Block) s.contents[i];
        }
        return s != null ? (E) s.contents[index] : null;
    }

    /** {@inheritDoc} */
    @Override
    public int size() {
        return size;
    }

    /** {@inheritDoc} */
    @Override
    public void clear() {
        contents = new Block(0);
        size = 0;
    }

    /** One level of contents, either an intermediate level or a leaf level. */
    protected static class Block {
        final Object[] contents = new Object[BLOCK_SIZE];

        final int shift;

        Block(int s) {
            shift = s;
        }
    }
}