ObjectIdSubclassMap: Use & rather than % for hashing

Bitwise and is faster than integer modulus operations, and since
the table size is always a power of 2, this is simple to use for
index operation.

Change-Id: I83d01e5c74fd9e910c633a98ea6f90b59092ba29
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

1 files changed, 13 insertions, 4 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectIdSubclassMap.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectIdSubclassMap.java
index aec0c07349..290b534454 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectIdSubclassMap.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectIdSubclassMap.java
@@ -63,19 +63,23 @@ import java.util.NoSuchElementException;
  *            type of subclass of ObjectId that will be stored in the map.
  */
 public class ObjectIdSubclassMap<V extends ObjectId> implements Iterable<V> {
+	private static final int INITIAL_TABLE_SIZE = 32;
+
 	private int size;
 
+	private int mask;
+
 	private V[] table;
 
 	/** Create an empty map. */
 	public ObjectIdSubclassMap() {
-		table = createArray(32);
+		initTable(INITIAL_TABLE_SIZE);
 	}
 
 	/** Remove all entries from this map. */
 	public void clear() {
 		size = 0;
-		table = createArray(32);
+		initTable(INITIAL_TABLE_SIZE);
 	}
 
 	/**
@@ -210,7 +214,7 @@ public class ObjectIdSubclassMap<V extends ObjectId> implements Iterable<V> {
 	}
 
 	private final int index(final AnyObjectId id) {
-		return (id.w1 >>> 1) % table.length;
+		return id.w1 & mask;
 	}
 
 	private void insert(final V newValue) {
@@ -226,7 +230,7 @@ public class ObjectIdSubclassMap<V extends ObjectId> implements Iterable<V> {
 		final V[] oldTable = table;
 		final int oldSize = table.length;
 
-		table = createArray(2 * oldSize);
+		initTable(oldSize << 1);
 		for (int i = 0; i < oldSize; i++) {
 			final V obj = oldTable[i];
 			if (obj != null)
@@ -234,6 +238,11 @@ public class ObjectIdSubclassMap<V extends ObjectId> implements Iterable<V> {
 		}
 	}
 
+	private void initTable(int sz) {
+		mask = sz - 1;
+		table = createArray(sz);
+	}
+
 	@SuppressWarnings("unchecked")
 	private final V[] createArray(final int sz) {
 		return (V[]) new ObjectId[sz];