alluxio-master-2.x/core/common/src/main/java/alluxio/collections/NonUniqueFieldIndex.java
/*
 * The Alluxio Open Foundation licenses this work under the Apache License, version 2.0
 * (the "License"). You may not use this work except in compliance with the License, which is
 * available at www.apache.org/licenses/LICENSE-2.0
 *
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND,
 * either express or implied, as more fully set forth in the License.
 *
 * See the NOTICE file distributed with this work for information regarding copyright ownership.
 */

package alluxio.collections;

import com.google.common.collect.Iterables;

import java.util.Collections;
import java.util.Iterator;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicBoolean;
import javax.annotation.concurrent.ThreadSafe;

/**
 * A class representing a non-unique index. A non-unique index is an index where an index value can
 * map to one or more objects.
 *
 * @param <T> type of objects in this index
 * @param <V> type of the field used for indexing
 */
@ThreadSafe
public class NonUniqueFieldIndex<T, V> implements FieldIndex<T, V> {
  private final IndexDefinition<T, V> mIndexDefinition;
  private final ConcurrentHashMap<V, ConcurrentHashSet<T>> mIndexMap;

  /**
   * Constructs a new {@link NonUniqueFieldIndex} instance.
   *
   * @param indexDefinition definition of index
   */
  public NonUniqueFieldIndex(IndexDefinition<T, V> indexDefinition) {
    mIndexMap = new ConcurrentHashMap<>(8, 0.95f, 8);
    mIndexDefinition = indexDefinition;
  }

  @Override
  public boolean add(T object) {
    AtomicBoolean res = new AtomicBoolean(false);
    V fieldValue = mIndexDefinition.getFieldValue(object);
    mIndexMap.compute(fieldValue, (value, set) -> {
      if (set == null) {
        set = new ConcurrentHashSet<>();
      }
      res.set(set.add(object));
      return set;
    });
    return res.get();
  }

  @Override
  public boolean remove(T object) {
    AtomicBoolean res = new AtomicBoolean(false);
    V fieldValue = mIndexDefinition.getFieldValue(object);
    mIndexMap.computeIfPresent(fieldValue, (value, set) -> {
      res.set(set.remove(object));
      if (set.isEmpty()) {
        return null;
      }
      return set;
    });
    return res.get();
  }

  @Override
  public void clear() {
    mIndexMap.clear();
  }

  @Override
  public boolean containsField(V fieldValue) {
    return mIndexMap.containsKey(fieldValue);
  }

  @Override
  public boolean containsObject(T object) {
    V fieldValue = mIndexDefinition.getFieldValue(object);
    ConcurrentHashSet<T> set = mIndexMap.get(fieldValue);

    if (set == null) {
      return false;
    }
    return set.contains(object);
  }

  @Override
  public Set<T> getByField(V value) {
    Set<T> set = mIndexMap.get(value);
    return set == null ? Collections.<T>emptySet() : set;
  }

  @Override
  public T getFirst(V value) {
    Set<T> all = mIndexMap.get(value);
    return all == null ? null : Iterables.getFirst(all, null);
  }

  @Override
  public Iterator<T> iterator() {
    return new NonUniqueFieldIndexIterator();
  }

  @Override
  public int size() {
    int totalSize = 0;
    for (ConcurrentHashSet<T> innerSet : mIndexMap.values()) {
      totalSize += innerSet.size();
    }
    return totalSize;
  }

  /**
   * Specialized iterator for {@link NonUniqueFieldIndex}.
   *
   * This is needed to support consistent removal from the set and the indices.
   */
  private class NonUniqueFieldIndexIterator implements Iterator<T> {
    /**
     * Iterator of {@link NonUniqueFieldIndex#mIndexMap}. This iterator keeps track of the
     * inner set which is under iteration.
     */
    private final Iterator<ConcurrentHashSet<T>> mIndexIterator;
    /**
     * Iterator inside each inner set. This iterator keeps track of the objects.
     */
    private Iterator<T> mObjectIterator;
    /**
     * Keeps track of current object. It is used to do the remove.
     */
    private T mObject;

    public NonUniqueFieldIndexIterator() {
      mIndexIterator = mIndexMap.values().iterator();
      mObjectIterator = null;
      mObject = null;
    }

    @Override
    public boolean hasNext() {
      if (mObjectIterator != null && mObjectIterator.hasNext()) {
        return true;
      }
      while (mIndexIterator.hasNext()) {
        mObjectIterator = mIndexIterator.next().iterator();
        if (mObjectIterator.hasNext()) {
          return true;
        }
      }
      return false;
    }

    @Override
    public T next() {
      while (mObjectIterator == null || !mObjectIterator.hasNext()) {
        mObjectIterator = mIndexIterator.next().iterator();
      }

      final T next = mObjectIterator.next();
      mObject = next;
      return next;
    }

    @Override
    public void remove() {
      if (mObject != null) {
        NonUniqueFieldIndex.this.remove(mObject);
        mObject = null;
      } else {
        throw new IllegalStateException("next() was not called before remove()");
      }
    }
  }
}
