diff options
author | Thomas Watson | 2018-12-11 14:15:31 +0000 |
---|---|---|
committer | Thomas Watson | 2018-12-12 02:53:16 +0000 |
commit | f2691ad6b309188f0909cc5e67c10698d3a0a136 (patch) | |
tree | 5fba484ccf7dd0246b578810f4010d3bec3d2b12 | |
parent | 7ab737ec81650ae8a497e1d05b81fdc82c1c5afc (diff) | |
download | rt.equinox.framework-f2691ad6b309188f0909cc5e67c10698d3a0a136.tar.gz rt.equinox.framework-f2691ad6b309188f0909cc5e67c10698d3a0a136.tar.xz rt.equinox.framework-f2691ad6b309188f0909cc5e67c10698d3a0a136.zip |
Bug 541258 - Remove deprecated internal KeyedHashSetY20181212-2200I20181216-1800I20181215-1800I20181215-0340I20181214-1800I20181214-0720I20181214-0105I20181213-1800I20181212-1800I20181212-0230
Change-Id: I32f2e473a30080d8de6ff4ba9934c18de381de41
Signed-off-by: Thomas Watson <tjwatson@us.ibm.com>
2 files changed, 7 insertions, 505 deletions
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 4996ba75f..33bb142dd 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 98445fa69..000000000 --- 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; - } -} |