*       array. This hashing API accepts an arbitrary sequence of byte and multibyte values (via
 *       {@link Hasher}), but this is merely a convenience; these are always translated into raw
 *       byte sequences under the covers.
 *   <li><b>hash code:</b> each hash function always yields hash codes of the same fixed bit length
 *       (given by {@link #bits}). For example, {@link Hashing#sha1} produces a 160-bit number,

  private void trim() {
    int left = 0;
    int right = 2 * k - 1;

    int minThresholdPosition = 0;
    // The leftmost position at which the greatest of the k lower elements
    // -- the new value of threshold -- might be found.

    int iterations = 0;
    int maxIterations = IntMath.log2(right - left, RoundingMode.CEILING) * 3;
    while (left < right) {

  /**
   * Applies a supplemental hash function to a given hash code, which defends against poor quality
   * hash functions. This is critical when the concurrent hash map uses power-of-two length hash
   * tables, that otherwise encounter collisions for hash codes that do not differ in lower or upper
   * bits.
   *
   * @param h hash code
   */
  static int rehash(int h) {
    // Spread bits to regularize both segment and index locations,

    public E higher(E e) {
      synchronized (mutex) {
        return delegate().higher(e);
      }
    }

    @Override
    @CheckForNull
    public E lower(E e) {
      synchronized (mutex) {
        return delegate().lower(e);
      }
    }

    @Override
    @CheckForNull
    public E pollFirst() {
      synchronized (mutex) {
        return delegate().pollFirst();

  static {
    ImmutableSet.Builder<Integer> intValues = ImmutableSet.builder();
    // Add boundary values manually to avoid over/under flow (this covers 2^N for 0 and 31).
    intValues.add(Integer.MAX_VALUE - 1, Integer.MAX_VALUE);
    // Add values up to 40. This covers cases like "square of a prime" and such.
    for (int i = 1; i <= 40; i++) {
      intValues.add(i);
    }

    assertSame(testEquivalence, map.valueEquivalence);
    assertSame(map.keyStrength.defaultEquivalence(), map.keyEquivalence);
  }

  public void testSetConcurrencyLevel() {
    // round up to the nearest power of two

    checkConcurrencyLevel(1, 1);
    checkConcurrencyLevel(2, 2);
    checkConcurrencyLevel(3, 4);
    checkConcurrencyLevel(4, 4);
    checkConcurrencyLevel(5, 8);
    checkConcurrencyLevel(6, 8);

    assertSame(testEquivalence, map.valueEquivalence);
    assertSame(map.keyStrength.defaultEquivalence(), map.keyEquivalence);
  }

  public void testSetConcurrencyLevel() {
    // round up to the nearest power of two

    checkConcurrencyLevel(1, 1);
    checkConcurrencyLevel(2, 2);
    checkConcurrencyLevel(3, 4);
    checkConcurrencyLevel(4, 4);
    checkConcurrencyLevel(5, 8);
    checkConcurrencyLevel(6, 8);

    AssertionFailedError failure = new AssertionFailedError(message);
    failure.initCause(cause);
    return failure;
  }

  // This test covers a bug where an Error thrown from a callback could cause the TimeoutFuture to
  // never complete when timing out.  Notably, nothing would get logged since the Error would get

  }

  private static final int EVEN_POWERS_OF_TWO = 0x55555555;
  private static final int ODD_POWERS_OF_TWO = 0xaaaaaaaa;

  @VisibleForTesting
  static boolean isEvenLevel(int index) {
    int oneBased = ~~(index + 1); // for GWT
    checkState(oneBased > 0, "negative index");
    return (oneBased & EVEN_POWERS_OF_TWO) > (oneBased & ODD_POWERS_OF_TWO);
  }

  /**

   * is merely copied. Only as the power set is iterated are the individual subsets created, and
   * these subsets themselves occupy only a small constant amount of memory.
   *
   * @param set the set of elements to construct a power set from
   * @return the power set, as an immutable set of immutable sets