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