Print this page
| Split |
Close |
| Expand all |
| Collapse all |
--- old/src/share/classes/java/util/concurrent/LinkedBlockingDeque.java
+++ new/src/share/classes/java/util/concurrent/LinkedBlockingDeque.java
1 1 /*
2 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 3 *
4 4 * This code is free software; you can redistribute it and/or modify it
5 5 * under the terms of the GNU General Public License version 2 only, as
6 6 * published by the Free Software Foundation. Oracle designates this
7 7 * particular file as subject to the "Classpath" exception as provided
8 8 * by Oracle in the LICENSE file that accompanied this code.
9 9 *
10 10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 13 * version 2 for more details (a copy is included in the LICENSE file that
14 14 * accompanied this code).
15 15 *
16 16 * You should have received a copy of the GNU General Public License version
17 17 * 2 along with this work; if not, write to the Free Software Foundation,
18 18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 19 *
20 20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 21 * or visit www.oracle.com if you need additional information or have any
22 22 * questions.
23 23 */
24 24
25 25 /*
26 26 * This file is available under and governed by the GNU General Public
27 27 * License version 2 only, as published by the Free Software Foundation.
28 28 * However, the following notice accompanied the original version of this
29 29 * file:
30 30 *
31 31 * Written by Doug Lea with assistance from members of JCP JSR-166
32 32 * Expert Group and released to the public domain, as explained at
33 33 * http://creativecommons.org/licenses/publicdomain
34 34 */
35 35
36 36 package java.util.concurrent;
37 37
38 38 import java.util.AbstractQueue;
39 39 import java.util.Collection;
40 40 import java.util.Iterator;
41 41 import java.util.NoSuchElementException;
42 42 import java.util.concurrent.locks.Condition;
43 43 import java.util.concurrent.locks.ReentrantLock;
44 44
45 45 /**
46 46 * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on
47 47 * linked nodes.
48 48 *
49 49 * <p> The optional capacity bound constructor argument serves as a
50 50 * way to prevent excessive expansion. The capacity, if unspecified,
51 51 * is equal to {@link Integer#MAX_VALUE}. Linked nodes are
52 52 * dynamically created upon each insertion unless this would bring the
53 53 * deque above capacity.
54 54 *
55 55 * <p>Most operations run in constant time (ignoring time spent
56 56 * blocking). Exceptions include {@link #remove(Object) remove},
57 57 * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link
58 58 * #removeLastOccurrence removeLastOccurrence}, {@link #contains
59 59 * contains}, {@link #iterator iterator.remove()}, and the bulk
60 60 * operations, all of which run in linear time.
61 61 *
62 62 * <p>This class and its iterator implement all of the
63 63 * <em>optional</em> methods of the {@link Collection} and {@link
64 64 * Iterator} interfaces.
65 65 *
66 66 * <p>This class is a member of the
67 67 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
68 68 * Java Collections Framework</a>.
69 69 *
70 70 * @since 1.6
71 71 * @author Doug Lea
72 72 * @param <E> the type of elements held in this collection
73 73 */
74 74 public class LinkedBlockingDeque<E>
75 75 extends AbstractQueue<E>
76 76 implements BlockingDeque<E>, java.io.Serializable {
77 77
78 78 /*
79 79 * Implemented as a simple doubly-linked list protected by a
80 80 * single lock and using conditions to manage blocking.
81 81 *
82 82 * To implement weakly consistent iterators, it appears we need to
83 83 * keep all Nodes GC-reachable from a predecessor dequeued Node.
84 84 * That would cause two problems:
85 85 * - allow a rogue Iterator to cause unbounded memory retention
86 86 * - cause cross-generational linking of old Nodes to new Nodes if
87 87 * a Node was tenured while live, which generational GCs have a
88 88 * hard time dealing with, causing repeated major collections.
89 89 * However, only non-deleted Nodes need to be reachable from
90 90 * dequeued Nodes, and reachability does not necessarily have to
91 91 * be of the kind understood by the GC. We use the trick of
92 92 * linking a Node that has just been dequeued to itself. Such a
93 93 * self-link implicitly means to jump to "first" (for next links)
94 94 * or "last" (for prev links).
95 95 */
96 96
97 97 /*
98 98 * We have "diamond" multiple interface/abstract class inheritance
99 99 * here, and that introduces ambiguities. Often we want the
100 100 * BlockingDeque javadoc combined with the AbstractQueue
101 101 * implementation, so a lot of method specs are duplicated here.
102 102 */
103 103
104 104 private static final long serialVersionUID = -387911632671998426L;
105 105
106 106 /** Doubly-linked list node class */
107 107 static final class Node<E> {
108 108 /**
109 109 * The item, or null if this node has been removed.
110 110 */
111 111 E item;
112 112
113 113 /**
114 114 * One of:
115 115 * - the real predecessor Node
116 116 * - this Node, meaning the predecessor is tail
117 117 * - null, meaning there is no predecessor
118 118 */
|
↓ open down ↓ |
118 lines elided |
↑ open up ↑ |
119 119 Node<E> prev;
120 120
121 121 /**
122 122 * One of:
123 123 * - the real successor Node
124 124 * - this Node, meaning the successor is head
125 125 * - null, meaning there is no successor
126 126 */
127 127 Node<E> next;
128 128
129 - Node(E x, Node<E> p, Node<E> n) {
129 + Node(E x) {
130 130 item = x;
131 - prev = p;
132 - next = n;
133 131 }
134 132 }
135 133
136 134 /**
137 135 * Pointer to first node.
138 136 * Invariant: (first == null && last == null) ||
139 137 * (first.prev == null && first.item != null)
140 138 */
141 139 transient Node<E> first;
142 140
143 141 /**
144 142 * Pointer to last node.
145 143 * Invariant: (first == null && last == null) ||
146 144 * (last.next == null && last.item != null)
147 145 */
148 146 transient Node<E> last;
149 147
150 148 /** Number of items in the deque */
151 149 private transient int count;
152 150
153 151 /** Maximum number of items in the deque */
154 152 private final int capacity;
155 153
156 154 /** Main lock guarding all access */
157 155 final ReentrantLock lock = new ReentrantLock();
158 156
159 157 /** Condition for waiting takes */
160 158 private final Condition notEmpty = lock.newCondition();
161 159
162 160 /** Condition for waiting puts */
163 161 private final Condition notFull = lock.newCondition();
164 162
165 163 /**
166 164 * Creates a {@code LinkedBlockingDeque} with a capacity of
167 165 * {@link Integer#MAX_VALUE}.
168 166 */
169 167 public LinkedBlockingDeque() {
170 168 this(Integer.MAX_VALUE);
171 169 }
172 170
173 171 /**
174 172 * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity.
175 173 *
176 174 * @param capacity the capacity of this deque
177 175 * @throws IllegalArgumentException if {@code capacity} is less than 1
178 176 */
179 177 public LinkedBlockingDeque(int capacity) {
180 178 if (capacity <= 0) throw new IllegalArgumentException();
181 179 this.capacity = capacity;
182 180 }
183 181
184 182 /**
185 183 * Creates a {@code LinkedBlockingDeque} with a capacity of
186 184 * {@link Integer#MAX_VALUE}, initially containing the elements of
187 185 * the given collection, added in traversal order of the
188 186 * collection's iterator.
189 187 *
190 188 * @param c the collection of elements to initially contain
191 189 * @throws NullPointerException if the specified collection or any
|
↓ open down ↓ |
49 lines elided |
↑ open up ↑ |
192 190 * of its elements are null
193 191 */
194 192 public LinkedBlockingDeque(Collection<? extends E> c) {
195 193 this(Integer.MAX_VALUE);
196 194 final ReentrantLock lock = this.lock;
197 195 lock.lock(); // Never contended, but necessary for visibility
198 196 try {
199 197 for (E e : c) {
200 198 if (e == null)
201 199 throw new NullPointerException();
202 - if (!linkLast(e))
200 + if (!linkLast(new Node<E>(e)))
203 201 throw new IllegalStateException("Deque full");
204 202 }
205 203 } finally {
206 204 lock.unlock();
207 205 }
208 206 }
209 207
210 208
211 209 // Basic linking and unlinking operations, called only while holding lock
212 210
213 211 /**
214 - * Links e as first element, or returns false if full.
212 + * Links node as first element, or returns false if full.
215 213 */
216 - private boolean linkFirst(E e) {
214 + private boolean linkFirst(Node<E> node) {
217 215 // assert lock.isHeldByCurrentThread();
218 216 if (count >= capacity)
219 217 return false;
220 218 Node<E> f = first;
221 - Node<E> x = new Node<E>(e, null, f);
222 - first = x;
219 + node.next = f;
220 + first = node;
223 221 if (last == null)
224 - last = x;
222 + last = node;
225 223 else
226 - f.prev = x;
224 + f.prev = node;
227 225 ++count;
228 226 notEmpty.signal();
229 227 return true;
230 228 }
231 229
232 230 /**
233 - * Links e as last element, or returns false if full.
231 + * Links node as last element, or returns false if full.
234 232 */
235 - private boolean linkLast(E e) {
233 + private boolean linkLast(Node<E> node) {
236 234 // assert lock.isHeldByCurrentThread();
237 235 if (count >= capacity)
238 236 return false;
239 237 Node<E> l = last;
240 - Node<E> x = new Node<E>(e, l, null);
241 - last = x;
238 + node.prev = l;
239 + last = node;
242 240 if (first == null)
243 - first = x;
241 + first = node;
244 242 else
245 - l.next = x;
243 + l.next = node;
246 244 ++count;
247 245 notEmpty.signal();
248 246 return true;
249 247 }
250 248
251 249 /**
252 250 * Removes and returns first element, or null if empty.
253 251 */
254 252 private E unlinkFirst() {
255 253 // assert lock.isHeldByCurrentThread();
256 254 Node<E> f = first;
257 255 if (f == null)
258 256 return null;
259 257 Node<E> n = f.next;
260 258 E item = f.item;
261 259 f.item = null;
262 260 f.next = f; // help GC
263 261 first = n;
264 262 if (n == null)
265 263 last = null;
266 264 else
267 265 n.prev = null;
268 266 --count;
269 267 notFull.signal();
270 268 return item;
271 269 }
272 270
273 271 /**
274 272 * Removes and returns last element, or null if empty.
275 273 */
276 274 private E unlinkLast() {
277 275 // assert lock.isHeldByCurrentThread();
278 276 Node<E> l = last;
279 277 if (l == null)
280 278 return null;
281 279 Node<E> p = l.prev;
282 280 E item = l.item;
283 281 l.item = null;
284 282 l.prev = l; // help GC
285 283 last = p;
286 284 if (p == null)
287 285 first = null;
288 286 else
289 287 p.next = null;
290 288 --count;
291 289 notFull.signal();
292 290 return item;
293 291 }
294 292
295 293 /**
296 294 * Unlinks x.
297 295 */
298 296 void unlink(Node<E> x) {
299 297 // assert lock.isHeldByCurrentThread();
300 298 Node<E> p = x.prev;
301 299 Node<E> n = x.next;
302 300 if (p == null) {
303 301 unlinkFirst();
304 302 } else if (n == null) {
305 303 unlinkLast();
306 304 } else {
307 305 p.next = n;
308 306 n.prev = p;
309 307 x.item = null;
310 308 // Don't mess with x's links. They may still be in use by
311 309 // an iterator.
312 310 --count;
313 311 notFull.signal();
314 312 }
315 313 }
316 314
317 315 // BlockingDeque methods
318 316
319 317 /**
320 318 * @throws IllegalStateException {@inheritDoc}
321 319 * @throws NullPointerException {@inheritDoc}
322 320 */
323 321 public void addFirst(E e) {
324 322 if (!offerFirst(e))
325 323 throw new IllegalStateException("Deque full");
326 324 }
327 325
328 326 /**
329 327 * @throws IllegalStateException {@inheritDoc}
330 328 * @throws NullPointerException {@inheritDoc}
331 329 */
|
↓ open down ↓ |
76 lines elided |
↑ open up ↑ |
332 330 public void addLast(E e) {
333 331 if (!offerLast(e))
334 332 throw new IllegalStateException("Deque full");
335 333 }
336 334
337 335 /**
338 336 * @throws NullPointerException {@inheritDoc}
339 337 */
340 338 public boolean offerFirst(E e) {
341 339 if (e == null) throw new NullPointerException();
340 + Node<E> node = new Node<E>(e);
342 341 final ReentrantLock lock = this.lock;
343 342 lock.lock();
344 343 try {
345 - return linkFirst(e);
344 + return linkFirst(node);
346 345 } finally {
347 346 lock.unlock();
348 347 }
349 348 }
350 349
351 350 /**
352 351 * @throws NullPointerException {@inheritDoc}
353 352 */
354 353 public boolean offerLast(E e) {
355 354 if (e == null) throw new NullPointerException();
355 + Node<E> node = new Node<E>(e);
356 356 final ReentrantLock lock = this.lock;
357 357 lock.lock();
358 358 try {
359 - return linkLast(e);
359 + return linkLast(node);
360 360 } finally {
361 361 lock.unlock();
362 362 }
363 363 }
364 364
365 365 /**
366 366 * @throws NullPointerException {@inheritDoc}
367 367 * @throws InterruptedException {@inheritDoc}
368 368 */
369 369 public void putFirst(E e) throws InterruptedException {
370 370 if (e == null) throw new NullPointerException();
371 + Node<E> node = new Node<E>(e);
371 372 final ReentrantLock lock = this.lock;
372 373 lock.lock();
373 374 try {
374 - while (!linkFirst(e))
375 + while (!linkFirst(node))
375 376 notFull.await();
376 377 } finally {
377 378 lock.unlock();
378 379 }
379 380 }
380 381
381 382 /**
382 383 * @throws NullPointerException {@inheritDoc}
383 384 * @throws InterruptedException {@inheritDoc}
384 385 */
385 386 public void putLast(E e) throws InterruptedException {
386 387 if (e == null) throw new NullPointerException();
388 + Node<E> node = new Node<E>(e);
387 389 final ReentrantLock lock = this.lock;
388 390 lock.lock();
389 391 try {
390 - while (!linkLast(e))
392 + while (!linkLast(node))
391 393 notFull.await();
392 394 } finally {
393 395 lock.unlock();
394 396 }
395 397 }
396 398
397 399 /**
398 400 * @throws NullPointerException {@inheritDoc}
399 401 * @throws InterruptedException {@inheritDoc}
400 402 */
401 403 public boolean offerFirst(E e, long timeout, TimeUnit unit)
402 404 throws InterruptedException {
403 405 if (e == null) throw new NullPointerException();
406 + Node<E> node = new Node<E>(e);
404 407 long nanos = unit.toNanos(timeout);
405 408 final ReentrantLock lock = this.lock;
406 409 lock.lockInterruptibly();
407 410 try {
408 - while (!linkFirst(e)) {
411 + while (!linkFirst(node)) {
409 412 if (nanos <= 0)
410 413 return false;
411 414 nanos = notFull.awaitNanos(nanos);
412 415 }
413 416 return true;
414 417 } finally {
415 418 lock.unlock();
416 419 }
417 420 }
418 421
419 422 /**
420 423 * @throws NullPointerException {@inheritDoc}
421 424 * @throws InterruptedException {@inheritDoc}
422 425 */
423 426 public boolean offerLast(E e, long timeout, TimeUnit unit)
424 427 throws InterruptedException {
425 428 if (e == null) throw new NullPointerException();
429 + Node<E> node = new Node<E>(e);
426 430 long nanos = unit.toNanos(timeout);
427 431 final ReentrantLock lock = this.lock;
428 432 lock.lockInterruptibly();
429 433 try {
430 - while (!linkLast(e)) {
434 + while (!linkLast(node)) {
431 435 if (nanos <= 0)
432 436 return false;
433 437 nanos = notFull.awaitNanos(nanos);
434 438 }
435 439 return true;
436 440 } finally {
437 441 lock.unlock();
438 442 }
439 443 }
440 444
441 445 /**
442 446 * @throws NoSuchElementException {@inheritDoc}
443 447 */
444 448 public E removeFirst() {
445 449 E x = pollFirst();
446 450 if (x == null) throw new NoSuchElementException();
447 451 return x;
448 452 }
449 453
450 454 /**
451 455 * @throws NoSuchElementException {@inheritDoc}
452 456 */
453 457 public E removeLast() {
454 458 E x = pollLast();
455 459 if (x == null) throw new NoSuchElementException();
456 460 return x;
457 461 }
458 462
459 463 public E pollFirst() {
460 464 final ReentrantLock lock = this.lock;
461 465 lock.lock();
462 466 try {
463 467 return unlinkFirst();
464 468 } finally {
465 469 lock.unlock();
466 470 }
467 471 }
468 472
469 473 public E pollLast() {
470 474 final ReentrantLock lock = this.lock;
471 475 lock.lock();
472 476 try {
473 477 return unlinkLast();
474 478 } finally {
475 479 lock.unlock();
476 480 }
477 481 }
478 482
479 483 public E takeFirst() throws InterruptedException {
480 484 final ReentrantLock lock = this.lock;
481 485 lock.lock();
482 486 try {
483 487 E x;
484 488 while ( (x = unlinkFirst()) == null)
485 489 notEmpty.await();
486 490 return x;
487 491 } finally {
488 492 lock.unlock();
489 493 }
490 494 }
491 495
492 496 public E takeLast() throws InterruptedException {
493 497 final ReentrantLock lock = this.lock;
494 498 lock.lock();
495 499 try {
496 500 E x;
497 501 while ( (x = unlinkLast()) == null)
498 502 notEmpty.await();
499 503 return x;
500 504 } finally {
501 505 lock.unlock();
502 506 }
503 507 }
504 508
505 509 public E pollFirst(long timeout, TimeUnit unit)
506 510 throws InterruptedException {
507 511 long nanos = unit.toNanos(timeout);
508 512 final ReentrantLock lock = this.lock;
509 513 lock.lockInterruptibly();
510 514 try {
511 515 E x;
512 516 while ( (x = unlinkFirst()) == null) {
513 517 if (nanos <= 0)
514 518 return null;
515 519 nanos = notEmpty.awaitNanos(nanos);
516 520 }
517 521 return x;
518 522 } finally {
519 523 lock.unlock();
520 524 }
521 525 }
522 526
523 527 public E pollLast(long timeout, TimeUnit unit)
524 528 throws InterruptedException {
525 529 long nanos = unit.toNanos(timeout);
526 530 final ReentrantLock lock = this.lock;
527 531 lock.lockInterruptibly();
528 532 try {
529 533 E x;
530 534 while ( (x = unlinkLast()) == null) {
531 535 if (nanos <= 0)
532 536 return null;
533 537 nanos = notEmpty.awaitNanos(nanos);
534 538 }
535 539 return x;
536 540 } finally {
537 541 lock.unlock();
538 542 }
539 543 }
540 544
541 545 /**
542 546 * @throws NoSuchElementException {@inheritDoc}
543 547 */
544 548 public E getFirst() {
545 549 E x = peekFirst();
546 550 if (x == null) throw new NoSuchElementException();
547 551 return x;
548 552 }
549 553
550 554 /**
551 555 * @throws NoSuchElementException {@inheritDoc}
552 556 */
553 557 public E getLast() {
554 558 E x = peekLast();
555 559 if (x == null) throw new NoSuchElementException();
556 560 return x;
557 561 }
558 562
559 563 public E peekFirst() {
560 564 final ReentrantLock lock = this.lock;
561 565 lock.lock();
562 566 try {
563 567 return (first == null) ? null : first.item;
564 568 } finally {
565 569 lock.unlock();
566 570 }
567 571 }
568 572
569 573 public E peekLast() {
570 574 final ReentrantLock lock = this.lock;
571 575 lock.lock();
572 576 try {
573 577 return (last == null) ? null : last.item;
574 578 } finally {
575 579 lock.unlock();
576 580 }
577 581 }
578 582
579 583 public boolean removeFirstOccurrence(Object o) {
580 584 if (o == null) return false;
581 585 final ReentrantLock lock = this.lock;
582 586 lock.lock();
583 587 try {
584 588 for (Node<E> p = first; p != null; p = p.next) {
585 589 if (o.equals(p.item)) {
586 590 unlink(p);
587 591 return true;
588 592 }
589 593 }
590 594 return false;
591 595 } finally {
592 596 lock.unlock();
593 597 }
594 598 }
595 599
596 600 public boolean removeLastOccurrence(Object o) {
597 601 if (o == null) return false;
598 602 final ReentrantLock lock = this.lock;
599 603 lock.lock();
600 604 try {
601 605 for (Node<E> p = last; p != null; p = p.prev) {
602 606 if (o.equals(p.item)) {
603 607 unlink(p);
604 608 return true;
605 609 }
606 610 }
607 611 return false;
608 612 } finally {
609 613 lock.unlock();
610 614 }
611 615 }
612 616
613 617 // BlockingQueue methods
614 618
615 619 /**
616 620 * Inserts the specified element at the end of this deque unless it would
617 621 * violate capacity restrictions. When using a capacity-restricted deque,
618 622 * it is generally preferable to use method {@link #offer(Object) offer}.
619 623 *
620 624 * <p>This method is equivalent to {@link #addLast}.
621 625 *
622 626 * @throws IllegalStateException if the element cannot be added at this
623 627 * time due to capacity restrictions
624 628 * @throws NullPointerException if the specified element is null
625 629 */
626 630 public boolean add(E e) {
627 631 addLast(e);
628 632 return true;
629 633 }
630 634
631 635 /**
632 636 * @throws NullPointerException if the specified element is null
633 637 */
634 638 public boolean offer(E e) {
635 639 return offerLast(e);
636 640 }
637 641
638 642 /**
639 643 * @throws NullPointerException {@inheritDoc}
640 644 * @throws InterruptedException {@inheritDoc}
641 645 */
642 646 public void put(E e) throws InterruptedException {
643 647 putLast(e);
644 648 }
645 649
646 650 /**
647 651 * @throws NullPointerException {@inheritDoc}
648 652 * @throws InterruptedException {@inheritDoc}
649 653 */
650 654 public boolean offer(E e, long timeout, TimeUnit unit)
651 655 throws InterruptedException {
652 656 return offerLast(e, timeout, unit);
653 657 }
654 658
655 659 /**
656 660 * Retrieves and removes the head of the queue represented by this deque.
657 661 * This method differs from {@link #poll poll} only in that it throws an
658 662 * exception if this deque is empty.
659 663 *
660 664 * <p>This method is equivalent to {@link #removeFirst() removeFirst}.
661 665 *
662 666 * @return the head of the queue represented by this deque
663 667 * @throws NoSuchElementException if this deque is empty
664 668 */
665 669 public E remove() {
666 670 return removeFirst();
667 671 }
668 672
669 673 public E poll() {
670 674 return pollFirst();
671 675 }
672 676
673 677 public E take() throws InterruptedException {
674 678 return takeFirst();
675 679 }
676 680
677 681 public E poll(long timeout, TimeUnit unit) throws InterruptedException {
678 682 return pollFirst(timeout, unit);
679 683 }
680 684
681 685 /**
682 686 * Retrieves, but does not remove, the head of the queue represented by
683 687 * this deque. This method differs from {@link #peek peek} only in that
684 688 * it throws an exception if this deque is empty.
685 689 *
686 690 * <p>This method is equivalent to {@link #getFirst() getFirst}.
687 691 *
688 692 * @return the head of the queue represented by this deque
689 693 * @throws NoSuchElementException if this deque is empty
690 694 */
691 695 public E element() {
692 696 return getFirst();
693 697 }
694 698
695 699 public E peek() {
696 700 return peekFirst();
697 701 }
698 702
699 703 /**
700 704 * Returns the number of additional elements that this deque can ideally
701 705 * (in the absence of memory or resource constraints) accept without
702 706 * blocking. This is always equal to the initial capacity of this deque
703 707 * less the current {@code size} of this deque.
704 708 *
705 709 * <p>Note that you <em>cannot</em> always tell if an attempt to insert
706 710 * an element will succeed by inspecting {@code remainingCapacity}
707 711 * because it may be the case that another thread is about to
708 712 * insert or remove an element.
709 713 */
710 714 public int remainingCapacity() {
711 715 final ReentrantLock lock = this.lock;
712 716 lock.lock();
713 717 try {
714 718 return capacity - count;
715 719 } finally {
716 720 lock.unlock();
717 721 }
718 722 }
719 723
720 724 /**
721 725 * @throws UnsupportedOperationException {@inheritDoc}
722 726 * @throws ClassCastException {@inheritDoc}
723 727 * @throws NullPointerException {@inheritDoc}
724 728 * @throws IllegalArgumentException {@inheritDoc}
725 729 */
726 730 public int drainTo(Collection<? super E> c) {
727 731 return drainTo(c, Integer.MAX_VALUE);
728 732 }
729 733
730 734 /**
731 735 * @throws UnsupportedOperationException {@inheritDoc}
732 736 * @throws ClassCastException {@inheritDoc}
733 737 * @throws NullPointerException {@inheritDoc}
734 738 * @throws IllegalArgumentException {@inheritDoc}
735 739 */
736 740 public int drainTo(Collection<? super E> c, int maxElements) {
737 741 if (c == null)
738 742 throw new NullPointerException();
739 743 if (c == this)
740 744 throw new IllegalArgumentException();
741 745 final ReentrantLock lock = this.lock;
742 746 lock.lock();
743 747 try {
744 748 int n = Math.min(maxElements, count);
745 749 for (int i = 0; i < n; i++) {
746 750 c.add(first.item); // In this order, in case add() throws.
747 751 unlinkFirst();
748 752 }
749 753 return n;
750 754 } finally {
751 755 lock.unlock();
752 756 }
753 757 }
754 758
755 759 // Stack methods
756 760
757 761 /**
758 762 * @throws IllegalStateException {@inheritDoc}
759 763 * @throws NullPointerException {@inheritDoc}
760 764 */
761 765 public void push(E e) {
762 766 addFirst(e);
763 767 }
764 768
765 769 /**
766 770 * @throws NoSuchElementException {@inheritDoc}
767 771 */
768 772 public E pop() {
769 773 return removeFirst();
770 774 }
771 775
772 776 // Collection methods
773 777
774 778 /**
775 779 * Removes the first occurrence of the specified element from this deque.
776 780 * If the deque does not contain the element, it is unchanged.
777 781 * More formally, removes the first element {@code e} such that
778 782 * {@code o.equals(e)} (if such an element exists).
779 783 * Returns {@code true} if this deque contained the specified element
780 784 * (or equivalently, if this deque changed as a result of the call).
781 785 *
782 786 * <p>This method is equivalent to
783 787 * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}.
784 788 *
785 789 * @param o element to be removed from this deque, if present
786 790 * @return {@code true} if this deque changed as a result of the call
787 791 */
788 792 public boolean remove(Object o) {
789 793 return removeFirstOccurrence(o);
790 794 }
791 795
792 796 /**
793 797 * Returns the number of elements in this deque.
794 798 *
795 799 * @return the number of elements in this deque
796 800 */
797 801 public int size() {
798 802 final ReentrantLock lock = this.lock;
799 803 lock.lock();
800 804 try {
801 805 return count;
802 806 } finally {
803 807 lock.unlock();
804 808 }
805 809 }
806 810
807 811 /**
808 812 * Returns {@code true} if this deque contains the specified element.
809 813 * More formally, returns {@code true} if and only if this deque contains
810 814 * at least one element {@code e} such that {@code o.equals(e)}.
811 815 *
812 816 * @param o object to be checked for containment in this deque
813 817 * @return {@code true} if this deque contains the specified element
814 818 */
815 819 public boolean contains(Object o) {
816 820 if (o == null) return false;
817 821 final ReentrantLock lock = this.lock;
818 822 lock.lock();
819 823 try {
820 824 for (Node<E> p = first; p != null; p = p.next)
821 825 if (o.equals(p.item))
822 826 return true;
823 827 return false;
824 828 } finally {
825 829 lock.unlock();
826 830 }
827 831 }
828 832
829 833 /*
830 834 * TODO: Add support for more efficient bulk operations.
831 835 *
832 836 * We don't want to acquire the lock for every iteration, but we
833 837 * also want other threads a chance to interact with the
834 838 * collection, especially when count is close to capacity.
835 839 */
836 840
837 841 // /**
838 842 // * Adds all of the elements in the specified collection to this
839 843 // * queue. Attempts to addAll of a queue to itself result in
840 844 // * {@code IllegalArgumentException}. Further, the behavior of
841 845 // * this operation is undefined if the specified collection is
842 846 // * modified while the operation is in progress.
843 847 // *
844 848 // * @param c collection containing elements to be added to this queue
845 849 // * @return {@code true} if this queue changed as a result of the call
846 850 // * @throws ClassCastException {@inheritDoc}
847 851 // * @throws NullPointerException {@inheritDoc}
848 852 // * @throws IllegalArgumentException {@inheritDoc}
849 853 // * @throws IllegalStateException {@inheritDoc}
850 854 // * @see #add(Object)
851 855 // */
852 856 // public boolean addAll(Collection<? extends E> c) {
853 857 // if (c == null)
854 858 // throw new NullPointerException();
855 859 // if (c == this)
856 860 // throw new IllegalArgumentException();
857 861 // final ReentrantLock lock = this.lock;
858 862 // lock.lock();
859 863 // try {
860 864 // boolean modified = false;
861 865 // for (E e : c)
862 866 // if (linkLast(e))
863 867 // modified = true;
864 868 // return modified;
865 869 // } finally {
866 870 // lock.unlock();
867 871 // }
868 872 // }
869 873
870 874 /**
871 875 * Returns an array containing all of the elements in this deque, in
872 876 * proper sequence (from first to last element).
873 877 *
874 878 * <p>The returned array will be "safe" in that no references to it are
875 879 * maintained by this deque. (In other words, this method must allocate
876 880 * a new array). The caller is thus free to modify the returned array.
877 881 *
878 882 * <p>This method acts as bridge between array-based and collection-based
879 883 * APIs.
880 884 *
881 885 * @return an array containing all of the elements in this deque
882 886 */
883 887 @SuppressWarnings("unchecked")
884 888 public Object[] toArray() {
885 889 final ReentrantLock lock = this.lock;
886 890 lock.lock();
887 891 try {
888 892 Object[] a = new Object[count];
889 893 int k = 0;
890 894 for (Node<E> p = first; p != null; p = p.next)
891 895 a[k++] = p.item;
892 896 return a;
893 897 } finally {
894 898 lock.unlock();
895 899 }
896 900 }
897 901
898 902 /**
899 903 * Returns an array containing all of the elements in this deque, in
900 904 * proper sequence; the runtime type of the returned array is that of
901 905 * the specified array. If the deque fits in the specified array, it
902 906 * is returned therein. Otherwise, a new array is allocated with the
903 907 * runtime type of the specified array and the size of this deque.
904 908 *
905 909 * <p>If this deque fits in the specified array with room to spare
906 910 * (i.e., the array has more elements than this deque), the element in
907 911 * the array immediately following the end of the deque is set to
908 912 * {@code null}.
909 913 *
910 914 * <p>Like the {@link #toArray()} method, this method acts as bridge between
911 915 * array-based and collection-based APIs. Further, this method allows
912 916 * precise control over the runtime type of the output array, and may,
913 917 * under certain circumstances, be used to save allocation costs.
914 918 *
915 919 * <p>Suppose {@code x} is a deque known to contain only strings.
916 920 * The following code can be used to dump the deque into a newly
917 921 * allocated array of {@code String}:
918 922 *
919 923 * <pre>
920 924 * String[] y = x.toArray(new String[0]);</pre>
921 925 *
922 926 * Note that {@code toArray(new Object[0])} is identical in function to
923 927 * {@code toArray()}.
924 928 *
925 929 * @param a the array into which the elements of the deque are to
926 930 * be stored, if it is big enough; otherwise, a new array of the
927 931 * same runtime type is allocated for this purpose
928 932 * @return an array containing all of the elements in this deque
929 933 * @throws ArrayStoreException if the runtime type of the specified array
930 934 * is not a supertype of the runtime type of every element in
931 935 * this deque
932 936 * @throws NullPointerException if the specified array is null
933 937 */
934 938 @SuppressWarnings("unchecked")
935 939 public <T> T[] toArray(T[] a) {
936 940 final ReentrantLock lock = this.lock;
937 941 lock.lock();
938 942 try {
939 943 if (a.length < count)
940 944 a = (T[])java.lang.reflect.Array.newInstance
941 945 (a.getClass().getComponentType(), count);
942 946
943 947 int k = 0;
944 948 for (Node<E> p = first; p != null; p = p.next)
945 949 a[k++] = (T)p.item;
946 950 if (a.length > k)
947 951 a[k] = null;
|
↓ open down ↓ |
507 lines elided |
↑ open up ↑ |
948 952 return a;
949 953 } finally {
950 954 lock.unlock();
951 955 }
952 956 }
953 957
954 958 public String toString() {
955 959 final ReentrantLock lock = this.lock;
956 960 lock.lock();
957 961 try {
958 - return super.toString();
962 + Node<E> p = first;
963 + if (p == null)
964 + return "[]";
965 +
966 + StringBuilder sb = new StringBuilder();
967 + sb.append('[');
968 + for (;;) {
969 + E e = p.item;
970 + sb.append(e == this ? "(this Collection)" : e);
971 + p = p.next;
972 + if (p == null)
973 + return sb.append(']').toString();
974 + sb.append(',').append(' ');
975 + }
959 976 } finally {
960 977 lock.unlock();
961 978 }
962 979 }
963 980
964 981 /**
965 982 * Atomically removes all of the elements from this deque.
966 983 * The deque will be empty after this call returns.
967 984 */
968 985 public void clear() {
969 986 final ReentrantLock lock = this.lock;
970 987 lock.lock();
971 988 try {
972 989 for (Node<E> f = first; f != null; ) {
973 990 f.item = null;
974 991 Node<E> n = f.next;
975 992 f.prev = null;
976 993 f.next = null;
977 994 f = n;
978 995 }
979 996 first = last = null;
980 997 count = 0;
981 998 notFull.signalAll();
982 999 } finally {
983 1000 lock.unlock();
984 1001 }
985 1002 }
986 1003
987 1004 /**
988 1005 * Returns an iterator over the elements in this deque in proper sequence.
989 1006 * The elements will be returned in order from first (head) to last (tail).
990 1007 * The returned {@code Iterator} is a "weakly consistent" iterator that
991 1008 * will never throw {@link java.util.ConcurrentModificationException
992 1009 * ConcurrentModificationException},
993 1010 * and guarantees to traverse elements as they existed upon
994 1011 * construction of the iterator, and may (but is not guaranteed to)
995 1012 * reflect any modifications subsequent to construction.
996 1013 *
997 1014 * @return an iterator over the elements in this deque in proper sequence
998 1015 */
999 1016 public Iterator<E> iterator() {
1000 1017 return new Itr();
1001 1018 }
1002 1019
1003 1020 /**
1004 1021 * Returns an iterator over the elements in this deque in reverse
1005 1022 * sequential order. The elements will be returned in order from
1006 1023 * last (tail) to first (head).
1007 1024 * The returned {@code Iterator} is a "weakly consistent" iterator that
1008 1025 * will never throw {@link java.util.ConcurrentModificationException
1009 1026 * ConcurrentModificationException},
1010 1027 * and guarantees to traverse elements as they existed upon
1011 1028 * construction of the iterator, and may (but is not guaranteed to)
1012 1029 * reflect any modifications subsequent to construction.
1013 1030 */
1014 1031 public Iterator<E> descendingIterator() {
1015 1032 return new DescendingItr();
1016 1033 }
1017 1034
1018 1035 /**
1019 1036 * Base class for Iterators for LinkedBlockingDeque
1020 1037 */
1021 1038 private abstract class AbstractItr implements Iterator<E> {
1022 1039 /**
1023 1040 * The next node to return in next()
1024 1041 */
1025 1042 Node<E> next;
1026 1043
1027 1044 /**
1028 1045 * nextItem holds on to item fields because once we claim that
1029 1046 * an element exists in hasNext(), we must return item read
1030 1047 * under lock (in advance()) even if it was in the process of
1031 1048 * being removed when hasNext() was called.
1032 1049 */
1033 1050 E nextItem;
1034 1051
1035 1052 /**
1036 1053 * Node returned by most recent call to next. Needed by remove.
1037 1054 * Reset to null if this element is deleted by a call to remove.
1038 1055 */
1039 1056 private Node<E> lastRet;
1040 1057
1041 1058 abstract Node<E> firstNode();
1042 1059 abstract Node<E> nextNode(Node<E> n);
1043 1060
1044 1061 AbstractItr() {
1045 1062 // set to initial position
1046 1063 final ReentrantLock lock = LinkedBlockingDeque.this.lock;
|
↓ open down ↓ |
78 lines elided |
↑ open up ↑ |
1047 1064 lock.lock();
1048 1065 try {
1049 1066 next = firstNode();
1050 1067 nextItem = (next == null) ? null : next.item;
1051 1068 } finally {
1052 1069 lock.unlock();
1053 1070 }
1054 1071 }
1055 1072
1056 1073 /**
1074 + * Returns the successor node of the given non-null, but
1075 + * possibly previously deleted, node.
1076 + */
1077 + private Node<E> succ(Node<E> n) {
1078 + // Chains of deleted nodes ending in null or self-links
1079 + // are possible if multiple interior nodes are removed.
1080 + for (;;) {
1081 + Node<E> s = nextNode(n);
1082 + if (s == null)
1083 + return null;
1084 + else if (s.item != null)
1085 + return s;
1086 + else if (s == n)
1087 + return firstNode();
1088 + else
1089 + n = s;
1090 + }
1091 + }
1092 +
1093 + /**
1057 1094 * Advances next.
1058 1095 */
1059 1096 void advance() {
1060 1097 final ReentrantLock lock = LinkedBlockingDeque.this.lock;
1061 1098 lock.lock();
1062 1099 try {
1063 1100 // assert next != null;
1064 - Node<E> s = nextNode(next);
1065 - if (s == next) {
1066 - next = firstNode();
1067 - } else {
1068 - // Skip over removed nodes.
1069 - // May be necessary if multiple interior Nodes are removed.
1070 - while (s != null && s.item == null)
1071 - s = nextNode(s);
1072 - next = s;
1073 - }
1101 + next = succ(next);
1074 1102 nextItem = (next == null) ? null : next.item;
1075 1103 } finally {
1076 1104 lock.unlock();
1077 1105 }
1078 1106 }
1079 1107
1080 1108 public boolean hasNext() {
1081 1109 return next != null;
1082 1110 }
1083 1111
1084 1112 public E next() {
1085 1113 if (next == null)
1086 1114 throw new NoSuchElementException();
1087 1115 lastRet = next;
1088 1116 E x = nextItem;
1089 1117 advance();
1090 1118 return x;
1091 1119 }
1092 1120
1093 1121 public void remove() {
1094 1122 Node<E> n = lastRet;
1095 1123 if (n == null)
1096 1124 throw new IllegalStateException();
1097 1125 lastRet = null;
1098 1126 final ReentrantLock lock = LinkedBlockingDeque.this.lock;
1099 1127 lock.lock();
1100 1128 try {
1101 1129 if (n.item != null)
1102 1130 unlink(n);
1103 1131 } finally {
1104 1132 lock.unlock();
1105 1133 }
1106 1134 }
1107 1135 }
1108 1136
1109 1137 /** Forward iterator */
1110 1138 private class Itr extends AbstractItr {
1111 1139 Node<E> firstNode() { return first; }
1112 1140 Node<E> nextNode(Node<E> n) { return n.next; }
1113 1141 }
1114 1142
1115 1143 /** Descending iterator */
1116 1144 private class DescendingItr extends AbstractItr {
1117 1145 Node<E> firstNode() { return last; }
1118 1146 Node<E> nextNode(Node<E> n) { return n.prev; }
1119 1147 }
1120 1148
1121 1149 /**
1122 1150 * Save the state of this deque to a stream (that is, serialize it).
1123 1151 *
1124 1152 * @serialData The capacity (int), followed by elements (each an
1125 1153 * {@code Object}) in the proper order, followed by a null
1126 1154 * @param s the stream
1127 1155 */
1128 1156 private void writeObject(java.io.ObjectOutputStream s)
1129 1157 throws java.io.IOException {
1130 1158 final ReentrantLock lock = this.lock;
1131 1159 lock.lock();
1132 1160 try {
1133 1161 // Write out capacity and any hidden stuff
1134 1162 s.defaultWriteObject();
1135 1163 // Write out all elements in the proper order.
1136 1164 for (Node<E> p = first; p != null; p = p.next)
1137 1165 s.writeObject(p.item);
1138 1166 // Use trailing null as sentinel
1139 1167 s.writeObject(null);
1140 1168 } finally {
1141 1169 lock.unlock();
1142 1170 }
1143 1171 }
1144 1172
1145 1173 /**
1146 1174 * Reconstitute this deque from a stream (that is,
1147 1175 * deserialize it).
1148 1176 * @param s the stream
1149 1177 */
1150 1178 private void readObject(java.io.ObjectInputStream s)
1151 1179 throws java.io.IOException, ClassNotFoundException {
1152 1180 s.defaultReadObject();
1153 1181 count = 0;
1154 1182 first = null;
1155 1183 last = null;
1156 1184 // Read in all elements and place in queue
1157 1185 for (;;) {
1158 1186 @SuppressWarnings("unchecked")
1159 1187 E item = (E)s.readObject();
1160 1188 if (item == null)
1161 1189 break;
1162 1190 add(item);
1163 1191 }
1164 1192 }
1165 1193
1166 1194 }
|
↓ open down ↓ |
83 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX