2 * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved.
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v1.0 which accompanies this distribution,
6 * and is available at http://www.eclipse.org/legal/epl-v10.html
8 package org.opendaylight.yangtools.util;
10 import com.google.common.annotations.Beta;
11 import com.google.common.base.Preconditions;
12 import com.google.common.collect.ImmutableMap;
13 import com.google.common.collect.UnmodifiableIterator;
14 import java.io.IOException;
15 import java.io.ObjectInputStream;
16 import java.io.ObjectOutputStream;
17 import java.io.Serializable;
18 import java.lang.reflect.Field;
19 import java.util.AbstractMap.SimpleImmutableEntry;
20 import java.util.AbstractSet;
21 import java.util.ArrayList;
22 import java.util.Arrays;
23 import java.util.Collection;
24 import java.util.Iterator;
25 import java.util.List;
28 import javax.annotation.Nonnull;
31 * Implementation of the {@link Map} interface which stores a set of immutable mappings using a key-to-offset map and
32 * a backing array. This is useful for situations where the same key set is shared across a multitude of maps, as this
33 * class uses a global cache to share the key-to-offset mapping.
35 * @param <K> the type of keys maintained by this map
36 * @param <V> the type of mapped values
39 public final class ImmutableOffsetMap<K, V> implements UnmodifiableMapPhase<K, V>, Serializable {
40 private static final long serialVersionUID = 1L;
42 private final Map<K, Integer> offsets;
43 private final V[] objects;
47 * Construct a new instance backed by specified key-to-offset map and array of objects.
49 * @param offsets Key-to-offset map, may not be null
50 * @param objects Array of value object, may not be null. The array is stored as is, the caller
51 * is responsible for ensuring its contents remain unmodified.
53 ImmutableOffsetMap(@Nonnull final Map<K, Integer> offsets, @Nonnull final V[] objects) {
54 this.offsets = Preconditions.checkNotNull(offsets);
55 this.objects = Preconditions.checkNotNull(objects);
56 Preconditions.checkArgument(offsets.size() == objects.length);
60 * Construct a new instance based on some other instance.
62 * @param m Instance to share data with, may not be null.
64 ImmutableOffsetMap(@Nonnull final ImmutableOffsetMap<K, V> m) {
65 this.offsets = m.offsets;
66 this.objects = m.objects;
70 * Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true,
71 * as this method returns an {@link ImmutableMap} for empty and singleton inputs, as those are more memory-efficient.
72 * This method also recognizes {@link ImmutableOffsetMap} on input, and returns it back without doing anything else.
73 * It also recognizes {@link MutableOffsetMap} (as returned by {@link #toModifiableMap()}) and makes an efficient
74 * copy of its contents. All other maps are converted to an {@link ImmutableOffsetMap} with the same iteration
77 * @param m Input map, may not be null.
78 * @return An isolated, immutable copy of the input map
80 @Nonnull public static <K, V> Map<K, V> copyOf(@Nonnull final Map<K, V> m) {
81 // Prevent a copy. Note that ImmutableMap is not listed here because of its potentially larger keySet overhead.
82 if (m instanceof ImmutableOffsetMap || m instanceof SharedSingletonMap) {
86 // Familiar and efficient to copy
87 if (m instanceof MutableOffsetMap) {
88 return ((MutableOffsetMap<K, V>) m).toUnmodifiableMap();
91 final int size = m.size();
93 // Shares a single object
94 return ImmutableMap.of();
97 // Efficient single-entry implementation.
98 final Entry<K, V> e = m.entrySet().iterator().next();
99 return SharedSingletonMap.of(e.getKey(), e.getValue());
102 // copyOf() disconnects the key set while retaining its order across cache lookup.
103 final Map<K, Integer> offsets = OffsetMapCache.orderedOffsets(m.keySet());
104 @SuppressWarnings("unchecked")
105 final V[] array = (V[]) new Object[offsets.size()];
106 for (Entry<K, V> e : m.entrySet()) {
107 array[offsets.get(e.getKey())] = e.getValue();
110 return new ImmutableOffsetMap<>(offsets, array);
115 return offsets.size();
119 public boolean isEmpty() {
120 return offsets.isEmpty();
124 public int hashCode() {
130 for (Entry<K, Integer> e : offsets.entrySet()) {
131 result += e.getKey().hashCode() ^ objects[e.getValue()].hashCode();
139 public boolean equals(final Object o) {
147 if (o instanceof ImmutableOffsetMap) {
148 final ImmutableOffsetMap<?, ?> om = (ImmutableOffsetMap<?, ?>) o;
149 if (offsets.equals(om.offsets) && Arrays.deepEquals(objects, om.objects)) {
152 } else if (o instanceof MutableOffsetMap) {
153 // Let MutableOffsetMap do the actual work.
154 return o.equals(this);
155 } else if (o instanceof Map) {
156 final Map<?, ?> om = (Map<?, ?>)o;
158 // Size and key sets have to match
159 if (size() != om.size() || !keySet().equals(om.keySet())) {
164 // Ensure all objects are present
165 for (Entry<K, Integer> e : offsets.entrySet()) {
166 if (!objects[e.getValue()].equals(om.get(e.getKey()))) {
170 } catch (ClassCastException e) {
171 // Can be thrown by om.get() indicating we have incompatible key types
182 public boolean containsKey(final Object key) {
183 return offsets.containsKey(key);
187 public boolean containsValue(final Object value) {
188 for (Object o : objects) {
189 if (value.equals(o)) {
197 public V get(final Object key) {
198 final Integer offset = offsets.get(key);
199 return offset == null ? null : objects[offset];
203 public V remove(final Object key) {
204 throw new UnsupportedOperationException();
208 public V put(final K key, final V value) {
209 throw new UnsupportedOperationException();
213 public void putAll(final Map<? extends K, ? extends V> m) {
214 throw new UnsupportedOperationException();
218 public void clear() {
219 throw new UnsupportedOperationException();
223 public Set<K> keySet() {
224 return offsets.keySet();
228 public Collection<V> values() {
229 return new ConstantArrayCollection<>(objects);
233 public Set<Entry<K, V>> entrySet() {
234 return new EntrySet();
238 public MutableOffsetMap<K, V> toModifiableMap() {
239 return MutableOffsetMap.copyOf(this);
243 public String toString() {
244 final StringBuilder sb = new StringBuilder("{");
245 final Iterator<K> it = offsets.keySet().iterator();
247 while (it.hasNext()) {
248 sb.append(it.next());
250 sb.append(objects[i++]);
257 return sb.append('}').toString();
260 Map<K, Integer> offsets() {
268 private final class EntrySet extends AbstractSet<Entry<K, V>> {
270 public Iterator<Entry<K, V>> iterator() {
271 final Iterator<Entry<K, Integer>> it = offsets.entrySet().iterator();
273 return new UnmodifiableIterator<Entry<K, V>>() {
275 public boolean hasNext() {
280 public Entry<K, V> next() {
281 final Entry<K, Integer> e = it.next();
282 return new SimpleImmutableEntry<>(e.getKey(), objects[e.getValue()]);
289 return offsets.size();
293 private void writeObject(final ObjectOutputStream out) throws IOException {
294 out.writeInt(offsets.size());
295 for (Entry<K, V> e : entrySet()) {
296 out.writeObject(e.getKey());
297 out.writeObject(e.getValue());
301 private static final Field OFFSETS_FIELD = fieldFor("offsets");
302 private static final Field ARRAY_FIELD = fieldFor("objects");
304 private static Field fieldFor(final String name) {
307 f = ImmutableOffsetMap.class.getDeclaredField(name);
308 } catch (NoSuchFieldException | SecurityException e) {
309 throw new IllegalStateException("Failed to lookup field " + name, e);
312 f.setAccessible(true);
316 private void setField(final Field field, final Object value) throws IOException {
318 field.set(this, value);
319 } catch (IllegalArgumentException | IllegalAccessException e) {
320 throw new IOException("Failed to set field " + field, e);
324 @SuppressWarnings("unchecked")
325 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
326 final int s = in.readInt();
328 // ImmutableList.build() does not have a sizing hint ...
329 final List<K> keys = new ArrayList<>(s);
330 final V[] values = (V[]) new Object[s];
332 for (int i = 0; i < s; ++i) {
333 keys.add((K)in.readObject());
334 values[i] = (V)in.readObject();
337 setField(OFFSETS_FIELD, OffsetMapCache.orderedOffsets(keys));
338 setField(ARRAY_FIELD, values);