COWArrayList.java

/*
 * Copyright 2015-2022 QOS.CH Sarl (Switzerland)
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.log4j.helpers;

import java.util.List;
import java.util.ListIterator;
import java.util.Collection;
import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.atomic.AtomicBoolean;

/**
 * A GC-free lock-free thread-safe implementation of the {@link List} interface for use cases where iterations over the
 * list vastly out-number modifications on the list.
 *
 * <p>
 * Underneath, it wraps an instance of {@link CopyOnWriteArrayList} and exposes a copy of the array used by that
 * instance.
 *
 * <p>
 * Typical use:
 * </p>
 *
 * <pre>
 *   COWArrayList&lt;Integer&gt; list = new COWArrayList(new Integer[0]);
 *
 *   // modify the list
 *   list.add(1);
 *   list.add(2);
 *
 *   Integer[] intArray = list.asTypedArray();
 *   int sum = 0;
 *   // iteration over the array is thread-safe
 *   for(int i = 0; i &lt; intArray.length; i++) {
 *     sum != intArray[i];
 *   }
 * </pre>
 *
 * <p>
 * If the list is not modified, then repetitive calls to {@link #asTypedArray()}, {@link #toArray()} and
 * {@link #toArray(Object[])} are guaranteed to be GC-free. Note that iterating over the list using
 * {@link COWArrayList#iterator()} and {@link COWArrayList#listIterator()} are
 * <b>not</b> GC-free.
 * </p>
 *
 * @author Ceki Gulcu
 * @since 1.2.20
 */
public class COWArrayList<E> implements List<E> {

    AtomicBoolean fresh = new AtomicBoolean(false);
    CopyOnWriteArrayList<E> underlyingList = new CopyOnWriteArrayList<E>();
    E[] ourCopy;
    final E[] modelArray;

    public COWArrayList(E[] modelArray) {
        this.modelArray = modelArray;
    }

    @Override
    public int size() {
        return underlyingList.size();
    }

    @Override
    public boolean isEmpty() {
        return underlyingList.isEmpty();
    }

    @Override
    public boolean contains(Object o) {
        return underlyingList.contains(o);
    }

    @Override
    public Iterator<E> iterator() {
        return underlyingList.iterator();
    }

    private void refreshCopyIfNecessary() {
        if (!isFresh()) {
            refreshCopy();
        }
    }

    private boolean isFresh() {
        return fresh.get();
    }

    private void refreshCopy() {
        ourCopy = underlyingList.toArray(modelArray);
        fresh.set(true);
    }

    @Override
    public Object[] toArray() {
        refreshCopyIfNecessary();
        return ourCopy;
    }

    @SuppressWarnings("unchecked")
    @Override
    public <T> T[] toArray(T[] a) {
        refreshCopyIfNecessary();
        return (T[]) ourCopy;
    }

    /**
     * Return an array of type E[]. The returned array is intended to be iterated over. If the list is modified,
     * subsequent calls to this method will return different/modified array instances.
     *
     * @return
     */
    public E[] asTypedArray() {
        refreshCopyIfNecessary();
        return ourCopy;
    }

    private void markAsStale() {
        fresh.set(false);
    }

    public void addIfAbsent(E e) {
        underlyingList.addIfAbsent(e);
        markAsStale();
    }

    @Override
    public boolean add(E e) {
        boolean result = underlyingList.add(e);
        markAsStale();
        return result;
    }

    @Override
    public boolean remove(Object o) {
        boolean result = underlyingList.remove(o);
        markAsStale();
        return result;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return underlyingList.containsAll(c);
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        markAsStale();
        boolean result = underlyingList.addAll(c);
        return result;
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> col) {
        markAsStale();
        boolean result = underlyingList.addAll(index, col);
        return result;
    }

    @Override
    public boolean removeAll(Collection<?> col) {
        markAsStale();
        boolean result = underlyingList.removeAll(col);
        return result;
    }

    @Override
    public boolean retainAll(Collection<?> col) {
        markAsStale();
        boolean result = underlyingList.retainAll(col);
        return result;
    }

    @Override
    public void clear() {
        markAsStale();
        underlyingList.clear();
    }

    @Override
    public E get(int index) {
        refreshCopyIfNecessary();
        return (E) ourCopy[index];
    }

    @Override
    public E set(int index, E element) {
        markAsStale();
        E e = underlyingList.set(index, element);
        return e;
    }

    @Override
    public void add(int index, E element) {
        markAsStale();
        underlyingList.add(index, element);
    }

    @Override
    public E remove(int index) {
        markAsStale();
        E e = (E) underlyingList.remove(index);
        return e;
    }

    @Override
    public int indexOf(Object o) {
        return underlyingList.indexOf(o);
    }

    @Override
    public int lastIndexOf(Object o) {
        return underlyingList.lastIndexOf(o);
    }

    @Override
    public ListIterator<E> listIterator() {
        return underlyingList.listIterator();
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        return underlyingList.listIterator(index);
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        return underlyingList.subList(fromIndex, toIndex);
    }

}