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