*
 * {@code CacheBuilder} builds caches with any combination of the following features:
 *
 * <ul>
 *   <li>automatic loading of entries into the cache
 *   <li>least-recently-used eviction when a maximum size is exceeded (note that the cache is
 *       divided into segments, each of which does LRU internally)
 *   <li>time-based expiration of entries, measured since last access or last write

 *
 * {@code CacheBuilder} builds caches with any combination of the following features:
 *
 * <ul>
 *   <li>automatic loading of entries into the cache
 *   <li>least-recently-used eviction when a maximum size is exceeded (note that the cache is
 *       divided into segments, each of which does LRU internally)
 *   <li>time-based expiration of entries, measured since last access or last write

   * </pre>
   */
  private static class ExampleStackTrace extends IllegalStateException {

    static final StackTraceElement[] EMPTY_STACK_TRACE = new StackTraceElement[0];

    static final ImmutableSet<String> EXCLUDED_CLASS_NAMES =
        ImmutableSet.of(
            CycleDetectingLockFactory.class.getName(),
            ExampleStackTrace.class.getName(),
            LockGraphNode.class.getName());

   *
   * If a maximum size is specified, a best-effort bounding is performed per segment, using a
   * page-replacement algorithm to determine which entries to evict when the capacity has been
   * exceeded.
   *
   * The page replacement algorithm's data structures are kept casually consistent with the map. The
   * ordering of writes to a segment is sequentially consistent. An update to the map and recording

         *
         * We carry out this computation in modular arithmetic. Since times2ToThe32Mod accepts any
         * unsigned long, we don't have to do a mod on every operation, only when intermediate
         * results can exceed 2^63.
         */
        long result = times2ToThe32Mod(aHi * bHi /* < 2^62 */, m); // < m < 2^63
        result += aHi * bLo; // aHi * bLo < 2^63, result < 2^64
        if (result < 0) {

    return new MinimalCollection<>(type, true, contents);
  }

  private final E[] contents;
  private final Class<? super @NonNull E> type;
  private final boolean allowNulls;

  // Package-private so that it can be extended.
  MinimalCollection(Class<? super @NonNull E> type, boolean allowNulls, E... contents) {
    // TODO: consider making it shuffle the contents to test iteration order.
    this.contents = Platform.clone(contents);

 * <td>=
 * <td>Human-readable; no possibility of mixing up 0/O or 1/I. Defaults to upper case.
 * <tr>
 * <td>{@link #base32Hex()}
 * <td>0-9 A-V
 * <td>1.60
 * <td>=
 * <td>"Numerical" base 32; extended from the traditional hex alphabet. Defaults to upper case.
 * <tr>
 * <td>{@link #base64()}
 * <td>A-Z a-z 0-9 + /
 * <td>1.33
 * <td>=
 * <td>
 * <tr>
 * <td>{@link #base64Url()}

    Random r = new Random(9);
    for (int i = 0; i < ITERS; i++) {
      countRemaps(r.nextLong(), map);
    }
    for (int shard = 2; shard <= MAX_SHARDS; shard++) {
      // Rough: don't exceed 1.2x the expected number of remaps by more than 20
      assertTrue(map.get(shard) <= 1.2 * ITERS / shard + 20);
    }
  }

  private void countRemaps(long h, AtomicLongMap<Integer> map) {
    int last = 0;

   * @return the previous count of the element before the operation; possibly zero
   * @throws IllegalArgumentException if {@code occurrences} is negative, or if the resulting amount
   *     would exceed {@link Integer#MAX_VALUE}
   */
  @CanIgnoreReturnValue
  @Override
  public int add(E element, int occurrences) {
    checkNotNull(element);
    if (occurrences == 0) {
      return count(element);
    }

      int mask = hashTable.length - 1;

      // Invariant: all elements at indices in [knownRunStart, knownRunEnd) are nonnull.
      // If knownRunStart == knownRunEnd, this is vacuously true.
      // When knownRunEnd exceeds hashTable.length, it "wraps", detecting runs around the end
      // of the table.
      int knownRunStart = 0;
      int knownRunEnd = 0;

      outerLoop:
      while (knownRunStart < hashTable.length) {