android/guava/src/com/google/common/collect/RegularImmutableMap.java - platform/external/guava - Git at Google

 /*
  * Copyright (C) 2008 The Guava Authors
  *
  * 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 com.google.common.collect;

 import static com.google.common.base.Preconditions.checkElementIndex;
 import static com.google.common.base.Preconditions.checkPositionIndex;
 import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;

 import com.google.common.annotations.GwtCompatible;
 import com.google.common.annotations.VisibleForTesting;
 import java.util.AbstractMap;
 import java.util.Arrays;
 import java.util.Map.Entry;
 import org.checkerframework.checker.nullness.compatqual.NullableDecl;

 /**
  * A hash-based implementation of {@link ImmutableMap}.
  *
  * @author Louis Wasserman
  */
 @GwtCompatible(serializable = true, emulated = true)
 final class RegularImmutableMap<K, V> extends ImmutableMap<K, V> {
   private static final int ABSENT = -1;

   @SuppressWarnings("unchecked")
   static final ImmutableMap<Object, Object> EMPTY =
       new RegularImmutableMap<>(null, new Object[0], 0);

   /*
    * This is an implementation of ImmutableMap optimized especially for Android, which does not like
    * objects per entry.  Instead we use an open-addressed hash table.  This design is basically
    * equivalent to RegularImmutableSet, save that instead of having a hash table containing the
    * elements directly and null for empty positions, we store indices of the keys in the hash table,
    * and ABSENT for empty positions.  We then look up the keys in alternatingKeysAndValues.
    *
    * (The index actually stored is the index of the key in alternatingKeysAndValues, which is
    * double the index of the entry in entrySet.asList.)
    *
    * The basic data structure is described in https://en.wikipedia.org/wiki/Open_addressing.
    * The pointer to a key is stored in hashTable[Hashing.smear(key.hashCode())] % table.length,
    * save that if that location is already full, we try the next index, and the next, until we
    * find an empty table position.  Since the table has a power-of-two size, we use
    * & (table.length - 1) instead of % table.length, though.
    */

   private final transient int[] hashTable;
   @VisibleForTesting final transient Object[] alternatingKeysAndValues;
   private final transient int size;

   @SuppressWarnings("unchecked")
   static <K, V> RegularImmutableMap<K, V> create(int n, Object[] alternatingKeysAndValues) {
     if (n == 0) {
       return (RegularImmutableMap<K, V>) EMPTY;
     } else if (n == 1) {
       checkEntryNotNull(alternatingKeysAndValues[0], alternatingKeysAndValues[1]);
       return new RegularImmutableMap<K, V>(null, alternatingKeysAndValues, 1);
     }
     checkPositionIndex(n, alternatingKeysAndValues.length >> 1);
     int tableSize = ImmutableSet.chooseTableSize(n);
     int[] hashTable = createHashTable(alternatingKeysAndValues, n, tableSize, 0);
     return new RegularImmutableMap<K, V>(hashTable, alternatingKeysAndValues, n);
   }

   /**
    * Returns a hash table for the specified keys and values, and ensures that neither keys nor
    * values are null.
    */
   static int[] createHashTable(
       Object[] alternatingKeysAndValues, int n, int tableSize, int keyOffset) {
     if (n == 1) {
       // for n=1 we don't create a hash table, but we need to do the checkEntryNotNull check!
       checkEntryNotNull(
           alternatingKeysAndValues[keyOffset], alternatingKeysAndValues[keyOffset ^ 1]);
       return null;
     }
     int mask = tableSize - 1;
     int[] hashTable = new int[tableSize];
     Arrays.fill(hashTable, ABSENT);
     for (int i = 0; i < n; i++) {
       Object key = alternatingKeysAndValues[2 * i + keyOffset];
       Object value = alternatingKeysAndValues[2 * i + (keyOffset ^ 1)];
       checkEntryNotNull(key, value);
       for (int h = Hashing.smear(key.hashCode()); ; h++) {
         h &= mask;
         int previous = hashTable[h];
         if (previous == ABSENT) {
           hashTable[h] = 2 * i + keyOffset;
           break;
         } else if (alternatingKeysAndValues[previous].equals(key)) {
           throw new IllegalArgumentException(
               "Multiple entries with same key: "
                   + key
                   + "="
                   + value
                   + " and "
                   + alternatingKeysAndValues[previous]
                   + "="
                   + alternatingKeysAndValues[previous ^ 1]);
         }
       }
     }
     return hashTable;
   }

   private RegularImmutableMap(int[] hashTable, Object[] alternatingKeysAndValues, int size) {
     this.hashTable = hashTable;
     this.alternatingKeysAndValues = alternatingKeysAndValues;
     this.size = size;
   }

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

   @SuppressWarnings("unchecked")
   @Override
   @NullableDecl
   public V get(@NullableDecl Object key) {
     return (V) get(hashTable, alternatingKeysAndValues, size, 0, key);
   }

   static Object get(
       @NullableDecl int[] hashTable,
       @NullableDecl Object[] alternatingKeysAndValues,
       int size,
       int keyOffset,
       @NullableDecl Object key) {
     if (key == null) {
       return null;
     } else if (size == 1) {
       return alternatingKeysAndValues[keyOffset].equals(key)
           ? alternatingKeysAndValues[keyOffset ^ 1]
           : null;
     } else if (hashTable == null) {
       return null;
     }
     int mask = hashTable.length - 1;
     for (int h = Hashing.smear(key.hashCode()); ; h++) {
       h &= mask;
       int index = hashTable[h];
       if (index == ABSENT) {
         return null;
       } else if (alternatingKeysAndValues[index].equals(key)) {
         return alternatingKeysAndValues[index ^ 1];
       }
     }
   }

   @Override
   ImmutableSet<Entry<K, V>> createEntrySet() {
     return new EntrySet<>(this, alternatingKeysAndValues, 0, size);
   }

   static class EntrySet<K, V> extends ImmutableSet<Entry<K, V>> {
     private final transient ImmutableMap<K, V> map;
     private final transient Object[] alternatingKeysAndValues;
     private final transient int keyOffset;
     private final transient int size;

     EntrySet(ImmutableMap<K, V> map, Object[] alternatingKeysAndValues, int keyOffset, int size) {
       this.map = map;
       this.alternatingKeysAndValues = alternatingKeysAndValues;
       this.keyOffset = keyOffset;
       this.size = size;
     }

     @Override
     public UnmodifiableIterator<Entry<K, V>> iterator() {
       return asList().iterator();
     }

     @Override
     int copyIntoArray(Object[] dst, int offset) {
       return asList().copyIntoArray(dst, offset);
     }

     @Override
     ImmutableList<Entry<K, V>> createAsList() {
       return new ImmutableList<Entry<K, V>>() {
         @Override
         public Entry<K, V> get(int index) {
           checkElementIndex(index, size);
           @SuppressWarnings("unchecked")
           K key = (K) alternatingKeysAndValues[2 * index + keyOffset];
           @SuppressWarnings("unchecked")
           V value = (V) alternatingKeysAndValues[2 * index + (keyOffset ^ 1)];
           return new AbstractMap.SimpleImmutableEntry<K, V>(key, value);
         }

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

         @Override
         public boolean isPartialView() {
           return true;
         }
       };
     }

     @Override
     public boolean contains(Object object) {
       if (object instanceof Entry) {
         Entry<?, ?> entry = (Entry<?, ?>) object;
         Object k = entry.getKey();
         Object v = entry.getValue();
         return v != null && v.equals(map.get(k));
       }
       return false;
     }

     @Override
     boolean isPartialView() {
       return true;
     }

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

   @Override
   ImmutableSet<K> createKeySet() {
     @SuppressWarnings("unchecked")
     ImmutableList<K> keyList =
         (ImmutableList<K>) new KeysOrValuesAsList(alternatingKeysAndValues, 0, size);
     return new KeySet<K>(this, keyList);
   }

   static final class KeysOrValuesAsList extends ImmutableList<Object> {
     private final transient Object[] alternatingKeysAndValues;
     private final transient int offset;
     private final transient int size;

     KeysOrValuesAsList(Object[] alternatingKeysAndValues, int offset, int size) {
       this.alternatingKeysAndValues = alternatingKeysAndValues;
       this.offset = offset;
       this.size = size;
     }

     @Override
     public Object get(int index) {
       checkElementIndex(index, size);
       return alternatingKeysAndValues[2 * index + offset];
     }

     @Override
     boolean isPartialView() {
       return true;
     }

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

   static final class KeySet<K> extends ImmutableSet<K> {
     private final transient ImmutableMap<K, ?> map;
     private final transient ImmutableList<K> list;

     KeySet(ImmutableMap<K, ?> map, ImmutableList<K> list) {
       this.map = map;
       this.list = list;
     }

     @Override
     public UnmodifiableIterator<K> iterator() {
       return asList().iterator();
     }

     @Override
     int copyIntoArray(Object[] dst, int offset) {
       return asList().copyIntoArray(dst, offset);
     }

     @Override
     public ImmutableList<K> asList() {
       return list;
     }

     @Override
     public boolean contains(@NullableDecl Object object) {
       return map.get(object) != null;
     }

     @Override
     boolean isPartialView() {
       return true;
     }

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

   @SuppressWarnings("unchecked")
   @Override
   ImmutableCollection<V> createValues() {
     return (ImmutableList<V>) new KeysOrValuesAsList(alternatingKeysAndValues, 1, size);
   }

   @Override
   boolean isPartialView() {
     return false;
   }

   // This class is never actually serialized directly, but we have to make the
   // warning go away (and suppressing would suppress for all nested classes too)
   private static final long serialVersionUID = 0;
 }
	/*
	* Copyright (C) 2008 The Guava Authors
	*
	* 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 com.google.common.collect;

	import static com.google.common.base.Preconditions.checkElementIndex;
	import static com.google.common.base.Preconditions.checkPositionIndex;
	import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;

	import com.google.common.annotations.GwtCompatible;
	import com.google.common.annotations.VisibleForTesting;
	import java.util.AbstractMap;
	import java.util.Arrays;
	import java.util.Map.Entry;
	import org.checkerframework.checker.nullness.compatqual.NullableDecl;

	/**
	* A hash-based implementation of {@link ImmutableMap}.
	*
	* @author Louis Wasserman
	*/
	@GwtCompatible(serializable = true, emulated = true)
	final class RegularImmutableMap<K, V> extends ImmutableMap<K, V> {
	private static final int ABSENT = -1;

	@SuppressWarnings("unchecked")
	static final ImmutableMap<Object, Object> EMPTY =
	new RegularImmutableMap<>(null, new Object[0], 0);

	/*
	* This is an implementation of ImmutableMap optimized especially for Android, which does not like
	* objects per entry. Instead we use an open-addressed hash table. This design is basically
	* equivalent to RegularImmutableSet, save that instead of having a hash table containing the
	* elements directly and null for empty positions, we store indices of the keys in the hash table,
	* and ABSENT for empty positions. We then look up the keys in alternatingKeysAndValues.
	*
	* (The index actually stored is the index of the key in alternatingKeysAndValues, which is
	* double the index of the entry in entrySet.asList.)
	*
	* The basic data structure is described in https://en.wikipedia.org/wiki/Open_addressing.
	* The pointer to a key is stored in hashTable[Hashing.smear(key.hashCode())] % table.length,
	* save that if that location is already full, we try the next index, and the next, until we
	* find an empty table position. Since the table has a power-of-two size, we use
	* & (table.length - 1) instead of % table.length, though.
	*/

	private final transient int[] hashTable;
	@VisibleForTesting final transient Object[] alternatingKeysAndValues;
	private final transient int size;

	@SuppressWarnings("unchecked")
	static <K, V> RegularImmutableMap<K, V> create(int n, Object[] alternatingKeysAndValues) {
	if (n == 0) {
	return (RegularImmutableMap<K, V>) EMPTY;
	} else if (n == 1) {
	checkEntryNotNull(alternatingKeysAndValues[0], alternatingKeysAndValues[1]);
	return new RegularImmutableMap<K, V>(null, alternatingKeysAndValues, 1);
	}
	checkPositionIndex(n, alternatingKeysAndValues.length >> 1);
	int tableSize = ImmutableSet.chooseTableSize(n);
	int[] hashTable = createHashTable(alternatingKeysAndValues, n, tableSize, 0);
	return new RegularImmutableMap<K, V>(hashTable, alternatingKeysAndValues, n);
	}

	/**
	* Returns a hash table for the specified keys and values, and ensures that neither keys nor
	* values are null.
	*/
	static int[] createHashTable(
	Object[] alternatingKeysAndValues, int n, int tableSize, int keyOffset) {
	if (n == 1) {
	// for n=1 we don't create a hash table, but we need to do the checkEntryNotNull check!
	checkEntryNotNull(
	alternatingKeysAndValues[keyOffset], alternatingKeysAndValues[keyOffset ^ 1]);
	return null;
	}
	int mask = tableSize - 1;
	int[] hashTable = new int[tableSize];
	Arrays.fill(hashTable, ABSENT);
	for (int i = 0; i < n; i++) {
	Object key = alternatingKeysAndValues[2 * i + keyOffset];
	Object value = alternatingKeysAndValues[2 * i + (keyOffset ^ 1)];
	checkEntryNotNull(key, value);
	for (int h = Hashing.smear(key.hashCode()); ; h++) {
	h &= mask;
	int previous = hashTable[h];
	if (previous == ABSENT) {
	hashTable[h] = 2 * i + keyOffset;
	break;
	} else if (alternatingKeysAndValues[previous].equals(key)) {
	throw new IllegalArgumentException(
	"Multiple entries with same key: "
	+ key
	+ "="
	+ value
	+ " and "
	+ alternatingKeysAndValues[previous]
	+ "="
	+ alternatingKeysAndValues[previous ^ 1]);
	}
	}
	}
	return hashTable;
	}

	private RegularImmutableMap(int[] hashTable, Object[] alternatingKeysAndValues, int size) {
	this.hashTable = hashTable;
	this.alternatingKeysAndValues = alternatingKeysAndValues;
	this.size = size;
	}

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

	@SuppressWarnings("unchecked")
	@Override
	@NullableDecl
	public V get(@NullableDecl Object key) {
	return (V) get(hashTable, alternatingKeysAndValues, size, 0, key);
	}

	static Object get(
	@NullableDecl int[] hashTable,
	@NullableDecl Object[] alternatingKeysAndValues,
	int size,
	int keyOffset,
	@NullableDecl Object key) {
	if (key == null) {
	return null;
	} else if (size == 1) {
	return alternatingKeysAndValues[keyOffset].equals(key)
	? alternatingKeysAndValues[keyOffset ^ 1]
	: null;
	} else if (hashTable == null) {
	return null;
	}
	int mask = hashTable.length - 1;
	for (int h = Hashing.smear(key.hashCode()); ; h++) {
	h &= mask;
	int index = hashTable[h];
	if (index == ABSENT) {
	return null;
	} else if (alternatingKeysAndValues[index].equals(key)) {
	return alternatingKeysAndValues[index ^ 1];
	}
	}
	}

	@Override
	ImmutableSet<Entry<K, V>> createEntrySet() {
	return new EntrySet<>(this, alternatingKeysAndValues, 0, size);
	}

	static class EntrySet<K, V> extends ImmutableSet<Entry<K, V>> {
	private final transient ImmutableMap<K, V> map;
	private final transient Object[] alternatingKeysAndValues;
	private final transient int keyOffset;
	private final transient int size;

	EntrySet(ImmutableMap<K, V> map, Object[] alternatingKeysAndValues, int keyOffset, int size) {
	this.map = map;
	this.alternatingKeysAndValues = alternatingKeysAndValues;
	this.keyOffset = keyOffset;
	this.size = size;
	}

	@Override
	public UnmodifiableIterator<Entry<K, V>> iterator() {
	return asList().iterator();
	}

	@Override
	int copyIntoArray(Object[] dst, int offset) {
	return asList().copyIntoArray(dst, offset);
	}

	@Override
	ImmutableList<Entry<K, V>> createAsList() {
	return new ImmutableList<Entry<K, V>>() {
	@Override
	public Entry<K, V> get(int index) {
	checkElementIndex(index, size);
	@SuppressWarnings("unchecked")
	K key = (K) alternatingKeysAndValues[2 * index + keyOffset];
	@SuppressWarnings("unchecked")
	V value = (V) alternatingKeysAndValues[2 * index + (keyOffset ^ 1)];
	return new AbstractMap.SimpleImmutableEntry<K, V>(key, value);
	}

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

	@Override
	public boolean isPartialView() {
	return true;
	}
	};
	}

	@Override
	public boolean contains(Object object) {
	if (object instanceof Entry) {
	Entry<?, ?> entry = (Entry<?, ?>) object;
	Object k = entry.getKey();
	Object v = entry.getValue();
	return v != null && v.equals(map.get(k));
	}
	return false;
	}

	@Override
	boolean isPartialView() {
	return true;
	}

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

	@Override
	ImmutableSet<K> createKeySet() {
	@SuppressWarnings("unchecked")
	ImmutableList<K> keyList =
	(ImmutableList<K>) new KeysOrValuesAsList(alternatingKeysAndValues, 0, size);
	return new KeySet<K>(this, keyList);
	}

	static final class KeysOrValuesAsList extends ImmutableList<Object> {
	private final transient Object[] alternatingKeysAndValues;
	private final transient int offset;
	private final transient int size;

	KeysOrValuesAsList(Object[] alternatingKeysAndValues, int offset, int size) {
	this.alternatingKeysAndValues = alternatingKeysAndValues;
	this.offset = offset;
	this.size = size;
	}

	@Override
	public Object get(int index) {
	checkElementIndex(index, size);
	return alternatingKeysAndValues[2 * index + offset];
	}

	@Override
	boolean isPartialView() {
	return true;
	}

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

	static final class KeySet<K> extends ImmutableSet<K> {
	private final transient ImmutableMap<K, ?> map;
	private final transient ImmutableList<K> list;

	KeySet(ImmutableMap<K, ?> map, ImmutableList<K> list) {
	this.map = map;
	this.list = list;
	}

	@Override
	public UnmodifiableIterator<K> iterator() {
	return asList().iterator();
	}

	@Override
	int copyIntoArray(Object[] dst, int offset) {
	return asList().copyIntoArray(dst, offset);
	}

	@Override
	public ImmutableList<K> asList() {
	return list;
	}

	@Override
	public boolean contains(@NullableDecl Object object) {
	return map.get(object) != null;
	}

	@Override
	boolean isPartialView() {
	return true;
	}

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

	@SuppressWarnings("unchecked")
	@Override
	ImmutableCollection<V> createValues() {
	return (ImmutableList<V>) new KeysOrValuesAsList(alternatingKeysAndValues, 1, size);
	}

	@Override
	boolean isPartialView() {
	return false;
	}

	// This class is never actually serialized directly, but we have to make the
	// warning go away (and suppressing would suppress for all nested classes too)
	private static final long serialVersionUID = 0;
	}