Replace custom maps on primitive int types with fastutil implementation.
BUG=
Change-Id: I8bac83016521fc430e7dd81c9aa959db1c27c8a4
diff --git a/build.gradle b/build.gradle
index 8eb9643..c6b7c03 100644
--- a/build.gradle
+++ b/build.gradle
@@ -75,6 +75,7 @@
dependencies {
compile 'net.sf.jopt-simple:jopt-simple:4.6'
compile group: 'com.google.guava', name: 'guava', version: '19.0'
+ compile group: 'it.unimi.dsi', name: 'fastutil', version: '7.2.0'
compile group: 'org.apache.commons', name: 'commons-compress', version: '1.12'
compile group: 'org.ow2.asm', name: 'asm', version: '5.1'
compile group: 'org.ow2.asm', name: 'asm-commons', version: '5.1'
diff --git a/src/main/java/com/android/tools/r8/dex/DexFileReader.java b/src/main/java/com/android/tools/r8/dex/DexFileReader.java
index a38d397..627d106 100644
--- a/src/main/java/com/android/tools/r8/dex/DexFileReader.java
+++ b/src/main/java/com/android/tools/r8/dex/DexFileReader.java
@@ -50,8 +50,8 @@
import com.android.tools.r8.graph.DexValue.DexValueString;
import com.android.tools.r8.graph.OffsetToObjectMapping;
import com.android.tools.r8.logging.Log;
-import com.android.tools.r8.utils.IntHashMap;
-import com.android.tools.r8.utils.InternalResource;
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.nio.ShortBuffer;
@@ -91,10 +91,10 @@
private OffsetToObjectMapping indexedItems = new OffsetToObjectMapping();
// Mapping from offset to code item;
- private IntHashMap<DexCode> codes = new IntHashMap<>();
+ private Int2ObjectMap<DexCode> codes = new Int2ObjectOpenHashMap<>();
// Mapping from offset to dex item;
- private IntHashMap<Object> offsetMap = new IntHashMap<>();
+ private Int2ObjectMap<Object> offsetMap = new Int2ObjectOpenHashMap<>();
// Factory to canonicalize certain dexitems.
private final DexItemFactory dexItemFactory;
@@ -140,7 +140,9 @@
}
private DexTypeList typeListAt(int offset) {
- if (offset == 0) return DexTypeList.empty();
+ if (offset == 0) {
+ return DexTypeList.empty();
+ }
return (DexTypeList) cacheAt(offset, this::parseTypeList);
}
@@ -358,9 +360,13 @@
}
private <T> Object cacheAt(int offset, Supplier<T> function) {
- if (offset == 0) return null; // return null for offset zero.
+ if (offset == 0) {
+ return null; // return null for offset zero.
+ }
Object result = offsetMap.get(offset);
- if (result != null) return result; // return the cached result.
+ if (result != null) {
+ return result; // return the cached result.
+ }
// Cache is empty so parse the structure.
file.position(offset);
result = function.get();
@@ -812,7 +818,7 @@
private static void populateMethodHandles(DexFileReader reader) {
Segment segment = reader.lookupSegment(Constants.TYPE_METHOD_HANDLE_ITEM);
reader.indexedItems.initializeMethodHandles(segment.size);
- for (int i = 0; i < segment.size; i++){
+ for (int i = 0; i < segment.size; i++) {
reader.indexedItems.setMethodHandle(i, reader.methodHandleAt(i));
}
}
@@ -820,7 +826,7 @@
private static void populateCallSites(DexFileReader reader) {
Segment segment = reader.lookupSegment(Constants.TYPE_CALL_SITE_ID_ITEM);
reader.indexedItems.initializeCallSites(segment.size);
- for (int i = 0; i < segment.size; i++){
+ for (int i = 0; i < segment.size; i++) {
reader.indexedItems.setCallSites(i, reader.callSiteAt(i));
}
}
@@ -828,7 +834,7 @@
private static void populateTypes(DexFileReader reader) {
Segment segment = reader.lookupSegment(Constants.TYPE_TYPE_ID_ITEM);
reader.indexedItems.initializeTypes(segment.size);
- for (int i = 0; i < segment.size; i++){
+ for (int i = 0; i < segment.size; i++) {
reader.indexedItems.setType(i, reader.typeAt(i));
}
}
@@ -836,7 +842,7 @@
private static void populateFields(DexFileReader reader) {
Segment segment = reader.lookupSegment(Constants.TYPE_FIELD_ID_ITEM);
reader.indexedItems.initializeFields(segment.size);
- for (int i = 0; i < segment.size; i++){
+ for (int i = 0; i < segment.size; i++) {
reader.indexedItems.setField(i, reader.fieldAt(i));
}
}
@@ -844,7 +850,7 @@
private static void populateProtos(DexFileReader reader) {
Segment segment = reader.lookupSegment(Constants.TYPE_PROTO_ID_ITEM);
reader.indexedItems.initializeProtos(segment.size);
- for (int i = 0; i < segment.size; i++){
+ for (int i = 0; i < segment.size; i++) {
reader.indexedItems.setProto(i, reader.protoAt(i));
}
}
@@ -852,7 +858,7 @@
private static void populateMethods(DexFileReader reader) {
Segment segment = reader.lookupSegment(Constants.TYPE_METHOD_ID_ITEM);
reader.indexedItems.initializeMethods(segment.size);
- for (int i = 0; i < segment.size; i++){
+ for (int i = 0; i < segment.size; i++) {
reader.indexedItems.setMethod(i, reader.methodAt(i));
}
}
diff --git a/src/main/java/com/android/tools/r8/optimize/DebugStripper.java b/src/main/java/com/android/tools/r8/optimize/DebugStripper.java
index d045f76..998bc8d 100644
--- a/src/main/java/com/android/tools/r8/optimize/DebugStripper.java
+++ b/src/main/java/com/android/tools/r8/optimize/DebugStripper.java
@@ -17,9 +17,10 @@
import com.android.tools.r8.naming.MemberNaming;
import com.android.tools.r8.naming.MemberNaming.Range;
import com.android.tools.r8.naming.MemberNaming.Signature;
-import com.android.tools.r8.utils.HashMapInt;
import com.android.tools.r8.utils.InternalOptions;
import com.google.common.collect.ImmutableMap;
+import it.unimi.dsi.fastutil.objects.Reference2IntMap;
+import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
import java.util.List;
public class DebugStripper {
@@ -50,6 +51,7 @@
}
private static class NumberedDebugInfo {
+
final int numberOfEntries;
final DexDebugInfo info;
@@ -103,7 +105,7 @@
}
private void processCode(DexEncodedMethod encodedMethod, MemberNaming naming,
- HashMapInt<DexString> nameCounts) {
+ Reference2IntMap<DexString> nameCounts) {
if (encodedMethod.getCode() == null) {
return;
}
@@ -118,7 +120,7 @@
if (options.skipDebugLineNumberOpt) {
startLine = originalInfo.startLine;
} else {
- int nameCount = nameCounts.get(name);
+ int nameCount = nameCounts.getInt(name);
if (nameCount == USED_ONCE) {
isUsedOnce = true;
startLine = 0;
@@ -132,7 +134,7 @@
DexDebugInfo newInfo = numberedInfo.info;
if (!options.skipDebugLineNumberOpt) {
// Fix up the line information.
- int previousCount = nameCounts.get(name);
+ int previousCount = nameCounts.getInt(name);
nameCounts.put(name, previousCount + numberedInfo.numberOfEntries);
// If we don't actually need line information and there are no debug entries, throw it away.
if (newInfo != null && isUsedOnce && newInfo.events.length == 0) {
@@ -147,7 +149,7 @@
}
private void processMethod(DexEncodedMethod method, ClassNaming classNaming,
- HashMapInt<DexString> nameCounts) {
+ Reference2IntMap<DexString> nameCounts) {
MemberNaming naming = null;
if (classNaming != null) {
Signature renamedSignature = classNameMapper.getRenamedMethodSignature(method.method);
@@ -157,7 +159,7 @@
}
private void processMethods(DexEncodedMethod[] methods, ClassNaming naming,
- HashMapInt<DexString> nameCounts) {
+ Reference2IntMap<DexString> nameCounts) {
if (methods == null) {
return;
}
@@ -172,14 +174,14 @@
}
String name = descriptorToName(clazz.type.toDescriptorString());
ClassNaming naming = classNameMapper == null ? null : classNameMapper.getClassNaming(name);
- HashMapInt<DexString> nameCounts = new HashMapInt<>();
+ Reference2IntMap<DexString> nameCounts = new Reference2IntOpenHashMap<>();
setIntialNameCounts(nameCounts, clazz.directMethods());
setIntialNameCounts(nameCounts, clazz.virtualMethods());
processMethods(clazz.directMethods(), naming, nameCounts);
processMethods(clazz.virtualMethods(), naming, nameCounts);
}
- private void setIntialNameCounts(HashMapInt<DexString> nameCounts,
+ private void setIntialNameCounts(Reference2IntMap<DexString> nameCounts,
DexEncodedMethod[] methods) {
for (DexEncodedMethod method : methods) {
if (nameCounts.containsKey(method.method.name)) {
diff --git a/src/main/java/com/android/tools/r8/shaking/SimpleClassMerger.java b/src/main/java/com/android/tools/r8/shaking/SimpleClassMerger.java
index bc43ae8..a2864e4 100644
--- a/src/main/java/com/android/tools/r8/shaking/SimpleClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/SimpleClassMerger.java
@@ -23,9 +23,6 @@
import com.android.tools.r8.optimize.InvokeSingleTargetExtractor;
import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
import com.android.tools.r8.utils.FieldSignatureEquivalence;
-import com.android.tools.r8.utils.HashMapInt;
-import com.android.tools.r8.utils.IdentityHashMapInt;
-import com.android.tools.r8.utils.IntIntHashMap;
import com.android.tools.r8.utils.MethodSignatureEquivalence;
import com.android.tools.r8.utils.Timing;
import com.google.common.base.Equivalence;
@@ -33,6 +30,10 @@
import com.google.common.collect.Iterables;
import com.google.common.collect.Iterators;
import com.google.common.collect.Sets;
+import it.unimi.dsi.fastutil.ints.Int2IntMap;
+import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;
+import it.unimi.dsi.fastutil.objects.Reference2IntMap;
+import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
@@ -274,7 +275,7 @@
}
private <T> Set<T> mergeArrays(T[] one, T[] other) {
- Set<T> merged = new LinkedHashSet<T>();
+ Set<T> merged = new LinkedHashSet<>();
Collections.addAll(merged, one);
Collections.addAll(merged, other);
return merged;
@@ -513,22 +514,26 @@
private static class CollisionDetector {
+ private static int NOT_FOUND = 1 << (Integer.SIZE - 1);
+
// TODO(herhut): Maybe cache seenPositions for target classes.
- private final Map<DexString, IntIntHashMap> seenPositions = new IdentityHashMap<>();
- private final HashMapInt<DexProto> targetProtoCache;
- private final HashMapInt<DexProto> sourceProtoCache;
+ private final Map<DexString, Int2IntMap> seenPositions = new IdentityHashMap<>();
+ private final Reference2IntMap<DexProto> targetProtoCache;
+ private final Reference2IntMap<DexProto> sourceProtoCache;
private final DexType source, target;
- private final Set<DexMethod> invokes;
+ private final Collection<DexMethod> invokes;
private final Map<DexType, DexType> substituions;
- private CollisionDetector(DexType source, DexType target, Set<DexMethod> invokes,
+ private CollisionDetector(DexType source, DexType target, Collection<DexMethod> invokes,
Map<DexType, DexType> substitutions) {
this.source = source;
this.target = target;
this.invokes = invokes;
this.substituions = substitutions;
- this.targetProtoCache = new IdentityHashMapInt<>(invokes.size() / 2);
- this.sourceProtoCache = new IdentityHashMapInt<>(invokes.size() / 2);
+ this.targetProtoCache = new Reference2IntOpenHashMap<>(invokes.size() / 2);
+ this.targetProtoCache.defaultReturnValue(NOT_FOUND);
+ this.sourceProtoCache = new Reference2IntOpenHashMap<>(invokes.size() / 2);
+ this.sourceProtoCache.defaultReturnValue(NOT_FOUND);
}
boolean mayCollide() {
@@ -538,11 +543,11 @@
return false;
}
for (DexMethod method : invokes) {
- IntIntHashMap positionsMap = seenPositions.get(method.name);
+ Int2IntMap positionsMap = seenPositions.get(method.name);
if (positionsMap != null) {
int arity = method.proto.parameters.values.length;
- if (positionsMap.containsKey(arity)) {
- int previous = positionsMap.get(arity);
+ int previous = positionsMap.get(arity);
+ if (previous != NOT_FOUND) {
assert previous != 0;
int positions = computePositionsFor(method.proto, source, sourceProtoCache,
substituions);
@@ -561,55 +566,58 @@
int arity = parameters.length;
int positions = computePositionsFor(method.proto, target, targetProtoCache, substituions);
if (positions != 0) {
- IntIntHashMap positionsMap =
- seenPositions.computeIfAbsent(method.name, k -> new IntIntHashMap());
+ Int2IntMap positionsMap =
+ seenPositions.computeIfAbsent(method.name, k -> {
+ Int2IntMap result = new Int2IntOpenHashMap();
+ result.defaultReturnValue(NOT_FOUND);
+ return result;
+ });
int value = 0;
- if (positionsMap.containsKey(arity)) {
- value = positionsMap.get(arity);
+ int previous = positionsMap.get(arity);
+ if (previous != NOT_FOUND) {
+ value = previous;
}
value |= positions;
positionsMap.put(arity, value);
}
}
- int filled = 0;
- for (IntIntHashMap pos : seenPositions.values()) {
- filled += pos.size();
- }
+
}
private int computePositionsFor(DexProto proto, DexType type,
- HashMapInt<DexProto> cache, Map<DexType, DexType> substituions) {
- if (cache.containsKey(proto)) {
- return cache.get(proto);
+ Reference2IntMap<DexProto> cache, Map<DexType, DexType> substitutions) {
+ int result = cache.getInt(proto);
+ if (result != NOT_FOUND) {
+ return result;
}
- int result = 0;
- int bits = 0;
+ result = 0;
+ int bitsUsed = 0;
int accumulator = 0;
for (DexType aType : proto.parameters.values) {
- if (substituions != null) {
+ if (substitutions != null) {
// Substitute the type with the already merged class to estimate what it will
// look like.
- while (substituions.containsKey(aType)) {
- aType = substituions.get(aType);
+ while (substitutions.containsKey(aType)) {
+ aType = substitutions.get(aType);
}
}
accumulator <<= 1;
- bits++;
+ bitsUsed++;
if (aType == type) {
accumulator |= 1;
}
- // Handle overflow on 32 bit boundary.
- if (bits == Integer.SIZE) {
+ // Handle overflow on 31 bit boundary.
+ if (bitsUsed == Integer.SIZE - 1) {
result |= accumulator;
accumulator = 0;
- bits = 0;
+ bitsUsed = 0;
}
}
// We also take the return type into account for potential conflicts.
DexType returnType = proto.returnType;
- if (substituions != null) {
- while (substituions.containsKey(returnType)) {
- returnType = substituions.get(returnType);
+ if (substitutions != null) {
+ while (substitutions.containsKey(returnType)) {
+ returnType = substitutions.get(returnType);
}
}
accumulator <<= 1;
diff --git a/src/main/java/com/android/tools/r8/utils/HashMapInt.java b/src/main/java/com/android/tools/r8/utils/HashMapInt.java
deleted file mode 100644
index 7e91644..0000000
--- a/src/main/java/com/android/tools/r8/utils/HashMapInt.java
+++ /dev/null
@@ -1,120 +0,0 @@
-// Copyright (c) 2016, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-package com.android.tools.r8.utils;
-
-// Hash map based on open addressing where keys are Objects and values are basic ints.
-// Provides: put, get, and size.
-
-import java.util.Arrays;
-import java.util.Iterator;
-import java.util.Objects;
-
-public class HashMapInt<T> extends SimpleHashMap {
-
- private Object[] keys;
- private int[] values;
-
- public HashMapInt() {
- super();
- }
-
- public HashMapInt(int initialCapacity) {
- super(initialCapacity);
- }
-
- public HashMapInt(int initialCapacity, double loadFactor) {
- super(initialCapacity, loadFactor);
- }
-
- public void put(final T key, final int value) {
- if (key == null) {
- throw new RuntimeException("HashMapInt does not support null as key.");
- }
- ensureCapacity();
- basePut(key, value);
- }
-
- boolean equals(Object one, Object other) {
- return one.equals(other);
- }
-
- public int get(final T key) {
- if (key == null) {
- throw new RuntimeException("HashMapInt does not support null as key.");
- }
- int count = 1;
- int index = firstProbe(key);
- while (!equals(key, keys[index])) {
- if (keys[index] == null) {
- throw new RuntimeException("HashMapInt get only works if key is present.");
- }
- index = nextProbe(index, count++);
- }
- return values[index];
- }
-
- int firstProbe(T key) {
- return firstProbe(key.hashCode());
- }
-
- public boolean containsKey(final T key) {
- if (key == null) {
- throw new RuntimeException("HashMapInt does not support null as key.");
- }
- int count = 1;
- for (int index = firstProbe(key); ; index = nextProbe(index, count++)) {
- Object k = keys[index];
- if (k == null) {
- return false;
- }
- if (equals(k, key)) {
- return true;
- }
- }
- }
-
- private void basePut(final T key, final int value) {
- int count = 1;
- int index = firstProbe(key);
- while ((keys[index] != null) && (keys[index] != key)) {
- index = nextProbe(index, count++);
- }
- if (keys[index] == null) {
- keys[index] = key;
- incrementSize();
- }
- values[index] = value;
- }
-
- @SuppressWarnings("unchecked")
- public Iterable<Integer> values() {
- return () -> Arrays.stream(keys).filter(Objects::nonNull).map((key) -> get((T) key)).iterator();
- }
-
- @SuppressWarnings("unchecked")
- public Iterable<T> keys() {
- return () -> (Iterator<T>) Arrays.stream(keys).filter(Objects::nonNull).iterator();
- }
-
- @SuppressWarnings("unchecked")
- void resize() {
- final Object[] oldKeys = keys;
- final int[] oldValues = values;
- final int oldLength = length();
- super.resize();
- // Repopulate.
- for (int index = 0; index < oldLength; index++) {
- T key = (T) oldKeys[index];
- if (key != null) {
- basePut(key, oldValues[index]);
- }
- }
- }
-
- void initialize(final int length, final int limit) {
- super.initialize(length, limit);
- keys = new Object[length];
- values = new int[length];
- }
-}
diff --git a/src/main/java/com/android/tools/r8/utils/IdentityHashMapInt.java b/src/main/java/com/android/tools/r8/utils/IdentityHashMapInt.java
deleted file mode 100644
index 66e62ac..0000000
--- a/src/main/java/com/android/tools/r8/utils/IdentityHashMapInt.java
+++ /dev/null
@@ -1,29 +0,0 @@
-// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-package com.android.tools.r8.utils;
-
-public class IdentityHashMapInt<T> extends HashMapInt<T> {
-
- public IdentityHashMapInt() {
- super();
- }
-
- public IdentityHashMapInt(int initialCapacity) {
- super(initialCapacity);
- }
-
- public IdentityHashMapInt(int initialCapacity, double loadFactor) {
- super(initialCapacity, loadFactor);
- }
-
- @Override
- int firstProbe(T key) {
- return firstProbe(System.identityHashCode(key));
- }
-
- @Override
- boolean equals(Object one, Object other) {
- return one == other;
- }
-}
diff --git a/src/main/java/com/android/tools/r8/utils/IntHashMap.java b/src/main/java/com/android/tools/r8/utils/IntHashMap.java
deleted file mode 100644
index 6a92316..0000000
--- a/src/main/java/com/android/tools/r8/utils/IntHashMap.java
+++ /dev/null
@@ -1,113 +0,0 @@
-// Copyright (c) 2016, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-package com.android.tools.r8.utils;
-
-// Hash map based on open addressing where keys are basic ints and values are Objects.
-// Provides: put, get, and size.
-
-import java.util.Arrays;
-import java.util.Iterator;
-import java.util.Objects;
-import java.util.stream.IntStream;
-
-public class IntHashMap<T> extends SimpleHashMap {
-
- private int[] keys;
- private Object[] values;
-
- public IntHashMap() {
- super();
- }
-
- public IntHashMap(int initialCapacity) {
- super(initialCapacity);
- }
-
- public IntHashMap(int initialCapacity, double loadFactor) {
- super(initialCapacity, loadFactor);
- }
-
- public void put(final int key, final T value) {
- if (value == null) {
- throw new RuntimeException("IntHashMap does not support null as value.");
- }
- ensureCapacity();
- basePut(key, value);
- }
-
- public T get(final int key) {
- int count = 1;
- int index = firstProbe(computeHash(key));
- // Note that unused entries in keys is 0.
- // That means we only need to check for value != null when key == 0.
- while ((keys[index] != key) && (values[index] != null)) {
- index = nextProbe(index, count++);
- }
- assert (keys[index] == key) || (values[index] == null);
- @SuppressWarnings("unchecked")
- T result = (T) values[index];
- return result;
- }
-
- private void basePut(final int key, final Object value) {
- assert value != null;
- int count = 1;
- int index = firstProbe(computeHash(key));
- while ((values[index] != null) && (keys[index] != key)) {
- index = nextProbe(index, count++);
- }
- if (values[index] == null) {
- keys[index] = key;
- incrementSize();
- }
- values[index] = value;
- assert value.equals(get(key));
- }
-
- void resize() {
- final int[] oldKeys = keys;
- final Object[] oldValues = values;
- final int oldLength = length();
- super.resize();
- // Repopulate.
- for (int index = 0; index < oldLength; index++) {
- Object value = oldValues[index];
- if (value != null) {
- basePut(oldKeys[index], value);
- }
- }
- }
-
- void initialize(final int length, final int limit) {
- super.initialize(length, limit);
- keys = new int[length];
- values = new Object[length];
- }
-
- @SuppressWarnings("unchecked")
- public Iterable<T> values() {
- return () -> (Iterator<T>) Arrays.stream(values).filter(Objects::nonNull).iterator();
- }
-
- public Iterable<Integer> keys() {
- if (get(0) != null) {
- return () -> IntStream.concat(IntStream.of(0), Arrays.stream(keys).filter(i -> i != 0))
- .iterator();
- }
- return () -> Arrays.stream(keys).filter(i -> i != 0 || get(i) != null).distinct().iterator();
- }
-
- // Thomas Wang, Integer Hash Functions.
- // http://www.concentric.net/~Ttwang/tech/inthash.htm
- private static int computeHash(final int key) {
- int hash = key;
- hash = ~hash + (hash << 15); // hash = (hash << 15) - hash - 1;
- hash = hash ^ (hash >> 12);
- hash = hash + (hash << 2);
- hash = hash ^ (hash >> 4);
- hash = hash * 2057; // hash = (hash + (hash << 3)) + (hash << 11);
- hash = hash ^ (hash >> 16);
- return hash & 0x3fffffff;
- }
-}
diff --git a/src/main/java/com/android/tools/r8/utils/IntIntHashMap.java b/src/main/java/com/android/tools/r8/utils/IntIntHashMap.java
deleted file mode 100644
index 03d4911..0000000
--- a/src/main/java/com/android/tools/r8/utils/IntIntHashMap.java
+++ /dev/null
@@ -1,113 +0,0 @@
-// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-package com.android.tools.r8.utils;
-
-// Hash map based on open addressing where keys are positive basic ints and values are basic ints.
-// Provides: put, get, and size.
-
-import java.util.Arrays;
-
-public class IntIntHashMap extends SimpleHashMap {
-
- private final int EMPTY_KEY = -1;
-
- private int[] keys;
- private int[] values;
-
- public IntIntHashMap() {
- super();
- }
-
- public IntIntHashMap(int initialCapacity) {
- super(initialCapacity);
- }
-
- public IntIntHashMap(int initialCapacity, double loadFactor) {
- super(initialCapacity, loadFactor);
- }
-
- public void put(final int key, final int value) {
- if (key < 0) {
- throw new RuntimeException("IntIntHashMap does not support negative ints as key.");
- }
- ensureCapacity();
- basePut(key, value);
- }
-
- public int get(final int key) {
- if (key < 0) {
- throw new RuntimeException("IntIntHashMap does not support negative ints as key.");
- }
- int count = 1;
- int index = firstProbe(key);
- while (key != keys[index]) {
- if (keys[index] == EMPTY_KEY) {
- throw new RuntimeException("IntIntHashMap get only works if key is present.");
- }
- index = nextProbe(index, count++);
- }
- return values[index];
- }
-
- public boolean containsKey(final int key) {
- if (key < 0) {
- throw new RuntimeException("IntIntHashMap does not support negative ints as key.");
- }
- int count = 1;
- for (int index = firstProbe(key); ; index = nextProbe(index, count++)) {
- int k = keys[index];
- if (k == EMPTY_KEY) {
- return false;
- }
- if (k == key) {
- return true;
- }
- }
- }
-
- private void basePut(final int key, final int value) {
- int count = 1;
- int index = firstProbe(key);
- while ((keys[index] != EMPTY_KEY) && (keys[index] != key)) {
- index = nextProbe(index, count++);
- }
- if (keys[index] != key) {
- incrementSize();
- keys[index] = key;
- }
- values[index] = value;
- }
-
- void resize() {
- final int[] oldKeys = keys;
- final int[] oldValues = values;
- final int oldLength = length();
- super.resize();
- // Repopulate.
- for (int index = 0; index < oldLength; index++) {
- int key = oldKeys[index];
- if (key != EMPTY_KEY) {
- basePut(key, oldValues[index]);
- }
- }
- }
-
- void initialize(final int length, final int limit) {
- super.initialize(length, limit);
- keys = new int[length];
- Arrays.fill(keys, EMPTY_KEY);
- values = new int[length];
- }
-
-
- @SuppressWarnings("unchecked")
- public Iterable<Integer> values() {
- return () -> Arrays.stream(keys).filter(k -> k > EMPTY_KEY).map(this::get).iterator();
- }
-
- @SuppressWarnings("unchecked")
- public Iterable<Integer> keys() {
- return () -> Arrays.stream(keys).filter(k -> k > EMPTY_KEY).iterator();
- }
-}
diff --git a/src/test/java/com/android/tools/r8/utils/HashMapIntTest.java b/src/test/java/com/android/tools/r8/utils/HashMapIntTest.java
deleted file mode 100644
index 5d8fffe..0000000
--- a/src/test/java/com/android/tools/r8/utils/HashMapIntTest.java
+++ /dev/null
@@ -1,81 +0,0 @@
-// Copyright (c) 2016, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-package com.android.tools.r8.utils;
-
-import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Iterables;
-import java.util.Random;
-import java.util.Set;
-import org.junit.Assert;
-import org.junit.Test;
-
-public class HashMapIntTest {
-
- static private String getString(int i) {
- String SALTCHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
- StringBuilder salt = new StringBuilder();
- Random rnd = new Random();
- while (salt.length() < 18) {
- int index = (int) (rnd.nextFloat() * SALTCHARS.length());
- salt.append(SALTCHARS.charAt(index));
- }
- salt.append(" ");
- salt.append(i);
- return salt.toString();
- }
-
- @Test(expected = RuntimeException.class)
- public void putInvalid() throws Exception {
- HashMapInt<Object> map = new HashMapInt<>();
- map.put(null, 12);
- }
-
- @Test
- public void put() throws Exception {
- HashMapInt<Object> map = new HashMapInt<>();
- Object key = new Object();
- int value = 0;
- map.put(key, value);
- Assert.assertTrue(map.containsKey(key));
- Assert.assertFalse(map.containsKey(new Object[0]));
- Assert.assertEquals(map.get(key), value);
- Assert.assertEquals(map.size(), 1);
- }
-
- @Test
- public void random() throws Exception {
- final int length = 5999;
- HashMapInt<String> map = new HashMapInt<>();
- String[] array = new String[length];
- for (int i = 0; i < length; i++) {
- array[i] = getString(i);
- map.put(array[i], i * 3);
- }
- Assert.assertEquals(length, map.size());
- for (int i = 0; i < length; i++) {
- Assert.assertEquals(map.get(array[i]), i * 3);
- }
- for (int i : map.values()) {
- Assert.assertTrue(i < length * 3 && i >= 0 && i % 3 == 0);
- }
- Assert.assertEquals(length, Iterables.size(map.values()));
- Set<String> items = ImmutableSet.copyOf(array);
- for (String s : map.keys()) {
- Assert.assertTrue(items.contains(s));
- }
- Assert.assertEquals(length, Iterables.size(map.keys()));
- }
-
- @Test
- public void overwrite() throws Exception {
- HashMapInt<Object> map = new HashMapInt<>();
- Object key = new Object();
- int value1 = 0;
- map.put(key, value1);
- Assert.assertEquals(map.get(key), value1);
- int value2 = -1;
- map.put(key, value2);
- Assert.assertEquals(map.get(key), value2);
- }
-}
diff --git a/src/test/java/com/android/tools/r8/utils/IdentityHashMapIntTest.java b/src/test/java/com/android/tools/r8/utils/IdentityHashMapIntTest.java
deleted file mode 100644
index dd57960..0000000
--- a/src/test/java/com/android/tools/r8/utils/IdentityHashMapIntTest.java
+++ /dev/null
@@ -1,78 +0,0 @@
-// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-package com.android.tools.r8.utils;
-
-import com.google.common.collect.Iterables;
-import com.google.common.collect.Sets;
-import java.util.Collections;
-import java.util.Set;
-import org.junit.Assert;
-import org.junit.Test;
-
-public class IdentityHashMapIntTest {
-
- @Test(expected = RuntimeException.class)
- public void putInvalid() throws Exception {
- IdentityHashMapInt<Object> map = new IdentityHashMapInt<>();
- map.put(null, 12);
- }
-
- @Test
- public void put() throws Exception {
- IdentityHashMapInt<Object> map = new IdentityHashMapInt<>();
- Object key = new AllEqual();
- int value = 0;
- map.put(key, value);
- Assert.assertTrue(map.containsKey(key));
- Assert.assertFalse(map.containsKey(new Object()));
- Assert.assertFalse(map.containsKey(new AllEqual()));
- Assert.assertEquals(map.get(key), value);
- Assert.assertEquals(map.size(), 1);
- }
-
- @Test
- public void random() throws Exception {
- final int length = 5999;
- IdentityHashMapInt<Object> map = new IdentityHashMapInt<>();
- AllEqual[] array = new AllEqual[length];
- for (int i = 0; i < length; i++) {
- array[i] = new AllEqual();
- map.put(array[i], i * 3);
- }
- Assert.assertEquals(length, map.size());
- for (int i = 0; i < length; i++) {
- Assert.assertEquals(map.get(array[i]), i * 3);
- }
- for (int i : map.values()) {
- Assert.assertTrue(i < length * 3 && i >= 0 && i % 3 == 0);
- }
- Assert.assertEquals(length, Iterables.size(map.values()));
- Set<Object> items = Sets.newIdentityHashSet();
- Collections.addAll(items, array);
- for (Object o : map.keys()) {
- Assert.assertTrue(items.contains(o));
- }
- Assert.assertEquals(length, Iterables.size(map.keys()));
- }
-
- @Test
- public void overwrite() throws Exception {
- IdentityHashMapInt<Object> map = new IdentityHashMapInt<>();
- Object key = new Object();
- int value1 = 0;
- map.put(key, value1);
- Assert.assertEquals(map.get(key), value1);
- int value2 = -1;
- map.put(key, value2);
- Assert.assertEquals(map.get(key), value2);
- }
-
- private static class AllEqual {
-
- @Override
- public boolean equals(Object o) {
- return true;
- }
- }
-}
diff --git a/src/test/java/com/android/tools/r8/utils/IntHashMapTest.java b/src/test/java/com/android/tools/r8/utils/IntHashMapTest.java
deleted file mode 100644
index c4b4dc2..0000000
--- a/src/test/java/com/android/tools/r8/utils/IntHashMapTest.java
+++ /dev/null
@@ -1,83 +0,0 @@
-// Copyright (c) 2016, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-package com.android.tools.r8.utils;
-
-import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Iterables;
-import java.util.Random;
-import java.util.Set;
-import org.junit.Assert;
-import org.junit.Test;
-
-public class IntHashMapTest {
-
- static private String getRandomString() {
- String SALTCHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
- StringBuilder salt = new StringBuilder();
- Random rnd = new Random();
- while (salt.length() < 18) {
- int index = (int) (rnd.nextFloat() * SALTCHARS.length());
- salt.append(SALTCHARS.charAt(index));
- }
- return salt.toString();
- }
-
- @Test(expected = RuntimeException.class)
- public void putInvalid() throws Exception {
- IntHashMap<Object> map = new IntHashMap<>();
- map.put(12, null);
- }
-
- @Test
- public void put() throws Exception {
- IntHashMap<Object> map = new IntHashMap<>();
- int key = 1;
- Object value = new Object();
- map.put(key, value);
- Assert.assertEquals(map.get(key), value);
- Assert.assertEquals(map.size(), 1);
- map.put(key + 1, value);
- Assert.assertEquals(map.get(key + 1), value);
- Assert.assertEquals(map.size(), 2);
- Assert.assertEquals(map.get(0), null);
- map.put(0, value);
- Assert.assertEquals(map.get(0), value);
- }
-
- @Test
- public void random() throws Exception {
- final int length = 5999;
- IntHashMap<String> map = new IntHashMap<>();
- String[] array = new String[length];
- for (int i = 0; i < length; i++) {
- array[i] = getRandomString();
- map.put(i, array[i]);
- }
- Assert.assertEquals(length, map.size());
- for (int i = 0; i < length; i++) {
- Assert.assertEquals(map.get(i), array[i]);
- }
- Set<String> items = ImmutableSet.copyOf(array);
- for (String s : map.values()) {
- Assert.assertTrue(items.contains(s));
- }
- Assert.assertEquals(length, Iterables.size(map.values()));
- for (int i : map.keys()) {
- Assert.assertTrue(i < length && i >= 0);
- }
- Assert.assertEquals(length, Iterables.size(map.keys()));
- }
-
- @Test
- public void overwrite() throws Exception {
- IntHashMap<Object> map = new IntHashMap<>();
- int key = 1;
- Object value1 = new Object();
- map.put(key, value1);
- Assert.assertEquals(map.get(key), value1);
- Object value2 = new Object[0];
- map.put(key, value2);
- Assert.assertEquals(map.get(key), value2);
- }
-}
diff --git a/src/test/java/com/android/tools/r8/utils/IntIntHashMapTest.java b/src/test/java/com/android/tools/r8/utils/IntIntHashMapTest.java
deleted file mode 100644
index d129a03..0000000
--- a/src/test/java/com/android/tools/r8/utils/IntIntHashMapTest.java
+++ /dev/null
@@ -1,75 +0,0 @@
-// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-package com.android.tools.r8.utils;
-
-import com.google.common.collect.Iterables;
-import java.util.Iterator;
-import java.util.LinkedHashSet;
-import java.util.Random;
-import java.util.Set;
-import org.junit.Assert;
-import org.junit.Test;
-
-public class IntIntHashMapTest {
-
- @Test(expected = RuntimeException.class)
- public void putInvalid() throws Exception {
- IntIntHashMap map = new IntIntHashMap();
- map.put(-1, 12);
- }
-
- @Test
- public void put() throws Exception {
- IntIntHashMap map = new IntIntHashMap();
- int key = 22;
- int value = 0;
- map.put(key, value);
- Assert.assertTrue(map.containsKey(key));
- Assert.assertFalse(map.containsKey(33));
- Assert.assertEquals(map.get(key), value);
- Assert.assertEquals(map.size(), 1);
- }
-
- @Test
- public void random() throws Exception {
- final int length = 5999;
- IntIntHashMap map = new IntIntHashMap();
- Random rnd = new Random();
- Set<Integer> seen = new LinkedHashSet<>();
- String[] array = new String[length];
- for (int i = 0; i < length; i++) {
- int next;
- do {
- next = rnd.nextInt(4 * length);
- } while (seen.contains(next));
- seen.add(next);
- map.put(next, i * 3);
- }
- Assert.assertEquals(seen.size(), map.size());
- Iterator<Integer> it = seen.iterator();
- for (int i = 0; i < length; i++) {
- Assert.assertEquals(map.get(it.next()), i * 3);
- }
- for (int i : map.values()) {
- Assert.assertTrue(i < length * 3 && i >= 0 && i % 3 == 0);
- }
- Assert.assertEquals(length, Iterables.size(map.values()));
- for (Integer key : map.keys()) {
- Assert.assertTrue(seen.contains(key));
- }
- Assert.assertEquals(seen.size(), Iterables.size(map.keys()));
- }
-
- @Test
- public void overwrite() throws Exception {
- IntIntHashMap map = new IntIntHashMap();
- int key = 42;
- int value1 = 0;
- map.put(key, value1);
- Assert.assertEquals(map.get(key), value1);
- int value2 = -1;
- map.put(key, value2);
- Assert.assertEquals(map.get(key), value2);
- }
-}
