1 /* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 3 * 4 * This code is free software; you can redistribute it and/or modify it 5 * under the terms of the GNU General Public License version 2 only, as 6 * published by the Free Software Foundation. 7 * 8 * This code is distributed in the hope that it will be useful, but WITHOUT 9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 11 * version 2 for more details (a copy is included in the LICENSE file that 12 * accompanied this code). 13 * 14 * You should have received a copy of the GNU General Public License version 15 * 2 along with this work; if not, write to the Free Software Foundation, 16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 17 * 18 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 19 * or visit www.oracle.com if you need additional information or have any 20 * questions. 21 */ 22 23 /* 24 * This file is available under and governed by the GNU General Public 25 * License version 2 only, as published by the Free Software Foundation. 26 * However, the following notice accompanied the original version of this 27 * file: 28 * 29 * Written by Martin Buchholz with assistance from members of JCP 30 * JSR-166 Expert Group and released to the public domain, as 31 * explained at http://creativecommons.org/publicdomain/zero/1.0/ 32 */ 33 34 /* 35 * @test 36 * @modules java.base/java.util.concurrent:open 37 * @run testng WhiteBox 38 * @summary White box tests of implementation details 39 */ 40 41 import static java.util.concurrent.TimeUnit.MILLISECONDS; 42 import static org.testng.Assert.*; 43 44 import org.testng.annotations.Test; 45 46 import java.lang.ref.ReferenceQueue; 47 import java.lang.ref.WeakReference; 48 import java.lang.invoke.MethodHandles; 49 import java.lang.invoke.VarHandle; 50 import java.util.ArrayDeque; 51 import java.util.ArrayList; 52 import java.util.Arrays; 53 import java.util.Collection; 54 import java.util.Collections; 55 import java.util.Iterator; 56 import java.util.List; 57 import java.util.NoSuchElementException; 58 import java.util.Queue; 59 import java.util.concurrent.ArrayBlockingQueue; 60 import java.util.concurrent.CountDownLatch; 61 import java.util.concurrent.ThreadLocalRandom; 62 import java.util.function.BooleanSupplier; 63 64 @Test 65 public class WhiteBox { 66 final ThreadLocalRandom rnd = ThreadLocalRandom.current(); 67 final MethodHandles.Lookup lookup = MethodHandles.lookup(); 68 final VarHandle ITRS, ITEMS, TAKEINDEX, PUTINDEX, COUNT, HEAD, NEXT, PREVTAKEINDEX; 69 WhiteBox()70 WhiteBox() throws ReflectiveOperationException { 71 Class<?> qClass = ArrayBlockingQueue.class; 72 Class<?> itrClass = Class.forName(qClass.getName() + "$Itr"); 73 Class<?> itrsClass = Class.forName(qClass.getName() + "$Itrs"); 74 Class<?> nodeClass = Class.forName(itrsClass.getName() + "$Node"); 75 ITRS = findVarHandle(qClass, "itrs", itrsClass); 76 ITEMS = findVarHandle(qClass, "items", Object[].class); 77 TAKEINDEX = findVarHandle(qClass, "takeIndex", int.class); 78 PUTINDEX = findVarHandle(qClass, "putIndex", int.class); 79 COUNT = findVarHandle(qClass, "count", int.class); 80 HEAD = findVarHandle(itrsClass, "head", nodeClass); 81 NEXT = findVarHandle(nodeClass, "next", nodeClass); 82 PREVTAKEINDEX = findVarHandle(itrClass, "prevTakeIndex", int.class); 83 } 84 findVarHandle(Class<?> recv, String name, Class<?> type)85 VarHandle findVarHandle(Class<?> recv, String name, Class<?> type) 86 throws ReflectiveOperationException { 87 return MethodHandles.privateLookupIn(recv, lookup) 88 .findVarHandle(recv, name, type); 89 } 90 itrs(ArrayBlockingQueue q)91 Object itrs(ArrayBlockingQueue q) { return ITRS.get(q); } items(ArrayBlockingQueue q)92 Object[] items(ArrayBlockingQueue q) { return (Object[]) ITEMS.get(q); } takeIndex(ArrayBlockingQueue q)93 int takeIndex(ArrayBlockingQueue q) { return (int) TAKEINDEX.get(q); } putIndex(ArrayBlockingQueue q)94 int putIndex(ArrayBlockingQueue q) { return (int) PUTINDEX.get(q); } count(ArrayBlockingQueue q)95 int count(ArrayBlockingQueue q) { return (int) COUNT.get(q); } head(Object itrs)96 Object head(Object itrs) { return HEAD.get(itrs); } next(Object node)97 Object next(Object node) { return NEXT.get(node); } prevTakeIndex(Iterator itr)98 int prevTakeIndex(Iterator itr) { return (int) PREVTAKEINDEX.get(itr); } 99 isDetached(Iterator it)100 boolean isDetached(Iterator it) { 101 return prevTakeIndex(it) < 0; 102 } 103 assertIteratorExhausted(Iterator it)104 void assertIteratorExhausted(Iterator it) { 105 if (rnd.nextBoolean()) { 106 assertTrue(!it.hasNext()); 107 assertTrue(isDetached(it)); 108 } 109 if (rnd.nextBoolean()) { 110 it.forEachRemaining(e -> { throw new AssertionError(); }); 111 assertTrue(isDetached(it)); 112 } 113 if (rnd.nextBoolean()) 114 try { it.next(); fail("should throw"); } 115 catch (NoSuchElementException success) {} 116 } 117 trackedIterators(ArrayBlockingQueue q)118 List<Iterator> trackedIterators(ArrayBlockingQueue q) { 119 List<Iterator> its = new ArrayList<>(); 120 Object itrs = itrs(q); 121 if (itrs != null) { 122 for (Object p = head(itrs); p != null; p = next(p)) 123 its.add(((WeakReference<Iterator>)(p)).get()); 124 Collections.reverse(its); 125 } 126 return its; 127 } 128 attachedIterators(ArrayBlockingQueue q)129 List<Iterator> attachedIterators(ArrayBlockingQueue q) { 130 List<Iterator> its = new ArrayList<>(); 131 Object itrs = itrs(q); 132 if (itrs != null) { 133 for (Object p = head(itrs); p != null; p = next(p)) { 134 Iterator it = ((WeakReference<Iterator>)(p)).get(); 135 if (it != null && !isDetached(it)) 136 its.add(it); 137 } 138 Collections.reverse(its); 139 } 140 return its; 141 } 142 assertRemoveThrowsISE(Iterator it)143 void assertRemoveThrowsISE(Iterator it) { 144 if (rnd.nextBoolean()) 145 try { it.remove(); fail("should throw"); } 146 catch (IllegalStateException success) {} 147 } 148 assertRemoveHasNoEffect(Iterator it, Collection c)149 void assertRemoveHasNoEffect(Iterator it, Collection c) { 150 if (rnd.nextBoolean()) { 151 int size = c.size(); 152 it.remove(); // no effect 153 assertEquals(c.size(), size); 154 assertRemoveThrowsISE(it); 155 } 156 } 157 checkIterationSanity(Queue q)158 void checkIterationSanity(Queue q) { 159 if (rnd.nextBoolean()) 160 return; 161 int size = q.size(); 162 Object[] a = q.toArray(); 163 Object[] b = new Object[size+2]; 164 Arrays.fill(b, Boolean.TRUE); 165 Object[] c = q.toArray(b); 166 assertEquals(a.length, size); 167 assertSame(b, c); 168 assertNull(b[size]); 169 assertSame(b[size+1], Boolean.TRUE); 170 assertEquals(q.toString(), Arrays.toString(a)); 171 Integer[] xx = null, yy = null; 172 if (size > 0) { 173 xx = new Integer[size - 1]; 174 Arrays.fill(xx, 42); 175 yy = ((Queue<Integer>)q).toArray(xx); 176 for (Integer zz : xx) 177 assertEquals(42, (int) zz); 178 } 179 Iterator it = q.iterator(); 180 for (int i = 0; i < size; i++) { 181 if (rnd.nextBoolean()) assertTrue(it.hasNext()); 182 Object x = it.next(); 183 assertSame(x, a[i]); 184 assertSame(x, b[i]); 185 assertSame(x, yy[i]); 186 } 187 if (rnd.nextBoolean()) assertTrue(!it.hasNext()); 188 } 189 190 /** 191 * Instead of having putIndex (and takeIndex) at the initial 192 * default of 0, move them to a random location. 193 */ randomizePutIndex(ArrayBlockingQueue q)194 void randomizePutIndex(ArrayBlockingQueue q) { 195 assertTrue(q.isEmpty()); 196 int capacity = q.remainingCapacity(); 197 int n = rnd.nextInt(capacity + 1); 198 int putIndex = putIndex(q); 199 for (int i = n; i-->0; ) q.add(Boolean.TRUE); 200 for (int i = n; i-->0; ) q.remove(); 201 assertEquals(putIndex(q), (putIndex + n) % items(q).length); 202 } 203 204 /** No guarantees, but effective in practice. */ forceFullGc()205 static void forceFullGc() { 206 long timeoutMillis = 1000L; 207 CountDownLatch finalized = new CountDownLatch(1); 208 ReferenceQueue<Object> queue = new ReferenceQueue<>(); 209 WeakReference<Object> ref = new WeakReference<>( 210 new Object() { protected void finalize() { finalized.countDown(); }}, 211 queue); 212 try { 213 for (int tries = 3; tries--> 0; ) { 214 System.gc(); 215 if (finalized.await(timeoutMillis, MILLISECONDS) 216 && queue.remove(timeoutMillis) != null 217 && ref.get() == null) { 218 System.runFinalization(); // try to pick up stragglers 219 return; 220 } 221 timeoutMillis *= 4; 222 } 223 } catch (InterruptedException unexpected) { 224 throw new AssertionError("unexpected InterruptedException"); 225 } 226 throw new AssertionError("failed to do a \"full\" gc"); 227 } 228 gcAwait(BooleanSupplier s)229 static void gcAwait(BooleanSupplier s) { 230 for (int i = 0; i < 10; i++) { 231 if (s.getAsBoolean()) 232 return; 233 forceFullGc(); 234 } 235 throw new AssertionError("failed to satisfy condition"); 236 } 237 clear_willClearItrs()238 public void clear_willClearItrs() { 239 boolean fair = rnd.nextBoolean(); 240 int capacity = rnd.nextInt(2, 10); 241 ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); 242 randomizePutIndex(q); 243 List<Iterator> its = new ArrayList<>(); 244 for (int i = 0; i < capacity; i++) 245 assertTrue(q.add(i)); 246 assertNull(itrs(q)); 247 for (int i = 0; i < capacity; i++) { 248 its.add(q.iterator()); 249 assertEquals(trackedIterators(q), its); 250 q.poll(); 251 q.add(capacity + i); 252 } 253 q.clear(); 254 assertNull(itrs(q)); 255 int j = 0; 256 for (Iterator it : its) { 257 assertTrue(isDetached(it)); 258 if (rnd.nextBoolean()) assertTrue(it.hasNext()); 259 if (rnd.nextBoolean()) { 260 assertEquals(it.next(), j); 261 assertIteratorExhausted(it); 262 } 263 j++; 264 } 265 } 266 queueEmptyingWillClearItrs()267 public void queueEmptyingWillClearItrs() { 268 boolean fair = rnd.nextBoolean(); 269 int capacity = rnd.nextInt(2, 10); 270 ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); 271 randomizePutIndex(q); 272 List<Iterator> its = new ArrayList<>(); 273 for (int i = 0; i < capacity; i++) 274 q.add(i); 275 assertNull(itrs(q)); 276 for (int i = 0; i < capacity; i++) { 277 its.add(q.iterator()); 278 assertEquals(trackedIterators(q), its); 279 q.poll(); 280 q.add(capacity+i); 281 } 282 for (int i = 0; i < capacity; i++) 283 q.poll(); 284 assertNull(itrs(q)); 285 int j = 0; 286 for (Iterator it : its) { 287 assertTrue(isDetached(it)); 288 if (rnd.nextBoolean()) assertTrue(it.hasNext()); 289 if (rnd.nextBoolean()) { 290 assertEquals(it.next(), j); 291 assertIteratorExhausted(it); 292 } 293 j++; 294 } 295 } 296 advancing2CyclesWillRemoveIterators()297 public void advancing2CyclesWillRemoveIterators() { 298 boolean fair = rnd.nextBoolean(); 299 int capacity = rnd.nextInt(2, 10); 300 ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); 301 List<Iterator> its = new ArrayList<>(); 302 for (int i = 0; i < capacity; i++) 303 q.add(i); 304 assertNull(itrs(q)); 305 for (int i = capacity; i < 3 * capacity; i++) { 306 its.add(q.iterator()); 307 assertEquals(trackedIterators(q), its); 308 q.poll(); 309 q.add(i); 310 } 311 for (int i = 3 * capacity; i < 4 * capacity; i++) { 312 assertEquals(trackedIterators(q), its.subList(capacity,2*capacity)); 313 q.poll(); 314 q.add(i); 315 } 316 assertNull(itrs(q)); 317 int j = 0; 318 for (Iterator it : its) { 319 assertTrue(isDetached(it)); 320 if (rnd.nextBoolean()) assertTrue(it.hasNext()); 321 if (rnd.nextBoolean()) { 322 assertEquals(it.next(), j); 323 assertIteratorExhausted(it); 324 } 325 j++; 326 } 327 } 328 329 /** 330 * Interior removal of elements used by an iterator will cause it 331 * to be untracked. 332 */ interiorRemovalOfElementsUsedByIterator()333 public void interiorRemovalOfElementsUsedByIterator() { 334 boolean fair = rnd.nextBoolean(); 335 int capacity = rnd.nextInt(10, 20); 336 ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); 337 randomizePutIndex(q); 338 q.add(0); 339 for (int i = 1; i < 2 * capacity; i++) { 340 q.add(i); 341 Integer[] elts = { -1, -2, -3 }; 342 for (Integer elt : elts) q.add(elt); 343 assertEquals(q.remove(), i - 1); 344 Iterator it = q.iterator(); 345 assertEquals(it.next(), i); 346 assertEquals(it.next(), elts[0]); 347 Collections.shuffle(Arrays.asList(elts)); 348 assertTrue(q.remove(elts[0])); 349 assertTrue(q.remove(elts[1])); 350 assertEquals(trackedIterators(q), Collections.singletonList(it)); 351 assertTrue(q.remove(elts[2])); 352 assertNull(itrs(q)); 353 assertEquals(it.next(), -2); 354 assertIteratorExhausted(it); 355 assertTrue(isDetached(it)); 356 } 357 } 358 iteratorsOnEmptyQueue()359 public void iteratorsOnEmptyQueue() { 360 boolean fair = rnd.nextBoolean(); 361 int capacity = rnd.nextInt(1, 10); 362 ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); 363 randomizePutIndex(q); 364 for (int i = 0; i < 4; i++) { 365 Iterator it = q.iterator(); 366 assertNull(itrs(q)); 367 assertIteratorExhausted(it); 368 assertTrue(isDetached(it)); 369 assertRemoveThrowsISE(it); 370 } 371 } 372 interiorRemovalOfIteratorsLastElement()373 public void interiorRemovalOfIteratorsLastElement() { 374 boolean fair = rnd.nextBoolean(); 375 int capacity = rnd.nextInt(3, 10); 376 ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); 377 randomizePutIndex(q); 378 List<Iterator> its = new ArrayList<>(); 379 for (int i = 0; i < capacity; i++) 380 q.add(i); 381 for (int i = 0; i < capacity; i++) { 382 Iterator it = q.iterator(); 383 its.add(it); 384 for (int j = 0; j < i; j++) 385 assertEquals(j, it.next()); 386 assertEquals(attachedIterators(q), its); 387 } 388 q.remove(capacity - 1); 389 assertEquals(attachedIterators(q), its); 390 for (int i = 1; i < capacity - 1; i++) { 391 q.remove(capacity - i - 1); 392 Iterator it = its.get(capacity - i); 393 assertTrue(isDetached(it)); 394 assertEquals(attachedIterators(q), its.subList(0, capacity - i)); 395 if (rnd.nextBoolean()) assertTrue(it.hasNext()); 396 assertEquals(it.next(), capacity - i); 397 assertIteratorExhausted(it); 398 } 399 assertEquals(attachedIterators(q), its.subList(0, 2)); 400 q.remove(0); 401 assertTrue(q.isEmpty()); 402 assertNull(itrs(q)); 403 Iterator it = its.get(0); 404 assertEquals(it.next(), 0); 405 assertRemoveHasNoEffect(it, q); 406 assertIteratorExhausted(it); 407 assertTrue(isDetached(it)); 408 assertRemoveHasNoEffect(its.get(1), q); 409 } 410 411 /** 412 * Checks "interior" removal of alternating elements, straddling 2 cycles 413 */ interiorRemovalOfAlternatingElements()414 public void interiorRemovalOfAlternatingElements() { 415 boolean fair = rnd.nextBoolean(); 416 int capacity = 2 * rnd.nextInt(2, 10); 417 ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); 418 List<Iterator> its = new ArrayList<>(); 419 // Move takeIndex to middle 420 for (int i = 0; i < capacity/2; i++) { 421 assertTrue(q.add(i)); 422 assertEquals(q.poll(), i); 423 } 424 assertEquals(takeIndex(q), capacity/2); 425 for (int i = 0; i < capacity; i++) 426 q.add(i); 427 for (int i = 0; i < capacity; i++) { 428 Iterator it = q.iterator(); 429 its.add(it); 430 for (int j = 0; j < i; j++) 431 assertEquals(j, it.next()); 432 assertEquals(attachedIterators(q), its); 433 } 434 435 // Remove all even elements, in either direction, using 436 // q.remove(), or iterator.remove() 437 switch (rnd.nextInt(3)) { 438 case 0: 439 for (int i = 0; i < capacity; i+=2) assertTrue(q.remove(i)); 440 break; 441 case 1: 442 for (int i = capacity - 2; i >= 0; i-=2) assertTrue(q.remove(i)); 443 break; 444 case 2: 445 Iterator it = q.iterator(); 446 while (it.hasNext()) { 447 int i = (Integer) it.next(); 448 if ((i & 1) == 0) 449 it.remove(); 450 } 451 break; 452 default: throw new AssertionError(); 453 } 454 assertEquals(attachedIterators(q), its); 455 456 for (int i = 0; i < capacity; i++) { 457 Iterator it = its.get(i); 458 boolean even = ((i & 1) == 0); 459 if (even) { 460 if (rnd.nextBoolean()) assertTrue(it.hasNext()); 461 assertEquals(i, it.next()); 462 for (int j = i+1; j < capacity; j += 2) 463 assertEquals(j, it.next()); 464 assertTrue(!isDetached(it)); 465 assertTrue(!it.hasNext()); 466 assertTrue(isDetached(it)); 467 } else { /* odd */ 468 if (rnd.nextBoolean()) assertTrue(it.hasNext()); 469 assertRemoveHasNoEffect(it, q); 470 assertEquals(i, it.next()); 471 for (int j = i+2; j < capacity; j += 2) 472 assertEquals(j, it.next()); 473 assertTrue(!isDetached(it)); 474 assertTrue(!it.hasNext()); 475 assertTrue(isDetached(it)); 476 } 477 } 478 assertEquals(trackedIterators(q), Collections.emptyList()); 479 assertNull(itrs(q)); 480 } 481 garbageCollectionOfUnreachableIterators()482 public void garbageCollectionOfUnreachableIterators() { 483 boolean fair = rnd.nextBoolean(); 484 int capacity = rnd.nextInt(1, 10); 485 ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); 486 randomizePutIndex(q); 487 List<Iterator> its = new ArrayList<>(); 488 for (int i = 0; i < capacity; i++) q.add(i); 489 for (int i = 0; i < capacity; i++) its.add(q.iterator()); 490 assertEquals(attachedIterators(q), its); 491 its = null; 492 gcAwait(() -> { 493 List<Iterator> trackedIterators = trackedIterators(q); 494 assertEquals(trackedIterators.size(), capacity); 495 for (Iterator x : trackedIterators) 496 if (x != null) return false; 497 return true; 498 }); 499 Iterator it = q.iterator(); // 500 assertEquals(trackedIterators(q), Collections.singletonList(it)); 501 } 502 garbageCollectionOfUnreachableIteratorsWithRandomlyRetainedSubset()503 public void garbageCollectionOfUnreachableIteratorsWithRandomlyRetainedSubset() { 504 boolean fair = rnd.nextBoolean(); 505 int capacity = rnd.nextInt(10, 20); 506 ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); 507 randomizePutIndex(q); 508 List<Iterator> its = new ArrayList<>(); 509 List<Iterator> retained = new ArrayList<>(); 510 final int size = 1 + rnd.nextInt(capacity); 511 for (int i = 0; i < size; i++) q.add(i); 512 for (int i = 0; i < size; i++) its.add(q.iterator()); 513 assertEquals(attachedIterators(q), its); 514 // Leave sufficient gaps in retained 515 for (int i = 0; i < size; i+= 2+rnd.nextInt(3)) 516 retained.add(its.get(i)); 517 its = null; 518 gcAwait(() -> { 519 List<Iterator> trackedIterators = trackedIterators(q); 520 assertEquals(trackedIterators.size(), size); 521 for (Iterator it : trackedIterators) 522 if ((it != null) ^ retained.contains(it)) return false; 523 return true; 524 }); 525 Iterator it = q.iterator(); // trigger another sweep 526 retained.add(it); 527 assertEquals(trackedIterators(q), retained); 528 } 529 530 /** 531 * Checks incremental sweeping of unreachable iterators. 532 * Excessively white box?! 533 */ incrementalSweepingOfUnreachableIterators()534 public void incrementalSweepingOfUnreachableIterators() { 535 boolean fair = rnd.nextBoolean(); 536 int capacity = rnd.nextInt(10, 20); 537 ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); 538 randomizePutIndex(q); 539 final int SHORT_SWEEP_PROBES = 4; 540 final int LONG_SWEEP_PROBES = 16; 541 final int PROBE_HOP = LONG_SWEEP_PROBES + 6 * SHORT_SWEEP_PROBES; 542 final int PROBE_HOP_COUNT = 10; 543 // Expect around 8 sweeps per PROBE_HOP 544 final int SWEEPS_PER_PROBE_HOP = 8; 545 List<Iterator> its = new ArrayList<>(); 546 for (int i = 0; i < capacity; i++) 547 q.add(i); 548 for (int i = 0; i < PROBE_HOP_COUNT * PROBE_HOP; i++) 549 its.add(q.iterator()); 550 assertEquals(attachedIterators(q), its); 551 // make some garbage, separated by PROBE_HOP 552 for (int i = 0; i < its.size(); i += PROBE_HOP) 553 its.set(i, null); 554 its.removeIf(it -> it == null); 555 forceFullGc(); 556 int retries; 557 for (retries = 0; 558 trackedIterators(q).contains(null) && retries < 1000; 559 retries++) 560 // one round of sweeping 561 its.add(q.iterator()); 562 assertTrue(retries >= PROBE_HOP_COUNT * (SWEEPS_PER_PROBE_HOP - 2)); 563 assertTrue(retries <= PROBE_HOP_COUNT * (SWEEPS_PER_PROBE_HOP + 2)); 564 assertEquals(trackedIterators(q), its); 565 } 566 Iterator_remove_safetyWhileInDetachedMode()567 public void Iterator_remove_safetyWhileInDetachedMode() { 568 boolean fair = rnd.nextBoolean(); 569 int capacity = rnd.nextInt(10, 20); 570 ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); 571 List<Iterator> its = new ArrayList<>(); 572 for (int i = 0; i < capacity/2; i++) { 573 q.add(i); 574 q.remove(); 575 } 576 assertEquals(takeIndex(q), capacity/2); 577 for (int i = 0; i < capacity; i++) 578 q.add(i); 579 for (int i = 0; i < capacity; i++) { 580 Iterator it = q.iterator(); 581 its.add(it); 582 for (int j = 0; j < i; j++) 583 assertEquals(j, it.next()); 584 } 585 assertEquals(attachedIterators(q), its); 586 for (int i = capacity - 1; i >= 0; i--) { 587 Iterator it = its.get(i); 588 assertEquals(i, it.next()); // last element 589 assertTrue(!isDetached(it)); 590 assertTrue(!it.hasNext()); // first hasNext failure 591 assertTrue(isDetached(it)); 592 int size = q.size(); 593 assertTrue(q.contains(i)); 594 switch (rnd.nextInt(3)) { 595 case 0: 596 it.remove(); 597 assertTrue(!q.contains(i)); 598 assertEquals(q.size(), size - 1); 599 break; 600 case 1: 601 // replace i with impostor 602 if (q.remainingCapacity() == 0) { 603 assertTrue(q.remove(i)); 604 assertTrue(q.add(-1)); 605 } else { 606 assertTrue(q.add(-1)); 607 assertTrue(q.remove(i)); 608 } 609 it.remove(); // should have no effect 610 assertEquals(size, q.size()); 611 assertTrue(q.contains(-1)); 612 assertTrue(q.remove(-1)); 613 break; 614 case 2: 615 // replace i with true impostor 616 if (i != 0) { 617 assertTrue(q.remove(i)); 618 assertTrue(q.add(i)); 619 } 620 it.remove(); 621 assertTrue(!q.contains(i)); 622 assertEquals(q.size(), size - 1); 623 break; 624 default: throw new AssertionError(); 625 } 626 assertRemoveThrowsISE(it); 627 assertTrue(isDetached(it)); 628 assertTrue(!trackedIterators(q).contains(it)); 629 } 630 assertTrue(q.isEmpty()); 631 assertNull(itrs(q)); 632 for (Iterator it : its) 633 assertIteratorExhausted(it); 634 } 635 636 /** 637 * Checks dequeues bypassing iterators' current positions. 638 */ dequeuesBypassingIteratorCurrentPositions()639 public void dequeuesBypassingIteratorCurrentPositions() { 640 boolean fair = rnd.nextBoolean(); 641 int capacity = rnd.nextInt(10, 20); 642 ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); 643 Queue<Iterator> its0 = new ArrayDeque<>(); 644 Queue<Iterator> itsMid = new ArrayDeque<>(); 645 List<Iterator> its = new ArrayList<>(); 646 for (int i = 0; i < capacity; i++) 647 q.add(i); 648 for (int i = 0; i < 2 * capacity + 1; i++) { 649 Iterator it = q.iterator(); 650 its.add(it); 651 its0.add(it); 652 } 653 for (int i = 0; i < 2 * capacity + 1; i++) { 654 Iterator it = q.iterator(); 655 for (int j = 0; j < capacity/2; j++) 656 assertEquals(j, it.next()); 657 its.add(it); 658 itsMid.add(it); 659 } 660 for (int i = capacity; i < 3 * capacity; i++) { 661 Iterator it; 662 663 it = its0.remove(); 664 assertRemoveThrowsISE(it); 665 if (rnd.nextBoolean()) assertTrue(it.hasNext()); 666 assertEquals(0, it.next()); 667 int victim = i - capacity; 668 for (int j = victim + (victim == 0 ? 1 : 0); j < i; j++) { 669 if (rnd.nextBoolean()) assertTrue(it.hasNext()); 670 assertEquals(j, it.next()); 671 } 672 assertIteratorExhausted(it); 673 674 it = itsMid.remove(); 675 if (victim >= capacity/2) 676 assertRemoveHasNoEffect(it, q); 677 assertEquals(capacity/2, it.next()); 678 if (victim > capacity/2) 679 assertRemoveHasNoEffect(it, q); 680 for (int j = Math.max(victim, capacity/2 + 1); j < i; j++) { 681 if (rnd.nextBoolean()) assertTrue(it.hasNext()); 682 assertEquals(j, it.next()); 683 } 684 assertIteratorExhausted(it); 685 686 if (rnd.nextBoolean()) { 687 assertEquals(victim, q.remove()); 688 } else { 689 ArrayList list = new ArrayList(1); 690 q.drainTo(list, 1); 691 assertEquals(list.size(), 1); 692 assertEquals(victim, list.get(0)); 693 } 694 assertTrue(q.add(i)); 695 } 696 // takeIndex has wrapped twice. 697 Iterator it0 = its0.remove(); 698 Iterator itMid = itsMid.remove(); 699 assertTrue(isDetached(it0)); 700 assertTrue(isDetached(itMid)); 701 if (rnd.nextBoolean()) assertTrue(it0.hasNext()); 702 if (rnd.nextBoolean()) assertTrue(itMid.hasNext()); 703 assertRemoveThrowsISE(it0); 704 assertRemoveHasNoEffect(itMid, q); 705 if (rnd.nextBoolean()) assertEquals(0, it0.next()); 706 if (rnd.nextBoolean()) assertEquals(capacity/2, itMid.next()); 707 assertTrue(isDetached(it0)); 708 assertTrue(isDetached(itMid)); 709 assertEquals(capacity, q.size()); 710 assertEquals(0, q.remainingCapacity()); 711 } 712 713 /** 714 * Checks collective sanity of iteration, toArray() and toString(). 715 */ collectiveSanity()716 public void collectiveSanity() { 717 boolean fair = rnd.nextBoolean(); 718 int capacity = rnd.nextInt(10, 20); 719 ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); 720 randomizePutIndex(q); 721 for (int i = 0; i < capacity; i++) { 722 checkIterationSanity(q); 723 assertEquals(capacity, q.size() + q.remainingCapacity()); 724 q.add(i); 725 } 726 for (int i = 0; i < (capacity + (capacity >> 1)); i++) { 727 checkIterationSanity(q); 728 assertEquals(capacity, q.size() + q.remainingCapacity()); 729 assertEquals(i, q.peek()); 730 assertEquals(i, q.poll()); 731 checkIterationSanity(q); 732 assertEquals(capacity, q.size() + q.remainingCapacity()); 733 q.add(capacity + i); 734 } 735 for (int i = 0; i < capacity; i++) { 736 checkIterationSanity(q); 737 assertEquals(capacity, q.size() + q.remainingCapacity()); 738 int expected = i + capacity + (capacity >> 1); 739 assertEquals(expected, q.peek()); 740 assertEquals(expected, q.poll()); 741 } 742 checkIterationSanity(q); 743 } 744 iteratorsDetachedWhenExhaustedAndLastRetRemoved()745 public void iteratorsDetachedWhenExhaustedAndLastRetRemoved() { 746 boolean fair = rnd.nextBoolean(); 747 int capacity = rnd.nextInt(2, 10); 748 ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair); 749 randomizePutIndex(q); 750 int size = rnd.nextInt(1, capacity + 1); 751 for (int i = 0; i < size; i++) q.add(i); 752 Iterator it = q.iterator(); 753 for (int i = 0; i < size - 1; i++) assertEquals(i, it.next()); 754 assertEquals(trackedIterators(q), Collections.singletonList(it)); 755 assertFalse(isDetached(it)); 756 switch (rnd.nextInt(2)) { 757 case 0: assertTrue(q.remove(size - 1)); break; 758 case 1: assertTrue(q.removeIf(e -> e.equals(size - 1))); break; 759 default: throw new AssertionError(); 760 } 761 assertEquals(size - 1, it.next()); // should trigger detach 762 assertNull(itrs(q)); 763 assertTrue(isDetached(it)); 764 assertRemoveHasNoEffect(it, q); 765 } 766 } 767