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.MapMakerInternalMap.DRAIN_THRESHOLD; 20 import static com.google.common.truth.Truth.assertThat; 21 22 import com.google.common.base.Equivalence; 23 import com.google.common.collect.MapMakerInternalMap.InternalEntry; 24 import com.google.common.collect.MapMakerInternalMap.Segment; 25 import com.google.common.collect.MapMakerInternalMap.Strength; 26 import com.google.common.collect.MapMakerInternalMap.WeakValueEntry; 27 import com.google.common.collect.MapMakerInternalMap.WeakValueReference; 28 import com.google.common.testing.NullPointerTester; 29 import java.lang.ref.Reference; 30 import java.util.concurrent.atomic.AtomicReferenceArray; 31 import junit.framework.TestCase; 32 33 /** @author Charles Fry */ 34 @SuppressWarnings("deprecation") // many tests of deprecated methods 35 public class MapMakerInternalMapTest extends TestCase { 36 37 static final int SMALL_MAX_SIZE = DRAIN_THRESHOLD * 5; 38 39 private static <K, V> 40 MapMakerInternalMap<K, V, ? extends InternalEntry<K, V, ?>, ? extends Segment<K, V, ?, ?>> makeMap(MapMaker maker)41 makeMap(MapMaker maker) { 42 return MapMakerInternalMap.create(maker); 43 } 44 createMapMaker()45 private static MapMaker createMapMaker() { 46 MapMaker maker = new MapMaker(); 47 maker.useCustomMap = true; 48 return maker; 49 } 50 51 // constructor tests 52 testDefaults()53 public void testDefaults() { 54 MapMakerInternalMap<Object, Object, ?, ?> map = makeMap(createMapMaker()); 55 56 assertSame(Strength.STRONG, map.keyStrength()); 57 assertSame(Strength.STRONG, map.valueStrength()); 58 assertSame(map.keyStrength().defaultEquivalence(), map.keyEquivalence); 59 assertSame(map.valueStrength().defaultEquivalence(), map.valueEquivalence()); 60 61 assertThat(map.entryHelper) 62 .isInstanceOf(MapMakerInternalMap.StrongKeyStrongValueEntry.Helper.class); 63 64 assertEquals(4, map.concurrencyLevel); 65 66 // concurrency level 67 assertThat(map.segments).hasLength(4); 68 // initial capacity / concurrency level 69 assertEquals(16 / map.segments.length, map.segments[0].table.length()); 70 } 71 testSetKeyEquivalence()72 public void testSetKeyEquivalence() { 73 Equivalence<Object> testEquivalence = 74 new Equivalence<Object>() { 75 @Override 76 protected boolean doEquivalent(Object a, Object b) { 77 return false; 78 } 79 80 @Override 81 protected int doHash(Object t) { 82 return 0; 83 } 84 }; 85 86 MapMakerInternalMap<Object, Object, ?, ?> map = 87 makeMap(createMapMaker().keyEquivalence(testEquivalence)); 88 assertSame(testEquivalence, map.keyEquivalence); 89 assertSame(map.valueStrength().defaultEquivalence(), map.valueEquivalence()); 90 } 91 testSetConcurrencyLevel()92 public void testSetConcurrencyLevel() { 93 // round up to the nearest power of two 94 95 checkConcurrencyLevel(1, 1); 96 checkConcurrencyLevel(2, 2); 97 checkConcurrencyLevel(3, 4); 98 checkConcurrencyLevel(4, 4); 99 checkConcurrencyLevel(5, 8); 100 checkConcurrencyLevel(6, 8); 101 checkConcurrencyLevel(7, 8); 102 checkConcurrencyLevel(8, 8); 103 } 104 checkConcurrencyLevel(int concurrencyLevel, int segmentCount)105 private static void checkConcurrencyLevel(int concurrencyLevel, int segmentCount) { 106 MapMakerInternalMap<Object, Object, ?, ?> map = 107 makeMap(createMapMaker().concurrencyLevel(concurrencyLevel)); 108 assertThat(map.segments).hasLength(segmentCount); 109 } 110 testSetInitialCapacity()111 public void testSetInitialCapacity() { 112 // share capacity over each segment, then round up to the nearest power of two 113 114 checkInitialCapacity(1, 0, 1); 115 checkInitialCapacity(1, 1, 1); 116 checkInitialCapacity(1, 2, 2); 117 checkInitialCapacity(1, 3, 4); 118 checkInitialCapacity(1, 4, 4); 119 checkInitialCapacity(1, 5, 8); 120 checkInitialCapacity(1, 6, 8); 121 checkInitialCapacity(1, 7, 8); 122 checkInitialCapacity(1, 8, 8); 123 124 checkInitialCapacity(2, 0, 1); 125 checkInitialCapacity(2, 1, 1); 126 checkInitialCapacity(2, 2, 1); 127 checkInitialCapacity(2, 3, 2); 128 checkInitialCapacity(2, 4, 2); 129 checkInitialCapacity(2, 5, 4); 130 checkInitialCapacity(2, 6, 4); 131 checkInitialCapacity(2, 7, 4); 132 checkInitialCapacity(2, 8, 4); 133 134 checkInitialCapacity(4, 0, 1); 135 checkInitialCapacity(4, 1, 1); 136 checkInitialCapacity(4, 2, 1); 137 checkInitialCapacity(4, 3, 1); 138 checkInitialCapacity(4, 4, 1); 139 checkInitialCapacity(4, 5, 2); 140 checkInitialCapacity(4, 6, 2); 141 checkInitialCapacity(4, 7, 2); 142 checkInitialCapacity(4, 8, 2); 143 } 144 checkInitialCapacity( int concurrencyLevel, int initialCapacity, int segmentSize)145 private static void checkInitialCapacity( 146 int concurrencyLevel, int initialCapacity, int segmentSize) { 147 MapMakerInternalMap<Object, Object, ?, ?> map = 148 makeMap( 149 createMapMaker().concurrencyLevel(concurrencyLevel).initialCapacity(initialCapacity)); 150 for (int i = 0; i < map.segments.length; i++) { 151 assertEquals(segmentSize, map.segments[i].table.length()); 152 } 153 } 154 testSetWeakKeys()155 public void testSetWeakKeys() { 156 MapMakerInternalMap<Object, Object, ?, ?> map = makeMap(createMapMaker().weakKeys()); 157 checkStrength(map, Strength.WEAK, Strength.STRONG); 158 assertThat(map.entryHelper) 159 .isInstanceOf(MapMakerInternalMap.WeakKeyStrongValueEntry.Helper.class); 160 } 161 testSetWeakValues()162 public void testSetWeakValues() { 163 MapMakerInternalMap<Object, Object, ?, ?> map = makeMap(createMapMaker().weakValues()); 164 checkStrength(map, Strength.STRONG, Strength.WEAK); 165 assertThat(map.entryHelper) 166 .isInstanceOf(MapMakerInternalMap.StrongKeyWeakValueEntry.Helper.class); 167 } 168 checkStrength( MapMakerInternalMap<Object, Object, ?, ?> map, Strength keyStrength, Strength valueStrength)169 private static void checkStrength( 170 MapMakerInternalMap<Object, Object, ?, ?> map, Strength keyStrength, Strength valueStrength) { 171 assertSame(keyStrength, map.keyStrength()); 172 assertSame(valueStrength, map.valueStrength()); 173 assertSame(keyStrength.defaultEquivalence(), map.keyEquivalence); 174 assertSame(valueStrength.defaultEquivalence(), map.valueEquivalence()); 175 } 176 177 // Segment core tests 178 testNewEntry()179 public void testNewEntry() { 180 for (MapMaker maker : allWeakValueStrengthMakers()) { 181 MapMakerInternalMap<Object, Object, ?, ?> map = makeMap(maker); 182 Segment<Object, Object, ?, ?> segment = map.segments[0]; 183 184 Object keyOne = new Object(); 185 Object valueOne = new Object(); 186 int hashOne = map.hash(keyOne); 187 InternalEntry<Object, Object, ?> entryOne = segment.newEntryForTesting(keyOne, hashOne, null); 188 WeakValueReference<Object, Object, ?> valueRefOne = 189 segment.newWeakValueReferenceForTesting(entryOne, valueOne); 190 assertSame(valueOne, valueRefOne.get()); 191 segment.setWeakValueReferenceForTesting(entryOne, valueRefOne); 192 193 assertSame(keyOne, entryOne.getKey()); 194 assertEquals(hashOne, entryOne.getHash()); 195 assertNull(entryOne.getNext()); 196 assertSame(valueRefOne, segment.getWeakValueReferenceForTesting(entryOne)); 197 198 Object keyTwo = new Object(); 199 Object valueTwo = new Object(); 200 int hashTwo = map.hash(keyTwo); 201 202 InternalEntry<Object, Object, ?> entryTwo = 203 segment.newEntryForTesting(keyTwo, hashTwo, entryOne); 204 WeakValueReference<Object, Object, ?> valueRefTwo = 205 segment.newWeakValueReferenceForTesting(entryTwo, valueTwo); 206 assertSame(valueTwo, valueRefTwo.get()); 207 segment.setWeakValueReferenceForTesting(entryTwo, valueRefTwo); 208 209 assertSame(keyTwo, entryTwo.getKey()); 210 assertEquals(hashTwo, entryTwo.getHash()); 211 assertSame(entryOne, entryTwo.getNext()); 212 assertSame(valueRefTwo, segment.getWeakValueReferenceForTesting(entryTwo)); 213 } 214 } 215 testCopyEntry()216 public void testCopyEntry() { 217 for (MapMaker maker : allWeakValueStrengthMakers()) { 218 MapMakerInternalMap<Object, Object, ?, ?> map = makeMap(maker); 219 Segment<Object, Object, ?, ?> segment = map.segments[0]; 220 221 Object keyOne = new Object(); 222 Object valueOne = new Object(); 223 int hashOne = map.hash(keyOne); 224 InternalEntry<Object, Object, ?> entryOne = segment.newEntryForTesting(keyOne, hashOne, null); 225 segment.setValueForTesting(entryOne, valueOne); 226 227 Object keyTwo = new Object(); 228 Object valueTwo = new Object(); 229 int hashTwo = map.hash(keyTwo); 230 InternalEntry<Object, Object, ?> entryTwo = segment.newEntryForTesting(keyTwo, hashTwo, null); 231 segment.setValueForTesting(entryTwo, valueTwo); 232 233 InternalEntry<Object, Object, ?> copyOne = segment.copyForTesting(entryOne, null); 234 assertSame(keyOne, entryOne.getKey()); 235 assertEquals(hashOne, entryOne.getHash()); 236 assertNull(entryOne.getNext()); 237 assertSame(valueOne, copyOne.getValue()); 238 239 InternalEntry<Object, Object, ?> copyTwo = segment.copyForTesting(entryTwo, copyOne); 240 assertSame(keyTwo, copyTwo.getKey()); 241 assertEquals(hashTwo, copyTwo.getHash()); 242 assertSame(copyOne, copyTwo.getNext()); 243 assertSame(valueTwo, copyTwo.getValue()); 244 } 245 } 246 testSegmentGetAndContains()247 public void testSegmentGetAndContains() { 248 MapMakerInternalMap<Object, Object, ?, ?> map = 249 makeMap(createMapMaker().concurrencyLevel(1).weakValues()); 250 Segment<Object, Object, ?, ?> segment = map.segments[0]; 251 // TODO(fry): check recency ordering 252 253 Object key = new Object(); 254 int hash = map.hash(key); 255 Object value = new Object(); 256 AtomicReferenceArray<? extends InternalEntry<Object, Object, ?>> table = segment.table; 257 int index = hash & (table.length() - 1); 258 259 InternalEntry<Object, Object, ?> entry = segment.newEntryForTesting(key, hash, null); 260 segment.setValueForTesting(entry, value); 261 262 assertNull(segment.get(key, hash)); 263 264 // count == 0 265 segment.setTableEntryForTesting(index, entry); 266 assertNull(segment.get(key, hash)); 267 assertFalse(segment.containsKey(key, hash)); 268 assertFalse(segment.containsValue(value)); 269 270 // count == 1 271 segment.count++; 272 assertSame(value, segment.get(key, hash)); 273 assertTrue(segment.containsKey(key, hash)); 274 assertTrue(segment.containsValue(value)); 275 // don't see absent values now that count > 0 276 assertNull(segment.get(new Object(), hash)); 277 278 // null key 279 InternalEntry<Object, Object, ?> nullEntry = segment.newEntryForTesting(null, hash, entry); 280 Object nullValue = new Object(); 281 WeakValueReference<Object, Object, ?> nullValueRef = 282 segment.newWeakValueReferenceForTesting(nullEntry, nullValue); 283 segment.setWeakValueReferenceForTesting(nullEntry, nullValueRef); 284 segment.setTableEntryForTesting(index, nullEntry); 285 // skip the null key 286 assertSame(value, segment.get(key, hash)); 287 assertTrue(segment.containsKey(key, hash)); 288 assertTrue(segment.containsValue(value)); 289 assertFalse(segment.containsValue(nullValue)); 290 291 // hash collision 292 InternalEntry<Object, Object, ?> dummyEntry = 293 segment.newEntryForTesting(new Object(), hash, entry); 294 Object dummyValue = new Object(); 295 WeakValueReference<Object, Object, ?> dummyValueRef = 296 segment.newWeakValueReferenceForTesting(dummyEntry, dummyValue); 297 segment.setWeakValueReferenceForTesting(dummyEntry, dummyValueRef); 298 segment.setTableEntryForTesting(index, dummyEntry); 299 assertSame(value, segment.get(key, hash)); 300 assertTrue(segment.containsKey(key, hash)); 301 assertTrue(segment.containsValue(value)); 302 assertTrue(segment.containsValue(dummyValue)); 303 304 // key collision 305 dummyEntry = segment.newEntryForTesting(key, hash, entry); 306 dummyValue = new Object(); 307 dummyValueRef = segment.newWeakValueReferenceForTesting(dummyEntry, dummyValue); 308 segment.setWeakValueReferenceForTesting(dummyEntry, dummyValueRef); 309 segment.setTableEntryForTesting(index, dummyEntry); 310 // returns the most recent entry 311 assertSame(dummyValue, segment.get(key, hash)); 312 assertTrue(segment.containsKey(key, hash)); 313 assertTrue(segment.containsValue(value)); 314 assertTrue(segment.containsValue(dummyValue)); 315 } 316 testSegmentReplaceValue()317 public void testSegmentReplaceValue() { 318 MapMakerInternalMap<Object, Object, ?, ?> map = 319 makeMap(createMapMaker().concurrencyLevel(1).weakValues()); 320 Segment<Object, Object, ?, ?> segment = map.segments[0]; 321 // TODO(fry): check recency ordering 322 323 Object key = new Object(); 324 int hash = map.hash(key); 325 Object oldValue = new Object(); 326 Object newValue = new Object(); 327 AtomicReferenceArray<? extends InternalEntry<Object, Object, ?>> table = segment.table; 328 int index = hash & (table.length() - 1); 329 330 InternalEntry<Object, Object, ?> entry = segment.newEntryForTesting(key, hash, null); 331 WeakValueReference<Object, Object, ?> oldValueRef = 332 segment.newWeakValueReferenceForTesting(entry, oldValue); 333 segment.setWeakValueReferenceForTesting(entry, oldValueRef); 334 335 // no entry 336 assertFalse(segment.replace(key, hash, oldValue, newValue)); 337 assertEquals(0, segment.count); 338 339 // same value 340 segment.setTableEntryForTesting(index, entry); 341 segment.count++; 342 assertEquals(1, segment.count); 343 assertSame(oldValue, segment.get(key, hash)); 344 assertTrue(segment.replace(key, hash, oldValue, newValue)); 345 assertEquals(1, segment.count); 346 assertSame(newValue, segment.get(key, hash)); 347 348 // different value 349 assertFalse(segment.replace(key, hash, oldValue, newValue)); 350 assertEquals(1, segment.count); 351 assertSame(newValue, segment.get(key, hash)); 352 353 // cleared 354 segment.setWeakValueReferenceForTesting(entry, oldValueRef); 355 oldValueRef.clear(); 356 assertFalse(segment.replace(key, hash, oldValue, newValue)); 357 assertEquals(0, segment.count); 358 assertNull(segment.get(key, hash)); 359 } 360 testSegmentReplace()361 public void testSegmentReplace() { 362 MapMakerInternalMap<Object, Object, ?, ?> map = 363 makeMap(createMapMaker().concurrencyLevel(1).weakValues()); 364 Segment<Object, Object, ?, ?> segment = map.segments[0]; 365 // TODO(fry): check recency ordering 366 367 Object key = new Object(); 368 int hash = map.hash(key); 369 Object oldValue = new Object(); 370 Object newValue = new Object(); 371 AtomicReferenceArray<? extends InternalEntry<Object, Object, ?>> table = segment.table; 372 int index = hash & (table.length() - 1); 373 374 InternalEntry<Object, Object, ?> entry = segment.newEntryForTesting(key, hash, null); 375 WeakValueReference<Object, Object, ?> oldValueRef = 376 segment.newWeakValueReferenceForTesting(entry, oldValue); 377 segment.setWeakValueReferenceForTesting(entry, oldValueRef); 378 379 // no entry 380 assertNull(segment.replace(key, hash, newValue)); 381 assertEquals(0, segment.count); 382 383 // same key 384 segment.setTableEntryForTesting(index, entry); 385 segment.count++; 386 assertEquals(1, segment.count); 387 assertSame(oldValue, segment.get(key, hash)); 388 assertSame(oldValue, segment.replace(key, hash, newValue)); 389 assertEquals(1, segment.count); 390 assertSame(newValue, segment.get(key, hash)); 391 392 // cleared 393 segment.setWeakValueReferenceForTesting(entry, oldValueRef); 394 oldValueRef.clear(); 395 assertNull(segment.replace(key, hash, newValue)); 396 assertEquals(0, segment.count); 397 assertNull(segment.get(key, hash)); 398 } 399 testSegmentPut()400 public void testSegmentPut() { 401 MapMakerInternalMap<Object, Object, ?, ?> map = 402 makeMap(createMapMaker().concurrencyLevel(1).weakValues()); 403 Segment<Object, Object, ?, ?> segment = map.segments[0]; 404 // TODO(fry): check recency ordering 405 406 Object key = new Object(); 407 int hash = map.hash(key); 408 Object oldValue = new Object(); 409 Object newValue = new Object(); 410 411 // no entry 412 assertEquals(0, segment.count); 413 assertNull(segment.put(key, hash, oldValue, false)); 414 assertEquals(1, segment.count); 415 416 // same key 417 assertSame(oldValue, segment.put(key, hash, newValue, false)); 418 assertEquals(1, segment.count); 419 assertSame(newValue, segment.get(key, hash)); 420 421 // cleared 422 InternalEntry<Object, Object, ?> entry = segment.getEntry(key, hash); 423 WeakValueReference<Object, Object, ?> oldValueRef = 424 segment.newWeakValueReferenceForTesting(entry, oldValue); 425 segment.setWeakValueReferenceForTesting(entry, oldValueRef); 426 assertSame(oldValue, segment.get(key, hash)); 427 oldValueRef.clear(); 428 assertNull(segment.put(key, hash, newValue, false)); 429 assertEquals(1, segment.count); 430 assertSame(newValue, segment.get(key, hash)); 431 } 432 testSegmentPutIfAbsent()433 public void testSegmentPutIfAbsent() { 434 MapMakerInternalMap<Object, Object, ?, ?> map = 435 makeMap(createMapMaker().concurrencyLevel(1).weakValues()); 436 Segment<Object, Object, ?, ?> segment = map.segments[0]; 437 // TODO(fry): check recency ordering 438 439 Object key = new Object(); 440 int hash = map.hash(key); 441 Object oldValue = new Object(); 442 Object newValue = new Object(); 443 444 // no entry 445 assertEquals(0, segment.count); 446 assertNull(segment.put(key, hash, oldValue, true)); 447 assertEquals(1, segment.count); 448 449 // same key 450 assertSame(oldValue, segment.put(key, hash, newValue, true)); 451 assertEquals(1, segment.count); 452 assertSame(oldValue, segment.get(key, hash)); 453 454 // cleared 455 InternalEntry<Object, Object, ?> entry = segment.getEntry(key, hash); 456 WeakValueReference<Object, Object, ?> oldValueRef = 457 segment.newWeakValueReferenceForTesting(entry, oldValue); 458 segment.setWeakValueReferenceForTesting(entry, oldValueRef); 459 assertSame(oldValue, segment.get(key, hash)); 460 oldValueRef.clear(); 461 assertNull(segment.put(key, hash, newValue, true)); 462 assertEquals(1, segment.count); 463 assertSame(newValue, segment.get(key, hash)); 464 } 465 testSegmentPut_expand()466 public void testSegmentPut_expand() { 467 MapMakerInternalMap<Object, Object, ?, ?> map = 468 makeMap(createMapMaker().concurrencyLevel(1).initialCapacity(1)); 469 Segment<Object, Object, ?, ?> segment = map.segments[0]; 470 assertEquals(1, segment.table.length()); 471 472 int count = 1024; 473 for (int i = 0; i < count; i++) { 474 Object key = new Object(); 475 Object value = new Object(); 476 int hash = map.hash(key); 477 assertNull(segment.put(key, hash, value, false)); 478 assertTrue(segment.table.length() > i); 479 } 480 } 481 testSegmentRemove()482 public void testSegmentRemove() { 483 MapMakerInternalMap<Object, Object, ?, ?> map = 484 makeMap(createMapMaker().concurrencyLevel(1).weakValues()); 485 Segment<Object, Object, ?, ?> segment = map.segments[0]; 486 487 Object key = new Object(); 488 int hash = map.hash(key); 489 Object oldValue = new Object(); 490 AtomicReferenceArray<? extends InternalEntry<Object, Object, ?>> table = segment.table; 491 int index = hash & (table.length() - 1); 492 493 InternalEntry<Object, Object, ?> entry = segment.newEntryForTesting(key, hash, null); 494 WeakValueReference<Object, Object, ?> oldValueRef = 495 segment.newWeakValueReferenceForTesting(entry, oldValue); 496 segment.setWeakValueReferenceForTesting(entry, oldValueRef); 497 498 // no entry 499 assertEquals(0, segment.count); 500 assertNull(segment.remove(key, hash)); 501 assertEquals(0, segment.count); 502 503 // same key 504 segment.setTableEntryForTesting(index, entry); 505 segment.count++; 506 assertEquals(1, segment.count); 507 assertSame(oldValue, segment.get(key, hash)); 508 assertSame(oldValue, segment.remove(key, hash)); 509 assertEquals(0, segment.count); 510 assertNull(segment.get(key, hash)); 511 512 // cleared 513 segment.setTableEntryForTesting(index, entry); 514 segment.count++; 515 assertEquals(1, segment.count); 516 assertSame(oldValue, segment.get(key, hash)); 517 oldValueRef.clear(); 518 assertNull(segment.remove(key, hash)); 519 assertEquals(0, segment.count); 520 assertNull(segment.get(key, hash)); 521 } 522 testSegmentRemoveValue()523 public void testSegmentRemoveValue() { 524 MapMakerInternalMap<Object, Object, ?, ?> map = 525 makeMap(createMapMaker().concurrencyLevel(1).weakValues()); 526 Segment<Object, Object, ?, ?> segment = map.segments[0]; 527 528 Object key = new Object(); 529 int hash = map.hash(key); 530 Object oldValue = new Object(); 531 Object newValue = new Object(); 532 AtomicReferenceArray<? extends InternalEntry<Object, Object, ?>> table = segment.table; 533 int index = hash & (table.length() - 1); 534 535 InternalEntry<Object, Object, ?> entry = segment.newEntryForTesting(key, hash, null); 536 WeakValueReference<Object, Object, ?> oldValueRef = 537 segment.newWeakValueReferenceForTesting(entry, oldValue); 538 segment.setWeakValueReferenceForTesting(entry, oldValueRef); 539 540 // no entry 541 assertEquals(0, segment.count); 542 assertNull(segment.remove(key, hash)); 543 assertEquals(0, segment.count); 544 545 // same value 546 segment.setTableEntryForTesting(index, entry); 547 segment.count++; 548 assertEquals(1, segment.count); 549 assertSame(oldValue, segment.get(key, hash)); 550 assertTrue(segment.remove(key, hash, oldValue)); 551 assertEquals(0, segment.count); 552 assertNull(segment.get(key, hash)); 553 554 // different value 555 segment.setTableEntryForTesting(index, entry); 556 segment.count++; 557 assertEquals(1, segment.count); 558 assertSame(oldValue, segment.get(key, hash)); 559 assertFalse(segment.remove(key, hash, newValue)); 560 assertEquals(1, segment.count); 561 assertSame(oldValue, segment.get(key, hash)); 562 563 // cleared 564 assertSame(oldValue, segment.get(key, hash)); 565 oldValueRef.clear(); 566 assertFalse(segment.remove(key, hash, oldValue)); 567 assertEquals(0, segment.count); 568 assertNull(segment.get(key, hash)); 569 } 570 571 @SuppressWarnings("GuardedBy") testExpand()572 public void testExpand() { 573 MapMakerInternalMap<Object, Object, ?, ?> map = 574 makeMap(createMapMaker().concurrencyLevel(1).initialCapacity(1)); 575 Segment<Object, Object, ?, ?> segment = map.segments[0]; 576 assertEquals(1, segment.table.length()); 577 578 // manually add elements to avoid expansion 579 int originalCount = 1024; 580 InternalEntry<Object, Object, ?> entry = null; 581 for (int i = 0; i < originalCount; i++) { 582 Object key = new Object(); 583 Object value = new Object(); 584 int hash = map.hash(key); 585 // chain all entries together as we only have a single bucket 586 entry = segment.newEntryForTesting(key, hash, entry); 587 segment.setValueForTesting(entry, value); 588 } 589 segment.setTableEntryForTesting(0, entry); 590 segment.count = originalCount; 591 ImmutableMap<Object, Object> originalMap = ImmutableMap.copyOf(map); 592 assertEquals(originalCount, originalMap.size()); 593 assertEquals(originalMap, map); 594 595 for (int i = 1; i <= originalCount * 2; i *= 2) { 596 if (i > 1) { 597 // TODO(b/145386688): This access should be guarded by 'segment', which is not currently 598 // held 599 segment.expand(); 600 } 601 assertEquals(i, segment.table.length()); 602 assertEquals(originalCount, countLiveEntries(map)); 603 assertEquals(originalCount, segment.count); 604 assertEquals(originalMap, map); 605 } 606 } 607 testRemoveFromChain()608 public void testRemoveFromChain() { 609 MapMakerInternalMap<Object, Object, ?, ?> map = makeMap(createMapMaker().concurrencyLevel(1)); 610 Segment<Object, Object, ?, ?> segment = map.segments[0]; 611 612 // create 3 objects and chain them together 613 Object keyOne = new Object(); 614 Object valueOne = new Object(); 615 int hashOne = map.hash(keyOne); 616 InternalEntry<Object, Object, ?> entryOne = segment.newEntryForTesting(keyOne, hashOne, null); 617 segment.setValueForTesting(entryOne, valueOne); 618 Object keyTwo = new Object(); 619 Object valueTwo = new Object(); 620 int hashTwo = map.hash(keyTwo); 621 InternalEntry<Object, Object, ?> entryTwo = 622 segment.newEntryForTesting(keyTwo, hashTwo, entryOne); 623 segment.setValueForTesting(entryTwo, valueTwo); 624 Object keyThree = new Object(); 625 Object valueThree = new Object(); 626 int hashThree = map.hash(keyThree); 627 InternalEntry<Object, Object, ?> entryThree = 628 segment.newEntryForTesting(keyThree, hashThree, entryTwo); 629 segment.setValueForTesting(entryThree, valueThree); 630 631 // alone 632 assertNull(segment.removeFromChainForTesting(entryOne, entryOne)); 633 634 // head 635 assertSame(entryOne, segment.removeFromChainForTesting(entryTwo, entryTwo)); 636 637 // middle 638 InternalEntry<Object, Object, ?> newFirst = 639 segment.removeFromChainForTesting(entryThree, entryTwo); 640 assertSame(keyThree, newFirst.getKey()); 641 assertSame(valueThree, newFirst.getValue()); 642 assertEquals(hashThree, newFirst.getHash()); 643 assertSame(entryOne, newFirst.getNext()); 644 645 // tail (remaining entries are copied in reverse order) 646 newFirst = segment.removeFromChainForTesting(entryThree, entryOne); 647 assertSame(keyTwo, newFirst.getKey()); 648 assertSame(valueTwo, newFirst.getValue()); 649 assertEquals(hashTwo, newFirst.getHash()); 650 newFirst = newFirst.getNext(); 651 assertSame(keyThree, newFirst.getKey()); 652 assertSame(valueThree, newFirst.getValue()); 653 assertEquals(hashThree, newFirst.getHash()); 654 assertNull(newFirst.getNext()); 655 } 656 657 @SuppressWarnings("GuardedBy") testExpand_cleanup()658 public void testExpand_cleanup() { 659 MapMakerInternalMap<Object, Object, ?, ?> map = 660 makeMap(createMapMaker().concurrencyLevel(1).initialCapacity(1)); 661 Segment<Object, Object, ?, ?> segment = map.segments[0]; 662 assertEquals(1, segment.table.length()); 663 664 // manually add elements to avoid expansion 665 // 1/3 null keys, 1/3 null values 666 int originalCount = 1024; 667 InternalEntry<Object, Object, ?> entry = null; 668 for (int i = 0; i < originalCount; i++) { 669 Object key = new Object(); 670 Object value = (i % 3 == 0) ? null : new Object(); 671 int hash = map.hash(key); 672 if (i % 3 == 1) { 673 key = null; 674 } 675 // chain all entries together as we only have a single bucket 676 entry = segment.newEntryForTesting(key, hash, entry); 677 segment.setValueForTesting(entry, value); 678 } 679 segment.setTableEntryForTesting(0, entry); 680 segment.count = originalCount; 681 int liveCount = originalCount / 3; 682 assertEquals(1, segment.table.length()); 683 assertEquals(liveCount, countLiveEntries(map)); 684 ImmutableMap<Object, Object> originalMap = ImmutableMap.copyOf(map); 685 assertEquals(liveCount, originalMap.size()); 686 // can't compare map contents until cleanup occurs 687 688 for (int i = 1; i <= originalCount * 2; i *= 2) { 689 if (i > 1) { 690 // TODO(b/145386688): This access should be guarded by 'segment', which is not currently 691 // held 692 segment.expand(); 693 } 694 assertEquals(i, segment.table.length()); 695 assertEquals(liveCount, countLiveEntries(map)); 696 // expansion cleanup is sloppy, with a goal of avoiding unnecessary copies 697 assertTrue(segment.count >= liveCount); 698 assertTrue(segment.count <= originalCount); 699 assertEquals(originalMap, ImmutableMap.copyOf(map)); 700 } 701 } 702 countLiveEntries(MapMakerInternalMap<K, V, ?, ?> map)703 private static <K, V> int countLiveEntries(MapMakerInternalMap<K, V, ?, ?> map) { 704 int result = 0; 705 for (Segment<K, V, ?, ?> segment : map.segments) { 706 AtomicReferenceArray<? extends InternalEntry<K, V, ?>> table = segment.table; 707 for (int i = 0; i < table.length(); i++) { 708 for (InternalEntry<K, V, ?> e = table.get(i); e != null; e = e.getNext()) { 709 if (map.isLiveForTesting(e)) { 710 result++; 711 } 712 } 713 } 714 } 715 return result; 716 } 717 testClear()718 public void testClear() { 719 MapMakerInternalMap<Object, Object, ?, ?> map = 720 makeMap(createMapMaker().concurrencyLevel(1).initialCapacity(1)); 721 Segment<Object, Object, ?, ?> segment = map.segments[0]; 722 AtomicReferenceArray<? extends InternalEntry<Object, Object, ?>> table = segment.table; 723 assertEquals(1, table.length()); 724 725 Object key = new Object(); 726 Object value = new Object(); 727 int hash = map.hash(key); 728 InternalEntry<Object, Object, ?> entry = segment.newEntryForTesting(key, hash, null); 729 segment.setValueForTesting(entry, value); 730 731 segment.setTableEntryForTesting(0, entry); 732 segment.readCount.incrementAndGet(); 733 segment.count = 1; 734 735 assertSame(entry, table.get(0)); 736 737 segment.clear(); 738 assertNull(table.get(0)); 739 assertEquals(0, segment.readCount.get()); 740 assertEquals(0, segment.count); 741 } 742 testRemoveEntry()743 public void testRemoveEntry() { 744 MapMakerInternalMap<Object, Object, ?, ?> map = 745 makeMap(createMapMaker().concurrencyLevel(1).initialCapacity(1)); 746 Segment<Object, Object, ?, ?> segment = map.segments[0]; 747 AtomicReferenceArray<? extends InternalEntry<Object, Object, ?>> table = segment.table; 748 assertEquals(1, table.length()); 749 750 Object key = new Object(); 751 Object value = new Object(); 752 int hash = map.hash(key); 753 InternalEntry<Object, Object, ?> entry = segment.newEntryForTesting(key, hash, null); 754 segment.setValueForTesting(entry, value); 755 756 // remove absent 757 assertFalse(segment.removeTableEntryForTesting(entry)); 758 759 segment.setTableEntryForTesting(0, entry); 760 segment.count = 1; 761 assertTrue(segment.removeTableEntryForTesting(entry)); 762 assertEquals(0, segment.count); 763 assertNull(table.get(0)); 764 } 765 testClearValue()766 public void testClearValue() { 767 MapMakerInternalMap<Object, Object, ?, ?> map = 768 makeMap(createMapMaker().concurrencyLevel(1).initialCapacity(1).weakValues()); 769 Segment<Object, Object, ?, ?> segment = map.segments[0]; 770 AtomicReferenceArray<? extends InternalEntry<Object, Object, ?>> table = segment.table; 771 assertEquals(1, table.length()); 772 773 Object key = new Object(); 774 Object value = new Object(); 775 int hash = map.hash(key); 776 InternalEntry<Object, Object, ?> entry = segment.newEntryForTesting(key, hash, null); 777 segment.setValueForTesting(entry, value); 778 WeakValueReference<Object, Object, ?> valueRef = segment.getWeakValueReferenceForTesting(entry); 779 780 // clear absent 781 assertFalse(segment.clearValueForTesting(key, hash, valueRef)); 782 783 segment.setTableEntryForTesting(0, entry); 784 // don't increment count; this is used during computation 785 assertTrue(segment.clearValueForTesting(key, hash, valueRef)); 786 // no notification sent with clearValue 787 assertEquals(0, segment.count); 788 assertNull(table.get(0)); 789 790 // clear wrong value reference 791 segment.setTableEntryForTesting(0, entry); 792 WeakValueReference<Object, Object, ?> otherValueRef = 793 segment.newWeakValueReferenceForTesting(entry, value); 794 segment.setWeakValueReferenceForTesting(entry, otherValueRef); 795 assertFalse(segment.clearValueForTesting(key, hash, valueRef)); 796 segment.setWeakValueReferenceForTesting(entry, valueRef); 797 assertTrue(segment.clearValueForTesting(key, hash, valueRef)); 798 } 799 800 // reference queues 801 testDrainKeyReferenceQueueOnWrite()802 public void testDrainKeyReferenceQueueOnWrite() { 803 for (MapMaker maker : allWeakKeyStrengthMakers()) { 804 MapMakerInternalMap<Object, Object, ?, ?> map = makeMap(maker.concurrencyLevel(1)); 805 if (maker.getKeyStrength() == Strength.WEAK) { 806 Segment<Object, Object, ?, ?> segment = map.segments[0]; 807 808 Object keyOne = new Object(); 809 int hashOne = map.hash(keyOne); 810 Object valueOne = new Object(); 811 Object keyTwo = new Object(); 812 Object valueTwo = new Object(); 813 814 map.put(keyOne, valueOne); 815 InternalEntry<Object, Object, ?> entry = segment.getEntry(keyOne, hashOne); 816 817 @SuppressWarnings("unchecked") 818 Reference<Object> reference = (Reference<Object>) entry; 819 reference.enqueue(); 820 821 map.put(keyTwo, valueTwo); 822 assertFalse(map.containsKey(keyOne)); 823 assertFalse(map.containsValue(valueOne)); 824 assertNull(map.get(keyOne)); 825 assertEquals(1, map.size()); 826 assertNull(segment.getKeyReferenceQueueForTesting().poll()); 827 } 828 } 829 } 830 testDrainValueReferenceQueueOnWrite()831 public void testDrainValueReferenceQueueOnWrite() { 832 for (MapMaker maker : allWeakValueStrengthMakers()) { 833 MapMakerInternalMap<Object, Object, ?, ?> map = makeMap(maker.concurrencyLevel(1)); 834 if (maker.getValueStrength() == Strength.WEAK) { 835 Segment<Object, Object, ?, ?> segment = map.segments[0]; 836 837 Object keyOne = new Object(); 838 int hashOne = map.hash(keyOne); 839 Object valueOne = new Object(); 840 Object keyTwo = new Object(); 841 Object valueTwo = new Object(); 842 843 map.put(keyOne, valueOne); 844 WeakValueEntry<Object, Object, ?> entry = 845 (WeakValueEntry<Object, Object, ?>) segment.getEntry(keyOne, hashOne); 846 WeakValueReference<Object, Object, ?> valueReference = entry.getValueReference(); 847 848 @SuppressWarnings("unchecked") 849 Reference<Object> reference = (Reference<Object>) valueReference; 850 reference.enqueue(); 851 852 map.put(keyTwo, valueTwo); 853 assertFalse(map.containsKey(keyOne)); 854 assertFalse(map.containsValue(valueOne)); 855 assertNull(map.get(keyOne)); 856 assertEquals(1, map.size()); 857 assertNull(segment.getValueReferenceQueueForTesting().poll()); 858 } 859 } 860 } 861 testDrainKeyReferenceQueueOnRead()862 public void testDrainKeyReferenceQueueOnRead() { 863 for (MapMaker maker : allWeakKeyStrengthMakers()) { 864 MapMakerInternalMap<Object, Object, ?, ?> map = makeMap(maker.concurrencyLevel(1)); 865 if (maker.getKeyStrength() == Strength.WEAK) { 866 Segment<Object, Object, ?, ?> segment = map.segments[0]; 867 868 Object keyOne = new Object(); 869 int hashOne = map.hash(keyOne); 870 Object valueOne = new Object(); 871 Object keyTwo = new Object(); 872 873 map.put(keyOne, valueOne); 874 InternalEntry<Object, Object, ?> entry = segment.getEntry(keyOne, hashOne); 875 876 @SuppressWarnings("unchecked") 877 Reference<Object> reference = (Reference<Object>) entry; 878 reference.enqueue(); 879 880 for (int i = 0; i < SMALL_MAX_SIZE; i++) { 881 Object unused = map.get(keyTwo); 882 } 883 assertFalse(map.containsKey(keyOne)); 884 assertFalse(map.containsValue(valueOne)); 885 assertNull(map.get(keyOne)); 886 assertEquals(0, map.size()); 887 assertNull(segment.getKeyReferenceQueueForTesting().poll()); 888 } 889 } 890 } 891 testDrainValueReferenceQueueOnRead()892 public void testDrainValueReferenceQueueOnRead() { 893 for (MapMaker maker : allWeakValueStrengthMakers()) { 894 MapMakerInternalMap<Object, Object, ?, ?> map = makeMap(maker.concurrencyLevel(1)); 895 if (maker.getValueStrength() == Strength.WEAK) { 896 Segment<Object, Object, ?, ?> segment = map.segments[0]; 897 898 Object keyOne = new Object(); 899 int hashOne = map.hash(keyOne); 900 Object valueOne = new Object(); 901 Object keyTwo = new Object(); 902 903 map.put(keyOne, valueOne); 904 WeakValueEntry<Object, Object, ?> entry = 905 (WeakValueEntry<Object, Object, ?>) segment.getEntry(keyOne, hashOne); 906 WeakValueReference<Object, Object, ?> valueReference = entry.getValueReference(); 907 908 @SuppressWarnings("unchecked") 909 Reference<Object> reference = (Reference<Object>) valueReference; 910 reference.enqueue(); 911 912 for (int i = 0; i < SMALL_MAX_SIZE; i++) { 913 Object unused = map.get(keyTwo); 914 } 915 assertFalse(map.containsKey(keyOne)); 916 assertFalse(map.containsValue(valueOne)); 917 assertNull(map.get(keyOne)); 918 assertEquals(0, map.size()); 919 assertNull(segment.getValueReferenceQueueForTesting().poll()); 920 } 921 } 922 } 923 924 // utility methods 925 allWeakKeyStrengthMakers()926 private static Iterable<MapMaker> allWeakKeyStrengthMakers() { 927 return ImmutableList.of(createMapMaker().weakKeys(), createMapMaker().weakKeys().weakValues()); 928 } 929 allWeakValueStrengthMakers()930 private static Iterable<MapMaker> allWeakValueStrengthMakers() { 931 return ImmutableList.of( 932 createMapMaker().weakValues(), createMapMaker().weakKeys().weakValues()); 933 } 934 testNullParameters()935 public void testNullParameters() throws Exception { 936 NullPointerTester tester = new NullPointerTester(); 937 tester.testAllPublicInstanceMethods(makeMap(createMapMaker())); 938 } 939 } 940