001/*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.collect;
016
017import static com.google.common.base.Preconditions.checkNotNull;
018
019import com.google.common.annotations.GwtIncompatible;
020import com.google.common.annotations.VisibleForTesting;
021import com.google.common.base.Equivalence;
022import com.google.common.base.Function;
023import com.google.common.collect.MapMaker.Dummy;
024import com.google.common.collect.MapMakerInternalMap.InternalEntry;
025import javax.annotation.CheckForNull;
026
027/**
028 * Contains static methods pertaining to instances of {@link Interner}.
029 *
030 * @author Kevin Bourrillion
031 * @since 3.0
032 */
033@GwtIncompatible
034@ElementTypesAreNonnullByDefault
035public final class Interners {
036  private Interners() {}
037
038  /**
039   * Builder for {@link Interner} instances.
040   *
041   * @since 21.0
042   */
043  public static class InternerBuilder {
044    private final MapMaker mapMaker = new MapMaker();
045    private boolean strong = true;
046
047    private InternerBuilder() {}
048
049    /**
050     * Instructs the {@link InternerBuilder} to build a strong interner.
051     *
052     * @see Interners#newStrongInterner()
053     */
054    public InternerBuilder strong() {
055      this.strong = true;
056      return this;
057    }
058
059    /**
060     * Instructs the {@link InternerBuilder} to build a weak interner.
061     *
062     * @see Interners#newWeakInterner()
063     */
064    @GwtIncompatible("java.lang.ref.WeakReference")
065    public InternerBuilder weak() {
066      this.strong = false;
067      return this;
068    }
069
070    /**
071     * Sets the concurrency level that will be used by the to-be-built {@link Interner}.
072     *
073     * @see MapMaker#concurrencyLevel(int)
074     */
075    public InternerBuilder concurrencyLevel(int concurrencyLevel) {
076      this.mapMaker.concurrencyLevel(concurrencyLevel);
077      return this;
078    }
079
080    public <E> Interner<E> build() {
081      if (!strong) {
082        mapMaker.weakKeys();
083      }
084      return new InternerImpl<>(mapMaker);
085    }
086  }
087
088  /** Returns a fresh {@link InternerBuilder} instance. */
089  public static InternerBuilder newBuilder() {
090    return new InternerBuilder();
091  }
092
093  /**
094   * Returns a new thread-safe interner which retains a strong reference to each instance it has
095   * interned, thus preventing these instances from being garbage-collected. If this retention is
096   * acceptable, this implementation may perform better than {@link #newWeakInterner}.
097   */
098  public static <E> Interner<E> newStrongInterner() {
099    return newBuilder().strong().build();
100  }
101
102  /**
103   * Returns a new thread-safe interner which retains a weak reference to each instance it has
104   * interned, and so does not prevent these instances from being garbage-collected. This most
105   * likely does not perform as well as {@link #newStrongInterner}, but is the best alternative when
106   * the memory usage of that implementation is unacceptable.
107   */
108  @GwtIncompatible("java.lang.ref.WeakReference")
109  public static <E> Interner<E> newWeakInterner() {
110    return newBuilder().weak().build();
111  }
112
113  @VisibleForTesting
114  static final class InternerImpl<E> implements Interner<E> {
115    // MapMaker is our friend, we know about this type
116    @VisibleForTesting final MapMakerInternalMap<E, Dummy, ?, ?> map;
117
118    private InternerImpl(MapMaker mapMaker) {
119      this.map =
120          MapMakerInternalMap.createWithDummyValues(mapMaker.keyEquivalence(Equivalence.equals()));
121    }
122
123    @Override
124    public E intern(E sample) {
125      while (true) {
126        // trying to read the canonical...
127        @SuppressWarnings("rawtypes") // using raw types to avoid a bug in our nullness checker :(
128        InternalEntry entry = map.getEntry(sample);
129        if (entry != null) {
130          Object canonical = entry.getKey();
131          if (canonical != null) { // only matters if weak/soft keys are used
132            // The compiler would know this is safe if not for our use of raw types (see above).
133            @SuppressWarnings("unchecked")
134            E result = (E) canonical;
135            return result;
136          }
137        }
138
139        // didn't see it, trying to put it instead...
140        Dummy sneaky = map.putIfAbsent(sample, Dummy.VALUE);
141        if (sneaky == null) {
142          return sample;
143        } else {
144          /* Someone beat us to it! Trying again...
145           *
146           * Technically this loop not guaranteed to terminate, so theoretically (extremely
147           * unlikely) this thread might starve, but even then, there is always going to be another
148           * thread doing progress here.
149           */
150        }
151      }
152    }
153  }
154
155  /**
156   * Returns a function that delegates to the {@link Interner#intern} method of the given interner.
157   *
158   * @since 8.0
159   */
160  public static <E> Function<E, E> asFunction(Interner<E> interner) {
161    return new InternerFunction<>(checkNotNull(interner));
162  }
163
164  private static class InternerFunction<E> implements Function<E, E> {
165
166    private final Interner<E> interner;
167
168    public InternerFunction(Interner<E> interner) {
169      this.interner = interner;
170    }
171
172    @Override
173    public E apply(E input) {
174      return interner.intern(input);
175    }
176
177    @Override
178    public int hashCode() {
179      return interner.hashCode();
180    }
181
182    @Override
183    public boolean equals(@CheckForNull Object other) {
184      if (other instanceof InternerFunction) {
185        InternerFunction<?> that = (InternerFunction<?>) other;
186        return interner.equals(that.interner);
187      }
188
189      return false;
190    }
191  }
192}