Bug 541258 - Remove deprecated internal KeyedHashSet
Change-Id: I32f2e473a30080d8de6ff4ba9934c18de381de41
Signed-off-by: Thomas Watson <tjwatson@us.ibm.com>
diff --git a/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/framework/util/KeyedElement.java b/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/framework/util/KeyedElement.java
index 4996ba7..33bb142 100644
--- a/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/framework/util/KeyedElement.java
+++ b/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/framework/util/KeyedElement.java
@@ -1,5 +1,5 @@
/*******************************************************************************
- * Copyright (c) 2000, 2012 IBM Corporation and others.
+ * Copyright (c) 2000, 2018 IBM Corporation and others.
*
* This program and the accompanying materials
* are made available under the terms of the Eclipse Public License 2.0
@@ -14,9 +14,14 @@
package org.eclipse.osgi.framework.util;
/**
+ * NOTE: This interface defines an element that could be inserted into an internal class called
+ * <code>KeyedHashSet</code>. This internal class <code>KeyedHashSet</code> has been deleted.
+ * The KeyedElement interface has remained because of the use of it in <code>ClasspathEntry</code>.
+ * A keyed element can easily be put into a standard Map implementation by using the keyed element
+ * key for the mapping.
+ * <p>
* An element of an <code>KeyedHashSet</code>. A KeyedElement privides the key which is used to hash
* the elements in an <code>KeyedHashSet</code>.
- * @see KeyedHashSet
* @since 3.2
*/
// This class was moved from /org.eclipse.osgi/core/framework/org/eclipse/osgi/framework/internal/core/KeyedElement.java
diff --git a/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/framework/util/KeyedHashSet.java b/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/framework/util/KeyedHashSet.java
deleted file mode 100644
index 98445fa..0000000
--- a/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/framework/util/KeyedHashSet.java
+++ /dev/null
@@ -1,503 +0,0 @@
-/*******************************************************************************
- * Copyright (c) 2000, 2012 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.osgi.framework.util;
-
-import java.util.Iterator;
-import java.util.NoSuchElementException;
-
-/**
- * A set data structure which only accepts {@link KeyedElement} objects as elements of the set.
- * Unlike typical set implementations this set requires each element to provide its own key. This helps
- * reduce the overhead of storing the keys of each individual element<p>
- * This class in not thread safe, clients must ensure synchronization when modifying an object of this type.
- * @since 3.2
- * @deprecated This class will be removed in a future release
- */
-// This class was moved from /org.eclipse.osgi/core/framework/org/eclipse/osgi/framework/internal/core/KeyedHashSet.java
-@Deprecated
-public class KeyedHashSet {
- public static final int MINIMUM_SIZE = 7;
- int elementCount = 0;
- KeyedElement[] elements;
- private boolean replace;
- private int capacity;
-
- /**
- * Constructs an KeyedHashSet which allows elements to be replaced and with the minimum initial capacity.
- */
- public KeyedHashSet() {
- this(MINIMUM_SIZE, true);
- }
-
- /**
- * Constructs an KeyedHashSet with the minimum initial capacity.
- * @param replace true if this set allows elements to be replaced
- */
- public KeyedHashSet(boolean replace) {
- this(MINIMUM_SIZE, replace);
- }
-
- /**
- * Constructs an KeyedHashSet which allows elements to be replaced.
- * @param capacity the initial capacity of this set
- */
- public KeyedHashSet(int capacity) {
- this(capacity, true);
- }
-
- /**
- * Constructs an KeyedHashSet
- * @param capacity the initial capacity of this set
- * @param replace true if this set allows elements to be replaced
- */
- public KeyedHashSet(int capacity, boolean replace) {
- elements = new KeyedElement[Math.max(MINIMUM_SIZE, capacity * 2)];
- this.replace = replace;
- this.capacity = capacity;
- }
-
- /**
- * Constructs a new KeyedHashSet and copies to specified KeyedHashSet's contents to the new KeyedHashSet.
- * @param original the KeyedHashSet to copy
- */
- public KeyedHashSet(KeyedHashSet original) {
- elements = new KeyedElement[original.elements.length];
- System.arraycopy(original.elements, 0, elements, 0, original.elements.length);
- elementCount = original.elementCount;
- replace = original.replace;
- capacity = original.capacity;
- }
-
- /**
- * Adds an element to this set. If an element with the same key already exists,
- * replaces it depending on the replace flag.
- * @return true if the element was added/stored, false otherwise
- */
- public boolean add(KeyedElement element) {
- int hash = hash(element);
-
- // search for an empty slot at the end of the array
- for (int i = hash; i < elements.length; i++) {
- if (elements[i] == null) {
- elements[i] = element;
- elementCount++;
- // grow if necessary
- if (shouldGrow())
- expand();
- return true;
- }
- if (elements[i].compare(element)) {
- if (replace)
- elements[i] = element;
- return replace;
- }
- }
-
- // search for an empty slot at the beginning of the array
- for (int i = 0; i < hash - 1; i++) {
- if (elements[i] == null) {
- elements[i] = element;
- elementCount++;
- // grow if necessary
- if (shouldGrow())
- expand();
- return true;
- }
- if (elements[i].compare(element)) {
- if (replace)
- elements[i] = element;
- return replace;
- }
- }
-
- // if we didn't find a free slot, then try again with the expanded set
- expand();
- return add(element);
- }
-
- /**
- * Adds the specified list of elements to this set. Some elements may not
- * get added if the replace flag is set.
- * @param toAdd the list of elements to add to this set.
- */
- public void addAll(KeyedElement[] toAdd) {
- for (int i = 0; i < toAdd.length; i++)
- add(toAdd[i]);
- }
-
- /**
- * Returns true if the specified element exists in this set.
- * @param element the requested element
- * @return true if the specified element exists in this set; false otherwise.
- */
- public boolean contains(KeyedElement element) {
- return get(element) != null;
- }
-
- /**
- * Returns true if an element with the specified key exists in this set.
- * @param key the key of the requested element
- * @return true if an element with the specified key exists in this set; false otherwise
- */
- public boolean containsKey(Object key) {
- return getByKey(key) != null;
- }
-
- /**
- * Returns all elements that exist in this set
- * @return all elements that exist in this set
- */
- public KeyedElement[] elements() {
- return (KeyedElement[]) elements(new KeyedElement[elementCount]);
- }
-
- /**
- * Copies all elements that exist in this set into the specified array. No size
- * checking is done. If the specified array is to small an ArrayIndexOutOfBoundsException
- * will be thrown.
- * @param result the array to copy the existing elements into.
- * @return the specified array.
- * @throws ArrayIndexOutOfBoundsException if the specified array is to small.
- */
- public Object[] elements(Object[] result) {
- int j = 0;
- for (int i = 0; i < elements.length; i++) {
- KeyedElement element = elements[i];
- if (element != null)
- result[j++] = element;
- }
- return result;
- }
-
- /**
- * The array isn't large enough so double its size and rehash
- * all its current values.
- */
- protected void expand() {
- if (elements.length == Integer.MAX_VALUE) {
- throw new OutOfMemoryError();
- }
- KeyedElement[] oldElements = elements;
- int newSize = elements.length * 2;
- if (newSize < 0) {
- // overflowed; set to max
- newSize = Integer.MAX_VALUE;
- }
- elements = new KeyedElement[newSize];
-
- int maxArrayIndex = elements.length - 1;
- for (int i = 0; i < oldElements.length; i++) {
- KeyedElement element = oldElements[i];
- if (element != null) {
- int hash = hash(element);
- while (elements[hash] != null) {
- hash++;
- if (hash > maxArrayIndex)
- hash = 0;
- }
- elements[hash] = element;
- }
- }
- }
-
- /**
- * Returns the element with the specified key, or null if not found.
- * @param key the requested element's key
- * @return the element with the specified key, or null if not found.
- */
- public KeyedElement getByKey(Object key) {
- if (elementCount == 0)
- return null;
- int hash = keyHash(key);
-
- // search the last half of the array
- for (int i = hash; i < elements.length; i++) {
- KeyedElement element = elements[i];
- if (element == null)
- return null;
- if (element.getKey().equals(key))
- return element;
- }
-
- // search the beginning of the array
- for (int i = 0; i < hash - 1; i++) {
- KeyedElement element = elements[i];
- if (element == null)
- return null;
- if (element.getKey().equals(key))
- return element;
- }
-
- // nothing found so return null
- return null;
- }
-
- /**
- * Returns the element which compares to the specified element, or null if not found.
- * @see KeyedElement#compare(KeyedElement)
- * @param otherElement the requested element
- * @return the element which compares to the specified element, or null if not found.
- */
- public KeyedElement get(KeyedElement otherElement) {
- if (elementCount == 0)
- return null;
- int hash = hash(otherElement);
-
- // search the last half of the array
- for (int i = hash; i < elements.length; i++) {
- KeyedElement element = elements[i];
- if (element == null)
- return null;
- if (element.compare(otherElement))
- return element;
- }
-
- // search the beginning of the array
- for (int i = 0; i < hash - 1; i++) {
- KeyedElement element = elements[i];
- if (element == null)
- return null;
- if (element.compare(otherElement))
- return element;
- }
-
- // nothing found so return null
- return null;
- }
-
- /**
- * Returns true if this set is empty
- * @return true if this set is empty
- */
- public boolean isEmpty() {
- return elementCount == 0;
- }
-
- /**
- * The element at the given index has been removed so move
- * elements to keep the set properly hashed.
- * @param anIndex the index that has been removed
- */
- protected void rehashTo(int anIndex) {
-
- int target = anIndex;
- int index = anIndex + 1;
- if (index >= elements.length)
- index = 0;
- KeyedElement element = elements[index];
- while (element != null) {
- int hashIndex = hash(element);
- boolean match;
- if (index < target)
- match = !(hashIndex > target || hashIndex <= index);
- else
- match = !(hashIndex > target && hashIndex <= index);
- if (match) {
- elements[target] = element;
- target = index;
- }
- index++;
- if (index >= elements.length)
- index = 0;
- element = elements[index];
- }
- elements[target] = null;
- }
-
- /**
- * Removes the element with the specified key
- * @param key the requested element's key
- * @return true if an element was removed
- */
- public boolean removeByKey(Object key) {
- if (elementCount == 0)
- return false;
- int hash = keyHash(key);
-
- for (int i = hash; i < elements.length; i++) {
- KeyedElement element = elements[i];
- if (element == null)
- return false;
- if (element.getKey().equals(key)) {
- rehashTo(i);
- elementCount--;
- return true;
- }
- }
-
- for (int i = 0; i < hash - 1; i++) {
- KeyedElement element = elements[i];
- if (element == null)
- return false;
- if (element.getKey().equals(key)) {
- rehashTo(i);
- elementCount--;
- return true;
- }
- }
-
- return true;
- }
-
- /**
- * Removes the element which compares to the specified element
- * @param toRemove the requested element to remove
- * @return true if an element was removed
- */
- public boolean remove(KeyedElement toRemove) {
- if (elementCount == 0)
- return false;
-
- int hash = hash(toRemove);
-
- for (int i = hash; i < elements.length; i++) {
- KeyedElement element = elements[i];
- if (element == null)
- return false;
- if (element.compare(toRemove)) {
- rehashTo(i);
- elementCount--;
- return true;
- }
- }
-
- for (int i = 0; i < hash - 1; i++) {
- KeyedElement element = elements[i];
- if (element == null)
- return false;
- if (element.compare(toRemove)) {
- rehashTo(i);
- elementCount--;
- return true;
- }
- }
- return false;
- }
-
- private int hash(KeyedElement element) {
- return Math.abs(element.getKeyHashCode()) % elements.length;
- }
-
- private int keyHash(Object key) {
- return Math.abs(key.hashCode()) % elements.length;
- }
-
- /**
- * Removes all of the specified elements from this set
- * @param toRemove the requested elements to remove
- */
- public void removeAll(KeyedElement[] toRemove) {
- for (int i = 0; i < toRemove.length; i++)
- remove(toRemove[i]);
- }
-
- private boolean shouldGrow() {
- return elementCount > elements.length * 0.75;
- }
-
- /**
- * Returns the number of elements in this set
- * @return the number of elements in this set
- */
- public int size() {
- return elementCount;
- }
-
- public String toString() {
- StringBuffer result = new StringBuffer(100);
- result.append("{"); //$NON-NLS-1$
- boolean first = true;
- for (int i = 0; i < elements.length; i++) {
- if (elements[i] != null) {
- if (first)
- first = false;
- else
- result.append(", "); //$NON-NLS-1$
- result.append(elements[i]);
- }
- }
- result.append("}"); //$NON-NLS-1$
- return result.toString();
- }
-
- /**
- * Returns the number of collisions this set currently has
- * @return the number of collisions this set currently has
- */
- public int countCollisions() {
- int result = 0;
- int lastHash = 0;
- boolean found = false;
- for (int i = 0; i < elements.length; i++) {
- KeyedElement element = elements[i];
- if (element == null)
- found = false;
- else {
- int hash = hash(element);
- if (found)
- if (lastHash == hash)
- result++;
- else
- found = false;
- else {
- lastHash = hash;
- found = true;
- }
- }
- }
- return result;
- }
-
- /**
- * Returns an iterator of elements in this set
- * @return an iterator of elements in this set
- */
- public Iterator<KeyedElement> iterator() {
- return new EquinoxSetIterator();
- }
-
- class EquinoxSetIterator implements Iterator<KeyedElement> {
- private int currentIndex = -1;
- private int found;
-
- public boolean hasNext() {
- return found < elementCount;
- }
-
- public KeyedElement next() {
- if (!hasNext())
- throw new NoSuchElementException();
- while (++currentIndex < elements.length)
- if (elements[currentIndex] != null) {
- found++;
- return elements[currentIndex];
- }
- // this would mean we have less elements than we thought
- throw new NoSuchElementException();
- }
-
- public void remove() {
- // as allowed by the API
- throw new UnsupportedOperationException();
- }
- }
-
- /**
- * Clears all elements from this set
- */
- public void clear() {
- elements = new KeyedElement[Math.max(MINIMUM_SIZE, capacity * 2)];
- elementCount = 0;
- }
-}
