| /* | |
| * 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 <Q> | |
| * type of values | |
| * @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 <Q> | |
| * type of values | |
| * @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; | |
| } | |
| @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); | |
| } | |
| } | |
| } |