http://www.eclipse.org/platform: OSGi System Bundle %systemBundle (Eclipse Foundation) 
Copyright (c) 2003, 2016 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

/*******************************************************************************
 * Copyright (c) 2003, 2016 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.eventmgr;

import java.util.*;


A copy-on-write identity map. Write operations result in copying the underlying data so that
simultaneous read operations are not affected.
This allows for safe, unsynchronized traversal.


Note: This class uses identity for key and value comparison, not equals.

Since:3.5
/**
 * A copy-on-write identity map. Write operations result in copying the underlying data so that
 * simultaneous read operations are not affected.
 * This allows for safe, unsynchronized traversal.
 * 
 * <p>
 * Note: This class uses identity for key and value comparison, not equals.
 * 
 * @since 3.5
 */
public class CopyOnWriteIdentityMap<K, V> implements Map<K, V> {
	
The empty array singleton instance.

/**
	 * The empty array singleton instance.
	 */
	@SuppressWarnings("rawtypes")
	private static final Entry[] emptyArray = new Entry[0];

	
The array of entries. This field is volatile so it can be 
accessed from unsynchronized reader methods.

/**
	 * The array of entries. This field is volatile so it can be 
	 * accessed from unsynchronized reader methods.
	 */
	private volatile Entry<K, V>[] entries;

	
Creates an empty map.

/**
	 * Creates an empty map.
	 *
	 */
	public CopyOnWriteIdentityMap() {
		entries = empty();
	}

	
Copy constructor.

Params:
  • source – The CopyOnWriteMap to copy.
/**
	 * Copy constructor.
	 *
	 * @param source The CopyOnWriteMap to copy.
	 */
	public CopyOnWriteIdentityMap(CopyOnWriteIdentityMap<? extends K, ? extends V> source) {
		@SuppressWarnings("unchecked")
		Entry<K, V>[] toCopy = (Entry<K, V>[]) source.entries();
		this.entries = toCopy;
	}

	/* These methods modify the map and are synchronized. */

	
Add a key, value pair to the map.
If the key object is already in the map, then its value is replaced with the new value.
Keys are compared using identity.

Params:
  • key – The key object to be added to the list.
  • value – The value object to be associated with the key.
This may be null.
Throws:
Returns:null if the specified key was newly added to the map.
Otherwise the previous value of the key.
/**
	 * Add a key, value pair to the map.
	 * If the key object is already in the map, then its value is replaced with the new value.
	 * Keys are compared using identity.
	 *
	 * @param key The key object to be added to the list.
	 * @param value The value object to be associated with the key.
	 * This may be null.
	 * @return <code>null</code> if the specified key was newly added to the map.
	 * Otherwise the previous value of the key.
	 * @throws IllegalArgumentException If key is null.
	 */
	@Override
	public synchronized V put(K key, V value) {
		if (key == null) {
			throw new IllegalArgumentException();
		}

		int size = entries.length;
		for (int i = 0; i < size; i++) {
			if (entries[i].key == key) {
				V v = entries[i].value;
				if (v == value) {
					return v;
				}
				@SuppressWarnings("unchecked")
				Entry<K, V>[] newEntries = new Entry[size];
				System.arraycopy(entries, 0, newEntries, 0, size);
				newEntries[i] = new Entry<>(key, value);
				entries = newEntries;
				return v;
			}
		}

		@SuppressWarnings("unchecked")
		Entry<K, V>[] newEntries = new Entry[size + 1];
		if (size > 0) {
			System.arraycopy(entries, 0, newEntries, 0, size);
		}
		newEntries[size] = new Entry<>(key, value);
		entries = newEntries;
		return null;
	}

	
Add all the entries from the specified map to this map.

Params:
  • source – The map whose entries are to be added to this map.
/**
	 * Add all the entries from the specified map to this map.
	 * 
	 * @param source The map whose entries are to be added to this map.
	 */
	@Override
	public void putAll(Map<? extends K, ? extends V> source) {
		int sourceSize = source.size();
		if (sourceSize == 0) {
			return;
		}
		if (source instanceof CopyOnWriteIdentityMap<?, ?>) {
			putAll(((CopyOnWriteIdentityMap<? extends K, ? extends V>) source).entries());
			return;
		}

		@SuppressWarnings("unchecked")
		Entry<K, V>[] toCopy = new Entry[sourceSize];
		Iterator<? extends Map.Entry<? extends K, ? extends V>> iter = source.entrySet().iterator();
		for (int i = 0; i < sourceSize; i++) {
			Map.Entry<? extends K, ? extends V> mapEntry = iter.next();
			toCopy[i] = new Entry<K, V>(mapEntry.getKey(), mapEntry.getValue());
		}
		putAll(toCopy);
	}

	
Add all the keys from the specified array to this map with the value
null.

Params:
  • keys – The array of keys to be added to this map.
/**
	 * Add all the keys from the specified array to this map with the value
	 * <code>null</code>.
	 * 
	 * @param keys The array of keys to be added to this map.
	 */
	public <L extends K> void putAll(L[] keys) {
		int sourceSize = keys.length;
		if (sourceSize == 0) {
			return;
		}
		@SuppressWarnings("unchecked")
		Entry<K, V>[] toCopy = new Entry[sourceSize];
		for (int i = 0; i < sourceSize; i++) {
			toCopy[i] = new Entry<K, V>(keys[i], null);
		}
		putAll(toCopy);
	}

	
Add all the entries to this map.

Params:
  • toCopy – Array of entries to add to this map.
/**
	 * Add all the entries to this map.
	 * 
	 * @param toCopy Array of entries to add to this map.
	 */
	private synchronized void putAll(Entry<? extends K, ? extends V>[] toCopy) {
		int sourceSize = toCopy.length;
		int size = entries.length;
		@SuppressWarnings("unchecked")
		Entry<K, V>[] newEntries = new Entry[size + sourceSize];
		System.arraycopy(entries, 0, newEntries, 0, size);
		copy: for (int n = 0; n < sourceSize; n++) {
			@SuppressWarnings("unchecked")
			Entry<K, V> copy = (Entry<K, V>) toCopy[n];
			for (int i = 0; i < size; i++) {
				if (newEntries[i].key == copy.key) {
					newEntries[i] = copy;
					continue copy;
				}
			}
			newEntries[size] = copy;
			size++;
		}
		if (size == newEntries.length) {
			entries = newEntries;
			return;
		}
		@SuppressWarnings("unchecked")
		Entry<K, V>[] e = new Entry[size];
		System.arraycopy(newEntries, 0, e, 0, size);
		entries = e;
	}

	
Remove a key from the map and returns the value associated with the key.
Key objects are compared using identity.

Params:
  • key – The key object to be removed from the map.
Throws:
Returns:null if the key was not in the list. 
Otherwise, the value associated with the key.
/**
	 * Remove a key from the map and returns the value associated with the key.
	 * Key objects are compared using identity.
	 *
	 * @param key The key object to be removed from the map.
	 * @return <code>null</code> if the key was not in the list. 
	 * Otherwise, the value associated with the key.
	 * @throws IllegalArgumentException If key is null.
	 */
	@Override
	public synchronized V remove(Object key) {
		if (key == null) {
			throw new IllegalArgumentException();
		}

		int size = entries.length;
		for (int i = 0; i < size; i++) {
			if (entries[i].key == key) {
				V v = entries[i].value;
				entries = removeEntry(entries, i);
				return v;
			}
		}
		return null;
	}

	
Static method used to return an Entry array with the ith entry removed.

/**
	 * Static method used to return an Entry array with the ith entry removed.
	 */
	static <K, V> Entry<K, V>[] removeEntry(final Entry<K, V>[] entries, final int i) {
		int size = entries.length;
		if (size == 1) {
			return empty();
		}
		@SuppressWarnings("unchecked")
		Entry<K, V>[] newEntries = new Entry[size - 1];
		if (i > 0) {
			System.arraycopy(entries, 0, newEntries, 0, i);
		}
		int next = size - 1 - i;
		if (next > 0) {
			System.arraycopy(entries, i + 1, newEntries, i, next);
		}
		return newEntries;
	}

	
Remove all entries from the map.

/**
	 * Remove all entries from the map.
	 * 
	 */
	@Override
	public synchronized void clear() {
		entries = empty();
	}

	/* These methods only read the map and are not synchronized. */

	
Accessor for methods which only read the entries.

Returns:The array of entries. Callers to this method MUST NOT
modify the returned array.
/**
	 * Accessor for methods which only read the entries.
	 * @return The array of entries. Callers to this method MUST NOT
	 * modify the returned array.
	 */
	private Entry<K, V>[] entries() {
		return entries;
	}

	
Return the static empty array generically type safe.

Returns:The empty array of entries.
/**
	 * Return the static empty array generically type safe.
	 * @return The empty array of entries.
	 */
	@SuppressWarnings("unchecked")
	static <K, V> Entry<K, V>[] empty() {
		return emptyArray;
	}

	
Is the map empty?

Returns:true if the list is empty.
/**
	 * Is the map empty?
	 * 
	 * @return <code>true</code> if the list is empty.
	 */
	@Override
	public boolean isEmpty() {
		return size() == 0;
	}

	
Return the number of entries in the map.

Returns:The number of entries in the map.
/**
	 * Return the number of entries in the map.
	 * 
	 * @return The number of entries in the map.
	 */
	@Override
	public int size() {
		return entries().length;
	}

	
Return the value object for the specified key.
Keys are compared using identity.

Params:
  • key – The key object.
Throws:
Returns:The value object for the specified key.
/**
	 * Return the value object for the specified key.
	 * Keys are compared using identity.
	 * 
	 * @param key The key object.
	 * @return The value object for the specified key.
	 * @throws IllegalArgumentException If key is null.
	 */
	@Override
	public V get(Object key) {
		if (key == null) {
			throw new IllegalArgumentException();
		}

		for (Entry<K, V> entry : entries()) {
			if (entry.key == key) {
				return entry.value;
			}
		}
		return null;
	}

	
Check if the map contains the specified key.
Keys are compared using identity.

Params:
  • key – The key object.
Throws:
Returns:true if the specified key is in the map.
/**
	 * Check if the map contains the specified key.
	 * Keys are compared using identity.
	 * 
	 * @param key The key object.
	 * @return <code>true</code> if the specified key is in the map.
	 * @throws IllegalArgumentException If key is null.
	 */
	@Override
	public boolean containsKey(Object key) {
		if (key == null) {
			throw new IllegalArgumentException();
		}

		for (Entry<K, V> entry : entries()) {
			if (entry.key == key) {
				return true;
			}
		}
		return false;
	}

	
Check if the map contains the specified value.
Values are compared using identity.

Params:
  • value – The value object.
Returns:true if the specified value is in the map.
/**
	 * Check if the map contains the specified value.
	 * Values are compared using identity.
	 * 
	 * @param value The value object.
	 * @return <code>true</code> if the specified value is in the map.
	 */
	@Override
	public boolean containsValue(Object value) {
		for (Entry<K, V> entry : entries()) {
			if (entry.value == value) {
				return true;
			}
		}
		return false;
	}

	
Returns a snapshot of the entries in this map.
Changes to the returned set or this map will not affect each other.

Returns:A Set of Map.Entry for each entry in this map.
The entries returned by the set cannot be modified.
/**
	 * Returns a snapshot of the entries in this map.
	 * Changes to the returned set or this map will not affect each other.
	 * 
	 * @return A Set of Map.Entry for each entry in this map.
	 * The entries returned by the set cannot be modified.
	 */
	@Override
	public Set<Map.Entry<K, V>> entrySet() {
		return new Snapshot<>(entries()).entrySet();
	}

	
Returns a snapshot of the keys in this map.
Changes to the returned set or this map will not affect each other.

Returns:A Set of the key objects in this map
/**
	 * Returns a snapshot of the keys in this map.
	 * Changes to the returned set or this map will not affect each other.
	 * 
	 * @return A Set of the key objects in this map
	 */
	@Override
	public Set<K> keySet() {
		return new Snapshot<>(entries()).keySet();
	}

	
Returns a snapshot of the values in this map.
Changes to the returned set or this map will not affect each other.

Returns:A Collection of the value objects in this map.
/**
	 * Returns a snapshot of the values in this map.
	 * Changes to the returned set or this map will not affect each other.
	 * 
	 * @return A Collection of the value objects in this map.
	 */
	@Override
	public Collection<V> values() {
		return new Snapshot<>(entries()).values();
	}

	
This class represents the entry in this identity map.
Entry is immutable.

/**
	 * This class represents the entry in this identity map.
	 * Entry is immutable.
	 */
	static private final class Entry<K, V> implements Map.Entry<K, V> {
		
Key object.

/**
		 * Key object.
		 */
		final K key;

		
Value object.

/**
		 * Value object.
		 */
		final V value;

		
Constructor for map entry.

Params:
  • key – Key object in entry. Used for uniqueness.
  • value – Value object stored with key object.
/**
		 * Constructor for map entry.
		 * @param key Key object in entry. Used for uniqueness.
		 * @param value Value object stored with key object.
		 */
		Entry(final K key, final V value) {
			this.key = key;
			this.value = value;
		}

		@Override
		public K getKey() {
			return key;
		}

		@Override
		public V getValue() {
			return value;
		}

		@Override
		public V setValue(V value) {
			throw new UnsupportedOperationException(); // entries cannot be modified.
		}

		@Override
		public String toString() {
			return key + "=" + value; //$NON-NLS-1$
		}

		@Override
		public int hashCode() {
			return System.identityHashCode(key) ^ System.identityHashCode(value);
		}

		@Override
		public boolean equals(Object obj) {
			if (obj == this) {
				return true;
			}

			if (!(obj instanceof Map.Entry)) {
				return false;
			}

			Map.Entry<?, ?> e = (Map.Entry<?, ?>) obj;
			return (key == e.getKey()) && (value == e.getValue());
		}
	}

	
A snapshot of the entries in the map. This snapshot used by
the map collection views. Changes made by the collection 
views only mutate the snapshot and not the map. The collection
views only allow removal not addition.

/**
	 * A snapshot of the entries in the map. This snapshot used by
	 * the map collection views. Changes made by the collection 
	 * views only mutate the snapshot and not the map. The collection
	 * views only allow removal not addition.
	 */
	static private final class Snapshot<K, V> {
		volatile Entry<K, V>[] entries;

		Snapshot(Entry<K, V>[] e) {
			entries = e;
		}

		Entry<K, V>[] entries() {
			return entries;
		}

		synchronized void removeEntry(int i) {
			entries = CopyOnWriteIdentityMap.removeEntry(entries, i);
		}

		synchronized void clearEntries() {
			entries = CopyOnWriteIdentityMap.empty();
		}

		Set<Map.Entry<K, V>> entrySet() {
			return new EntrySet();
		}

		Set<K> keySet() {
			return new KeySet();
		}

		Collection<V> values() {
			return new ValueCollection();
		}

		
Entry set view over the snapshot.

/**
		 * Entry set view over the snapshot.
		 */
		private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
			EntrySet() {
				super();
			}

			@Override
			public Iterator<Map.Entry<K, V>> iterator() {
				return new EntryIterator();
			}

			@Override
			public int size() {
				return entries().length;
			}

			@Override
			public boolean remove(Object o) {
				if (o == null) {
					throw new IllegalArgumentException();
				}

				synchronized (Snapshot.this) {
					int size = entries.length;
					for (int i = 0; i < size; i++) {
						if (entries[i].equals(o)) {
							removeEntry(i);
							return true;
						}
					}
				}
				return false;
			}

			@Override
			public void clear() {
				clearEntries();
			}
		}

		
Entry set iterator over the snapshot.

/** 
		 * Entry set iterator over the snapshot.
		 */
		private final class EntryIterator extends SnapshotIterator<Map.Entry<K, V>> {
			EntryIterator() {
				super();
			}

			@Override
			public Map.Entry<K, V> next() {
				return nextEntry();
			}
		}

		
Key set view over the snapshot.

/**
		 * Key set view over the snapshot.
		 */
		private final class KeySet extends AbstractSet<K> {
			KeySet() {
				super();
			}

			@Override
			public Iterator<K> iterator() {
				return new KeyIterator();
			}

			@Override
			public int size() {
				return entries().length;
			}

			@Override
			public boolean remove(Object o) {
				if (o == null) {
					throw new IllegalArgumentException();
				}

				synchronized (Snapshot.this) {
					int size = entries.length;
					for (int i = 0; i < size; i++) {
						if (entries[i].key == o) {
							removeEntry(i);
							return true;
						}
					}
				}
				return false;
			}

			@Override
			public void clear() {
				clearEntries();
			}
		}

		
Key set iterator over the snapshot.

/** 
		 * Key set iterator over the snapshot.
		 */
		private final class KeyIterator extends SnapshotIterator<K> {
			KeyIterator() {
				super();
			}

			@Override
			public K next() {
				return nextEntry().key;
			}
		}

		
Value collection view over the snapshot.

/**
		 * Value collection view over the snapshot.
		 */
		private final class ValueCollection extends AbstractCollection<V> {
			ValueCollection() {
				super();
			}

			@Override
			public Iterator<V> iterator() {
				return new ValueIterator();
			}

			@Override
			public int size() {
				return entries().length;
			}

			@Override
			public boolean remove(Object o) {
				if (o == null) {
					throw new IllegalArgumentException();
				}

				synchronized (Snapshot.this) {
					int size = entries.length;
					for (int i = 0; i < size; i++) {
						if (entries[i].value == o) {
							removeEntry(i);
							return true;
						}
					}
				}
				return false;
			}

			@Override
			public void clear() {
				clearEntries();
			}
		}

		
Value collection iterator over the snapshot.

/** 
		 * Value collection iterator over the snapshot.
		 */
		private final class ValueIterator extends SnapshotIterator<V> {
			ValueIterator() {
				super();
			}

			@Override
			public V next() {
				return nextEntry().value;
			}
		}

		
Base iterator class handling removal and concurrent modifications.

/** 
		 * Base iterator class handling removal and concurrent modifications.
		 */
		private abstract class SnapshotIterator<E> implements Iterator<E> {
			private int length;
			private int cursor;

			SnapshotIterator() {
				length = entries().length;
				cursor = 0;
			}

			@Override
			public final boolean hasNext() {
				return cursor < length;
			}

			protected final Entry<K, V> nextEntry() {
				Entry<K, V>[] e = entries();
				if (length != e.length) {
					throw new ConcurrentModificationException();
				}
				if (cursor == length) {
					throw new NoSuchElementException();
				}
				return e[cursor++];
			}

			@Override
			public final void remove() {
				if (length != entries().length) {
					throw new ConcurrentModificationException();
				}
				if (cursor == 0) {
					throw new IllegalStateException();
				}
				cursor--;
				removeEntry(cursor);
				length = entries().length;
			}
		}
	}
}