bundles/org.eclipse.core.resources/src/org/eclipse/core/internal/events/NodeIDMap.java

/*******************************************************************************
 * Copyright (c) 2000, 2005 IBM Corporation and others.
 *
 * This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-2.0/
 *
 * SPDX-License-Identifier: EPL-2.0
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.core.internal.events;

import org.eclipse.core.runtime.IPath;

/**
 * A specialized map that maps Node IDs to their old and new paths.
 * Used for calculating moves during resource change notification.
 */
public class NodeIDMap {
	//using prime table sizes improves our hash function
	private static final int[] SIZES = new int[] {13, 29, 71, 173, 349, 733, 1511, 3079, 6133, 16381, 32653, 65543, 131111, 262139, 524287, 1051601};
	private static final double LOAD_FACTOR = 0.75;
	//2^32 * golden ratio
	private static final long LARGE_NUMBER = 2654435761L;

	int sizeOffset = 0;
	protected int elementCount = 0;
	protected long[] ids;
	protected IPath[] oldPaths;
	protected IPath[] newPaths;

	/**
	 * Creates a new node ID map of default capacity.
	 */
	public NodeIDMap() {
		this.sizeOffset = 0;
		this.ids = new long[SIZES[sizeOffset]];
		this.oldPaths = new IPath[SIZES[sizeOffset]];
		this.newPaths = new IPath[SIZES[sizeOffset]];
	}

	/**
	 * The array isn't large enough so double its size and rehash
	 * all its current values.
	 */
	protected void expand() {
		int newLength;
		try {
			newLength = SIZES[++sizeOffset];
		} catch (ArrayIndexOutOfBoundsException e) {
			//will only occur if there are > 1 million elements in delta
			newLength = ids.length * 2;
		}
		long[] grownIds = new long[newLength];
		IPath[] grownOldPaths = new IPath[newLength];
		IPath[] grownNewPaths = new IPath[newLength];
		int maxArrayIndex = newLength - 1;
		for (int i = 0; i < ids.length; i++) {
			long id = ids[i];
			if (id != 0) {
				int hash = hashFor(id, newLength);
				while (grownIds[hash] != 0) {
					hash++;
					if (hash > maxArrayIndex)
						hash = 0;
				}
				grownIds[hash] = id;
				grownOldPaths[hash] = oldPaths[i];
				grownNewPaths[hash] = newPaths[i];
			}
		}
		ids = grownIds;
		oldPaths = grownOldPaths;
		newPaths = grownNewPaths;
	}

	/**
	 * Returns the index of the given element in the map.  If not
	 * found, returns -1.
	 */
	private int getIndex(long searchID) {
		final int len = ids.length;
		int hash = hashFor(searchID, len);

		// search the last half of the array
		for (int i = hash; i < len; i++) {
			if (ids[i] == searchID)
				return i;
			// marker info not found so return -1
			if (ids[i] == 0)
				return -1;
		}

		// search the beginning of the array
		for (int i = 0; i < hash - 1; i++) {
			if (ids[i] == searchID)
				return i;
			// marker info not found so return -1
			if (ids[i] == 0)
				return -1;
		}
		// marker info not found so return -1
		return -1;
	}

	/**
	 * Returns the new path location for the given ID, or null
	 * if no new path is available.
	 */
	public IPath getNewPath(long nodeID) {
		int index = getIndex(nodeID);
		if (index == -1)
			return null;
		return newPaths[index];
	}

	/**
	 * Returns the old path location for the given ID, or null
	 * if no old path is available.
	 */
	public IPath getOldPath(long nodeID) {
		int index = getIndex(nodeID);
		if (index == -1)
			return null;
		return oldPaths[index];
	}

	private int hashFor(long id, int size) {
		//Knuth's hash function from Art of Computer Programming section 6.4
		return (int) Math.abs((id * LARGE_NUMBER) % size);
	}

	/**
	 * Returns true if there are no elements in the map, and
	 * false otherwise.
	 */
	public boolean isEmpty() {
		return elementCount == 0;
	}

	/**
	 * Adds the given path mappings to the map.  If either oldPath
	 * or newPath is null, they are ignored (old map values are not overwritten).
	 */
	private void put(long id, IPath oldPath, IPath newPath) {
		if (oldPath == null && newPath == null)
			return;
		int hash = hashFor(id, ids.length);

		// search for an empty slot at the end of the array
		for (int i = hash; i < ids.length; i++) {
			if (ids[i] == id) {
				//replace value for existing entry
				if (oldPath != null)
					oldPaths[i] = oldPath;
				if (newPath != null)
					newPaths[i] = newPath;
				return;
			}
			if (ids[i] == 0) {
				//add a new entry to the map
				ids[i] = id;
				if (oldPath != null)
					oldPaths[i] = oldPath;
				if (newPath != null)
					newPaths[i] = newPath;
				elementCount++;
				// grow if necessary
				if (shouldGrow())
					expand();
				return;
			}
		}

		// search for an empty slot at the beginning of the array
		for (int i = 0; i < hash - 1; i++) {
			if (ids[i] == id) {
				//replace value for existing entry
				if (oldPath != null)
					oldPaths[i] = oldPath;
				if (newPath != null)
					newPaths[i] = newPath;
				return;
			}
			if (ids[i] == 0) {
				//add a new entry to the map
				ids[i] = id;
				if (oldPath != null)
					oldPaths[i] = oldPath;
				if (newPath != null)
					newPaths[i] = newPath;
				elementCount++;
				// grow if necessary
				if (shouldGrow())
					expand();
				return;
			}
		}
		// if we didn't find a free slot, then try again with the expanded set
		expand();
		put(id, oldPath, newPath);
	}

	/**
	 * Adds an entry for a node's old path
	 */
	public void putOldPath(long id, IPath path) {
		put(id, path, null);
	}

	/**
	 * Adds an entry for a node's old path
	 */
	public void putNewPath(long id, IPath path) {
		put(id, null, path);
	}

	private boolean shouldGrow() {
		return elementCount > ids.length * LOAD_FACTOR;
	}
}