123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241 |
- /*
- * Copyright (C) 2009, Google Inc.
- * Copyright (C) 2008, Marek Zawirski <marek.zawirski@gmail.com>
- * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
- * and other copyright owners as documented in the project's IP log.
- *
- * This program and the accompanying materials are made available
- * under the terms of the Eclipse Distribution License v1.0 which
- * accompanies this distribution, is reproduced below, and is
- * available at http://www.eclipse.org/org/documents/edl-v10.php
- *
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or
- * without modification, are permitted provided that the following
- * conditions are met:
- *
- * - Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- *
- * - Redistributions in binary form must reproduce the above
- * copyright notice, this list of conditions and the following
- * disclaimer in the documentation and/or other materials provided
- * with the distribution.
- *
- * - Neither the name of the Eclipse Foundation, Inc. nor the
- * names of its contributors may be used to endorse or promote
- * products derived from this software without specific prior
- * written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
- * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
- * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
- * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
- * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
- * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
- * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
- package org.eclipse.jgit.lib;
-
- import java.util.Iterator;
- import java.util.NoSuchElementException;
-
- /**
- * Fast, efficient map specifically for {@link ObjectId} subclasses.
- * <p>
- * This map provides an efficient translation from any ObjectId instance to a
- * cached subclass of ObjectId that has the same value.
- * <p>
- * Raw value equality is tested when comparing two ObjectIds (or subclasses),
- * not reference equality and not <code>.equals(Object)</code> equality. This
- * allows subclasses to override <code>equals</code> to supply their own
- * extended semantics.
- *
- * @param <V>
- * type of subclass of ObjectId that will be stored in the map.
- */
- public class ObjectIdSubclassMap<V extends ObjectId> implements Iterable<V> {
- private int size;
-
- private V[] obj_hash;
-
- /** Create an empty map. */
- public ObjectIdSubclassMap() {
- obj_hash = createArray(32);
- }
-
- /** Remove all entries from this map. */
- public void clear() {
- size = 0;
- obj_hash = createArray(32);
- }
-
- /**
- * Lookup an existing mapping.
- *
- * @param toFind
- * the object identifier to find.
- * @return the instance mapped to toFind, or null if no mapping exists.
- */
- public V get(final AnyObjectId toFind) {
- int i = index(toFind);
- V obj;
-
- while ((obj = obj_hash[i]) != null) {
- if (AnyObjectId.equals(obj, toFind))
- return obj;
- if (++i == obj_hash.length)
- i = 0;
- }
- return null;
- }
-
- /**
- * Returns true if this map contains the specified object.
- *
- * @param toFind
- * object to find.
- * @return true if the mapping exists for this object; false otherwise.
- */
- public boolean contains(final 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(ObjectId)}.
- *
- * @param newValue
- * the object to store.
- * @param <Q>
- * type of instance to store.
- */
- public <Q extends V> void add(final Q newValue) {
- if (obj_hash.length - 1 <= size * 2)
- grow();
- insert(newValue);
- size++;
- }
-
- /**
- * 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.
- * @param <Q>
- * type of instance to store.
- */
- public <Q extends V> V addIfAbsent(final Q newValue) {
- int i = index(newValue);
- V obj;
-
- while ((obj = obj_hash[i]) != null) {
- if (AnyObjectId.equals(obj, newValue))
- return obj;
- if (++i == obj_hash.length)
- i = 0;
- }
-
- if (obj_hash.length - 1 <= size * 2) {
- grow();
- insert(newValue);
- } else {
- obj_hash[i] = newValue;
- }
- size++;
- return newValue;
- }
-
- /**
- * @return number of objects in map
- */
- public int size() {
- return size;
- }
-
- /** @return true if {@link #size()} is 0. */
- public boolean isEmpty() {
- return size == 0;
- }
-
- public Iterator<V> iterator() {
- return new Iterator<V>() {
- private int found;
-
- private int i;
-
- public boolean hasNext() {
- return found < size;
- }
-
- public V next() {
- while (i < obj_hash.length) {
- final V v = obj_hash[i++];
- if (v != null) {
- found++;
- return v;
- }
- }
- throw new NoSuchElementException();
- }
-
- public void remove() {
- throw new UnsupportedOperationException();
- }
- };
- }
-
- private final int index(final AnyObjectId id) {
- return (id.w1 >>> 1) % obj_hash.length;
- }
-
- private void insert(final V newValue) {
- int j = index(newValue);
- while (obj_hash[j] != null) {
- if (++j >= obj_hash.length)
- j = 0;
- }
- obj_hash[j] = newValue;
- }
-
- private void grow() {
- final V[] old_hash = obj_hash;
- final int old_hash_size = obj_hash.length;
-
- obj_hash = createArray(2 * old_hash_size);
- for (int i = 0; i < old_hash_size; i++) {
- final V obj = old_hash[i];
- if (obj != null)
- insert(obj);
- }
- }
-
- @SuppressWarnings("unchecked")
- private final V[] createArray(final int sz) {
- return (V[]) new ObjectId[sz];
- }
- }
|