alluxio-master-2.x/core/common/src/main/java/alluxio/collections/ConcurrentIdentityHashMap.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 java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.stream.Collectors;
import javax.annotation.concurrent.ThreadSafe;

/**
 * An implementation {@link ConcurrentHashMap} that utilizes identity semantics
 * with its keys
 *
 * Having identity semantics means that it is possible to have two objects with which are
 * equal based on the object's {@code equals()} implementation, but not be overridden in the hash
 * map if you try to put both. For example:
 *
 * <pre>
 *   ConcurrentIdentityHashMap&lt;String, Boolean&gt; map = new ConcurrentIdentityHashMap&lt;&gt;();
 *   String s1 = new String("test");
 *   String s2 = new String("test");
 *   map.put(s1, true);
 *   map.put(s2, false);
 *   map.size(); // Prints "2".
 *   map.get(s1); // true
 *   map.get(s2); // false
 * </pre>
 *
 * Keys in this mapped are hashed based on the identity, that is, the location in memory of the
 * objects rather than the equality which java typically uses for comparison.
 *
 * This implementation of {@link ConcurrentMap} has a few limitations which the corresponding
 * {@link ConcurrentHashMap} does not have.
 *
 * - This map's {@link #entrySet()} returns a copy of the entries at the time of calling the method.
 * The returned set does will not receive updates from the underlying map. This is a departure
 * from the behavior of {@link ConcurrentHashMap}
 *
 * - This map's {@link #keySet()} does return the map-backed keySet and provides the same
 * behavior as in {@link ConcurrentHashMap}, however the difference is that {@link Set#toArray()}
 * and {@link Set#toArray(Object[])} methods are left unimplemented and will throw an error if
 * the user attempts to convert the set into an array.
 *
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 */
@ThreadSafe
public class ConcurrentIdentityHashMap<K, V> implements ConcurrentMap<K, V> {
  private static final String UNSUPPORTED_OP_FMT = "%s is not supported in this set returned from "
          + ConcurrentIdentityHashMap.class.getCanonicalName();

  private final ConcurrentHashMap<IdentityObject<K>, V> mInternalMap;

  /**
   * Creates a new, empty map with the default initial table size (16).
   */
  public ConcurrentIdentityHashMap() {
    mInternalMap = new ConcurrentHashMap<>();
  }

  /**
   * Creates a new, empty map with an initial table size accommodating the specified number of
   * elements without having to dynamically resize.
   *
   * @param initialCapacity The implementation performs internal sizing to accommodate this many
   *        elements.
   * @throws IllegalArgumentException if the initial capacity of
   *         elements is negative
   */
  public ConcurrentIdentityHashMap(int initialCapacity) {
    mInternalMap = new ConcurrentHashMap<>(initialCapacity);
  }

  /**
   * Creates a new, empty map with an initial table size based on the given number of elements
   * ({@code initialCapacity}) and initial load factor ({@code loadFactor}) with a
   * {@code concurrencyLevel} of 1.
   *
   * @param initialCapacity the initial capacity. The implementation performs internal sizing to
   *        accommodate this many elements, given the specified load factor.
   * @param loadFactor the load factor (table density) for
   *        establishing the initial table size
   * @throws IllegalArgumentException if the initial capacity of
   * elements is negative or the load factor is nonpositive
   */
  public ConcurrentIdentityHashMap(int initialCapacity, float loadFactor) {
    this(initialCapacity, loadFactor, 1);
  }

  /**
   * Creates a new, empty map with an initial table size based on the given number of elements
   * ({@code initialCapacity}), load factor ({@code loadFactor}), and number of
   * expected concurrently updating threads ({@code concurrencyLevel}).
   *
   * @param initialCapacity the initial capacity. The implementation performs internal sizing to
   *        accommodate this many elements, given the specified load factor.
   * @param loadFactor the load factor (table density) for
   *        establishing the initial table size
   * @param concurrencyLevel the estimated number of concurrently updating threads. The
   *        implementation may use this value as a sizing hint.
   * @throws IllegalArgumentException if the initial capacity is negative or the load factor or
   *         concurrencyLevel are nonpositive
   */
  public ConcurrentIdentityHashMap(int initialCapacity,
      float loadFactor, int concurrencyLevel) {
    mInternalMap = new ConcurrentHashMap<>(initialCapacity, loadFactor, concurrencyLevel);
  }

  @Override
  public boolean containsKey(Object k) {
    return mInternalMap.containsKey(new IdentityObject<>(k));
  }

  @Override
  public V put(K k, V v) {
    return mInternalMap.put(new IdentityObject<>(k), v);
  }

  @Override
  public V putIfAbsent(K k, V v) {
    return mInternalMap.putIfAbsent(new IdentityObject<>(k), v);
  }

  @Override
  public boolean remove(Object k, Object v) {
    return mInternalMap.remove(new IdentityObject<>(k), v);
  }

  @Override
  public V remove(Object k) {
    return mInternalMap.remove(new IdentityObject<>(k));
  }

  @Override
  public boolean replace(K k, V v1, V v2) {
    return mInternalMap.replace(new IdentityObject<>(k), v1, v2);
  }

  @Override
  public V replace(K k, V v) {
    return mInternalMap.replace(new IdentityObject<>(k), v);
  }

  @Override
  public V get(Object k) {
    return mInternalMap.get(new IdentityObject<>(k));
  }

  @Override
  public Collection<V> values() {
    return mInternalMap.values();
  }

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

  /**
   * Returns a set representing the entries of this map at the time of calling.
   *
   * Note, this method will create a copy of the map's entry set at creation time. Standard
   * behavior in the {@link ConcurrentHashMap} says that the entry set backed by the map is
   * updated when the underlying map is updated. That is not the case for this class.
   *
   * @return The set of entries in the map at time of calling
   */
  @Override
  public Set<Map.Entry<K, V>> entrySet() {
    return mInternalMap.entrySet().stream().map(IdentityEntry<K, V>::new)
        .collect(Collectors.toSet());
  }

  @Override
  public void putAll(Map<? extends K, ? extends V> map) {
    map.forEach((k, v) -> mInternalMap.put(new IdentityObject<>(k), v));
  }

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

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

  @Override
  public boolean containsValue(Object value) {
    return mInternalMap.containsValue(value);
  }

  /**
   * Returns a set representing all keys contained within the map.
   *
   * Note this method departs slightly from the standard {@link ConcurrentHashMap} implementation
   * by providing its own implementation of a Set for {@link IdentityObject}. Not all methods
   * have been implemented. Namely the {@code toArray}, {@code add*}, and
   * {@code *all(Collection<?> c)} methods.
   *
   * @return The set of keys in the map
   */
  @Override
  public Set<K> keySet() {
    Set<IdentityObject<K>> set = mInternalMap.keySet();
    return new Set<K>() {

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

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

      @Override
      public boolean contains(Object o) {
        return set.contains(new IdentityObject<>(o));
      }

      @Override
      public Iterator<K> iterator() {
        return set.stream().map(IdentityObject::get).iterator();
      }

      @Override
      public Object[] toArray() {
        throw new UnsupportedOperationException(String.format(UNSUPPORTED_OP_FMT, "toArray"));
      }

      @Override
      public <T> T[] toArray(T[] a) {
        throw new UnsupportedOperationException(String.format(UNSUPPORTED_OP_FMT, "toArray"));
      }

      @Override
      public boolean add(K k) {
        throw new UnsupportedOperationException(String.format(UNSUPPORTED_OP_FMT, "add"));
      }

      @Override
      public boolean remove(Object o) {
        return set.remove(new IdentityObject<>(o));
      }

      /*
       * This method is possible to implement if inputs from the input collection are auto-boxed
       * into an IdentityObject<T> but the implementation has been left absent for now.
       */
      @Override
      public boolean containsAll(Collection<?> c) {
        throw new UnsupportedOperationException(String.format(UNSUPPORTED_OP_FMT, "containsAll"));
      }

      @Override
      public boolean addAll(Collection<? extends K> c) {
        throw new UnsupportedOperationException(String.format(UNSUPPORTED_OP_FMT, "addAll"));
      }

      /*
       * This method is possible to implement if inputs from the input collection are auto-boxed
       * into an IdentityObject<T> but the implementation has been left absent for now.
       */
      @Override
      public boolean retainAll(Collection<?> c) {
        throw new UnsupportedOperationException(String.format(UNSUPPORTED_OP_FMT, "retainAll"));
      }

      /*
       * This method is possible to implement if inputs from the input collection are auto-boxed
       * into an IdentityObject<T> but the implementation has been left absent for now.
       */
      @Override
      public boolean removeAll(Collection<?> c) {
        throw new UnsupportedOperationException(String.format(UNSUPPORTED_OP_FMT, "removeAll"));
      }

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

  private class IdentityObject<T> {
    private T mObj;

    public IdentityObject(T o) {
      mObj = o;
    }

    public T get() {
      return mObj;
    }

    /*
     * This method hashes on top of the {@link System#identityHashCode(Object)} because the
     * {@link ConcurrentHashMap} implementation uses a bucketing strategy where hash collisions
     * occur for when values do not differ in upper or lower bits. Using the extra hash here
     * helps ensure more even spread among the buckets of the internal map
     */
    @Override
    public int hashCode() {
      // Robert Jenkins 32-bit integer hash
      int a = System.identityHashCode(mObj);
      a = (a + 0x7ed55d16) + (a << 12);
      a = (a ^ 0xc761c23c) ^ (a >> 19);
      a = (a + 0x165667b1) + (a << 5);
      a = (a + 0xd3a2646c) ^ (a << 9);
      a = (a + 0xfd7046c5) + (a << 3);
      a = (a ^ 0xb55a4f09) ^ (a >> 16);
      return a;
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) {
        return true;
      }
      if (!(o instanceof IdentityObject)) {
        return false;
      }

      try {
        IdentityObject<T> other = (IdentityObject<T>) o;
        return mObj == other.mObj;
      } catch (ClassCastException e) {
        return false;
      }
    }
  }

  private class IdentityEntry<T, P> implements Map.Entry<T, P> {
    private final IdentityObject<T> mKey;
    private P mValue;

    IdentityEntry(Map.Entry<IdentityObject<T>, P> e) {
      mKey = e.getKey();
      mValue = e.getValue();
    }

    @Override
    public T getKey() {
      return mKey.get();
    }

    @Override
    public P getValue() {
      return mValue;
    }

    @Override
    public P setValue(P v) {
      P old = mValue;
      mValue = v;
      return old;
    }

    @Override
    public int hashCode() {
      return Objects.hash(mKey, mValue);
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) {
        return true;
      }
      if (!(o instanceof IdentityEntry)) {
        return false;
      }

      try {
        IdentityEntry<T, P> other = (IdentityEntry<T, P>) o;
        return mKey.equals(other.mKey)
            && mValue.equals(other.mValue);
      } catch (ClassCastException e) {
        return false;
      }
    }
  }
}
