org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectIdOwnerMap.java - jgit - Git at Google

 /*
  * Copyright (C) 2011, Google Inc. and others
  *
  * This program and the accompanying materials are made available under the
  * terms of the Eclipse Distribution License v. 1.0 which is available at
  * https://www.eclipse.org/org/documents/edl-v10.php.
  *
  * SPDX-License-Identifier: BSD-3-Clause
  */

 package org.eclipse.jgit.lib;

 import java.util.Arrays;
 import java.util.Iterator;
 import java.util.NoSuchElementException;

 /**
  * Fast, efficient map for {@link org.eclipse.jgit.lib.ObjectId} subclasses in
  * only one map.
  * <p>
  * To use this map type, applications must have their entry value type extend
  * from {@link org.eclipse.jgit.lib.ObjectIdOwnerMap.Entry}, which itself
  * extends from ObjectId.
  * <p>
  * Object instances may only be stored in <b>ONE</b> ObjectIdOwnerMap. This
  * restriction exists because the map stores internal map state within each
  * object instance. If an instance is be placed in another ObjectIdOwnerMap it
  * could corrupt one or both map's internal state.
  * <p>
  * If an object instance must be in more than one map, applications may use
  * ObjectIdOwnerMap for one of the maps, and
  * {@link org.eclipse.jgit.lib.ObjectIdSubclassMap} for the other map(s). It is
  * encouraged to use ObjectIdOwnerMap for the map that is accessed most often,
  * as this implementation runs faster than the more general ObjectIdSubclassMap
  * implementation.
  *
  * @param <V>
  *            type of subclass of ObjectId that will be stored in the map.
  */
 public class ObjectIdOwnerMap<V extends ObjectIdOwnerMap.Entry>
 		implements Iterable<V>, ObjectIdSet {
 	/** Size of the initial directory, will grow as necessary. */
 	private static final int INITIAL_DIRECTORY = 1024;

 	/** Number of bits in a segment's index. Segments are 2^11 in size. */
 	private static final int SEGMENT_BITS = 11;

 	private static final int SEGMENT_SHIFT = 32 - SEGMENT_BITS;

 	/**
 	 * Top level directory of the segments.
 	 * <p>
 	 * The low {@link #bits} of the SHA-1 are used to select the segment from
 	 * this directory. Each segment is constant sized at 2^SEGMENT_BITS.
 	 */
 	V[][] directory;

 	/** Total number of objects in this map. */
 	int size;

 	/** The map doubles in capacity when {@link #size} reaches this target. */
 	private int grow;

 	/** Number of low bits used to form the index into {@link #directory}. */
 	int bits;

 	/** Low bit mask to index into {@link #directory}, {@code 2^bits-1}. */
 	private int mask;

 	/**
 	 * Create an empty map.
 	 */
 	@SuppressWarnings("unchecked")
 	public ObjectIdOwnerMap() {
 		bits = 0;
 		mask = 0;
 		grow = computeGrowAt(bits);

 		directory = (V[][]) new Entry[INITIAL_DIRECTORY][];
 		directory[0] = newSegment();
 	}

 	/**
 	 * Remove all entries from this map.
 	 */
 	public void clear() {
 		size = 0;

 		for (V[] tbl : directory) {
 			if (tbl == null)
 				break;
 			Arrays.fill(tbl, null);
 		}
 	}

 	/**
 	 * Lookup an existing mapping.
 	 *
 	 * @param toFind
 	 *            the object identifier to find.
 	 * @return the instance mapped to toFind, or null if no mapping exists.
 	 */
 	@SuppressWarnings("unchecked")
 	public V get(AnyObjectId toFind) {
 		if (toFind == null) {
 			return null;
 		}
 		int h = toFind.w1;
 		V obj = directory[h & mask][h >>> SEGMENT_SHIFT];
 		for (; obj != null; obj = (V) obj.next)
 			if (equals(obj, toFind))
 				return obj;
 		return null;
 	}

 	/**
 	 * {@inheritDoc}
 	 * <p>
 	 * Returns true if this map contains the specified object.
 	 */
 	@Override
 	public boolean contains(AnyObjectId toFind) {
 		return get(toFind) != null;
 	}

 	/**
 	 * Store an object for future lookup.
 	 * <p>
 	 * An existing mapping for <b>must not</b> be in this map. Callers must
 	 * first call {@link #get(AnyObjectId)} to verify there is no current
 	 * mapping prior to adding a new mapping, or use {@link #addIfAbsent(Entry)}.
 	 *
 	 * @param newValue
 	 *            the object to store.
 	 */
 	public <Q extends V> void add(Q newValue) {
 		if (++size == grow)
 			grow();

 		int h = newValue.w1;
 		V[] table = directory[h & mask];
 		h >>>= SEGMENT_SHIFT;

 		newValue.next = table[h];
 		table[h] = newValue;
 	}

 	/**
 	 * Store an object for future lookup.
 	 * <p>
 	 * Stores {@code newValue}, but only if there is not already an object for
 	 * the same object name. Callers can tell if the value is new by checking
 	 * the return value with reference equality:
 	 *
 	 * <pre>
 	 * V obj = ...;
 	 * boolean wasNew = map.addIfAbsent(obj) == obj;
 	 * </pre>
 	 *
 	 * @param newValue
 	 *            the object to store.
 	 * @return {@code newValue} if stored, or the prior value already stored and
 	 *         that would have been returned had the caller used
 	 *         {@code get(newValue)} first.
 	 */
 	@SuppressWarnings("unchecked")
 	public <Q extends V> V addIfAbsent(Q newValue) {
 		int h = newValue.w1;
 		V[] table = directory[h & mask];
 		h >>>= SEGMENT_SHIFT;

 		for (V obj = table[h]; obj != null; obj = (V) obj.next)
 			if (equals(obj, newValue))
 				return obj;

 		newValue.next = table[h];
 		table[h] = newValue;

 		if (++size == grow)
 			grow();
 		return newValue;
 	}

 	/**
 	 * Get number of objects in this map.
 	 *
 	 * @return number of objects in this map.
 	 */
 	public int size() {
 		return size;
 	}

 	/**
 	 * Whether this map is empty
 	 *
 	 * @return true if {@link #size()} is 0.
 	 */
 	public boolean isEmpty() {
 		return size == 0;
 	}

 	/** {@inheritDoc} */
 	@Override
 	public Iterator<V> iterator() {
 		return new Iterator<>() {
 			private int found;
 			private int dirIdx;
 			private int tblIdx;
 			private V next;

 			@Override
 			public boolean hasNext() {
 				return found < size;
 			}

 			@Override
 			public V next() {
 				if (next != null)
 					return found(next);

 				for (;;) {
 					V[] table = directory[dirIdx];
 					if (tblIdx == table.length) {
 						if (++dirIdx >= (1 << bits))
 							throw new NoSuchElementException();
 						table = directory[dirIdx];
 						tblIdx = 0;
 					}

 					while (tblIdx < table.length) {
 						V v = table[tblIdx++];
 						if (v != null)
 							return found(v);
 					}
 				}
 			}

 			@SuppressWarnings("unchecked")
 			private V found(V v) {
 				found++;
 				next = (V) v.next;
 				return v;
 			}

 			@Override
 			public void remove() {
 				throw new UnsupportedOperationException();
 			}
 		};
 	}

 	@SuppressWarnings("unchecked")
 	private void grow() {
 		final int oldDirLen = 1 << bits;
 		final int s = 1 << bits;

 		bits++;
 		mask = (1 << bits) - 1;
 		grow = computeGrowAt(bits);

 		// Quadruple the directory if it needs to expand. Expanding the
 		// directory is expensive because it generates garbage, so try
 		// to avoid doing it often.
 		//
 		final int newDirLen = 1 << bits;
 		if (directory.length < newDirLen) {
 			V[][] newDir = (V[][]) new Entry[newDirLen << 1][];
 			System.arraycopy(directory, 0, newDir, 0, oldDirLen);
 			directory = newDir;
 		}

 		// For every bucket of every old segment, split the chain between
 		// the old segment and the new segment's corresponding bucket. To
 		// select between them use the lowest bit that was just added into
 		// the mask above. This causes the table to double in capacity.
 		//
 		for (int dirIdx = 0; dirIdx < oldDirLen; dirIdx++) {
 			final V[] oldTable = directory[dirIdx];
 			final V[] newTable = newSegment();

 			for (int i = 0; i < oldTable.length; i++) {
 				V chain0 = null;
 				V chain1 = null;
 				V next;

 				for (V obj = oldTable[i]; obj != null; obj = next) {
 					next = (V) obj.next;

 					if ((obj.w1 & s) == 0) {
 						obj.next = chain0;
 						chain0 = obj;
 					} else {
 						obj.next = chain1;
 						chain1 = obj;
 					}
 				}

 				oldTable[i] = chain0;
 				newTable[i] = chain1;
 			}

 			directory[oldDirLen + dirIdx] = newTable;
 		}
 	}

 	@SuppressWarnings("unchecked")
 	private final V[] newSegment() {
 		return (V[]) new Entry[1 << SEGMENT_BITS];
 	}

 	private static final int computeGrowAt(int bits) {
 		return 1 << (bits + SEGMENT_BITS);
 	}

 	private static final boolean equals(AnyObjectId firstObjectId,
 			AnyObjectId secondObjectId) {
 		return firstObjectId.w2 == secondObjectId.w2
 				&& firstObjectId.w3 == secondObjectId.w3
 				&& firstObjectId.w4 == secondObjectId.w4
 				&& firstObjectId.w5 == secondObjectId.w5
 				&& firstObjectId.w1 == secondObjectId.w1;
 	}

 	/** Type of entry stored in the {@link ObjectIdOwnerMap}. */
 	public abstract static class Entry extends ObjectId {
 		transient Entry next;

 		/**
 		 * Initialize this entry with a specific ObjectId.
 		 *
 		 * @param id
 		 *            the id the entry represents.
 		 */
 		public Entry(AnyObjectId id) {
 			super(id);
 		}
 	}
 }
	/*
	* Copyright (C) 2011, Google Inc. and others
	*
	* This program and the accompanying materials are made available under the
	* terms of the Eclipse Distribution License v. 1.0 which is available at
	* https://www.eclipse.org/org/documents/edl-v10.php.
	*
	* SPDX-License-Identifier: BSD-3-Clause
	*/

	package org.eclipse.jgit.lib;

	import java.util.Arrays;
	import java.util.Iterator;
	import java.util.NoSuchElementException;

	/**
	* Fast, efficient map for {@link org.eclipse.jgit.lib.ObjectId} subclasses in
	* only one map.
	* <p>
	* To use this map type, applications must have their entry value type extend
	* from {@link org.eclipse.jgit.lib.ObjectIdOwnerMap.Entry}, which itself
	* extends from ObjectId.
	* <p>
	* Object instances may only be stored in <b>ONE</b> ObjectIdOwnerMap. This
	* restriction exists because the map stores internal map state within each
	* object instance. If an instance is be placed in another ObjectIdOwnerMap it
	* could corrupt one or both map's internal state.
	* <p>
	* If an object instance must be in more than one map, applications may use
	* ObjectIdOwnerMap for one of the maps, and
	* {@link org.eclipse.jgit.lib.ObjectIdSubclassMap} for the other map(s). It is
	* encouraged to use ObjectIdOwnerMap for the map that is accessed most often,
	* as this implementation runs faster than the more general ObjectIdSubclassMap
	* implementation.
	*
	* @param <V>
	* type of subclass of ObjectId that will be stored in the map.
	*/
	public class ObjectIdOwnerMap<V extends ObjectIdOwnerMap.Entry>
	implements Iterable<V>, ObjectIdSet {
	/** Size of the initial directory, will grow as necessary. */
	private static final int INITIAL_DIRECTORY = 1024;

	/** Number of bits in a segment's index. Segments are 2^11 in size. */
	private static final int SEGMENT_BITS = 11;

	private static final int SEGMENT_SHIFT = 32 - SEGMENT_BITS;

	/**
	* Top level directory of the segments.
	* <p>
	* The low {@link #bits} of the SHA-1 are used to select the segment from
	* this directory. Each segment is constant sized at 2^SEGMENT_BITS.
	*/
	V[][] directory;

	/** Total number of objects in this map. */
	int size;

	/** The map doubles in capacity when {@link #size} reaches this target. */
	private int grow;

	/** Number of low bits used to form the index into {@link #directory}. */
	int bits;

	/** Low bit mask to index into {@link #directory}, {@code 2^bits-1}. */
	private int mask;

	/**
	* Create an empty map.
	*/
	@SuppressWarnings("unchecked")
	public ObjectIdOwnerMap() {
	bits = 0;
	mask = 0;
	grow = computeGrowAt(bits);

	directory = (V[][]) new Entry[INITIAL_DIRECTORY][];
	directory[0] = newSegment();
	}

	/**
	* Remove all entries from this map.
	*/
	public void clear() {
	size = 0;

	for (V[] tbl : directory) {
	if (tbl == null)
	break;
	Arrays.fill(tbl, null);
	}
	}

	/**
	* Lookup an existing mapping.
	*
	* @param toFind
	* the object identifier to find.
	* @return the instance mapped to toFind, or null if no mapping exists.
	*/
	@SuppressWarnings("unchecked")
	public V get(AnyObjectId toFind) {
	if (toFind == null) {
	return null;
	}
	int h = toFind.w1;
	V obj = directory[h & mask][h >>> SEGMENT_SHIFT];
	for (; obj != null; obj = (V) obj.next)
	if (equals(obj, toFind))
	return obj;
	return null;
	}

	/**
	* {@inheritDoc}
	* <p>
	* Returns true if this map contains the specified object.
	*/
	@Override
	public boolean contains(AnyObjectId toFind) {
	return get(toFind) != null;
	}

	/**
	* Store an object for future lookup.
	* <p>
	* An existing mapping for <b>must not</b> be in this map. Callers must
	* first call {@link #get(AnyObjectId)} to verify there is no current
	* mapping prior to adding a new mapping, or use {@link #addIfAbsent(Entry)}.
	*
	* @param newValue
	* the object to store.
	*/
	public <Q extends V> void add(Q newValue) {
	if (++size == grow)
	grow();

	int h = newValue.w1;
	V[] table = directory[h & mask];
	h >>>= SEGMENT_SHIFT;

	newValue.next = table[h];
	table[h] = newValue;
	}

	/**
	* Store an object for future lookup.
	* <p>
	* Stores {@code newValue}, but only if there is not already an object for
	* the same object name. Callers can tell if the value is new by checking
	* the return value with reference equality:
	*
	* <pre>
	* V obj = ...;
	* boolean wasNew = map.addIfAbsent(obj) == obj;
	* </pre>
	*
	* @param newValue
	* the object to store.
	* @return {@code newValue} if stored, or the prior value already stored and
	* that would have been returned had the caller used
	* {@code get(newValue)} first.
	*/
	@SuppressWarnings("unchecked")
	public <Q extends V> V addIfAbsent(Q newValue) {
	int h = newValue.w1;
	V[] table = directory[h & mask];
	h >>>= SEGMENT_SHIFT;

	for (V obj = table[h]; obj != null; obj = (V) obj.next)
	if (equals(obj, newValue))
	return obj;

	newValue.next = table[h];
	table[h] = newValue;

	if (++size == grow)
	grow();
	return newValue;
	}

	/**
	* Get number of objects in this map.
	*
	* @return number of objects in this map.
	*/
	public int size() {
	return size;
	}

	/**
	* Whether this map is empty
	*
	* @return true if {@link #size()} is 0.
	*/
	public boolean isEmpty() {
	return size == 0;
	}

	/** {@inheritDoc} */
	@Override
	public Iterator<V> iterator() {
	return new Iterator<>() {
	private int found;
	private int dirIdx;
	private int tblIdx;
	private V next;

	@Override
	public boolean hasNext() {
	return found < size;
	}

	@Override
	public V next() {
	if (next != null)
	return found(next);

	for (;;) {
	V[] table = directory[dirIdx];
	if (tblIdx == table.length) {
	if (++dirIdx >= (1 << bits))
	throw new NoSuchElementException();
	table = directory[dirIdx];
	tblIdx = 0;
	}

	while (tblIdx < table.length) {
	V v = table[tblIdx++];
	if (v != null)
	return found(v);
	}
	}
	}

	@SuppressWarnings("unchecked")
	private V found(V v) {
	found++;
	next = (V) v.next;
	return v;
	}

	@Override
	public void remove() {
	throw new UnsupportedOperationException();
	}
	};
	}

	@SuppressWarnings("unchecked")
	private void grow() {
	final int oldDirLen = 1 << bits;
	final int s = 1 << bits;

	bits++;
	mask = (1 << bits) - 1;
	grow = computeGrowAt(bits);

	// Quadruple the directory if it needs to expand. Expanding the
	// directory is expensive because it generates garbage, so try
	// to avoid doing it often.
	//
	final int newDirLen = 1 << bits;
	if (directory.length < newDirLen) {
	V[][] newDir = (V[][]) new Entry[newDirLen << 1][];
	System.arraycopy(directory, 0, newDir, 0, oldDirLen);
	directory = newDir;
	}

	// For every bucket of every old segment, split the chain between
	// the old segment and the new segment's corresponding bucket. To
	// select between them use the lowest bit that was just added into
	// the mask above. This causes the table to double in capacity.
	//
	for (int dirIdx = 0; dirIdx < oldDirLen; dirIdx++) {
	final V[] oldTable = directory[dirIdx];
	final V[] newTable = newSegment();

	for (int i = 0; i < oldTable.length; i++) {
	V chain0 = null;
	V chain1 = null;
	V next;

	for (V obj = oldTable[i]; obj != null; obj = next) {
	next = (V) obj.next;

	if ((obj.w1 & s) == 0) {
	obj.next = chain0;
	chain0 = obj;
	} else {
	obj.next = chain1;
	chain1 = obj;
	}
	}

	oldTable[i] = chain0;
	newTable[i] = chain1;
	}

	directory[oldDirLen + dirIdx] = newTable;
	}
	}

	@SuppressWarnings("unchecked")
	private final V[] newSegment() {
	return (V[]) new Entry[1 << SEGMENT_BITS];
	}

	private static final int computeGrowAt(int bits) {
	return 1 << (bits + SEGMENT_BITS);
	}

	private static final boolean equals(AnyObjectId firstObjectId,
	AnyObjectId secondObjectId) {
	return firstObjectId.w2 == secondObjectId.w2
	&& firstObjectId.w3 == secondObjectId.w3
	&& firstObjectId.w4 == secondObjectId.w4
	&& firstObjectId.w5 == secondObjectId.w5
	&& firstObjectId.w1 == secondObjectId.w1;
	}

	/** Type of entry stored in the {@link ObjectIdOwnerMap}. */
	public abstract static class Entry extends ObjectId {
	transient Entry next;

	/**
	* Initialize this entry with a specific ObjectId.
	*
	* @param id
	* the id the entry represents.
	*/
	public Entry(AnyObjectId id) {
	super(id);
	}
	}
	}