Java 类com.google.common.collect.MapMakerInternalMap.ReferenceEntry 实例源码

@Override
public E intern(E sample) {
  while (true) {
    // trying to read the canonical...
    ReferenceEntry<E, Dummy> entry = map.getEntry(sample);
    if (entry != null) {
      E canonical = entry.getKey();
      if (canonical != null) { // only matters if weak/soft keys are used
        return canonical;
      }
    }

    // didn't see it, trying to put it instead...
    Dummy sneaky = map.putIfAbsent(sample, Dummy.VALUE);
    if (sneaky == null) {
      return sample;
    } else {
      /* Someone beat us to it! Trying again...
       *
       * Technically this loop not guaranteed to terminate, so theoretically (extremely
       * unlikely) this thread might starve, but even then, there is always going to be another
       * thread doing progress here.
       */}
  }
}

@Override
public E intern(E sample) {
  while (true) {
    // trying to read the canonical...
    ReferenceEntry<E, Dummy> entry = map.getEntry(sample);
    if (entry != null) {
      E canonical = entry.getKey();
      if (canonical != null) { // only matters if weak/soft keys are used
        return canonical;
      }
    }

    // didn't see it, trying to put it instead...
    Dummy sneaky = map.putIfAbsent(sample, Dummy.VALUE);
    if (sneaky == null) {
      return sample;
    } else {
      /* Someone beat us to it! Trying again...
       *
       * Technically this loop not guaranteed to terminate, so theoretically (extremely
       * unlikely) this thread might starve, but even then, there is always going to be another
       * thread doing progress here.
       */}
  }
}

@Override
public E intern(E sample) {
  while (true) {
    // trying to read the canonical...
    ReferenceEntry<E, Dummy> entry = map.getEntry(sample);
    if (entry != null) {
      E canonical = entry.getKey();
      if (canonical != null) { // only matters if weak/soft keys are used
        return canonical;
      }
    }

    // didn't see it, trying to put it instead...
    Dummy sneaky = map.putIfAbsent(sample, Dummy.VALUE);
    if (sneaky == null) {
      return sample;
    } else {
      /* Someone beat us to it! Trying again...
       *
       * Technically this loop not guaranteed to terminate, so theoretically (extremely
       * unlikely) this thread might starve, but even then, there is always going to be another
       * thread doing progress here.
       */}
  }
}

@Override
public E intern(E sample) {
  while (true) {
    // trying to read the canonical...
    ReferenceEntry<E, Dummy> entry = map.getEntry(sample);
    if (entry != null) {
      E canonical = entry.getKey();
      if (canonical != null) { // only matters if weak/soft keys are used
        return canonical;
      }
    }

    // didn't see it, trying to put it instead...
    Dummy sneaky = map.putIfAbsent(sample, Dummy.VALUE);
    if (sneaky == null) {
      return sample;
    } else {
      /* Someone beat us to it! Trying again...
       *
       * Technically this loop not guaranteed to terminate, so theoretically (extremely
       * unlikely) this thread might starve, but even then, there is always going to be another
       * thread doing progress here.
       */}
  }
}

@Override
public E intern(E sample) {
  while (true) {
    // trying to read the canonical...
    ReferenceEntry<E, Dummy> entry = map.getEntry(sample);
    if (entry != null) {
      E canonical = entry.getKey();
      if (canonical != null) { // only matters if weak/soft keys are used
        return canonical;
      }
    }

    // didn't see it, trying to put it instead...
    Dummy sneaky = map.putIfAbsent(sample, Dummy.VALUE);
    if (sneaky == null) {
      return sample;
    } else {
      /* Someone beat us to it! Trying again...
       *
       * Technically this loop not guaranteed to terminate, so theoretically (extremely
       * unlikely) this thread might starve, but even then, there is always going to be another
       * thread doing progress here.
       */
    }
  }
}

@Override public E intern(E sample) {
  while (true) {
    // trying to read the canonical...
    ReferenceEntry<E, Dummy> entry = map.getEntry(sample);
    if (entry != null) {
      E canonical = entry.getKey();
      if (canonical != null) { // only matters if weak/soft keys are used
        return canonical;
      }
    }

    // didn't see it, trying to put it instead...
    Dummy sneaky = map.putIfAbsent(sample, Dummy.VALUE);
    if (sneaky == null) {
      return sample;
    } else {
      /* Someone beat us to it! Trying again...
       *
       * Technically this loop not guaranteed to terminate, so theoretically (extremely
       * unlikely) this thread might starve, but even then, there is always going to be another
       * thread doing progress here.
       */
    }
  }
}

@Override public E intern(E sample) {
  while (true) {
    // trying to read the canonical...
    ReferenceEntry<E, Dummy> entry = map.getEntry(sample);
    if (entry != null) {
      E canonical = entry.getKey();
      if (canonical != null) { // only matters if weak/soft keys are used
        return canonical;
      }
    }

    // didn't see it, trying to put it instead...
    Dummy sneaky = map.putIfAbsent(sample, Dummy.VALUE);
    if (sneaky == null) {
      return sample;
    } else {
      /* Someone beat us to it! Trying again...
       *
       * Technically this loop not guaranteed to terminate, so theoretically (extremely
       * unlikely) this thread might starve, but even then, there is always going to be another
       * thread doing progress here.
       */
    }
  }
}

@Override public E intern(E sample) {
  while (true) {
    // trying to read the canonical...
    ReferenceEntry<E, Dummy> entry = map.getEntry(sample);
    if (entry != null) {
      E canonical = entry.getKey();
      if (canonical != null) { // only matters if weak/soft keys are used
        return canonical;
      }
    }

    // didn't see it, trying to put it instead...
    Dummy sneaky = map.putIfAbsent(sample, Dummy.VALUE);
    if (sneaky == null) {
      return sample;
    } else {
      /* Someone beat us to it! Trying again...
       *
       * Technically this loop not guaranteed to terminate, so theoretically (extremely
       * unlikely) this thread might starve, but even then, there is always going to be another
       * thread doing progress here.
       */
    }
  }
}

public void testRemovalListener_collected() {
  QueuingRemovalListener<Object, Object> listener =
      new QueuingRemovalListener<Object, Object>();
  MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
      .concurrencyLevel(1)
      .softValues()
      .removalListener(listener));
  Segment<Object, Object> segment = map.segments[0];
  assertTrue(listener.isEmpty());

  Object one = new Object();
  Object two = new Object();
  Object three = new Object();

  map.put(one, two);
  map.put(two, three);
  assertTrue(listener.isEmpty());

  int hash = map.hash(one);
  ReferenceEntry<Object, Object> entry = segment.getEntry(one, hash);
  map.reclaimValue(entry.getValueReference());
  assertNotified(listener, one, two, RemovalCause.COLLECTED);

  assertTrue(listener.isEmpty());
}

@Override public E intern(E sample) {
  while (true) {
    // trying to read the canonical...
    ReferenceEntry<E, Dummy> entry = map.getEntry(sample);
    if (entry != null) {
      E canonical = entry.getKey();
      if (canonical != null) { // only matters if weak/soft keys are used
        return canonical;
      }
    }

    // didn't see it, trying to put it instead...
    Dummy sneaky = map.putIfAbsent(sample, Dummy.VALUE);
    if (sneaky == null) {
      return sample;
    } else {
      /* Someone beat us to it! Trying again...
       *
       * Technically this loop not guaranteed to terminate, so theoretically (extremely
       * unlikely) this thread might starve, but even then, there is always going to be another
       * thread doing progress here.
       */
    }
  }
}

@Override public E intern(E sample) {
  while (true) {
    // trying to read the canonical...
    ReferenceEntry<E, Dummy> entry = map.getEntry(sample);
    if (entry != null) {
      E canonical = entry.getKey();
      if (canonical != null) { // only matters if weak/soft keys are used
        return canonical;
      }
    }

    // didn't see it, trying to put it instead...
    Dummy sneaky = map.putIfAbsent(sample, Dummy.VALUE);
    if (sneaky == null) {
      return sample;
    } else {
      /* Someone beat us to it! Trying again...
       *
       * Technically this loop not guaranteed to terminate, so theoretically (extremely
       * unlikely) this thread might starve, but even then, there is always going to be another
       * thread doing progress here.
       */
    }
  }
}

@Override public E intern(E sample) {
  while (true) {
    // trying to read the canonical...
    ReferenceEntry<E, Dummy> entry = map.getEntry(sample);
    if (entry != null) {
      E canonical = entry.getKey();
      if (canonical != null) { // only matters if weak/soft keys are used
        return canonical;
      }
    }

    // didn't see it, trying to put it instead...
    Dummy sneaky = map.putIfAbsent(sample, Dummy.VALUE);
    if (sneaky == null) {
      return sample;
    } else {
      /* Someone beat us to it! Trying again...
       *
       * Technically this loop not guaranteed to terminate, so theoretically (extremely
       * unlikely) this thread might starve, but even then, there is always going to be another
       * thread doing progress here.
       */
    }
  }
}

@Override public E intern(E sample) {
  while (true) {
    // trying to read the canonical...
    ReferenceEntry<E, Dummy> entry = map.getEntry(sample);
    if (entry != null) {
      E canonical = entry.getKey();
      if (canonical != null) { // only matters if weak/soft keys are used
        return canonical;
      }
    }

    // didn't see it, trying to put it instead...
    Dummy sneaky = map.putIfAbsent(sample, Dummy.VALUE);
    if (sneaky == null) {
      return sample;
    } else {
      /* Someone beat us to it! Trying again...
       *
       * Technically this loop not guaranteed to terminate, so theoretically (extremely
       * unlikely) this thread might starve, but even then, there is always going to be another
       * thread doing progress here.
       */
    }
  }
}

public void testNewEntry() {
  for (MapMaker maker : allEntryTypeMakers()) {
    MapMakerInternalMap<Object, Object> map = makeMap(maker);

    Object keyOne = new Object();
    Object valueOne = new Object();
    int hashOne = map.hash(keyOne);
    ReferenceEntry<Object, Object> entryOne = map.newEntry(keyOne, hashOne, null);
    ValueReference<Object, Object> valueRefOne = map.newValueReference(entryOne, valueOne);
    assertSame(valueOne, valueRefOne.get());
    entryOne.setValueReference(valueRefOne);

    assertSame(keyOne, entryOne.getKey());
    assertEquals(hashOne, entryOne.getHash());
    assertNull(entryOne.getNext());
    assertSame(valueRefOne, entryOne.getValueReference());

    Object keyTwo = new Object();
    Object valueTwo = new Object();
    int hashTwo = map.hash(keyTwo);
    ReferenceEntry<Object, Object> entryTwo = map.newEntry(keyTwo, hashTwo, entryOne);
    ValueReference<Object, Object> valueRefTwo = map.newValueReference(entryTwo, valueTwo);
    assertSame(valueTwo, valueRefTwo.get());
    entryTwo.setValueReference(valueRefTwo);

    assertSame(keyTwo, entryTwo.getKey());
    assertEquals(hashTwo, entryTwo.getHash());
    assertSame(entryOne, entryTwo.getNext());
    assertSame(valueRefTwo, entryTwo.getValueReference());
  }
}

public void testCopyEntry() {
  for (MapMaker maker : allEntryTypeMakers()) {
    MapMakerInternalMap<Object, Object> map = makeMap(maker);

    Object keyOne = new Object();
    Object valueOne = new Object();
    int hashOne = map.hash(keyOne);
    ReferenceEntry<Object, Object> entryOne = map.newEntry(keyOne, hashOne, null);
    entryOne.setValueReference(map.newValueReference(entryOne, valueOne));

    Object keyTwo = new Object();
    Object valueTwo = new Object();
    int hashTwo = map.hash(keyTwo);
    ReferenceEntry<Object, Object> entryTwo = map.newEntry(keyTwo, hashTwo, entryOne);
    entryTwo.setValueReference(map.newValueReference(entryTwo, valueTwo));
    if (map.evictsBySize()) {
      MapMakerInternalMap.connectEvictables(entryOne, entryTwo);
    }
    if (map.expires()) {
      MapMakerInternalMap.connectExpirables(entryOne, entryTwo);
    }
    assertConnected(map, entryOne, entryTwo);

    ReferenceEntry<Object, Object> copyOne = map.copyEntry(entryOne, null);
    assertSame(keyOne, entryOne.getKey());
    assertEquals(hashOne, entryOne.getHash());
    assertNull(entryOne.getNext());
    assertSame(valueOne, copyOne.getValueReference().get());
    assertConnected(map, copyOne, entryTwo);

    ReferenceEntry<Object, Object> copyTwo = map.copyEntry(entryTwo, copyOne);
    assertSame(keyTwo, copyTwo.getKey());
    assertEquals(hashTwo, copyTwo.getHash());
    assertSame(copyOne, copyTwo.getNext());
    assertSame(valueTwo, copyTwo.getValueReference().get());
    assertConnected(map, copyOne, copyTwo);
  }
}

private static <K, V> void assertConnected(
    MapMakerInternalMap<K, V> map, ReferenceEntry<K, V> one, ReferenceEntry<K, V> two) {
  if (map.evictsBySize()) {
    assertSame(two, one.getNextEvictable());
  }
  if (map.expires()) {
    assertSame(two, one.getNextExpirable());
  }
}

public void testSegmentReplace() {
  MapMakerInternalMap<Object, Object> map =
      makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
  Segment<Object, Object> segment = map.segments[0];
  // TODO(fry): check recency ordering

  Object key = new Object();
  int hash = map.hash(key);
  Object oldValue = new Object();
  Object newValue = new Object();
  AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
  int index = hash & (table.length() - 1);

  DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
  DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
  entry.setValueReference(oldValueRef);

  // no entry
  assertNull(segment.replace(key, hash, newValue));
  assertEquals(0, segment.count);

  // same key
  table.set(index, entry);
  segment.count++;
  assertEquals(1, segment.count);
  assertSame(oldValue, segment.get(key, hash));
  assertSame(oldValue, segment.replace(key, hash, newValue));
  assertEquals(1, segment.count);
  assertSame(newValue, segment.get(key, hash));

  // cleared
  entry.setValueReference(oldValueRef);
  assertSame(oldValue, segment.get(key, hash));
  oldValueRef.clear(null);
  assertNull(segment.replace(key, hash, newValue));
  assertEquals(0, segment.count);
  assertNull(segment.get(key, hash));
}

public void testSegmentPut() {
  MapMakerInternalMap<Object, Object> map =
      makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
  Segment<Object, Object> segment = map.segments[0];
  // TODO(fry): check recency ordering

  Object key = new Object();
  int hash = map.hash(key);
  Object oldValue = new Object();
  Object newValue = new Object();

  // no entry
  assertEquals(0, segment.count);
  assertNull(segment.put(key, hash, oldValue, false));
  assertEquals(1, segment.count);

  // same key
  assertSame(oldValue, segment.put(key, hash, newValue, false));
  assertEquals(1, segment.count);
  assertSame(newValue, segment.get(key, hash));

  // cleared
  ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
  DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
  entry.setValueReference(oldValueRef);
  assertSame(oldValue, segment.get(key, hash));
  oldValueRef.clear(null);
  assertNull(segment.put(key, hash, newValue, false));
  assertEquals(1, segment.count);
  assertSame(newValue, segment.get(key, hash));
}

public void testSegmentPutIfAbsent() {
  MapMakerInternalMap<Object, Object> map =
      makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
  Segment<Object, Object> segment = map.segments[0];
  // TODO(fry): check recency ordering

  Object key = new Object();
  int hash = map.hash(key);
  Object oldValue = new Object();
  Object newValue = new Object();

  // no entry
  assertEquals(0, segment.count);
  assertNull(segment.put(key, hash, oldValue, true));
  assertEquals(1, segment.count);

  // same key
  assertSame(oldValue, segment.put(key, hash, newValue, true));
  assertEquals(1, segment.count);
  assertSame(oldValue, segment.get(key, hash));

  // cleared
  ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
  DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
  entry.setValueReference(oldValueRef);
  assertSame(oldValue, segment.get(key, hash));
  oldValueRef.clear(null);
  assertNull(segment.put(key, hash, newValue, true));
  assertEquals(1, segment.count);
  assertSame(newValue, segment.get(key, hash));
}

public void testSegmentRemove() {
  MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().concurrencyLevel(1));
  Segment<Object, Object> segment = map.segments[0];

  Object key = new Object();
  int hash = map.hash(key);
  Object oldValue = new Object();
  AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
  int index = hash & (table.length() - 1);

  DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
  DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
  entry.setValueReference(oldValueRef);

  // no entry
  assertEquals(0, segment.count);
  assertNull(segment.remove(key, hash));
  assertEquals(0, segment.count);

  // same key
  table.set(index, entry);
  segment.count++;
  assertEquals(1, segment.count);
  assertSame(oldValue, segment.get(key, hash));
  assertSame(oldValue, segment.remove(key, hash));
  assertEquals(0, segment.count);
  assertNull(segment.get(key, hash));

  // cleared
  table.set(index, entry);
  segment.count++;
  assertEquals(1, segment.count);
  assertSame(oldValue, segment.get(key, hash));
  oldValueRef.clear(null);
  assertNull(segment.remove(key, hash));
  assertEquals(0, segment.count);
  assertNull(segment.get(key, hash));
}

public void testExpand() {
  MapMakerInternalMap<Object, Object> map =
      makeMap(createMapMaker().concurrencyLevel(1).initialCapacity(1));
  Segment<Object, Object> segment = map.segments[0];
  assertEquals(1, segment.table.length());

  // manually add elements to avoid expansion
  int originalCount = 1024;
  ReferenceEntry<Object, Object> entry = null;
  for (int i = 0; i < originalCount; i++) {
    Object key = new Object();
    Object value = new Object();
    int hash = map.hash(key);
    // chain all entries together as we only have a single bucket
    entry = map.newEntry(key, hash, entry);
    ValueReference<Object, Object> valueRef = map.newValueReference(entry, value);
    entry.setValueReference(valueRef);
  }
  segment.table.set(0, entry);
  segment.count = originalCount;
  ImmutableMap<Object, Object> originalMap = ImmutableMap.copyOf(map);
  assertEquals(originalCount, originalMap.size());
  assertEquals(originalMap, map);

  for (int i = 1; i <= originalCount * 2; i *= 2) {
    if (i > 1) {
      segment.expand();
    }
    assertEquals(i, segment.table.length());
    assertEquals(originalCount, countLiveEntries(map));
    assertEquals(originalCount, segment.count);
    assertEquals(originalMap, map);
  }
}

private static <K, V> int countLiveEntries(MapMakerInternalMap<K, V> map) {
  int result = 0;
  for (Segment<K, V> segment : map.segments) {
    AtomicReferenceArray<ReferenceEntry<K, V>> table = segment.table;
    for (int i = 0; i < table.length(); i++) {
      for (ReferenceEntry<K, V> e = table.get(i); e != null; e = e.getNext()) {
        if (map.isLive(e)) {
          result++;
        }
      }
    }
  }
  return result;
}

public void testClear() {
  MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
      .concurrencyLevel(1)
      .initialCapacity(1)
      .maximumSize(SMALL_MAX_SIZE)
      .expireAfterWrite(99999, SECONDS));
  Segment<Object, Object> segment = map.segments[0];
  AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
  assertEquals(1, table.length());

  Object key = new Object();
  Object value = new Object();
  int hash = map.hash(key);
  DummyEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
  segment.recordWrite(entry);
  segment.table.set(0, entry);
  segment.readCount.incrementAndGet();
  segment.count = 1;

  assertSame(entry, table.get(0));
  assertSame(entry, segment.evictionQueue.peek());
  assertSame(entry, segment.expirationQueue.peek());

  segment.clear();
  assertNull(table.get(0));
  assertTrue(segment.evictionQueue.isEmpty());
  assertTrue(segment.expirationQueue.isEmpty());
  assertEquals(0, segment.readCount.get());
  assertEquals(0, segment.count);
}

public void testRemoveEntry() {
  MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
      .concurrencyLevel(1)
      .initialCapacity(1)
      .maximumSize(SMALL_MAX_SIZE)
      .expireAfterWrite(99999, SECONDS)
      .removalListener(new CountingRemovalListener<Object, Object>()));
  Segment<Object, Object> segment = map.segments[0];
  AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
  assertEquals(1, table.length());

  Object key = new Object();
  Object value = new Object();
  int hash = map.hash(key);
  DummyEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);

  // remove absent
  assertFalse(segment.removeEntry(entry, hash, RemovalCause.COLLECTED));

  // remove live
  segment.recordWrite(entry);
  table.set(0, entry);
  segment.count = 1;
  assertTrue(segment.removeEntry(entry, hash, RemovalCause.COLLECTED));
  assertNotificationEnqueued(map, key, value);
  assertTrue(map.removalNotificationQueue.isEmpty());
  assertFalse(segment.evictionQueue.contains(entry));
  assertFalse(segment.expirationQueue.contains(entry));
  assertEquals(0, segment.count);
  assertNull(table.get(0));
}

static <K, V> void checkAndDrainRecencyQueue(MapMakerInternalMap<K, V> map,
    Segment<K, V> segment, List<ReferenceEntry<K, V>> reads) {
  if (map.evictsBySize() || map.expiresAfterAccess()) {
    assertSameEntries(reads, ImmutableList.copyOf(segment.recencyQueue));
  }
  segment.drainRecencyQueue();
}

static <K, V> void checkEvictionQueues(MapMakerInternalMap<K, V> map,
    Segment<K, V> segment, List<ReferenceEntry<K, V>> readOrder,
    List<ReferenceEntry<K, V>> writeOrder) {
  if (map.evictsBySize()) {
    assertSameEntries(readOrder, ImmutableList.copyOf(segment.evictionQueue));
  }
  if (map.expiresAfterAccess()) {
    assertSameEntries(readOrder, ImmutableList.copyOf(segment.expirationQueue));
  }
  if (map.expiresAfterWrite()) {
    assertSameEntries(writeOrder, ImmutableList.copyOf(segment.expirationQueue));
  }
}

private static <K, V> void assertSameEntries(List<ReferenceEntry<K, V>> expectedEntries,
    List<ReferenceEntry<K, V>> actualEntries) {
  int size = expectedEntries.size();
  assertEquals(size, actualEntries.size());
  for (int i = 0; i < size; i++) {
    ReferenceEntry<K, V> expectedEntry = expectedEntries.get(0);
    ReferenceEntry<K, V> actualEntry = actualEntries.get(0);
    assertSame(expectedEntry.getKey(), actualEntry.getKey());
    assertSame(expectedEntry.getValueReference().get(), actualEntry.getValueReference().get());
  }
}

public void testEvictEntries() {
  int maxSize = 10;
  MapMakerInternalMap<Object, Object> map =
      makeMap(createMapMaker().concurrencyLevel(1).maximumSize(maxSize));
  Segment<Object, Object> segment = map.segments[0];

  // manually add elements to avoid eviction
  int originalCount = 1024;
  ReferenceEntry<Object, Object> entry = null;
  LinkedHashMap<Object, Object> originalMap = Maps.newLinkedHashMap();
  for (int i = 0; i < originalCount; i++) {
    Object key = new Object();
    Object value = new Object();
    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
    int hash = map.hash(key);
    int index = hash & (table.length() - 1);
    ReferenceEntry<Object, Object> first = table.get(index);
    entry = map.newEntry(key, hash, first);
    ValueReference<Object, Object> valueRef = map.newValueReference(entry, value);
    entry.setValueReference(valueRef);
    segment.recordWrite(entry);
    table.set(index, entry);
    originalMap.put(key, value);
  }
  segment.count = originalCount;
  assertEquals(originalCount, originalMap.size());
  assertEquals(originalMap, map);

  for (int i = maxSize - 1; i < originalCount; i++) {
    assertTrue(segment.evictEntries());
    Iterator<Object> it = originalMap.keySet().iterator();
    it.next();
    it.remove();
    assertEquals(originalMap, map);
  }
  assertFalse(segment.evictEntries());
}

public void testDrainKeyReferenceQueueOnWrite() {
  for (MapMaker maker : allKeyValueStrengthMakers()) {
    MapMakerInternalMap<Object, Object> map =
        makeMap(maker.concurrencyLevel(1));
    if (map.usesKeyReferences()) {
      Segment<Object, Object> segment = map.segments[0];

      Object keyOne = new Object();
      int hashOne = map.hash(keyOne);
      Object valueOne = new Object();
      Object keyTwo = new Object();
      Object valueTwo = new Object();

      map.put(keyOne, valueOne);
      ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);

      @SuppressWarnings("unchecked")
      Reference<Object> reference = (Reference) entry;
      reference.enqueue();

      map.put(keyTwo, valueTwo);
      assertFalse(map.containsKey(keyOne));
      assertFalse(map.containsValue(valueOne));
      assertNull(map.get(keyOne));
      assertEquals(1, map.size());
      assertNull(segment.keyReferenceQueue.poll());
    }
  }
}

public void testDrainValueReferenceQueueOnWrite() {
  for (MapMaker maker : allKeyValueStrengthMakers()) {
    MapMakerInternalMap<Object, Object> map =
        makeMap(maker.concurrencyLevel(1));
    if (map.usesValueReferences()) {
      Segment<Object, Object> segment = map.segments[0];

      Object keyOne = new Object();
      int hashOne = map.hash(keyOne);
      Object valueOne = new Object();
      Object keyTwo = new Object();
      Object valueTwo = new Object();

      map.put(keyOne, valueOne);
      ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
      ValueReference<Object, Object> valueReference = entry.getValueReference();

      @SuppressWarnings("unchecked")
      Reference<Object> reference = (Reference) valueReference;
      reference.enqueue();

      map.put(keyTwo, valueTwo);
      assertFalse(map.containsKey(keyOne));
      assertFalse(map.containsValue(valueOne));
      assertNull(map.get(keyOne));
      assertEquals(1, map.size());
      assertNull(segment.valueReferenceQueue.poll());
    }
  }
}

public void testDrainKeyReferenceQueueOnRead() {
  for (MapMaker maker : allKeyValueStrengthMakers()) {
    MapMakerInternalMap<Object, Object> map =
        makeMap(maker.concurrencyLevel(1));
    if (map.usesKeyReferences()) {
      Segment<Object, Object> segment = map.segments[0];

      Object keyOne = new Object();
      int hashOne = map.hash(keyOne);
      Object valueOne = new Object();
      Object keyTwo = new Object();

      map.put(keyOne, valueOne);
      ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);

      @SuppressWarnings("unchecked")
      Reference<Object> reference = (Reference) entry;
      reference.enqueue();

      for (int i = 0; i < SMALL_MAX_SIZE; i++) {
        map.get(keyTwo);
      }
      assertFalse(map.containsKey(keyOne));
      assertFalse(map.containsValue(valueOne));
      assertNull(map.get(keyOne));
      assertEquals(0, map.size());
      assertNull(segment.keyReferenceQueue.poll());
    }
  }
}

public void testDrainValueReferenceQueueOnRead() {
  for (MapMaker maker : allKeyValueStrengthMakers()) {
    MapMakerInternalMap<Object, Object> map =
        makeMap(maker.concurrencyLevel(1));
    if (map.usesValueReferences()) {
      Segment<Object, Object> segment = map.segments[0];

      Object keyOne = new Object();
      int hashOne = map.hash(keyOne);
      Object valueOne = new Object();
      Object keyTwo = new Object();

      map.put(keyOne, valueOne);
      ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
      ValueReference<Object, Object> valueReference = entry.getValueReference();

      @SuppressWarnings("unchecked")
      Reference<Object> reference = (Reference) valueReference;
      reference.enqueue();

      for (int i = 0; i < SMALL_MAX_SIZE; i++) {
        map.get(keyTwo);
      }
      assertFalse(map.containsKey(keyOne));
      assertFalse(map.containsValue(valueOne));
      assertNull(map.get(keyOne));
      assertEquals(0, map.size());
      assertNull(segment.valueReferenceQueue.poll());
    }
  }
}

private static <K, V> DummyEntry<K, V> createDummyEntry(
    K key, int hash, V value, ReferenceEntry<K, V> next) {
  DummyEntry<K, V> entry = DummyEntry.create(key, hash, next);
  DummyValueReference<K, V> valueRef = DummyValueReference.create(value, entry);
  entry.setValueReference(valueRef);
  return entry;
}

public void testComputePartiallyCollectedKey() throws ExecutionException {
  MapMaker maker = createMapMaker().concurrencyLevel(1);
  CountingFunction computingFunction = new CountingFunction();
  ComputingConcurrentHashMap<Object, Object> map = makeComputingMap(maker, computingFunction);
  Segment<Object, Object> segment = map.segments[0];
  AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
  assertEquals(0, computingFunction.getCount());

  Object key = new Object();
  int hash = map.hash(key);
  Object value = new Object();
  int index = hash & (table.length() - 1);

  DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
  DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry);
  entry.setValueReference(valueRef);
  table.set(index, entry);
  segment.count++;

  assertSame(value, map.getOrCompute(key));
  assertEquals(0, computingFunction.getCount());
  assertEquals(1, segment.count);

  entry.clearKey();
  assertNotSame(value, map.getOrCompute(key));
  assertEquals(1, computingFunction.getCount());
  assertEquals(2, segment.count);
}

public void testComputePartiallyCollectedValue() throws ExecutionException {
  MapMaker maker = createMapMaker().concurrencyLevel(1);
  CountingFunction computingFunction = new CountingFunction();
  ComputingConcurrentHashMap<Object, Object> map = makeComputingMap(maker, computingFunction);
  Segment<Object, Object> segment = map.segments[0];
  AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
  assertEquals(0, computingFunction.getCount());

  Object key = new Object();
  int hash = map.hash(key);
  Object value = new Object();
  int index = hash & (table.length() - 1);

  DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
  DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry);
  entry.setValueReference(valueRef);
  table.set(index, entry);
  segment.count++;

  assertSame(value, map.getOrCompute(key));
  assertEquals(0, computingFunction.getCount());
  assertEquals(1, segment.count);

  valueRef.clear(null);
  assertNotSame(value, map.getOrCompute(key));
  assertEquals(1, computingFunction.getCount());
  assertEquals(1, segment.count);
}

public void testSegmentGetAndContains() {
  MapMakerInternalMap<Object, Object> map =
      makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
  Segment<Object, Object> segment = map.segments[0];
  // TODO(fry): check recency ordering

  Object key = new Object();
  int hash = map.hash(key);
  Object value = new Object();
  AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
  int index = hash & (table.length() - 1);

  ReferenceEntry<Object, Object> entry = map.newEntry(key, hash, null);
  ValueReference<Object, Object> valueRef = map.newValueReference(entry, value);
  entry.setValueReference(valueRef);

  assertNull(segment.get(key, hash));

  // count == 0
  table.set(index, entry);
  assertNull(segment.get(key, hash));
  assertFalse(segment.containsKey(key, hash));
  assertFalse(segment.containsValue(value));

  // count == 1
  segment.count++;
  assertSame(value, segment.get(key, hash));
  assertTrue(segment.containsKey(key, hash));
  assertTrue(segment.containsValue(value));
  // don't see absent values now that count > 0
  assertNull(segment.get(new Object(), hash));

  // null key
  DummyEntry<Object, Object> nullEntry = DummyEntry.create(null, hash, entry);
  Object nullValue = new Object();
  ValueReference<Object, Object> nullValueRef = map.newValueReference(nullEntry, nullValue);
  nullEntry.setValueReference(nullValueRef);
  table.set(index, nullEntry);
  // skip the null key
  assertSame(value, segment.get(key, hash));
  assertTrue(segment.containsKey(key, hash));
  assertTrue(segment.containsValue(value));
  assertFalse(segment.containsValue(nullValue));

  // hash collision
  DummyEntry<Object, Object> dummy = DummyEntry.create(new Object(), hash, entry);
  Object dummyValue = new Object();
  ValueReference<Object, Object> dummyValueRef = map.newValueReference(dummy, dummyValue);
  dummy.setValueReference(dummyValueRef);
  table.set(index, dummy);
  assertSame(value, segment.get(key, hash));
  assertTrue(segment.containsKey(key, hash));
  assertTrue(segment.containsValue(value));
  assertTrue(segment.containsValue(dummyValue));

  // key collision
  dummy = DummyEntry.create(key, hash, entry);
  dummyValue = new Object();
  dummyValueRef = map.newValueReference(dummy, dummyValue);
  dummy.setValueReference(dummyValueRef);
  table.set(index, dummy);
  // returns the most recent entry
  assertSame(dummyValue, segment.get(key, hash));
  assertTrue(segment.containsKey(key, hash));
  assertTrue(segment.containsValue(value));
  assertTrue(segment.containsValue(dummyValue));

  // expired
  dummy.setExpirationTime(0);
  assertNull(segment.get(key, hash));
  assertFalse(segment.containsKey(key, hash));
  assertTrue(segment.containsValue(value));
  assertFalse(segment.containsValue(dummyValue));
}

public void testSegmentReplaceValue() {
  MapMakerInternalMap<Object, Object> map =
      makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
  Segment<Object, Object> segment = map.segments[0];
  // TODO(fry): check recency ordering

  Object key = new Object();
  int hash = map.hash(key);
  Object oldValue = new Object();
  Object newValue = new Object();
  AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
  int index = hash & (table.length() - 1);

  DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
  DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
  entry.setValueReference(oldValueRef);

  // no entry
  assertFalse(segment.replace(key, hash, oldValue, newValue));
  assertEquals(0, segment.count);

  // same value
  table.set(index, entry);
  segment.count++;
  assertEquals(1, segment.count);
  assertSame(oldValue, segment.get(key, hash));
  assertTrue(segment.replace(key, hash, oldValue, newValue));
  assertEquals(1, segment.count);
  assertSame(newValue, segment.get(key, hash));

  // different value
  assertFalse(segment.replace(key, hash, oldValue, newValue));
  assertEquals(1, segment.count);
  assertSame(newValue, segment.get(key, hash));

  // cleared
  entry.setValueReference(oldValueRef);
  assertSame(oldValue, segment.get(key, hash));
  oldValueRef.clear(null);
  assertFalse(segment.replace(key, hash, oldValue, newValue));
  assertEquals(0, segment.count);
  assertNull(segment.get(key, hash));
}

public void testSegmentRemoveValue() {
  MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().concurrencyLevel(1));
  Segment<Object, Object> segment = map.segments[0];

  Object key = new Object();
  int hash = map.hash(key);
  Object oldValue = new Object();
  Object newValue = new Object();
  AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
  int index = hash & (table.length() - 1);

  DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
  DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry);
  entry.setValueReference(oldValueRef);

  // no entry
  assertEquals(0, segment.count);
  assertNull(segment.remove(key, hash));
  assertEquals(0, segment.count);

  // same value
  table.set(index, entry);
  segment.count++;
  assertEquals(1, segment.count);
  assertSame(oldValue, segment.get(key, hash));
  assertTrue(segment.remove(key, hash, oldValue));
  assertEquals(0, segment.count);
  assertNull(segment.get(key, hash));

  // different value
  table.set(index, entry);
  segment.count++;
  assertEquals(1, segment.count);
  assertSame(oldValue, segment.get(key, hash));
  assertFalse(segment.remove(key, hash, newValue));
  assertEquals(1, segment.count);
  assertSame(oldValue, segment.get(key, hash));

  // cleared
  assertSame(oldValue, segment.get(key, hash));
  oldValueRef.clear(null);
  assertFalse(segment.remove(key, hash, oldValue));
  assertEquals(0, segment.count);
  assertNull(segment.get(key, hash));
}

public void testReclaimKey() {
  CountingRemovalListener<Object, Object> listener =
      new CountingRemovalListener<Object, Object>();
  MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()
      .concurrencyLevel(1)
      .initialCapacity(1)
      .maximumSize(SMALL_MAX_SIZE)
      .expireAfterWrite(99999, SECONDS)
      .removalListener(listener));
  Segment<Object, Object> segment = map.segments[0];
  AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
  assertEquals(1, table.length());

  // create 3 objects and chain them together
  Object keyOne = new Object();
  Object valueOne = new Object();
  int hashOne = map.hash(keyOne);
  DummyEntry<Object, Object> entryOne = createDummyEntry(keyOne, hashOne, valueOne, null);
  Object keyTwo = new Object();
  Object valueTwo = new Object();
  int hashTwo = map.hash(keyTwo);
  DummyEntry<Object, Object> entryTwo = createDummyEntry(keyTwo, hashTwo, valueTwo, entryOne);
  Object keyThree = new Object();
  Object valueThree = new Object();
  int hashThree = map.hash(keyThree);
  DummyEntry<Object, Object> entryThree =
      createDummyEntry(keyThree, hashThree, valueThree, entryTwo);

  // absent
  assertEquals(0, listener.getCount());
  assertFalse(segment.reclaimKey(entryOne, hashOne));
  assertEquals(0, listener.getCount());
  table.set(0, entryOne);
  assertFalse(segment.reclaimKey(entryTwo, hashTwo));
  assertEquals(0, listener.getCount());
  table.set(0, entryTwo);
  assertFalse(segment.reclaimKey(entryThree, hashThree));
  assertEquals(0, listener.getCount());

  // present
  table.set(0, entryOne);
  segment.count = 1;
  assertTrue(segment.reclaimKey(entryOne, hashOne));
  assertEquals(1, listener.getCount());
  assertSame(keyOne, listener.getLastEvictedKey());
  assertSame(valueOne, listener.getLastEvictedValue());
  assertTrue(map.removalNotificationQueue.isEmpty());
  assertFalse(segment.evictionQueue.contains(entryOne));
  assertFalse(segment.expirationQueue.contains(entryOne));
  assertEquals(0, segment.count);
  assertNull(table.get(0));
}

public void testRemoveFromChain() {
  MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().concurrencyLevel(1));
  Segment<Object, Object> segment = map.segments[0];

  // create 3 objects and chain them together
  Object keyOne = new Object();
  Object valueOne = new Object();
  int hashOne = map.hash(keyOne);
  DummyEntry<Object, Object> entryOne = createDummyEntry(keyOne, hashOne, valueOne, null);
  Object keyTwo = new Object();
  Object valueTwo = new Object();
  int hashTwo = map.hash(keyTwo);
  DummyEntry<Object, Object> entryTwo = createDummyEntry(keyTwo, hashTwo, valueTwo, entryOne);
  Object keyThree = new Object();
  Object valueThree = new Object();
  int hashThree = map.hash(keyThree);
  DummyEntry<Object, Object> entryThree =
      createDummyEntry(keyThree, hashThree, valueThree, entryTwo);

  // alone
  assertNull(segment.removeFromChain(entryOne, entryOne));

  // head
  assertSame(entryOne, segment.removeFromChain(entryTwo, entryTwo));

  // middle
  ReferenceEntry<Object, Object> newFirst = segment.removeFromChain(entryThree, entryTwo);
  assertSame(keyThree, newFirst.getKey());
  assertSame(valueThree, newFirst.getValueReference().get());
  assertEquals(hashThree, newFirst.getHash());
  assertSame(entryOne, newFirst.getNext());

  // tail (remaining entries are copied in reverse order)
  newFirst = segment.removeFromChain(entryThree, entryOne);
  assertSame(keyTwo, newFirst.getKey());
  assertSame(valueTwo, newFirst.getValueReference().get());
  assertEquals(hashTwo, newFirst.getHash());
  newFirst = newFirst.getNext();
  assertSame(keyThree, newFirst.getKey());
  assertSame(valueThree, newFirst.getValueReference().get());
  assertEquals(hashThree, newFirst.getHash());
  assertNull(newFirst.getNext());
}