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