1 /* 2 * Copyright (C) 2011 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect; 18 19 import static com.google.common.collect.Lists.newArrayList; 20 import static com.google.common.collect.MapMakerInternalMap.DISCARDING_QUEUE; 21 import static com.google.common.collect.MapMakerInternalMap.DRAIN_THRESHOLD; 22 import static com.google.common.collect.MapMakerInternalMap.nullEntry; 23 import static com.google.common.collect.MapMakerInternalMap.unset; 24 import static java.util.concurrent.TimeUnit.SECONDS; 25 26 import com.google.common.base.Equivalence; 27 import com.google.common.base.Ticker; 28 import com.google.common.collect.MapMaker.RemovalCause; 29 import com.google.common.collect.MapMaker.RemovalListener; 30 import com.google.common.collect.MapMaker.RemovalNotification; 31 import com.google.common.collect.MapMakerInternalMap.EntryFactory; 32 import com.google.common.collect.MapMakerInternalMap.ReferenceEntry; 33 import com.google.common.collect.MapMakerInternalMap.Segment; 34 import com.google.common.collect.MapMakerInternalMap.Strength; 35 import com.google.common.collect.MapMakerInternalMap.ValueReference; 36 import com.google.common.testing.NullPointerTester; 37 38 import junit.framework.TestCase; 39 40 import java.lang.ref.Reference; 41 import java.lang.ref.ReferenceQueue; 42 import java.util.Iterator; 43 import java.util.LinkedHashMap; 44 import java.util.List; 45 import java.util.Map; 46 import java.util.Random; 47 import java.util.concurrent.ConcurrentLinkedQueue; 48 import java.util.concurrent.TimeUnit; 49 import java.util.concurrent.atomic.AtomicInteger; 50 import java.util.concurrent.atomic.AtomicReferenceArray; 51 52 /** 53 * @author Charles Fry 54 */ 55 @SuppressWarnings("deprecation") // many tests of deprecated methods 56 public class MapMakerInternalMapTest extends TestCase { 57 58 static final int SMALL_MAX_SIZE = DRAIN_THRESHOLD * 5; 59 makeMap(GenericMapMaker<K, V> maker)60 private static <K, V> MapMakerInternalMap<K, V> makeMap(GenericMapMaker<K, V> maker) { 61 return new MapMakerInternalMap<K, V>((MapMaker) maker); 62 } 63 makeMap(MapMaker maker)64 private static <K, V> MapMakerInternalMap<K, V> makeMap(MapMaker maker) { 65 return new MapMakerInternalMap<K, V>(maker); 66 } 67 createMapMaker()68 private static MapMaker createMapMaker() { 69 MapMaker maker = new MapMaker(); 70 maker.useCustomMap = true; 71 return maker; 72 } 73 74 // constructor tests 75 testDefaults()76 public void testDefaults() { 77 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker()); 78 79 assertSame(Strength.STRONG, map.keyStrength); 80 assertSame(Strength.STRONG, map.valueStrength); 81 assertSame(map.keyStrength.defaultEquivalence(), map.keyEquivalence); 82 assertSame(map.valueStrength.defaultEquivalence(), map.valueEquivalence); 83 84 assertEquals(0, map.expireAfterAccessNanos); 85 assertEquals(0, map.expireAfterWriteNanos); 86 assertEquals(MapMaker.UNSET_INT, map.maximumSize); 87 88 assertSame(EntryFactory.STRONG, map.entryFactory); 89 assertSame(MapMaker.NullListener.INSTANCE, map.removalListener); 90 assertSame(DISCARDING_QUEUE, map.removalNotificationQueue); 91 assertSame(Ticker.systemTicker(), map.ticker); 92 93 assertEquals(4, map.concurrencyLevel); 94 95 // concurrency level 96 assertEquals(4, map.segments.length); 97 // initial capacity / concurrency level 98 assertEquals(16 / map.segments.length, map.segments[0].table.length()); 99 100 assertFalse(map.evictsBySize()); 101 assertFalse(map.expires()); 102 assertFalse(map.expiresAfterWrite()); 103 assertFalse(map.expiresAfterAccess()); 104 } 105 testSetKeyEquivalence()106 public void testSetKeyEquivalence() { 107 Equivalence<Object> testEquivalence = new Equivalence<Object>() { 108 @Override 109 protected boolean doEquivalent(Object a, Object b) { 110 return false; 111 } 112 113 @Override 114 protected int doHash(Object t) { 115 return 0; 116 } 117 }; 118 119 MapMakerInternalMap<Object, Object> map = 120 makeMap(createMapMaker().keyEquivalence(testEquivalence)); 121 assertSame(testEquivalence, map.keyEquivalence); 122 assertSame(map.valueStrength.defaultEquivalence(), map.valueEquivalence); 123 } 124 testSetValueEquivalence()125 public void testSetValueEquivalence() { 126 Equivalence<Object> testEquivalence = new Equivalence<Object>() { 127 @Override 128 protected boolean doEquivalent(Object a, Object b) { 129 return false; 130 } 131 132 @Override 133 protected int doHash(Object t) { 134 return 0; 135 } 136 }; 137 138 MapMakerInternalMap<Object, Object> map = 139 makeMap(createMapMaker().valueEquivalence(testEquivalence)); 140 assertSame(testEquivalence, map.valueEquivalence); 141 assertSame(map.keyStrength.defaultEquivalence(), map.keyEquivalence); 142 } 143 testSetConcurrencyLevel()144 public void testSetConcurrencyLevel() { 145 // round up to nearest power of two 146 147 checkConcurrencyLevel(1, 1); 148 checkConcurrencyLevel(2, 2); 149 checkConcurrencyLevel(3, 4); 150 checkConcurrencyLevel(4, 4); 151 checkConcurrencyLevel(5, 8); 152 checkConcurrencyLevel(6, 8); 153 checkConcurrencyLevel(7, 8); 154 checkConcurrencyLevel(8, 8); 155 } 156 checkConcurrencyLevel(int concurrencyLevel, int segmentCount)157 private static void checkConcurrencyLevel(int concurrencyLevel, int segmentCount) { 158 MapMakerInternalMap<Object, Object> map = 159 makeMap(createMapMaker().concurrencyLevel(concurrencyLevel)); 160 assertEquals(segmentCount, map.segments.length); 161 } 162 testSetInitialCapacity()163 public void testSetInitialCapacity() { 164 // share capacity over each segment, then round up to nearest power of two 165 166 checkInitialCapacity(1, 0, 1); 167 checkInitialCapacity(1, 1, 1); 168 checkInitialCapacity(1, 2, 2); 169 checkInitialCapacity(1, 3, 4); 170 checkInitialCapacity(1, 4, 4); 171 checkInitialCapacity(1, 5, 8); 172 checkInitialCapacity(1, 6, 8); 173 checkInitialCapacity(1, 7, 8); 174 checkInitialCapacity(1, 8, 8); 175 176 checkInitialCapacity(2, 0, 1); 177 checkInitialCapacity(2, 1, 1); 178 checkInitialCapacity(2, 2, 1); 179 checkInitialCapacity(2, 3, 2); 180 checkInitialCapacity(2, 4, 2); 181 checkInitialCapacity(2, 5, 4); 182 checkInitialCapacity(2, 6, 4); 183 checkInitialCapacity(2, 7, 4); 184 checkInitialCapacity(2, 8, 4); 185 186 checkInitialCapacity(4, 0, 1); 187 checkInitialCapacity(4, 1, 1); 188 checkInitialCapacity(4, 2, 1); 189 checkInitialCapacity(4, 3, 1); 190 checkInitialCapacity(4, 4, 1); 191 checkInitialCapacity(4, 5, 2); 192 checkInitialCapacity(4, 6, 2); 193 checkInitialCapacity(4, 7, 2); 194 checkInitialCapacity(4, 8, 2); 195 } 196 checkInitialCapacity( int concurrencyLevel, int initialCapacity, int segmentSize)197 private static void checkInitialCapacity( 198 int concurrencyLevel, int initialCapacity, int segmentSize) { 199 MapMakerInternalMap<Object, Object> map = makeMap( 200 createMapMaker().concurrencyLevel(concurrencyLevel).initialCapacity(initialCapacity)); 201 for (int i = 0; i < map.segments.length; i++) { 202 assertEquals(segmentSize, map.segments[i].table.length()); 203 } 204 } 205 testSetMaximumSize()206 public void testSetMaximumSize() { 207 // vary maximumSize wrt concurrencyLevel 208 209 for (int maxSize = 1; maxSize < 8; maxSize++) { 210 checkMaximumSize(1, 8, maxSize); 211 checkMaximumSize(2, 8, maxSize); 212 checkMaximumSize(4, 8, maxSize); 213 checkMaximumSize(8, 8, maxSize); 214 } 215 216 checkMaximumSize(1, 8, Integer.MAX_VALUE); 217 checkMaximumSize(2, 8, Integer.MAX_VALUE); 218 checkMaximumSize(4, 8, Integer.MAX_VALUE); 219 checkMaximumSize(8, 8, Integer.MAX_VALUE); 220 221 // vary initial capacity wrt maximumSize 222 223 for (int capacity = 0; capacity < 8; capacity++) { 224 checkMaximumSize(1, capacity, 4); 225 checkMaximumSize(2, capacity, 4); 226 checkMaximumSize(4, capacity, 4); 227 checkMaximumSize(8, capacity, 4); 228 } 229 } 230 checkMaximumSize(int concurrencyLevel, int initialCapacity, int maxSize)231 private static void checkMaximumSize(int concurrencyLevel, int initialCapacity, int maxSize) { 232 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker() 233 .concurrencyLevel(concurrencyLevel) 234 .initialCapacity(initialCapacity) 235 .maximumSize(maxSize)); 236 int totalCapacity = 0; 237 for (int i = 0; i < map.segments.length; i++) { 238 totalCapacity += map.segments[i].maxSegmentSize; 239 } 240 assertTrue("totalCapcity=" + totalCapacity + ", maxSize=" + maxSize, totalCapacity <= maxSize); 241 } 242 testSetWeakKeys()243 public void testSetWeakKeys() { 244 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().weakKeys()); 245 checkStrength(map, Strength.WEAK, Strength.STRONG); 246 assertSame(EntryFactory.WEAK, map.entryFactory); 247 } 248 249 @SuppressWarnings("deprecation") testSetSoftKeys()250 public void testSetSoftKeys() { 251 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().softKeys()); 252 checkStrength(map, Strength.SOFT, Strength.STRONG); 253 assertSame(EntryFactory.SOFT, map.entryFactory); 254 } 255 testSetWeakValues()256 public void testSetWeakValues() { 257 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().weakValues()); 258 checkStrength(map, Strength.STRONG, Strength.WEAK); 259 assertSame(EntryFactory.STRONG, map.entryFactory); 260 } 261 testSetSoftValues()262 public void testSetSoftValues() { 263 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().softValues()); 264 checkStrength(map, Strength.STRONG, Strength.SOFT); 265 assertSame(EntryFactory.STRONG, map.entryFactory); 266 } 267 checkStrength( MapMakerInternalMap<Object, Object> map, Strength keyStrength, Strength valueStrength)268 private static void checkStrength( 269 MapMakerInternalMap<Object, Object> map, Strength keyStrength, Strength valueStrength) { 270 assertSame(keyStrength, map.keyStrength); 271 assertSame(valueStrength, map.valueStrength); 272 assertSame(keyStrength.defaultEquivalence(), map.keyEquivalence); 273 assertSame(valueStrength.defaultEquivalence(), map.valueEquivalence); 274 } 275 testSetExpireAfterWrite()276 public void testSetExpireAfterWrite() { 277 long duration = 42; 278 TimeUnit unit = SECONDS; 279 MapMakerInternalMap<Object, Object> map = 280 makeMap(createMapMaker().expireAfterWrite(duration, unit)); 281 assertEquals(unit.toNanos(duration), map.expireAfterWriteNanos); 282 } 283 testSetExpireAfterAccess()284 public void testSetExpireAfterAccess() { 285 long duration = 42; 286 TimeUnit unit = SECONDS; 287 MapMakerInternalMap<Object, Object> map = 288 makeMap(createMapMaker().expireAfterAccess(duration, unit)); 289 assertEquals(unit.toNanos(duration), map.expireAfterAccessNanos); 290 } 291 testSetRemovalListener()292 public void testSetRemovalListener() { 293 RemovalListener<Object, Object> testListener = new RemovalListener<Object, Object>() { 294 @Override 295 public void onRemoval(RemovalNotification<Object, Object> notification) {} 296 }; 297 MapMakerInternalMap<Object, Object> map = 298 makeMap(createMapMaker().removalListener(testListener)); 299 assertSame(testListener, map.removalListener); 300 } 301 302 // Removal listener tests 303 testRemovalListener_explicit()304 public void testRemovalListener_explicit() { 305 QueuingRemovalListener<Object, Object> listener = 306 new QueuingRemovalListener<Object, Object>(); 307 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker() 308 .removalListener(listener)); 309 assertTrue(listener.isEmpty()); 310 311 Object one = new Object(); 312 Object two = new Object(); 313 Object three = new Object(); 314 Object four = new Object(); 315 Object five = new Object(); 316 Object six = new Object(); 317 318 map.put(one, two); 319 map.remove(one); 320 assertNotified(listener, one, two, RemovalCause.EXPLICIT); 321 322 map.put(two, three); 323 map.remove(two, three); 324 assertNotified(listener, two, three, RemovalCause.EXPLICIT); 325 326 map.put(three, four); 327 Iterator<?> i = map.entrySet().iterator(); 328 i.next(); 329 i.remove(); 330 assertNotified(listener, three, four, RemovalCause.EXPLICIT); 331 332 map.put(four, five); 333 i = map.keySet().iterator(); 334 i.next(); 335 i.remove(); 336 assertNotified(listener, four, five, RemovalCause.EXPLICIT); 337 338 map.put(five, six); 339 i = map.values().iterator(); 340 i.next(); 341 i.remove(); 342 assertNotified(listener, five, six, RemovalCause.EXPLICIT); 343 344 assertTrue(listener.isEmpty()); 345 } 346 testRemovalListener_replaced()347 public void testRemovalListener_replaced() { 348 QueuingRemovalListener<Object, Object> listener = 349 new QueuingRemovalListener<Object, Object>(); 350 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker() 351 .removalListener(listener)); 352 assertTrue(listener.isEmpty()); 353 354 Object one = new Object(); 355 Object two = new Object(); 356 Object three = new Object(); 357 Object four = new Object(); 358 Object five = new Object(); 359 Object six = new Object(); 360 361 map.put(one, two); 362 map.put(one, three); 363 assertNotified(listener, one, two, RemovalCause.REPLACED); 364 365 Map<Object, Object> newMap = ImmutableMap.of(one, four); 366 map.putAll(newMap); 367 assertNotified(listener, one, three, RemovalCause.REPLACED); 368 369 map.replace(one, five); 370 assertNotified(listener, one, four, RemovalCause.REPLACED); 371 372 map.replace(one, five, six); 373 assertNotified(listener, one, five, RemovalCause.REPLACED); 374 } 375 testRemovalListener_collected()376 public void testRemovalListener_collected() { 377 QueuingRemovalListener<Object, Object> listener = 378 new QueuingRemovalListener<Object, Object>(); 379 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker() 380 .concurrencyLevel(1) 381 .softValues() 382 .removalListener(listener)); 383 Segment<Object, Object> segment = map.segments[0]; 384 assertTrue(listener.isEmpty()); 385 386 Object one = new Object(); 387 Object two = new Object(); 388 Object three = new Object(); 389 390 map.put(one, two); 391 map.put(two, three); 392 assertTrue(listener.isEmpty()); 393 394 int hash = map.hash(one); 395 ReferenceEntry<Object, Object> entry = segment.getEntry(one, hash); 396 map.reclaimValue(entry.getValueReference()); 397 assertNotified(listener, one, two, RemovalCause.COLLECTED); 398 399 assertTrue(listener.isEmpty()); 400 } 401 testRemovalListener_size()402 public void testRemovalListener_size() { 403 QueuingRemovalListener<Object, Object> listener = 404 new QueuingRemovalListener<Object, Object>(); 405 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker() 406 .concurrencyLevel(1) 407 .maximumSize(2) 408 .removalListener(listener)); 409 assertTrue(listener.isEmpty()); 410 411 Object one = new Object(); 412 Object two = new Object(); 413 Object three = new Object(); 414 Object four = new Object(); 415 416 map.put(one, two); 417 map.put(two, three); 418 assertTrue(listener.isEmpty()); 419 map.put(three, four); 420 assertNotified(listener, one, two, RemovalCause.SIZE); 421 422 assertTrue(listener.isEmpty()); 423 } 424 assertNotified( QueuingRemovalListener<K, V> listener, K key, V value, RemovalCause cause)425 static <K, V> void assertNotified( 426 QueuingRemovalListener<K, V> listener, K key, V value, RemovalCause cause) { 427 RemovalNotification<K, V> notification = listener.remove(); 428 assertSame(key, notification.getKey()); 429 assertSame(value, notification.getValue()); 430 assertSame(cause, notification.getCause()); 431 } 432 433 // Segment core tests 434 testNewEntry()435 public void testNewEntry() { 436 for (MapMaker maker : allEntryTypeMakers()) { 437 MapMakerInternalMap<Object, Object> map = makeMap(maker); 438 439 Object keyOne = new Object(); 440 Object valueOne = new Object(); 441 int hashOne = map.hash(keyOne); 442 ReferenceEntry<Object, Object> entryOne = map.newEntry(keyOne, hashOne, null); 443 ValueReference<Object, Object> valueRefOne = map.newValueReference(entryOne, valueOne); 444 assertSame(valueOne, valueRefOne.get()); 445 entryOne.setValueReference(valueRefOne); 446 447 assertSame(keyOne, entryOne.getKey()); 448 assertEquals(hashOne, entryOne.getHash()); 449 assertNull(entryOne.getNext()); 450 assertSame(valueRefOne, entryOne.getValueReference()); 451 452 Object keyTwo = new Object(); 453 Object valueTwo = new Object(); 454 int hashTwo = map.hash(keyTwo); 455 ReferenceEntry<Object, Object> entryTwo = map.newEntry(keyTwo, hashTwo, entryOne); 456 ValueReference<Object, Object> valueRefTwo = map.newValueReference(entryTwo, valueTwo); 457 assertSame(valueTwo, valueRefTwo.get()); 458 entryTwo.setValueReference(valueRefTwo); 459 460 assertSame(keyTwo, entryTwo.getKey()); 461 assertEquals(hashTwo, entryTwo.getHash()); 462 assertSame(entryOne, entryTwo.getNext()); 463 assertSame(valueRefTwo, entryTwo.getValueReference()); 464 } 465 } 466 testCopyEntry()467 public void testCopyEntry() { 468 for (MapMaker maker : allEntryTypeMakers()) { 469 MapMakerInternalMap<Object, Object> map = makeMap(maker); 470 471 Object keyOne = new Object(); 472 Object valueOne = new Object(); 473 int hashOne = map.hash(keyOne); 474 ReferenceEntry<Object, Object> entryOne = map.newEntry(keyOne, hashOne, null); 475 entryOne.setValueReference(map.newValueReference(entryOne, valueOne)); 476 477 Object keyTwo = new Object(); 478 Object valueTwo = new Object(); 479 int hashTwo = map.hash(keyTwo); 480 ReferenceEntry<Object, Object> entryTwo = map.newEntry(keyTwo, hashTwo, entryOne); 481 entryTwo.setValueReference(map.newValueReference(entryTwo, valueTwo)); 482 if (map.evictsBySize()) { 483 MapMakerInternalMap.connectEvictables(entryOne, entryTwo); 484 } 485 if (map.expires()) { 486 MapMakerInternalMap.connectExpirables(entryOne, entryTwo); 487 } 488 assertConnected(map, entryOne, entryTwo); 489 490 ReferenceEntry<Object, Object> copyOne = map.copyEntry(entryOne, null); 491 assertSame(keyOne, entryOne.getKey()); 492 assertEquals(hashOne, entryOne.getHash()); 493 assertNull(entryOne.getNext()); 494 assertSame(valueOne, copyOne.getValueReference().get()); 495 assertConnected(map, copyOne, entryTwo); 496 497 ReferenceEntry<Object, Object> copyTwo = map.copyEntry(entryTwo, copyOne); 498 assertSame(keyTwo, copyTwo.getKey()); 499 assertEquals(hashTwo, copyTwo.getHash()); 500 assertSame(copyOne, copyTwo.getNext()); 501 assertSame(valueTwo, copyTwo.getValueReference().get()); 502 assertConnected(map, copyOne, copyTwo); 503 } 504 } 505 assertConnected( MapMakerInternalMap<K, V> map, ReferenceEntry<K, V> one, ReferenceEntry<K, V> two)506 private static <K, V> void assertConnected( 507 MapMakerInternalMap<K, V> map, ReferenceEntry<K, V> one, ReferenceEntry<K, V> two) { 508 if (map.evictsBySize()) { 509 assertSame(two, one.getNextEvictable()); 510 } 511 if (map.expires()) { 512 assertSame(two, one.getNextExpirable()); 513 } 514 } 515 testSegmentGetAndContains()516 public void testSegmentGetAndContains() { 517 MapMakerInternalMap<Object, Object> map = 518 makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS)); 519 Segment<Object, Object> segment = map.segments[0]; 520 // TODO(fry): check recency ordering 521 522 Object key = new Object(); 523 int hash = map.hash(key); 524 Object value = new Object(); 525 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table; 526 int index = hash & (table.length() - 1); 527 528 ReferenceEntry<Object, Object> entry = map.newEntry(key, hash, null); 529 ValueReference<Object, Object> valueRef = map.newValueReference(entry, value); 530 entry.setValueReference(valueRef); 531 532 assertNull(segment.get(key, hash)); 533 534 // count == 0 535 table.set(index, entry); 536 assertNull(segment.get(key, hash)); 537 assertFalse(segment.containsKey(key, hash)); 538 assertFalse(segment.containsValue(value)); 539 540 // count == 1 541 segment.count++; 542 assertSame(value, segment.get(key, hash)); 543 assertTrue(segment.containsKey(key, hash)); 544 assertTrue(segment.containsValue(value)); 545 // don't see absent values now that count > 0 546 assertNull(segment.get(new Object(), hash)); 547 548 // null key 549 DummyEntry<Object, Object> nullEntry = DummyEntry.create(null, hash, entry); 550 Object nullValue = new Object(); 551 ValueReference<Object, Object> nullValueRef = map.newValueReference(nullEntry, nullValue); 552 nullEntry.setValueReference(nullValueRef); 553 table.set(index, nullEntry); 554 // skip the null key 555 assertSame(value, segment.get(key, hash)); 556 assertTrue(segment.containsKey(key, hash)); 557 assertTrue(segment.containsValue(value)); 558 assertFalse(segment.containsValue(nullValue)); 559 560 // hash collision 561 DummyEntry<Object, Object> dummy = DummyEntry.create(new Object(), hash, entry); 562 Object dummyValue = new Object(); 563 ValueReference<Object, Object> dummyValueRef = map.newValueReference(dummy, dummyValue); 564 dummy.setValueReference(dummyValueRef); 565 table.set(index, dummy); 566 assertSame(value, segment.get(key, hash)); 567 assertTrue(segment.containsKey(key, hash)); 568 assertTrue(segment.containsValue(value)); 569 assertTrue(segment.containsValue(dummyValue)); 570 571 // key collision 572 dummy = DummyEntry.create(key, hash, entry); 573 dummyValue = new Object(); 574 dummyValueRef = map.newValueReference(dummy, dummyValue); 575 dummy.setValueReference(dummyValueRef); 576 table.set(index, dummy); 577 // returns the most recent entry 578 assertSame(dummyValue, segment.get(key, hash)); 579 assertTrue(segment.containsKey(key, hash)); 580 assertTrue(segment.containsValue(value)); 581 assertTrue(segment.containsValue(dummyValue)); 582 583 // expired 584 dummy.setExpirationTime(0); 585 assertNull(segment.get(key, hash)); 586 assertFalse(segment.containsKey(key, hash)); 587 assertTrue(segment.containsValue(value)); 588 assertFalse(segment.containsValue(dummyValue)); 589 } 590 testSegmentReplaceValue()591 public void testSegmentReplaceValue() { 592 MapMakerInternalMap<Object, Object> map = 593 makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS)); 594 Segment<Object, Object> segment = map.segments[0]; 595 // TODO(fry): check recency ordering 596 597 Object key = new Object(); 598 int hash = map.hash(key); 599 Object oldValue = new Object(); 600 Object newValue = new Object(); 601 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table; 602 int index = hash & (table.length() - 1); 603 604 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null); 605 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry); 606 entry.setValueReference(oldValueRef); 607 608 // no entry 609 assertFalse(segment.replace(key, hash, oldValue, newValue)); 610 assertEquals(0, segment.count); 611 612 // same value 613 table.set(index, entry); 614 segment.count++; 615 assertEquals(1, segment.count); 616 assertSame(oldValue, segment.get(key, hash)); 617 assertTrue(segment.replace(key, hash, oldValue, newValue)); 618 assertEquals(1, segment.count); 619 assertSame(newValue, segment.get(key, hash)); 620 621 // different value 622 assertFalse(segment.replace(key, hash, oldValue, newValue)); 623 assertEquals(1, segment.count); 624 assertSame(newValue, segment.get(key, hash)); 625 626 // cleared 627 entry.setValueReference(oldValueRef); 628 assertSame(oldValue, segment.get(key, hash)); 629 oldValueRef.clear(null); 630 assertFalse(segment.replace(key, hash, oldValue, newValue)); 631 assertEquals(0, segment.count); 632 assertNull(segment.get(key, hash)); 633 } 634 testSegmentReplace()635 public void testSegmentReplace() { 636 MapMakerInternalMap<Object, Object> map = 637 makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS)); 638 Segment<Object, Object> segment = map.segments[0]; 639 // TODO(fry): check recency ordering 640 641 Object key = new Object(); 642 int hash = map.hash(key); 643 Object oldValue = new Object(); 644 Object newValue = new Object(); 645 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table; 646 int index = hash & (table.length() - 1); 647 648 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null); 649 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry); 650 entry.setValueReference(oldValueRef); 651 652 // no entry 653 assertNull(segment.replace(key, hash, newValue)); 654 assertEquals(0, segment.count); 655 656 // same key 657 table.set(index, entry); 658 segment.count++; 659 assertEquals(1, segment.count); 660 assertSame(oldValue, segment.get(key, hash)); 661 assertSame(oldValue, segment.replace(key, hash, newValue)); 662 assertEquals(1, segment.count); 663 assertSame(newValue, segment.get(key, hash)); 664 665 // cleared 666 entry.setValueReference(oldValueRef); 667 assertSame(oldValue, segment.get(key, hash)); 668 oldValueRef.clear(null); 669 assertNull(segment.replace(key, hash, newValue)); 670 assertEquals(0, segment.count); 671 assertNull(segment.get(key, hash)); 672 } 673 testSegmentPut()674 public void testSegmentPut() { 675 MapMakerInternalMap<Object, Object> map = 676 makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS)); 677 Segment<Object, Object> segment = map.segments[0]; 678 // TODO(fry): check recency ordering 679 680 Object key = new Object(); 681 int hash = map.hash(key); 682 Object oldValue = new Object(); 683 Object newValue = new Object(); 684 685 // no entry 686 assertEquals(0, segment.count); 687 assertNull(segment.put(key, hash, oldValue, false)); 688 assertEquals(1, segment.count); 689 690 // same key 691 assertSame(oldValue, segment.put(key, hash, newValue, false)); 692 assertEquals(1, segment.count); 693 assertSame(newValue, segment.get(key, hash)); 694 695 // cleared 696 ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash); 697 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry); 698 entry.setValueReference(oldValueRef); 699 assertSame(oldValue, segment.get(key, hash)); 700 oldValueRef.clear(null); 701 assertNull(segment.put(key, hash, newValue, false)); 702 assertEquals(1, segment.count); 703 assertSame(newValue, segment.get(key, hash)); 704 } 705 testSegmentPutIfAbsent()706 public void testSegmentPutIfAbsent() { 707 MapMakerInternalMap<Object, Object> map = 708 makeMap(createMapMaker().concurrencyLevel(1).expireAfterAccess(99999, SECONDS)); 709 Segment<Object, Object> segment = map.segments[0]; 710 // TODO(fry): check recency ordering 711 712 Object key = new Object(); 713 int hash = map.hash(key); 714 Object oldValue = new Object(); 715 Object newValue = new Object(); 716 717 // no entry 718 assertEquals(0, segment.count); 719 assertNull(segment.put(key, hash, oldValue, true)); 720 assertEquals(1, segment.count); 721 722 // same key 723 assertSame(oldValue, segment.put(key, hash, newValue, true)); 724 assertEquals(1, segment.count); 725 assertSame(oldValue, segment.get(key, hash)); 726 727 // cleared 728 ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash); 729 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry); 730 entry.setValueReference(oldValueRef); 731 assertSame(oldValue, segment.get(key, hash)); 732 oldValueRef.clear(null); 733 assertNull(segment.put(key, hash, newValue, true)); 734 assertEquals(1, segment.count); 735 assertSame(newValue, segment.get(key, hash)); 736 } 737 testSegmentPut_expand()738 public void testSegmentPut_expand() { 739 MapMakerInternalMap<Object, Object> map = 740 makeMap(createMapMaker().concurrencyLevel(1).initialCapacity(1)); 741 Segment<Object, Object> segment = map.segments[0]; 742 assertEquals(1, segment.table.length()); 743 744 int count = 1024; 745 for (int i = 0; i < count; i++) { 746 Object key = new Object(); 747 Object value = new Object(); 748 int hash = map.hash(key); 749 assertNull(segment.put(key, hash, value, false)); 750 assertTrue(segment.table.length() > i); 751 } 752 } 753 testSegmentPut_evict()754 public void testSegmentPut_evict() { 755 int maxSize = 10; 756 MapMakerInternalMap<Object, Object> map = 757 makeMap(createMapMaker().concurrencyLevel(1).maximumSize(maxSize)); 758 759 // manually add elements to avoid eviction 760 int originalCount = 1024; 761 LinkedHashMap<Object, Object> originalMap = Maps.newLinkedHashMap(); 762 for (int i = 0; i < originalCount; i++) { 763 Object key = new Object(); 764 Object value = new Object(); 765 map.put(key, value); 766 originalMap.put(key, value); 767 if (i >= maxSize) { 768 Iterator<Object> it = originalMap.keySet().iterator(); 769 it.next(); 770 it.remove(); 771 } 772 assertEquals(originalMap, map); 773 } 774 } 775 testSegmentRemove()776 public void testSegmentRemove() { 777 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().concurrencyLevel(1)); 778 Segment<Object, Object> segment = map.segments[0]; 779 780 Object key = new Object(); 781 int hash = map.hash(key); 782 Object oldValue = new Object(); 783 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table; 784 int index = hash & (table.length() - 1); 785 786 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null); 787 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry); 788 entry.setValueReference(oldValueRef); 789 790 // no entry 791 assertEquals(0, segment.count); 792 assertNull(segment.remove(key, hash)); 793 assertEquals(0, segment.count); 794 795 // same key 796 table.set(index, entry); 797 segment.count++; 798 assertEquals(1, segment.count); 799 assertSame(oldValue, segment.get(key, hash)); 800 assertSame(oldValue, segment.remove(key, hash)); 801 assertEquals(0, segment.count); 802 assertNull(segment.get(key, hash)); 803 804 // cleared 805 table.set(index, entry); 806 segment.count++; 807 assertEquals(1, segment.count); 808 assertSame(oldValue, segment.get(key, hash)); 809 oldValueRef.clear(null); 810 assertNull(segment.remove(key, hash)); 811 assertEquals(0, segment.count); 812 assertNull(segment.get(key, hash)); 813 } 814 testSegmentRemoveValue()815 public void testSegmentRemoveValue() { 816 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().concurrencyLevel(1)); 817 Segment<Object, Object> segment = map.segments[0]; 818 819 Object key = new Object(); 820 int hash = map.hash(key); 821 Object oldValue = new Object(); 822 Object newValue = new Object(); 823 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table; 824 int index = hash & (table.length() - 1); 825 826 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null); 827 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue, entry); 828 entry.setValueReference(oldValueRef); 829 830 // no entry 831 assertEquals(0, segment.count); 832 assertNull(segment.remove(key, hash)); 833 assertEquals(0, segment.count); 834 835 // same value 836 table.set(index, entry); 837 segment.count++; 838 assertEquals(1, segment.count); 839 assertSame(oldValue, segment.get(key, hash)); 840 assertTrue(segment.remove(key, hash, oldValue)); 841 assertEquals(0, segment.count); 842 assertNull(segment.get(key, hash)); 843 844 // different value 845 table.set(index, entry); 846 segment.count++; 847 assertEquals(1, segment.count); 848 assertSame(oldValue, segment.get(key, hash)); 849 assertFalse(segment.remove(key, hash, newValue)); 850 assertEquals(1, segment.count); 851 assertSame(oldValue, segment.get(key, hash)); 852 853 // cleared 854 assertSame(oldValue, segment.get(key, hash)); 855 oldValueRef.clear(null); 856 assertFalse(segment.remove(key, hash, oldValue)); 857 assertEquals(0, segment.count); 858 assertNull(segment.get(key, hash)); 859 } 860 testExpand()861 public void testExpand() { 862 MapMakerInternalMap<Object, Object> map = 863 makeMap(createMapMaker().concurrencyLevel(1).initialCapacity(1)); 864 Segment<Object, Object> segment = map.segments[0]; 865 assertEquals(1, segment.table.length()); 866 867 // manually add elements to avoid expansion 868 int originalCount = 1024; 869 ReferenceEntry<Object, Object> entry = null; 870 for (int i = 0; i < originalCount; i++) { 871 Object key = new Object(); 872 Object value = new Object(); 873 int hash = map.hash(key); 874 // chain all entries together as we only have a single bucket 875 entry = map.newEntry(key, hash, entry); 876 ValueReference<Object, Object> valueRef = map.newValueReference(entry, value); 877 entry.setValueReference(valueRef); 878 } 879 segment.table.set(0, entry); 880 segment.count = originalCount; 881 ImmutableMap<Object, Object> originalMap = ImmutableMap.copyOf(map); 882 assertEquals(originalCount, originalMap.size()); 883 assertEquals(originalMap, map); 884 885 for (int i = 1; i <= originalCount * 2; i *= 2) { 886 if (i > 1) { 887 segment.expand(); 888 } 889 assertEquals(i, segment.table.length()); 890 assertEquals(originalCount, countLiveEntries(map)); 891 assertEquals(originalCount, segment.count); 892 assertEquals(originalMap, map); 893 } 894 } 895 testReclaimKey()896 public void testReclaimKey() { 897 CountingRemovalListener<Object, Object> listener = 898 new CountingRemovalListener<Object, Object>(); 899 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker() 900 .concurrencyLevel(1) 901 .initialCapacity(1) 902 .maximumSize(SMALL_MAX_SIZE) 903 .expireAfterWrite(99999, SECONDS) 904 .removalListener(listener)); 905 Segment<Object, Object> segment = map.segments[0]; 906 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table; 907 assertEquals(1, table.length()); 908 909 // create 3 objects and chain them together 910 Object keyOne = new Object(); 911 Object valueOne = new Object(); 912 int hashOne = map.hash(keyOne); 913 DummyEntry<Object, Object> entryOne = createDummyEntry(keyOne, hashOne, valueOne, null); 914 Object keyTwo = new Object(); 915 Object valueTwo = new Object(); 916 int hashTwo = map.hash(keyTwo); 917 DummyEntry<Object, Object> entryTwo = createDummyEntry(keyTwo, hashTwo, valueTwo, entryOne); 918 Object keyThree = new Object(); 919 Object valueThree = new Object(); 920 int hashThree = map.hash(keyThree); 921 DummyEntry<Object, Object> entryThree = 922 createDummyEntry(keyThree, hashThree, valueThree, entryTwo); 923 924 // absent 925 assertEquals(0, listener.getCount()); 926 assertFalse(segment.reclaimKey(entryOne, hashOne)); 927 assertEquals(0, listener.getCount()); 928 table.set(0, entryOne); 929 assertFalse(segment.reclaimKey(entryTwo, hashTwo)); 930 assertEquals(0, listener.getCount()); 931 table.set(0, entryTwo); 932 assertFalse(segment.reclaimKey(entryThree, hashThree)); 933 assertEquals(0, listener.getCount()); 934 935 // present 936 table.set(0, entryOne); 937 segment.count = 1; 938 assertTrue(segment.reclaimKey(entryOne, hashOne)); 939 assertEquals(1, listener.getCount()); 940 assertSame(keyOne, listener.getLastEvictedKey()); 941 assertSame(valueOne, listener.getLastEvictedValue()); 942 assertTrue(map.removalNotificationQueue.isEmpty()); 943 assertFalse(segment.evictionQueue.contains(entryOne)); 944 assertFalse(segment.expirationQueue.contains(entryOne)); 945 assertEquals(0, segment.count); 946 assertNull(table.get(0)); 947 } 948 testRemoveFromChain()949 public void testRemoveFromChain() { 950 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker().concurrencyLevel(1)); 951 Segment<Object, Object> segment = map.segments[0]; 952 953 // create 3 objects and chain them together 954 Object keyOne = new Object(); 955 Object valueOne = new Object(); 956 int hashOne = map.hash(keyOne); 957 DummyEntry<Object, Object> entryOne = createDummyEntry(keyOne, hashOne, valueOne, null); 958 Object keyTwo = new Object(); 959 Object valueTwo = new Object(); 960 int hashTwo = map.hash(keyTwo); 961 DummyEntry<Object, Object> entryTwo = createDummyEntry(keyTwo, hashTwo, valueTwo, entryOne); 962 Object keyThree = new Object(); 963 Object valueThree = new Object(); 964 int hashThree = map.hash(keyThree); 965 DummyEntry<Object, Object> entryThree = 966 createDummyEntry(keyThree, hashThree, valueThree, entryTwo); 967 968 // alone 969 assertNull(segment.removeFromChain(entryOne, entryOne)); 970 971 // head 972 assertSame(entryOne, segment.removeFromChain(entryTwo, entryTwo)); 973 974 // middle 975 ReferenceEntry<Object, Object> newFirst = segment.removeFromChain(entryThree, entryTwo); 976 assertSame(keyThree, newFirst.getKey()); 977 assertSame(valueThree, newFirst.getValueReference().get()); 978 assertEquals(hashThree, newFirst.getHash()); 979 assertSame(entryOne, newFirst.getNext()); 980 981 // tail (remaining entries are copied in reverse order) 982 newFirst = segment.removeFromChain(entryThree, entryOne); 983 assertSame(keyTwo, newFirst.getKey()); 984 assertSame(valueTwo, newFirst.getValueReference().get()); 985 assertEquals(hashTwo, newFirst.getHash()); 986 newFirst = newFirst.getNext(); 987 assertSame(keyThree, newFirst.getKey()); 988 assertSame(valueThree, newFirst.getValueReference().get()); 989 assertEquals(hashThree, newFirst.getHash()); 990 assertNull(newFirst.getNext()); 991 } 992 testExpand_cleanup()993 public void testExpand_cleanup() { 994 MapMakerInternalMap<Object, Object> map = 995 makeMap(createMapMaker().concurrencyLevel(1).initialCapacity(1)); 996 Segment<Object, Object> segment = map.segments[0]; 997 assertEquals(1, segment.table.length()); 998 999 // manually add elements to avoid expansion 1000 // 1/3 null keys, 1/3 null values 1001 int originalCount = 1024; 1002 ReferenceEntry<Object, Object> entry = null; 1003 for (int i = 0; i < originalCount; i++) { 1004 Object key = new Object(); 1005 Object value = (i % 3 == 0) ? null : new Object(); 1006 int hash = map.hash(key); 1007 if (i % 3 == 1) { 1008 key = null; 1009 } 1010 // chain all entries together as we only have a single bucket 1011 entry = DummyEntry.create(key, hash, entry); 1012 ValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry); 1013 entry.setValueReference(valueRef); 1014 } 1015 segment.table.set(0, entry); 1016 segment.count = originalCount; 1017 int liveCount = originalCount / 3; 1018 assertEquals(1, segment.table.length()); 1019 assertEquals(liveCount, countLiveEntries(map)); 1020 ImmutableMap<Object, Object> originalMap = ImmutableMap.copyOf(map); 1021 assertEquals(liveCount, originalMap.size()); 1022 // can't compare map contents until cleanup occurs 1023 1024 for (int i = 1; i <= originalCount * 2; i *= 2) { 1025 if (i > 1) { 1026 segment.expand(); 1027 } 1028 assertEquals(i, segment.table.length()); 1029 assertEquals(liveCount, countLiveEntries(map)); 1030 // expansion cleanup is sloppy, with a goal of avoiding unnecessary copies 1031 assertTrue(segment.count >= liveCount); 1032 assertTrue(segment.count <= originalCount); 1033 assertEquals(originalMap, ImmutableMap.copyOf(map)); 1034 } 1035 } 1036 countLiveEntries(MapMakerInternalMap<K, V> map)1037 private static <K, V> int countLiveEntries(MapMakerInternalMap<K, V> map) { 1038 int result = 0; 1039 for (Segment<K, V> segment : map.segments) { 1040 AtomicReferenceArray<ReferenceEntry<K, V>> table = segment.table; 1041 for (int i = 0; i < table.length(); i++) { 1042 for (ReferenceEntry<K, V> e = table.get(i); e != null; e = e.getNext()) { 1043 if (map.isLive(e)) { 1044 result++; 1045 } 1046 } 1047 } 1048 } 1049 return result; 1050 } 1051 testClear()1052 public void testClear() { 1053 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker() 1054 .concurrencyLevel(1) 1055 .initialCapacity(1) 1056 .maximumSize(SMALL_MAX_SIZE) 1057 .expireAfterWrite(99999, SECONDS)); 1058 Segment<Object, Object> segment = map.segments[0]; 1059 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table; 1060 assertEquals(1, table.length()); 1061 1062 Object key = new Object(); 1063 Object value = new Object(); 1064 int hash = map.hash(key); 1065 DummyEntry<Object, Object> entry = createDummyEntry(key, hash, value, null); 1066 segment.recordWrite(entry); 1067 segment.table.set(0, entry); 1068 segment.readCount.incrementAndGet(); 1069 segment.count = 1; 1070 1071 assertSame(entry, table.get(0)); 1072 assertSame(entry, segment.evictionQueue.peek()); 1073 assertSame(entry, segment.expirationQueue.peek()); 1074 1075 segment.clear(); 1076 assertNull(table.get(0)); 1077 assertTrue(segment.evictionQueue.isEmpty()); 1078 assertTrue(segment.expirationQueue.isEmpty()); 1079 assertEquals(0, segment.readCount.get()); 1080 assertEquals(0, segment.count); 1081 } 1082 testRemoveEntry()1083 public void testRemoveEntry() { 1084 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker() 1085 .concurrencyLevel(1) 1086 .initialCapacity(1) 1087 .maximumSize(SMALL_MAX_SIZE) 1088 .expireAfterWrite(99999, SECONDS) 1089 .removalListener(new CountingRemovalListener<Object, Object>())); 1090 Segment<Object, Object> segment = map.segments[0]; 1091 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table; 1092 assertEquals(1, table.length()); 1093 1094 Object key = new Object(); 1095 Object value = new Object(); 1096 int hash = map.hash(key); 1097 DummyEntry<Object, Object> entry = createDummyEntry(key, hash, value, null); 1098 1099 // remove absent 1100 assertFalse(segment.removeEntry(entry, hash, RemovalCause.COLLECTED)); 1101 1102 // remove live 1103 segment.recordWrite(entry); 1104 table.set(0, entry); 1105 segment.count = 1; 1106 assertTrue(segment.removeEntry(entry, hash, RemovalCause.COLLECTED)); 1107 assertNotificationEnqueued(map, key, value, hash); 1108 assertTrue(map.removalNotificationQueue.isEmpty()); 1109 assertFalse(segment.evictionQueue.contains(entry)); 1110 assertFalse(segment.expirationQueue.contains(entry)); 1111 assertEquals(0, segment.count); 1112 assertNull(table.get(0)); 1113 } 1114 testReclaimValue()1115 public void testReclaimValue() { 1116 CountingRemovalListener<Object, Object> listener = 1117 new CountingRemovalListener<Object, Object>(); 1118 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker() 1119 .concurrencyLevel(1) 1120 .initialCapacity(1) 1121 .maximumSize(SMALL_MAX_SIZE) 1122 .expireAfterWrite(99999, SECONDS) 1123 .removalListener(listener)); 1124 Segment<Object, Object> segment = map.segments[0]; 1125 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table; 1126 assertEquals(1, table.length()); 1127 1128 Object key = new Object(); 1129 Object value = new Object(); 1130 int hash = map.hash(key); 1131 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null); 1132 DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry); 1133 entry.setValueReference(valueRef); 1134 1135 // reclaim absent 1136 assertFalse(segment.reclaimValue(key, hash, valueRef)); 1137 1138 // reclaim live 1139 segment.recordWrite(entry); 1140 table.set(0, entry); 1141 segment.count = 1; 1142 assertTrue(segment.reclaimValue(key, hash, valueRef)); 1143 assertEquals(1, listener.getCount()); 1144 assertSame(key, listener.getLastEvictedKey()); 1145 assertSame(value, listener.getLastEvictedValue()); 1146 assertTrue(map.removalNotificationQueue.isEmpty()); 1147 assertFalse(segment.evictionQueue.contains(entry)); 1148 assertFalse(segment.expirationQueue.contains(entry)); 1149 assertEquals(0, segment.count); 1150 assertNull(table.get(0)); 1151 1152 // reclaim wrong value reference 1153 table.set(0, entry); 1154 DummyValueReference<Object, Object> otherValueRef = DummyValueReference.create(value, entry); 1155 entry.setValueReference(otherValueRef); 1156 assertFalse(segment.reclaimValue(key, hash, valueRef)); 1157 assertEquals(1, listener.getCount()); 1158 assertTrue(segment.reclaimValue(key, hash, otherValueRef)); 1159 assertEquals(2, listener.getCount()); 1160 assertSame(key, listener.getLastEvictedKey()); 1161 assertSame(value, listener.getLastEvictedValue()); 1162 } 1163 testClearValue()1164 public void testClearValue() { 1165 MapMakerInternalMap<Object, Object> map = makeMap(createMapMaker() 1166 .concurrencyLevel(1) 1167 .initialCapacity(1) 1168 .maximumSize(SMALL_MAX_SIZE) 1169 .expireAfterWrite(99999, SECONDS) 1170 .removalListener(new CountingRemovalListener<Object, Object>())); 1171 Segment<Object, Object> segment = map.segments[0]; 1172 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table; 1173 assertEquals(1, table.length()); 1174 1175 Object key = new Object(); 1176 Object value = new Object(); 1177 int hash = map.hash(key); 1178 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null); 1179 DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry); 1180 entry.setValueReference(valueRef); 1181 1182 // clear absent 1183 assertFalse(segment.clearValue(key, hash, valueRef)); 1184 1185 // clear live 1186 segment.recordWrite(entry); 1187 table.set(0, entry); 1188 // don't increment count; this is used during computation 1189 assertTrue(segment.clearValue(key, hash, valueRef)); 1190 // no notification sent with clearValue 1191 assertTrue(map.removalNotificationQueue.isEmpty()); 1192 assertFalse(segment.evictionQueue.contains(entry)); 1193 assertFalse(segment.expirationQueue.contains(entry)); 1194 assertEquals(0, segment.count); 1195 assertNull(table.get(0)); 1196 1197 // clear wrong value reference 1198 table.set(0, entry); 1199 DummyValueReference<Object, Object> otherValueRef = DummyValueReference.create(value, entry); 1200 entry.setValueReference(otherValueRef); 1201 assertFalse(segment.clearValue(key, hash, valueRef)); 1202 entry.setValueReference(valueRef); 1203 assertTrue(segment.clearValue(key, hash, valueRef)); 1204 } 1205 assertNotificationEnqueued( MapMakerInternalMap<K, V> map, K key, V value, int hash)1206 private static <K, V> void assertNotificationEnqueued( 1207 MapMakerInternalMap<K, V> map, K key, V value, int hash) { 1208 RemovalNotification<K, V> notification = map.removalNotificationQueue.poll(); 1209 assertSame(key, notification.getKey()); 1210 assertSame(value, notification.getValue()); 1211 } 1212 1213 // Segment eviction tests 1214 testDrainRecencyQueueOnWrite()1215 public void testDrainRecencyQueueOnWrite() { 1216 for (MapMaker maker : allEvictingMakers()) { 1217 MapMakerInternalMap<Object, Object> map = makeMap(maker.concurrencyLevel(1)); 1218 Segment<Object, Object> segment = map.segments[0]; 1219 1220 if (segment.recencyQueue != DISCARDING_QUEUE) { 1221 Object keyOne = new Object(); 1222 Object valueOne = new Object(); 1223 Object keyTwo = new Object(); 1224 Object valueTwo = new Object(); 1225 1226 map.put(keyOne, valueOne); 1227 assertTrue(segment.recencyQueue.isEmpty()); 1228 1229 for (int i = 0; i < DRAIN_THRESHOLD / 2; i++) { 1230 map.get(keyOne); 1231 } 1232 assertFalse(segment.recencyQueue.isEmpty()); 1233 1234 map.put(keyTwo, valueTwo); 1235 assertTrue(segment.recencyQueue.isEmpty()); 1236 } 1237 } 1238 } 1239 testDrainRecencyQueueOnRead()1240 public void testDrainRecencyQueueOnRead() { 1241 for (MapMaker maker : allEvictingMakers()) { 1242 MapMakerInternalMap<Object, Object> map = makeMap(maker.concurrencyLevel(1)); 1243 Segment<Object, Object> segment = map.segments[0]; 1244 1245 if (segment.recencyQueue != DISCARDING_QUEUE) { 1246 Object keyOne = new Object(); 1247 Object valueOne = new Object(); 1248 1249 // repeated get of the same key 1250 1251 map.put(keyOne, valueOne); 1252 assertTrue(segment.recencyQueue.isEmpty()); 1253 1254 for (int i = 0; i < DRAIN_THRESHOLD / 2; i++) { 1255 map.get(keyOne); 1256 } 1257 assertFalse(segment.recencyQueue.isEmpty()); 1258 1259 for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) { 1260 map.get(keyOne); 1261 assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD); 1262 } 1263 1264 // get over many different keys 1265 1266 for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) { 1267 map.put(new Object(), new Object()); 1268 } 1269 assertTrue(segment.recencyQueue.isEmpty()); 1270 1271 for (int i = 0; i < DRAIN_THRESHOLD / 2; i++) { 1272 map.get(keyOne); 1273 } 1274 assertFalse(segment.recencyQueue.isEmpty()); 1275 1276 for (Object key : map.keySet()) { 1277 map.get(key); 1278 assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD); 1279 } 1280 } 1281 } 1282 } 1283 testRecordRead()1284 public void testRecordRead() { 1285 for (MapMaker maker : allEvictingMakers()) { 1286 MapMakerInternalMap<Object, Object> map = makeMap(maker.concurrencyLevel(1)); 1287 Segment<Object, Object> segment = map.segments[0]; 1288 List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList(); 1289 List<ReferenceEntry<Object, Object>> readOrder = Lists.newLinkedList(); 1290 for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) { 1291 Object key = new Object(); 1292 int hash = map.hash(key); 1293 Object value = new Object(); 1294 1295 ReferenceEntry<Object, Object> entry = createDummyEntry(key, hash, value, null); 1296 // must recordRead for drainRecencyQueue to believe this entry is live 1297 segment.recordWrite(entry); 1298 writeOrder.add(entry); 1299 readOrder.add(entry); 1300 } 1301 1302 checkEvictionQueues(map, segment, readOrder, writeOrder); 1303 checkExpirationTimes(map); 1304 1305 // access some of the elements 1306 Random random = new Random(); 1307 List<ReferenceEntry<Object, Object>> reads = Lists.newArrayList(); 1308 Iterator<ReferenceEntry<Object, Object>> i = readOrder.iterator(); 1309 while (i.hasNext()) { 1310 ReferenceEntry<Object, Object> entry = i.next(); 1311 if (random.nextBoolean()) { 1312 segment.recordRead(entry); 1313 reads.add(entry); 1314 i.remove(); 1315 } 1316 } 1317 checkAndDrainRecencyQueue(map, segment, reads); 1318 readOrder.addAll(reads); 1319 1320 checkEvictionQueues(map, segment, readOrder, writeOrder); 1321 checkExpirationTimes(map); 1322 } 1323 } 1324 testRecordReadOnGet()1325 public void testRecordReadOnGet() { 1326 for (MapMaker maker : allEvictingMakers()) { 1327 MapMakerInternalMap<Object, Object> map = makeMap(maker.concurrencyLevel(1)); 1328 Segment<Object, Object> segment = map.segments[0]; 1329 List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList(); 1330 List<ReferenceEntry<Object, Object>> readOrder = Lists.newLinkedList(); 1331 for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) { 1332 Object key = new Object(); 1333 int hash = map.hash(key); 1334 Object value = new Object(); 1335 1336 map.put(key, value); 1337 ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash); 1338 writeOrder.add(entry); 1339 readOrder.add(entry); 1340 } 1341 1342 checkEvictionQueues(map, segment, readOrder, writeOrder); 1343 checkExpirationTimes(map); 1344 assertTrue(segment.recencyQueue.isEmpty()); 1345 1346 // access some of the elements 1347 Random random = new Random(); 1348 List<ReferenceEntry<Object, Object>> reads = Lists.newArrayList(); 1349 Iterator<ReferenceEntry<Object, Object>> i = readOrder.iterator(); 1350 while (i.hasNext()) { 1351 ReferenceEntry<Object, Object> entry = i.next(); 1352 if (random.nextBoolean()) { 1353 map.get(entry.getKey()); 1354 reads.add(entry); 1355 i.remove(); 1356 assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD); 1357 } 1358 } 1359 int undrainedIndex = reads.size() - segment.recencyQueue.size(); 1360 checkAndDrainRecencyQueue(map, segment, reads.subList(undrainedIndex, reads.size())); 1361 readOrder.addAll(reads); 1362 1363 checkEvictionQueues(map, segment, readOrder, writeOrder); 1364 checkExpirationTimes(map); 1365 } 1366 } 1367 testRecordWrite()1368 public void testRecordWrite() { 1369 for (MapMaker maker : allEvictingMakers()) { 1370 MapMakerInternalMap<Object, Object> map = makeMap(maker.concurrencyLevel(1)); 1371 Segment<Object, Object> segment = map.segments[0]; 1372 List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList(); 1373 for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) { 1374 Object key = new Object(); 1375 int hash = map.hash(key); 1376 Object value = new Object(); 1377 1378 ReferenceEntry<Object, Object> entry = createDummyEntry(key, hash, value, null); 1379 // must recordRead for drainRecencyQueue to believe this entry is live 1380 segment.recordWrite(entry); 1381 writeOrder.add(entry); 1382 } 1383 1384 checkEvictionQueues(map, segment, writeOrder, writeOrder); 1385 checkExpirationTimes(map); 1386 1387 // access some of the elements 1388 Random random = new Random(); 1389 List<ReferenceEntry<Object, Object>> writes = Lists.newArrayList(); 1390 Iterator<ReferenceEntry<Object, Object>> i = writeOrder.iterator(); 1391 while (i.hasNext()) { 1392 ReferenceEntry<Object, Object> entry = i.next(); 1393 if (random.nextBoolean()) { 1394 segment.recordWrite(entry); 1395 writes.add(entry); 1396 i.remove(); 1397 } 1398 } 1399 writeOrder.addAll(writes); 1400 1401 checkEvictionQueues(map, segment, writeOrder, writeOrder); 1402 checkExpirationTimes(map); 1403 } 1404 } 1405 checkAndDrainRecencyQueue(MapMakerInternalMap<K, V> map, Segment<K, V> segment, List<ReferenceEntry<K, V>> reads)1406 static <K, V> void checkAndDrainRecencyQueue(MapMakerInternalMap<K, V> map, 1407 Segment<K, V> segment, List<ReferenceEntry<K, V>> reads) { 1408 if (map.evictsBySize() || map.expiresAfterAccess()) { 1409 assertSameEntries(reads, ImmutableList.copyOf(segment.recencyQueue)); 1410 } 1411 segment.drainRecencyQueue(); 1412 } 1413 checkEvictionQueues(MapMakerInternalMap<K, V> map, Segment<K, V> segment, List<ReferenceEntry<K, V>> readOrder, List<ReferenceEntry<K, V>> writeOrder)1414 static <K, V> void checkEvictionQueues(MapMakerInternalMap<K, V> map, 1415 Segment<K, V> segment, List<ReferenceEntry<K, V>> readOrder, 1416 List<ReferenceEntry<K, V>> writeOrder) { 1417 if (map.evictsBySize()) { 1418 assertSameEntries(readOrder, ImmutableList.copyOf(segment.evictionQueue)); 1419 } 1420 if (map.expiresAfterAccess()) { 1421 assertSameEntries(readOrder, ImmutableList.copyOf(segment.expirationQueue)); 1422 } 1423 if (map.expiresAfterWrite()) { 1424 assertSameEntries(writeOrder, ImmutableList.copyOf(segment.expirationQueue)); 1425 } 1426 } 1427 assertSameEntries(List<ReferenceEntry<K, V>> expectedEntries, List<ReferenceEntry<K, V>> actualEntries)1428 private static <K, V> void assertSameEntries(List<ReferenceEntry<K, V>> expectedEntries, 1429 List<ReferenceEntry<K, V>> actualEntries) { 1430 int size = expectedEntries.size(); 1431 assertEquals(size, actualEntries.size()); 1432 for (int i = 0; i < size; i++) { 1433 ReferenceEntry<K, V> expectedEntry = expectedEntries.get(0); 1434 ReferenceEntry<K, V> actualEntry = actualEntries.get(0); 1435 assertSame(expectedEntry.getKey(), actualEntry.getKey()); 1436 assertSame(expectedEntry.getValueReference().get(), actualEntry.getValueReference().get()); 1437 } 1438 } 1439 checkExpirationTimes(MapMakerInternalMap<K, V> map)1440 static <K, V> void checkExpirationTimes(MapMakerInternalMap<K, V> map) { 1441 if (!map.expires()) { 1442 return; 1443 } 1444 1445 for (Segment<K, V> segment : map.segments) { 1446 long lastExpirationTime = 0; 1447 for (ReferenceEntry<K, V> e : segment.recencyQueue) { 1448 long expirationTime = e.getExpirationTime(); 1449 assertTrue(expirationTime >= lastExpirationTime); 1450 lastExpirationTime = expirationTime; 1451 } 1452 1453 lastExpirationTime = 0; 1454 for (ReferenceEntry<K, V> e : segment.expirationQueue) { 1455 long expirationTime = e.getExpirationTime(); 1456 assertTrue(expirationTime >= lastExpirationTime); 1457 lastExpirationTime = expirationTime; 1458 } 1459 } 1460 } 1461 testEvictEntries()1462 public void testEvictEntries() { 1463 int maxSize = 10; 1464 MapMakerInternalMap<Object, Object> map = 1465 makeMap(createMapMaker().concurrencyLevel(1).maximumSize(maxSize)); 1466 Segment<Object, Object> segment = map.segments[0]; 1467 1468 // manually add elements to avoid eviction 1469 int originalCount = 1024; 1470 ReferenceEntry<Object, Object> entry = null; 1471 LinkedHashMap<Object, Object> originalMap = Maps.newLinkedHashMap(); 1472 for (int i = 0; i < originalCount; i++) { 1473 Object key = new Object(); 1474 Object value = new Object(); 1475 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table; 1476 int hash = map.hash(key); 1477 int index = hash & (table.length() - 1); 1478 ReferenceEntry<Object, Object> first = table.get(index); 1479 entry = map.newEntry(key, hash, first); 1480 ValueReference<Object, Object> valueRef = map.newValueReference(entry, value); 1481 entry.setValueReference(valueRef); 1482 segment.recordWrite(entry); 1483 table.set(index, entry); 1484 originalMap.put(key, value); 1485 } 1486 segment.count = originalCount; 1487 assertEquals(originalCount, originalMap.size()); 1488 assertEquals(originalMap, map); 1489 1490 for (int i = maxSize - 1; i < originalCount; i++) { 1491 assertTrue(segment.evictEntries()); 1492 Iterator<Object> it = originalMap.keySet().iterator(); 1493 it.next(); 1494 it.remove(); 1495 assertEquals(originalMap, map); 1496 } 1497 assertFalse(segment.evictEntries()); 1498 } 1499 1500 // reference queues 1501 testDrainKeyReferenceQueueOnWrite()1502 public void testDrainKeyReferenceQueueOnWrite() { 1503 for (MapMaker maker : allKeyValueStrengthMakers()) { 1504 MapMakerInternalMap<Object, Object> map = 1505 makeMap(maker.concurrencyLevel(1)); 1506 if (map.usesKeyReferences()) { 1507 Segment<Object, Object> segment = map.segments[0]; 1508 1509 Object keyOne = new Object(); 1510 int hashOne = map.hash(keyOne); 1511 Object valueOne = new Object(); 1512 Object keyTwo = new Object(); 1513 Object valueTwo = new Object(); 1514 1515 map.put(keyOne, valueOne); 1516 ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne); 1517 1518 @SuppressWarnings("unchecked") 1519 Reference<Object> reference = (Reference) entry; 1520 reference.enqueue(); 1521 1522 map.put(keyTwo, valueTwo); 1523 assertFalse(map.containsKey(keyOne)); 1524 assertFalse(map.containsValue(valueOne)); 1525 assertNull(map.get(keyOne)); 1526 assertEquals(1, map.size()); 1527 assertNull(segment.keyReferenceQueue.poll()); 1528 } 1529 } 1530 } 1531 testDrainValueReferenceQueueOnWrite()1532 public void testDrainValueReferenceQueueOnWrite() { 1533 for (MapMaker maker : allKeyValueStrengthMakers()) { 1534 MapMakerInternalMap<Object, Object> map = 1535 makeMap(maker.concurrencyLevel(1)); 1536 if (map.usesValueReferences()) { 1537 Segment<Object, Object> segment = map.segments[0]; 1538 1539 Object keyOne = new Object(); 1540 int hashOne = map.hash(keyOne); 1541 Object valueOne = new Object(); 1542 Object keyTwo = new Object(); 1543 Object valueTwo = new Object(); 1544 1545 map.put(keyOne, valueOne); 1546 ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne); 1547 ValueReference<Object, Object> valueReference = entry.getValueReference(); 1548 1549 @SuppressWarnings("unchecked") 1550 Reference<Object> reference = (Reference) valueReference; 1551 reference.enqueue(); 1552 1553 map.put(keyTwo, valueTwo); 1554 assertFalse(map.containsKey(keyOne)); 1555 assertFalse(map.containsValue(valueOne)); 1556 assertNull(map.get(keyOne)); 1557 assertEquals(1, map.size()); 1558 assertNull(segment.valueReferenceQueue.poll()); 1559 } 1560 } 1561 } 1562 testDrainKeyReferenceQueueOnRead()1563 public void testDrainKeyReferenceQueueOnRead() { 1564 for (MapMaker maker : allKeyValueStrengthMakers()) { 1565 MapMakerInternalMap<Object, Object> map = 1566 makeMap(maker.concurrencyLevel(1)); 1567 if (map.usesKeyReferences()) { 1568 Segment<Object, Object> segment = map.segments[0]; 1569 1570 Object keyOne = new Object(); 1571 int hashOne = map.hash(keyOne); 1572 Object valueOne = new Object(); 1573 Object keyTwo = new Object(); 1574 1575 map.put(keyOne, valueOne); 1576 ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne); 1577 1578 @SuppressWarnings("unchecked") 1579 Reference<Object> reference = (Reference) entry; 1580 reference.enqueue(); 1581 1582 for (int i = 0; i < SMALL_MAX_SIZE; i++) { 1583 map.get(keyTwo); 1584 } 1585 assertFalse(map.containsKey(keyOne)); 1586 assertFalse(map.containsValue(valueOne)); 1587 assertNull(map.get(keyOne)); 1588 assertEquals(0, map.size()); 1589 assertNull(segment.keyReferenceQueue.poll()); 1590 } 1591 } 1592 } 1593 testDrainValueReferenceQueueOnRead()1594 public void testDrainValueReferenceQueueOnRead() { 1595 for (MapMaker maker : allKeyValueStrengthMakers()) { 1596 MapMakerInternalMap<Object, Object> map = 1597 makeMap(maker.concurrencyLevel(1)); 1598 if (map.usesValueReferences()) { 1599 Segment<Object, Object> segment = map.segments[0]; 1600 1601 Object keyOne = new Object(); 1602 int hashOne = map.hash(keyOne); 1603 Object valueOne = new Object(); 1604 Object keyTwo = new Object(); 1605 1606 map.put(keyOne, valueOne); 1607 ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne); 1608 ValueReference<Object, Object> valueReference = entry.getValueReference(); 1609 1610 @SuppressWarnings("unchecked") 1611 Reference<Object> reference = (Reference) valueReference; 1612 reference.enqueue(); 1613 1614 for (int i = 0; i < SMALL_MAX_SIZE; i++) { 1615 map.get(keyTwo); 1616 } 1617 assertFalse(map.containsKey(keyOne)); 1618 assertFalse(map.containsValue(valueOne)); 1619 assertNull(map.get(keyOne)); 1620 assertEquals(0, map.size()); 1621 assertNull(segment.valueReferenceQueue.poll()); 1622 } 1623 } 1624 } 1625 1626 // utility methods 1627 1628 /** 1629 * Returns an iterable containing all combinations of maximumSize, expireAfterAccess/Write, 1630 * weak/softKeys and weak/softValues. 1631 */ allEntryTypeMakers()1632 private static Iterable<MapMaker> allEntryTypeMakers() { 1633 List<MapMaker> result = newArrayList(allKeyValueStrengthMakers()); 1634 for (MapMaker maker : allKeyValueStrengthMakers()) { 1635 result.add(maker.maximumSize(SMALL_MAX_SIZE)); 1636 } 1637 for (MapMaker maker : allKeyValueStrengthMakers()) { 1638 result.add(maker.expireAfterAccess(99999, SECONDS)); 1639 } 1640 for (MapMaker maker : allKeyValueStrengthMakers()) { 1641 result.add(maker.expireAfterWrite(99999, SECONDS)); 1642 } 1643 for (MapMaker maker : allKeyValueStrengthMakers()) { 1644 result.add(maker.maximumSize(SMALL_MAX_SIZE).expireAfterAccess(99999, SECONDS)); 1645 } 1646 for (MapMaker maker : allKeyValueStrengthMakers()) { 1647 result.add(maker.maximumSize(SMALL_MAX_SIZE).expireAfterWrite(99999, SECONDS)); 1648 } 1649 return result; 1650 } 1651 1652 /** 1653 * Returns an iterable containing all combinations of maximumSize and expireAfterAccess/Write. 1654 */ allEvictingMakers()1655 static Iterable<MapMaker> allEvictingMakers() { 1656 return ImmutableList.of(createMapMaker().maximumSize(SMALL_MAX_SIZE), 1657 createMapMaker().expireAfterAccess(99999, SECONDS), 1658 createMapMaker().expireAfterWrite(99999, SECONDS), 1659 createMapMaker() 1660 .maximumSize(SMALL_MAX_SIZE) 1661 .expireAfterAccess(SMALL_MAX_SIZE, TimeUnit.SECONDS), 1662 createMapMaker() 1663 .maximumSize(SMALL_MAX_SIZE) 1664 .expireAfterWrite(SMALL_MAX_SIZE, TimeUnit.SECONDS)); 1665 } 1666 1667 /** 1668 * Returns an iterable containing all combinations weak/softKeys and weak/softValues. 1669 */ 1670 @SuppressWarnings("deprecation") allKeyValueStrengthMakers()1671 private static Iterable<MapMaker> allKeyValueStrengthMakers() { 1672 return ImmutableList.of(createMapMaker(), 1673 createMapMaker().weakValues(), 1674 createMapMaker().softValues(), 1675 createMapMaker().weakKeys(), 1676 createMapMaker().weakKeys().weakValues(), 1677 createMapMaker().weakKeys().softValues(), 1678 createMapMaker().softKeys(), 1679 createMapMaker().softKeys().weakValues(), 1680 createMapMaker().softKeys().softValues()); 1681 } 1682 1683 // listeners 1684 1685 private static class CountingRemovalListener<K, V> implements RemovalListener<K, V> { 1686 private final AtomicInteger count = new AtomicInteger(); 1687 private K lastKey; 1688 private V lastValue; 1689 1690 @Override onRemoval(RemovalNotification<K, V> notification)1691 public void onRemoval(RemovalNotification<K, V> notification) { 1692 count.incrementAndGet(); 1693 lastKey = notification.getKey(); 1694 lastValue = notification.getValue(); 1695 } 1696 getCount()1697 public int getCount() { 1698 return count.get(); 1699 } 1700 getLastEvictedKey()1701 public K getLastEvictedKey() { 1702 return lastKey; 1703 } 1704 getLastEvictedValue()1705 public V getLastEvictedValue() { 1706 return lastValue; 1707 } 1708 } 1709 1710 static class QueuingRemovalListener<K, V> 1711 extends ConcurrentLinkedQueue<RemovalNotification<K, V>> implements RemovalListener<K, V> { 1712 @Override onRemoval(RemovalNotification<K, V> notification)1713 public void onRemoval(RemovalNotification<K, V> notification) { 1714 add(notification); 1715 } 1716 } 1717 1718 // entries and values 1719 createDummyEntry( K key, int hash, V value, ReferenceEntry<K, V> next)1720 private static <K, V> DummyEntry<K, V> createDummyEntry( 1721 K key, int hash, V value, ReferenceEntry<K, V> next) { 1722 DummyEntry<K, V> entry = DummyEntry.create(key, hash, next); 1723 DummyValueReference<K, V> valueRef = DummyValueReference.create(value, entry); 1724 entry.setValueReference(valueRef); 1725 return entry; 1726 } 1727 1728 static class DummyEntry<K, V> implements ReferenceEntry<K, V> { 1729 private K key; 1730 private final int hash; 1731 private final ReferenceEntry<K, V> next; 1732 DummyEntry(K key, int hash, ReferenceEntry<K, V> next)1733 public DummyEntry(K key, int hash, ReferenceEntry<K, V> next) { 1734 this.key = key; 1735 this.hash = hash; 1736 this.next = next; 1737 } 1738 create(K key, int hash, ReferenceEntry<K, V> next)1739 public static <K, V> DummyEntry<K, V> create(K key, int hash, ReferenceEntry<K, V> next) { 1740 return new DummyEntry<K, V>(key, hash, next); 1741 } 1742 clearKey()1743 public void clearKey() { 1744 this.key = null; 1745 } 1746 1747 private ValueReference<K, V> valueReference = unset(); 1748 1749 @Override getValueReference()1750 public ValueReference<K, V> getValueReference() { 1751 return valueReference; 1752 } 1753 1754 @Override setValueReference(ValueReference<K, V> valueReference)1755 public void setValueReference(ValueReference<K, V> valueReference) { 1756 this.valueReference = valueReference; 1757 } 1758 1759 @Override getNext()1760 public ReferenceEntry<K, V> getNext() { 1761 return next; 1762 } 1763 1764 @Override getHash()1765 public int getHash() { 1766 return hash; 1767 } 1768 1769 @Override getKey()1770 public K getKey() { 1771 return key; 1772 } 1773 1774 private long expirationTime = Long.MAX_VALUE; 1775 1776 @Override getExpirationTime()1777 public long getExpirationTime() { 1778 return expirationTime; 1779 } 1780 1781 @Override setExpirationTime(long time)1782 public void setExpirationTime(long time) { 1783 this.expirationTime = time; 1784 } 1785 1786 private ReferenceEntry<K, V> nextExpirable = nullEntry(); 1787 1788 @Override getNextExpirable()1789 public ReferenceEntry<K, V> getNextExpirable() { 1790 return nextExpirable; 1791 } 1792 1793 @Override setNextExpirable(ReferenceEntry<K, V> next)1794 public void setNextExpirable(ReferenceEntry<K, V> next) { 1795 this.nextExpirable = next; 1796 } 1797 1798 private ReferenceEntry<K, V> previousExpirable = nullEntry(); 1799 1800 @Override getPreviousExpirable()1801 public ReferenceEntry<K, V> getPreviousExpirable() { 1802 return previousExpirable; 1803 } 1804 1805 @Override setPreviousExpirable(ReferenceEntry<K, V> previous)1806 public void setPreviousExpirable(ReferenceEntry<K, V> previous) { 1807 this.previousExpirable = previous; 1808 } 1809 1810 private ReferenceEntry<K, V> nextEvictable = nullEntry(); 1811 1812 @Override getNextEvictable()1813 public ReferenceEntry<K, V> getNextEvictable() { 1814 return nextEvictable; 1815 } 1816 1817 @Override setNextEvictable(ReferenceEntry<K, V> next)1818 public void setNextEvictable(ReferenceEntry<K, V> next) { 1819 this.nextEvictable = next; 1820 } 1821 1822 private ReferenceEntry<K, V> previousEvictable = nullEntry(); 1823 1824 @Override getPreviousEvictable()1825 public ReferenceEntry<K, V> getPreviousEvictable() { 1826 return previousEvictable; 1827 } 1828 1829 @Override setPreviousEvictable(ReferenceEntry<K, V> previous)1830 public void setPreviousEvictable(ReferenceEntry<K, V> previous) { 1831 this.previousEvictable = previous; 1832 } 1833 } 1834 1835 static class DummyValueReference<K, V> implements ValueReference<K, V> { 1836 final ReferenceEntry<K, V> entry; 1837 private V value; 1838 DummyValueReference(V value, ReferenceEntry<K, V> entry)1839 public DummyValueReference(V value, ReferenceEntry<K, V> entry) { 1840 this.value = value; 1841 this.entry = entry; 1842 } 1843 create(V value, ReferenceEntry<K, V> entry)1844 public static <K, V> DummyValueReference<K, V> create(V value, ReferenceEntry<K, V> entry) { 1845 return new DummyValueReference<K, V>(value, entry); 1846 } 1847 1848 @Override get()1849 public V get() { 1850 return value; 1851 } 1852 1853 @Override getEntry()1854 public ReferenceEntry<K, V> getEntry() { 1855 return entry; 1856 } 1857 1858 @Override copyFor(ReferenceQueue<V> queue, ReferenceEntry<K, V> entry)1859 public ValueReference<K, V> copyFor(ReferenceQueue<V> queue, ReferenceEntry<K, V> entry) { 1860 return new DummyValueReference<K, V>(value, entry); 1861 } 1862 1863 boolean computing = false; 1864 setComputing(boolean computing)1865 public void setComputing(boolean computing) { 1866 this.computing = computing; 1867 } 1868 1869 @Override isComputingReference()1870 public boolean isComputingReference() { 1871 return computing; 1872 } 1873 1874 @Override waitForValue()1875 public V waitForValue() { 1876 return get(); 1877 } 1878 1879 @Override clear(ValueReference<K, V> newValue)1880 public void clear(ValueReference<K, V> newValue) { 1881 value = null; 1882 } 1883 } 1884 testNullParameters()1885 public void testNullParameters() throws Exception { 1886 NullPointerTester tester = new NullPointerTester(); 1887 tester.testAllPublicInstanceMethods(makeMap(createMapMaker())); 1888 } 1889 1890 } 1891