001 /*
002 @(#)ConcurrentList.java 0.4 08Jul03
003
004 Copyright (c) 2003 Arno Formella and Jose B. Gonzalez Lopez.
005 All Rights Reserved.
006
007 LGPL
008
009 */
010
011 /* a possible package location */
012 // package es.uvigo.ei.cd.java.util.concurrent;
013
014 import java.util.*;
015
016 /**
017 Implementation of a concurrent list, similar, although not identical,
018 to the <tt>List</tt> interface.
019
020 Implements all list operations, and permits all elements
021 (including <tt>null</tt>) to be stored in the list; however,
022 still not supported operations (especially bulk operations)
023 cause an <tt>UnSupportedOperationException</tt>.
024 Note that the size of a ConcurrentList has a special semantics:
025 it is defined as the number of iterations, the executing threads
026 needs to traverse the list.
027 In addition to implementing the
028 <tt>List</tt> interface, the <tt>ConcurrentList</tt> class provides
029 uniformly named methods to <tt>access</tt>, <tt>insert</tt> and
030 <tt>remove</tt> an element at the beginning and end of the list.
031 These operations allow a concurrent list to be used as a stack,
032 queue, or double-ended queue (deque).<p>
033
034 <b>Note that this implementation allows for concurrent operations
035 to take place.</b> Multiple threads
036 may access the same list concurrently, the list <i>need not to </i>
037 be synchronized externally. All available methods including iteration
038 can be performed concurrently, but please note the following special
039 semantics of concurrently manipulating a list.<p>
040
041 All of the operations perform as could be expected for a doubly-linked
042 list. Operations that index into the list will traverse the list
043 from the begining to the end. Additionally to this linear iteration,
044 the indexing thread must compete for locks during the iteration,
045 which possibly makes such operations quite slow.<p>
046
047 Semantics of manipulating a list concurrently:
048 <ul>
049 <li>
050 If a concurrent list is manipulated by only one thread at a time,
051 the list behaves exactly as expected from a normal linked list.
052 <li>
053 If a concurrent list is manipulated by more than one thread at a time,
054 there exists a sequential ordering of the operations such that
055 the list behaves exactly as expected from a normal linked list when
056 the operations are performed in that sequential order by only one thread.
057 </ul>
058
059 Invariants of the implementation:
060 <ul>
061 <li>
062 All locks on items are aquired in strict order in direction from the
063 beginning to the ending of the linked items in the list.
064 Hence, the concurrently operating threads cannot deadlock.
065 <li>
066 Each item holds the number of iterators that currently hold this item
067 as item being last returned.
068 <li>
069 After a remove operation the item to be removed is not part of the
070 list any more.
071 <li>
072 The list contains always two dummy items indicating the head and
073 tail of the list which are never visible from the outside.
074 </ul>
075
076 Notes on the implementation:
077 <ul>
078 <li>
079 The concurrent list does not implement directly the list interface,
080 because there exists no counter reporting the current length (or
081 size) of the list. The necessary update of such a counter in each
082 operation that modifies the list would serialize the concurrent
083 accesses.
084 <li>
085 The access operations come in two flavors: the one which return
086 the elements held at the items in the list, these operations will
087 throw a NoSuchElementException whenever the operation cannot be
088 performed; and the one which return the items where the elements
089 are located, these operations return <tt>null</tt> whenever the operation
090 cannot be performed.
091 <li>
092 All inserting methods are based on the private <tt>addBefore()</tt> method.
093 <li>
094 All removing methods are based on the private <tt>remove()</tt> method.
095 <li>
096 Note that you <b>must</b> use the <tt>removeCurrent()</tt> method of
097 the iterator to remove the current item while iterating.
098 It is a severe bug to call the remove method of the list instead,
099 because it will deadlock.
100 The implementation can neither detect nor prevent this deadlock.
101 Special care must be taken not to call accidentally any
102 of the remove operations while maintaining the
103 iterator over the item to be removed.
104 <li>
105 Access operations with indices or elements cause NoSuchElementException
106 if the specified operation cannot be performed.
107 Access operations with items return null of the specified operation
108 cannot be performed.
109 </ul>
110
111 Possible extensions:
112 <ul>
113 <li>
114 One might think of maintaining an identification of the list within
115 each item. This would allow to throw exceptions if someone tries
116 to remove an item not belonging to the list.
117 <li>
118 The bulk operations are still not implemented. Before implementing
119 them one might consider the design of appropriate ConcurrentCollection
120 classes and interfaces first.
121 <li>
122 One might think of adding a counting flag at each item which indicates
123 that the item is currently blocked (or reserved) by some thread.
124 Such a counting flag would help to implement <it>views</it> of
125 the list (such as intended by the SubList-method of the list interface).
126 <li>
127 One might build a class to allow any thread the initialization
128 of the list after which the list is accessed concurrently.
129 <li>
130 One might extent the iterator implementation with reverse iteration
131 operations.
132 </ul>
133
134 Revisions:
135 <ul>
136 <li>
137 (0.4) update of the introductory comments
138 <li>
139 (0.3) (1) <b>bugfix:</b>
140 in removeCurrent() could be trapped in an infinite loop.
141 (2) some volatile modifier added where necessary.
142 <li>
143 (0.2) <b>bugfix:</b>
144 removeCurrent did not set deleted to true and did not set
145 references correctly ... silly bug.
146 </ul>
147
148 @author Arno Formella and José B. González López
149 @version 0.4, 08Jul03
150 @see List
151 */
152 public class ConcurrentList implements Cloneable {
153 /*
154 TODO list:
155 - consider implementing java.io.Serializable
156 - consider implementing the bulk operations
157 - consider implementing the equals operation
158 */
159
160 /**
161 There are two dummy items which mark the head and the tail
162 of this list.
163
164 A user of this list will never have access to
165 these items. Two markers are needed to guarantee deadlock
166 free access in all operations: locks on items are always
167 aquired in strict order in direction from head to tail.
168 */
169 private volatile transient ConcurrentItem head=new ConcurrentItem();
170 /**
171 There are two dummy items which mark the head and the tail
172 of this list.
173
174 A user of this list will never have access to
175 these items. Two markers are needed to guarantee deadlock
176 free access in all operations: locks on items are always
177 aquired in strict order in direction from head to tail.
178 */
179 private volatile transient ConcurrentItem tail=new ConcurrentItem();
180
181 /**
182 Constructs an empty concurrent list.
183 */
184 public ConcurrentList() {
185 head.next=tail;
186 tail.previous=head;
187 }
188
189 /**
190 Indicates whether this list is currently empty.
191
192 @return true if list is currently empty.
193 */
194 public boolean isEmpty() {
195 /*
196 This list is empty if there is no first item.
197 */
198 return getFirstItem()==null;
199 }
200
201 /**
202 Returns the first element in this list.
203
204 @return the first element in this list.
205 @throws NoSuchElementException if this list is currently empty.
206 */
207 public Object getFirst() {
208 /*
209 The currently first element is the element of the
210 item following the head once the thread has access
211 to the head.
212 */
213 synchronized(head) {
214 /*
215 Throw exception if the list is encountered empty.
216 */
217 if(head.next==tail) throw new NoSuchElementException();
218 return head.next.element;
219 }
220 }
221
222 /**
223 Returns the last element in this list.
224
225 @return the last element in this list.
226 @throws NoSuchElementException if this list is currently empty.
227 */
228 public Object getLast() {
229 /*
230 Insist on trying to get the lock over the last item in the list (the
231 previous of the tail) until the item locked is really the last one
232 in the list and has not been marked as deleted.
233 */
234 while(true) {
235 ConcurrentItem last=tail.previous;
236 synchronized(last) {
237 if(last.next==tail && !last.deleted) {
238 /*
239 If the encountered item turns out to be the head of the list,
240 the list is empty, hence, throw exception.
241 */
242 if(last==head) throw new NoSuchElementException();
243 return last.element;
244 }
245 }
246 }
247 }
248
249 /**
250 Returns the first item in this list.
251
252 @return the first item in this list
253 or null if this list is currently empty.
254 */
255 public ConcurrentItem getFirstItem() {
256 /*
257 The currently first item is the item following the head
258 once the thread has access to the head.
259 */
260 synchronized(head) {
261 /*
262 Return null if the list is encountered empty.
263 */
264 if(head.next==tail) return null;
265 return head.next;
266 }
267 }
268
269 /**
270 Returns the last item in this list.
271
272 @return the last item in this list
273 or null if this list is currently empty.
274 */
275 public ConcurrentItem getLastItem() {
276 /*
277 Insist on trying to get the lock over the last item in the list (the
278 previous of the tail) until the item locked is really the last one
279 in the list and has not been marked as deleted.
280 */
281 while(true) {
282 ConcurrentItem last=tail.previous;
283 synchronized(last) {
284 if(last.next==tail && !last.deleted) {
285 /*
286 If the encountered item turns out to be the head of the list,
287 the list is empty, hence, return null.
288 */
289 if(last==head) return null;
290 return last;
291 }
292 }
293 }
294 }
295
296 /**
297 Removes and returns the first element from this list.
298
299 @return the first element from this list.
300 @throws NoSuchElementException if this list is currently empty.
301 @throws InterruptedException if the thread is interrupted while
302 waiting for iterators releasing the first item.
303 */
304 public Object removeFirst() throws InterruptedException {
305 Object first;
306 /*
307 Aquire the locks over the head and its successor.
308 */
309 synchronized(head) {
310 synchronized(head.next) {
311 /*
312 Save the element of the first item (next of head) and
313 remove the first item.
314 Note that <tt>remove()</tt> will possibly throw the exceptions,
315 so we need not to take care of whether the first item
316 turns out to be the head.
317 Further, <tt>remove()</tt> needs only to acquire the third lock
318 over the successor of the first item (clearly, provided
319 the list was not encountered empty).
320 */
321 first=head.next.element;
322 remove(head.next);
323 }
324 }
325 return first;
326 }
327
328 /**
329 Removes and returns the last element from this list.
330
331 @return the last element from this list.
332 @throws NoSuchElementException if this list is currently empty.
333 @throws InterruptedException if the thread is interrupted while
334 waiting for iterators releasing the last item.
335 */
336 public Object removeLast() throws InterruptedException {
337 ConcurrentItem lastItem;
338 ConcurrentItem previous;
339 /*
340 Insist on trying to get the lock over the last item in the list (the
341 previous of the tail) until the item locked is really the last one
342 in the list and has not been marked as deleted.
343 */
344 while(true) {
345 previous=tail.previous;
346 synchronized(previous) {
347 synchronized(tail) {
348 if(previous.next==tail && !previous.deleted) {
349 /*
350 If the encountered item turns out to be the head of the list,
351 the list is empty, hence, throw exception.
352 */
353 if(previous==head) throw new NoSuchElementException();
354 lastItem=previous;
355 /*
356 Note it would be a violation of the invariant
357 (order of lock acquiring)
358 if one would try to remove the item at this point.
359 */
360 break;
361 }
362 }
363 }
364 }
365 /*
366 Save the element of the item that was encountered beforehand as
367 the last item and remove the item afterwards. Note that the
368 item that was seen as last item in the previous loop is deleted,
369 however, when eventually all locks are aquired, other threads
370 might have inserted new items at the end of the list.
371 */
372 Object last=previous.element;
373 remove(lastItem);
374 return last;
375 }
376
377 /**
378 Removes an item from this list.
379
380 @param item the item to be removed.
381 Precondition: item is part of this list.
382 @throws NoSuchElementException of the this list is currently empty.
383 @throws InterruptedException if the thread is interrupted while
384 waiting for iterators releasing the last item.
385 */
386 public void removeItem(ConcurrentItem item) throws InterruptedException {
387 remove(item);
388 }
389
390 /**
391 Inserts the given element at the beginning of this list.
392
393 @param element the element to be inserted at the beginning of this list.
394 @return the item that has been inserted.
395 */
396 public ConcurrentItem addFirst(Object element) {
397 /*
398 Aquire first the lock over the head, so at the time of
399 insertion, the element is put in front.
400 */
401 synchronized(head) {
402 return addBefore(element, head.next);
403 }
404 }
405
406 /**
407 Appends the given element to the end of this list.
408
409 @param element the element to be inserted at the end of this list.
410 @return the item that has been inserted.
411 */
412 public ConcurrentItem addLast(Object element) {
413 return addBefore(element, tail);
414 }
415
416 /**
417 Appends the given element to the end of this list.
418
419 @param element the element to be inserted at the end of this list.
420 @return always true.
421 */
422 public ConcurrentItem add(Object element) {
423 return addBefore(element, tail);
424 }
425
426 /**
427 Inserts the given element to this list before of the given item.
428
429 @param element the element to be inserted.
430 @param item the item which the element is inserted before.
431 Precondition: item is part of this list.
432 @throws NoSuchElementException if the item has been deleted while waiting.
433 */
434 public ConcurrentItem addItem(Object element, ConcurrentItem item) {
435 return addBefore(element, item);
436 }
437
438 /**
439 Makes this list the empty list.
440 */
441 public void clear() throws InterruptedException {
442 /*
443 Insist on trying to remove the first item unless the list is
444 encountered empty.
445 */
446 while(true) {
447 synchronized(head) {
448 if(head.next==tail) return;
449 remove(head.next);
450 }
451 }
452 }
453
454 /**
455 Returns a ConcurrentIterator of the items or elements in this list
456 (in proper sequence), starting at the beginning of this list.
457
458 The iterator is <i>fail-save</i>: if this list is structurally
459 modified at any time after the iterator is created, the iterator
460 will continue to the end of this list. Modifications behind the
461 current position of the iterator (i.e. in direction to the beginning)
462 will not be reflected during this iteration, modifications in
463 front of the current position of the iterator (i.e. in direction of
464 the ending) will be included in the on-going iteration.<p>
465 Note that you <b>must</b> use the removeCurrent method of the
466 iterator to remove the current item while iterating. It is a severe
467 bug to call the remove method of the list instead, because it will
468 deadlock. The implementation can neither detect nor prevent this
469 deadlock.
470
471 @return an Iterator of the elements in this list (in proper
472 sequence), starting at the beginning of this list.
473 @see Iterator
474 */
475 public ConcurrentIterator listIterator() {
476 return new ListItr();
477 }
478
479 /**
480 Returns a ConcurrentIterator of the items or elements in this list
481 (in proper sequence), starting at the specified position in the list.
482
483 The iterator is <i>fail-save</i>: if this list is structurally
484 modified at any time after the iterator is created, the iterator
485 will continue to the end of this list. Modifications behind the
486 current position of the iterator (i.e. in direction to the beginning)
487 will not be reflected during this iteration, modifications in
488 front of the current position of the iterator (i.e. in direction of
489 the ending) will be included in the on-going iteration.<p>
490 Note that you <b>must</b> use the <tt>removeCurrent()</tt> method of the
491 iterator to remove the current item while iterating. It is a severe
492 bug to call the <tt>remove()</tt> method of the list instead, because it will
493 deadlock. The implementation can neither detect nor prevent this
494 deadlock.
495
496 @param index index of first element to be returned from the
497 iterator (by a call to <tt>next()</tt>).
498 @return a ConcurrentIterator of the items or elements in this list
499 (in proper sequence), starting at the specified position
500 in the list.
501 @throws IndexOutOfBoundsException if index is out of range.
502 */
503 public ConcurrentIterator listIterator(int index) {
504 return new ListItr(index);
505 }
506
507 /**
508 Private implementation of the ConcurrentIterator.
509 */
510 private class ListItr implements ConcurrentIterator {
511
512 /*
513 lastReturned holds the item that was last returned to the calling
514 thread. Hence, while constructing the iterator it is set to the
515 head indicating that still no item has been returned.
516 */
517 private ConcurrentItem lastReturned=head;
518
519 /**
520 Constructs an iterator of the items or elements in the list
521 (in proper sequence), starting at the beginning of the list.
522 */
523 ListItr() {
524 /*
525 Exclusive access is required to lastReturned (which is
526 actually the head), because the counter which counts the number
527 of iterators currently holding this item as lastReturned must
528 be incremented, so we can use a generic method to advance the
529 iterator, which always decrements the counter of the current item
530 and increments the counter of the next item.
531 */
532 synchronized(lastReturned) {
533 lastReturned.iteratorCounter++;
534 }
535 }
536
537 /**
538 Constructs an iterator of the items or elements in the list
539 (in proper sequence), starting at the given position.
540
541 @throws IndexOutOfBoundsException if index is out of range.
542 */
543 ListItr(int index) {
544 /*
545 Exclusive access is required to lastReturned (which is
546 actually the head), because the counter which counts the number
547 of iterators currently holding this item as lastReturned must
548 be incremented, so we can use a generic method to advance the
549 iterator, which always decrements the counter of the current item
550 and increments the counter of the next item.
551 */
552 /*
553 A negative index certainly is out of range.
554 */
555 if(index<0) throw new IndexOutOfBoundsException();
556 synchronized(lastReturned) {
557 lastReturned.iteratorCounter++;
558 }
559 /*
560 Iterate to the specified index.
561 */
562 while(nextItem()!=null) {
563 if(index==0) return;
564 index--;
565 }
566 /*
567 The list was not sufficiently long.
568 */
569 throw new IndexOutOfBoundsException();
570 }
571
572 /**
573 Indicates whether there is another element after the current
574 position of the iterator.
575
576 Note that the information returned by this method is not reliable
577 if other threads are concurrently manipulating this list.
578 Hence, subsequent calls to <tt>next()</tt> still might cause an
579 exception.
580
581 @return true if an element is available, false otherwise.
582 */
583 public boolean hasNext() {
584 synchronized(lastReturned) {
585 return lastReturned.next==tail;
586 }
587 }
588
589 /**
590 Returns the next element in the list.
591
592 @return the next element in the list.
593 @throws NoSuchElementException if there are no more elements.
594 */
595 public Object next() {
596 Object element;
597 synchronized(lastReturned) {
598 /*
599 If the end of the list has already been reached earlier,
600 throw an exception.
601 */
602 if(lastReturned==tail) throw new NoSuchElementException();
603 synchronized(lastReturned.next) {
604 /*
605 The current and the next item are locked now. Decrement counter
606 of iterators in the current item and notify all threads possibly
607 waiting for the current element, if it is worthwhile.
608 */
609 lastReturned.iteratorCounter--;
610 if(lastReturned.iteratorCounter==0) lastReturned.notifyAll();
611 /*
612 If the end of the list is reached now, throw an exception.
613 */
614 lastReturned=lastReturned.next;
615 if(lastReturned==tail) throw new NoSuchElementException();
616 /*
617 Get the element to be returned and increment the counter of
618 iterators in the new current item.
619 */
620 element=lastReturned.element;
621 lastReturned.iteratorCounter++;
622 }
623 }
624 return element;
625 }
626
627 /**
628 Returns the next item in the list.
629
630 @return the next item in the list, or null if there are no more
631 items.
632 */
633 public ConcurrentItem nextItem() {
634 ConcurrentItem item=null;
635 synchronized(lastReturned) {
636 /*
637 If the end of the list has already been reached earlier, return null.
638 */
639 if(lastReturned==tail) return null;
640 synchronized(lastReturned.next) {
641 /*
642 The current and the next item are locked now. Decrement counter
643 of iterators in the current item and notify all threads possibly
644 waiting for the current element, if it is worthwhile.
645 */
646 lastReturned.iteratorCounter--;
647 if(lastReturned.iteratorCounter==0) lastReturned.notifyAll();
648 lastReturned=lastReturned.next;
649 if(lastReturned!=tail) {
650 /*
651 The end of the list has still not been reached.
652 Get the item to be returned and increment the counter of
653 iterators in the new current item.
654 */
655 item=lastReturned;
656 lastReturned.iteratorCounter++;
657 }
658 }
659 }
660 return item;
661 }
662
663 /**
664 Returns the next item and element in the list.
665
666 Allows for an atomic access to an item of the list. If one uses
667 the separate forms of first accessing the item then accessing
668 the element, another thread might have changed the element of the
669 item in the mean while.
670 The method is only visible in the package, but there is a wrapper
671 method which uses an item to transfer the element to the caller.
672 The design with an array is easy to extent if more than
673 one element should be returned.
674
675 @param elementArray the array will contain the element found,
676 the array will be unchanged if there are no more elements.
677 @return the next item in the list, or null if there are no more
678 elements.
679 */
680 ConcurrentItem nextItem(Object[] elementArray) {
681 ConcurrentItem item=null;
682 synchronized(lastReturned) {
683 /*
684 If the end of the list has already been reached earlier, return null.
685 */
686 if(lastReturned==tail) return null;
687 synchronized(lastReturned.next) {
688 /*
689 The current and the next item are locked now. Decrement counter
690 of iterators in the current item and notify all threads possibly
691 waiting for the current element, if it is worthwhile.
692 */
693 lastReturned.iteratorCounter--;
694 if(lastReturned.iteratorCounter==0) lastReturned.notifyAll();
695 lastReturned=lastReturned.next;
696 if(lastReturned!=tail) {
697 /*
698 The end of the list has still not been reached.
699 Get the element to be returned and increment the counter of
700 iterators in the new current item.
701 */
702 item=lastReturned;
703 elementArray[0]=item.element;
704 lastReturned.iteratorCounter++;
705 }
706 }
707 }
708 return item;
709 }
710
711 /**
712 Returns the next item and element in the list.
713
714 Allows for an atomic access to an item of the list. If one uses
715 the separate forms of first accessing the item then accessing
716 the element, another thread might have changed the element of the
717 item in the mean while.
718
719 @param item the item where to place the corresponding element, item will
720 be unchanged if there are no more elements.
721 @return the next item in the list, or null if there are no more
722 elements.
723 */
724 public ConcurrentItem nextItem(ConcurrentItem item) {
725 Object[] elementArray = new Object[1];
726 ConcurrentItem next_item = nextItem(elementArray);
727 /*
728 change the item only if a valid item has been found
729 */
730 if(next_item!=null) item.element = elementArray[0];
731 return next_item;
732 }
733
734 /**
735 The remove method declared by the iterator interface cannot be
736 overwritten directly, because a concurrent iterator might throw
737 an InterruptedException.
738
739 Use removeCurrent instead.
740
741 @see #removeCurrent
742 */
743 public void remove() {
744 throw new UnsupportedOperationException();
745 }
746
747 /**
748 Removes the item currently held by the iterator.
749
750 The iterator is placed to the previous item. The method can be
751 called several times without calling a <tt>next()</tt> method
752 as long as the iterator does not recover its initial state,
753 that is, being placed as after construction.
754
755 @throws NoSuchElementException if there is no current item,
756 i.e., if still none of the <tt>next()</tt> methods has
757 been executed or if the iteration already has completed.
758 @throws InterruptedException if the thread is interrupted while
759 waiting for iterators releasing the current item.
760 */
761 public void removeCurrent() throws InterruptedException {
762 /*
763 Throw exception if there is nothing that can be removed.
764 */
765 if(lastReturned==tail || lastReturned==head)
766 throw new NoSuchElementException();
767 /*
768 Because we might need to wait for other iterators to release the
769 item to be removed, the flag is used to indicate that it is the first
770 time both locks (over the current and the previous item) have been
771 achieved, hence, the iteratorCounter still has to be decremented.
772 */
773 boolean firstTime=true;
774 /*
775 Once we have get hold on a valid predecessor of lastReturned, we
776 store it in toReturn, so we can return it once the removal took place.
777 */
778 ConcurrentItem toReturn=null;
779 /*
780 Insist on trying to get hold on the current item and its predecessor.
781 Because we must aquire the locks in strict order, the structure of
782 the loop is more complex.
783 */
784 while(true) {
785 ConcurrentItem previous=lastReturned.previous;
786 synchronized(previous) {
787 /*
788 If we still did not update the iteratorCounter,
789 check whether the previous one has not been deleted (we
790 need an item where to place lastReturned) and check as well
791 if we really got hold over the previous item of lastReturned.
792 If neither is the case, keep on trying.
793 */
794 if(firstTime && (previous.deleted || previous!=lastReturned.previous))
795 continue;
796 /*
797 We got hold on the previous undeleted item. Increment its
798 iteratorCounter indicating that it is in use and store it
799 so we can return it, once we have achieved the removal.
800 */
801 if(firstTime) {
802 previous.iteratorCounter++;
803 toReturn=previous;
804 }
805 /*
806 Get hold on the current item.
807 */
808 synchronized(lastReturned) {
809 /*
810 It may happen that the item already has been removed by some
811 other thread because we might be in a later iteration of the
812 loop (and hence, the iteratorCounter was decremented already).
813 If the item is already deleted, everything is fine so break;
814 */
815 if(lastReturned.deleted) {
816 lastReturned=toReturn;
817 break;
818 }
819 /*
820 Decrement iteratorCounter at most once, so check firstTime first.
821 */
822 if(firstTime) lastReturned.iteratorCounter--;
823 /*
824 Wait until all other iterators have released this item.
825 */
826 if(lastReturned.iteratorCounter!=0) {
827 try {
828 /*
829 we must wait on the lastReturned item
830 */
831 lastReturned.wait();
832 }
833 catch(InterruptedException e) {
834 throw e;
835 }
836 /*
837 Every next iteration will not be the first one any more.
838 */
839 firstTime=false;
840 continue;
841 }
842 /*
843 Aquire the third lock, the lock over the next item of the one
844 to be removed.
845 */
846 synchronized(lastReturned.next) {
847 /*
848 Perform the actual remove operation.
849 */
850 lastReturned.deleted=true;
851 lastReturned.previous.next=lastReturned.next;
852 lastReturned.next.previous=lastReturned.previous;
853 }
854 /*
855 Notify all threads possibly waiting for the item just removed.
856 */
857 lastReturned.notifyAll();
858 /*
859 Adjust lastReturned to the predecessor and break.
860 */
861 lastReturned=toReturn;
862 break;
863 }
864 }
865 }
866 }
867
868 /**
869 Finishes an iteration.
870
871 Because an iteration over a ConcurrentList needs to maintain some
872 state information, one should call this method whenever an iterator
873 is not used any more.
874 Once <tt>finish()</tt> has been called, the state of the iteration is
875 the same as if one had iterated to the end of the list.
876 If this advice is not followed, other threads might get blocked
877 until the garbage collector finalizes the iterator.
878 */
879 public void finish() {
880 synchronized(lastReturned) {
881 if(lastReturned!=tail) {
882 /*
883 Decrement the iteration counter, if worthwhile, notify all
884 threads waiting on the item, and finally, advance directly
885 to the tail.
886 */
887 lastReturned.iteratorCounter--;
888 if(lastReturned.iteratorCounter==0) lastReturned.notifyAll();
889 lastReturned=tail;
890 }
891 }
892 }
893
894 /**
895 Adjusts the iterator counter and notifies waiting threads if
896 an iterator goes out of scope and <tt>finish()</tt> has not been
897 called appropriately.
898
899 @throws Throwable whatever might be risen by the garbage collector.
900 */
901 protected void finalize() throws Throwable {
902 try {
903 synchronized(lastReturned) {
904 /*
905 An iteration has finished if the lastReturned item is set at
906 the tail.
907 */
908 if(lastReturned!=tail) {
909 /*
910 Decrement the iteration counter, if worthwhile, notify all
911 threads waiting on the item.
912 */
913 lastReturned.iteratorCounter--;
914 if(lastReturned.iteratorCounter==0) lastReturned.notifyAll();
915 }
916 }
917 }
918 finally {
919 super.finalize();
920 }
921 }
922 }
923
924 /**
925 Basic method to insert an item into this list.
926
927 @param element the element to be inserted
928 @param item the item in front of which the element is to be inserted.
929 Precondition: item is part of the list.
930 @return the item that has been inserted.
931 @throws NoSuchElementException if the item in front of which the element
932 has to be inserted has been removed from this list while the thread
933 is waiting for the necessary locks.
934 */
935 private ConcurrentItem addBefore(Object element, ConcurrentItem item) {
936 /*
937 Insist on trying to lock the two consecutive items in the list.
938 */
939 while(true) {
940 ConcurrentItem previous=item.previous;
941 synchronized(previous) {
942 synchronized(item) {
943 /*
944 If the item in front of which we want to insert has been deleted
945 in the mean while, throw exception.
946 */
947 if(item.deleted) throw new NoSuchElementException();
948 /*
949 Check whether the two items are consecutive, if not: insist,
950 else insert a new item containing the element.
951 */
952 if(item.previous==previous) {
953 ConcurrentItem newItem=new ConcurrentItem(element, item, previous);
954 newItem.previous.next=newItem;
955 newItem.next.previous=newItem;
956 return newItem;
957 }
958 }
959 }
960 }
961 }
962
963 /**
964 Basic method to remove an item from this list.
965
966 @param item the item to be removed.
967 Precondition: item is part of this list.
968 @throws InterruptedException if the thread is interrupted while
969 waiting for iterators releasing the item.
970 @throws NoSuchElementException if this list is empty.
971 */
972 private void remove(ConcurrentItem item) throws InterruptedException {
973 /*
974 Throw exception if the item cannot be removed.
975 */
976 if(item==head || item==tail) throw new NoSuchElementException();
977 /*
978 Insist on trying to lock the three consecutive items in the list.
979 */
980 while(true) {
981 ConcurrentItem previous=item.previous;
982 synchronized(previous) {
983 synchronized(item) {
984 /*
985 If the item was deleted by another thread, nothing must be done
986 any more.
987 */
988 if(item.deleted) break;
989 /*
990 If we did not lock the predecessor we need to continue (some other
991 thread might have inserted an item in the mean while).
992 */
993 if(item.previous!=previous) continue;
994 /*
995 Wait for the iterators to release the item to be removed.
996 */
997 if(item.iteratorCounter > 0) {
998 try {
999 /*
1000 We must wait on the item.
1001 */
1002 item.wait();
1003 }
1004 catch(InterruptedException ex) {
1005 throw ex;
1006 }
1007 /*
1008 Try to get the locks again.
1009 */
1010 continue;
1011 }
1012 /*
1013 Get the third lock, remove the item, and done.
1014 */
1015 synchronized(item.next) {
1016 item.deleted=true;
1017 item.previous.next=item.next;
1018 item.next.previous=item.previous;
1019 break;
1020 }
1021 }
1022 }
1023 }
1024 }
1025
1026 /**
1027 Clones this list as currently seen by an iterator constructed for the
1028 thread.
1029
1030 Note that due to the concurrent nature of a ConcurrentList the
1031 resulting clone might be a list that never existed exactly like this
1032 during the execution of the program.
1033 However, if the list is not modified during cloning, the clone
1034 is an exact copy.
1035
1036 @return A new ConcurrentList containing all elements as seen
1037 by the executing thread during the copy iteration.
1038 */
1039 protected Object clone() throws CloneNotSupportedException {
1040 /*
1041 Construct a new iterator and collect all items in the list as seen
1042 by this iterator.
1043 */
1044 ConcurrentList newList=new ConcurrentList();
1045 ListItr iterator=new ListItr();
1046 /*
1047 iterate over the list and add the element to a new list
1048 */
1049 Object[] elementArray=new Object[1];
1050 while(iterator.nextItem(elementArray)!=null)
1051 newList.addLast(elementArray[0]);
1052 return newList;
1053 }
1054
1055 /**
1056 Returns the element at the specified position in this list.
1057
1058 Note that the method iterates from the beginning of this list,
1059 hence the operation might be quite slow.
1060
1061 @param index the index of the element to be returned.
1062 @return the object at the position specified by index.
1063 @throws IndexOutOfBoundsException if the specified index is out of range.
1064 */
1065 public Object get(int index) {
1066 /*
1067 A negative index certainly is out of range.
1068 */
1069 if(index<0) throw new IndexOutOfBoundsException();
1070 ListItr iterator=new ListItr();
1071 int counter=0;
1072 /*
1073 Step over the list unless the appropriate index has been reached or
1074 no more elements are available.
1075 */
1076 Object[] elementArray=new Object[1];
1077 while(iterator.nextItem(elementArray)!=null) {
1078 if(counter==index) {
1079 /*
1080 Finish the iteration because the iterator will go out of scope.
1081 */
1082 iterator.finish();
1083 return elementArray[0];
1084 }
1085 counter++;
1086 }
1087 /*
1088 The list was encountered shorter than necessary.
1089 */
1090 throw new IndexOutOfBoundsException();
1091 }
1092
1093 /**
1094 Returns the item at the specified position in this list.
1095
1096 Note that the method iterates from the beginning of this list,
1097 hence the operation might be quite slow.
1098
1099 @param index the index of the item to be returned.
1100 @return the item at the position specified by index or null
1101 if no such item exists.
1102 */
1103 public ConcurrentItem getItem(int index) {
1104 /*
1105 A negative index certainly is out of range.
1106 */
1107 if(index<0) return null;
1108 ListItr iterator=new ListItr();
1109 ConcurrentItem item;
1110 int counter=0;
1111 /*
1112 Step over the list unless the appropriate index has been reached or
1113 no more items are available.
1114 */
1115 while((item=iterator.nextItem())!=null) {
1116 if(counter==index) {
1117 /*
1118 Finish the iteration because the iterator will go out of scope.
1119 */
1120 iterator.finish();
1121 return item;
1122 }
1123 counter++;
1124 }
1125 /*
1126 The list was encountered shorter than necessary.
1127 */
1128 return null;
1129 }
1130
1131 /**
1132 Returns the item at the specified position in this list and
1133 fills atomicly the array with the element encountered.
1134
1135 The method is only visible in the package, but there is a wrapper
1136 method which uses an item to transfer the element to the caller.
1137 The design with an array is easy to extent if more than
1138 one element should be returned.
1139
1140 Note that the method iterates from the beginning of this list,
1141 hence the operation might be quite slow.
1142
1143 @param index the index of the item to be returned.
1144 @param elementArray, the array to hold the element found,
1145 the array will be unchanged if no appropriate item found
1146 @return the item at the position specified by index or null
1147 if no such item exists.
1148 */
1149 ConcurrentItem getItem(int index, Object[] elementArray) {
1150 /*
1151 A negative index certainly is out of range.
1152 */
1153 if(index<0) return null;
1154 ListItr iterator=new ListItr();
1155 ConcurrentItem item;
1156 int counter=0;
1157 Object[] element_array=new Object[1];
1158 /*
1159 Step over the list unless the appropriate index has been reached or
1160 no more items are available.
1161 */
1162 while((item=iterator.nextItem(element_array))!=null) {
1163 if(counter==index) {
1164 /*
1165 Finish the iteration because the iterator will go out of scope.
1166 */
1167 iterator.finish();
1168 elementArray[0]=element_array[0];
1169 return item;
1170 }
1171 counter++;
1172 }
1173 /*
1174 The list was encountered shorter than necessary.
1175 */
1176 return null;
1177 }
1178
1179 /**
1180 Returns the item at the specified position in this list and
1181 fills atomicly the parameter item with the element encountered.
1182
1183 Allows for an atomic access to an item of the list. If one uses
1184 the separate forms of first accessing the item then accessing
1185 the element, another thread might have changed the element of the
1186 item in the mean while.
1187
1188 Note that the method iterates from the beginning of this list,
1189 hence the operation might be quite slow.
1190
1191 @param index the index of the item to be returned.
1192 @param item, the item to hold the element found,
1193 the item will be unchanged if no appropriate item found
1194 @return the item at the position specified by index or null
1195 if no such item exists.
1196 */
1197 public ConcurrentItem getItem(int index, ConcurrentItem item) {
1198 Object[] element_array = new Object[1];
1199 ConcurrentItem get_item = getItem(index, element_array);
1200 /*
1201 change the item only if a valid item has been found
1202 */
1203 if(get_item!=null) item.element = element_array[0];
1204 return get_item;
1205 }
1206
1207 /**
1208 Sets the element at the specified position.
1209
1210 Note that the method iterates from the beginning of this list,
1211 hence the operation might be quite slow.
1212
1213 @param index the index of the item to be returned.
1214 @param element the element used to replace
1215 @return the element found at the position specified by index.
1216 @throws IndexOutOfBoundsException if the specified index is out of range.
1217 */
1218 public Object set(int index, Object element) {
1219 /*
1220 A negative index certainly is out of range.
1221 */
1222 if(index<0) throw new IndexOutOfBoundsException();
1223 ListItr iterator=new ListItr();
1224 ConcurrentItem item;
1225 int counter=0;
1226 /*
1227 Iterate over the list and replace the element if the corresponding
1228 index is found.
1229 */
1230 while((item=iterator.nextItem())!=null) {
1231 if(counter==index) {
1232 /*
1233 Finish the iteration because the iterator will go out of scope.
1234 */
1235 iterator.finish();
1236 return item.setElement(element);
1237 }
1238 counter++;
1239 }
1240 /*
1241 The list was encountered shorter than necessary.
1242 */
1243 throw new IndexOutOfBoundsException();
1244 }
1245
1246 /**
1247 Returns <tt>true</tt> if this list contains the specified element.
1248
1249 Note that the method iterates from the beginning of this list,
1250 hence the operation might be quite slow.
1251
1252 More formally, returns <tt>true</tt> if and only if this list contains
1253 at least one element <tt>e</tt> such that <tt>(element==null ? e==null
1254 : element.equals(e))</tt>.
1255
1256 @param element element whose presence in this list is to be tested.
1257 @return <tt>true</tt> if this list contains the specified element.
1258 */
1259 public boolean contains(Object element) {
1260 return indexOf(element)!=-1;
1261 }
1262
1263 /**
1264 Returns the index in this list of the first occurrence of the
1265 specified element, or -1 if this list does not contain the
1266 element.
1267
1268 More formally, returns the lowest index i such that
1269 <tt>(element==null ? get(i)==null : element.equals(get(i)))</tt>,
1270 or -1 if there is no such index.
1271
1272 @param element element to search for.
1273 @return the index in this list of the first occurrence of the
1274 specified element, or -1 if the list does not contain the
1275 element.
1276 */
1277 public int indexOf(Object element) {
1278 ListItr iterator=new ListItr();
1279 int index=0;
1280 Object[] elementArray=new Object[1];
1281 /*
1282 Distinguish the cases whether to compare the reference or whether
1283 to compare using the equals method of the object.
1284 */
1285 if(element==null) {
1286 /*
1287 Step over the list unless the appropriate element has been found or
1288 no more elements are available.
1289 */
1290 while(iterator.nextItem(elementArray)!=null) {
1291 if(elementArray[0]==null) {
1292 /*
1293 Finish the iteration because the iterator will go out of scope.
1294 */
1295 iterator.finish();
1296 return index;
1297 }
1298 index++;
1299 }
1300 }
1301 else {
1302 /*
1303 Step over the list unless the appropriate element has been found or
1304 no more elements are available.
1305 */
1306 while(iterator.nextItem(elementArray)!=null) {
1307 if(element.equals(elementArray[0])) {
1308 /*
1309 Finish the iteration because the iterator will go out of scope.
1310 */
1311 iterator.finish();
1312 return index;
1313 }
1314 index++;
1315 }
1316 }
1317 /*
1318 The element was not found.
1319 */
1320 return -1;
1321 }
1322
1323 /**
1324 Inserts the specified element at the specified position in this list.
1325
1326 Hence, shifts the element currently at that position (if any) and any
1327 subsequent elements to the right.
1328
1329 @param index index at which the specified element is to be inserted.
1330 @param element element to be inserted.
1331 @throws IndexOutOfBoundsException if the specified index is out of range.
1332 */
1333 public void add(int index, Object element) {
1334 /*
1335 A negative index certainly is out of range.
1336 */
1337 if(index<0) throw new IndexOutOfBoundsException();
1338 ListItr iterator=new ListItr();
1339 ConcurrentItem item;
1340 /*
1341 Step over the list unless no more elements are available.
1342 */
1343 while((item=iterator.nextItem())!=null) {
1344 if(index==0) {
1345 /*
1346 Insert the item before the one corresponding to the index.
1347 */
1348 addBefore(element,item);
1349 /*
1350 Finish the iteration because the iterator will go out of scope.
1351 */
1352 iterator.finish();
1353 return;
1354 }
1355 index--;
1356 }
1357 /*
1358 The list was encountered shorter than necessary.
1359 */
1360 throw new IndexOutOfBoundsException();
1361 }
1362
1363 /**
1364 Removes the element at the specified position in this list.
1365
1366 hence, shifts any subsequent elements to the left.
1367 Returns the element that was removed from the list.
1368
1369 @param index the index of the element to removed.
1370 @return the element previously at the specified position.
1371 @throws IndexOutOfBoundsException if the specified index is out of range.
1372 @throws InterruptedException if the thread is interrupted while
1373 waiting for iterators releasing the item
1374 */
1375 public Object remove(int index) throws InterruptedException {
1376 /*
1377 A negative index certainly is out of range.
1378 */
1379 if(index<0) throw new IndexOutOfBoundsException();
1380 ListItr iterator=new ListItr();
1381 Object[] elementArray=new Object[1];
1382 /*
1383 Step over the list unless no more elements are available.
1384 */
1385 while(iterator.nextItem(elementArray)!=null) {
1386 if(index==0) {
1387 /*
1388 Remove the item with the corresponding index.
1389 */
1390 iterator.removeCurrent();
1391 /*
1392 Finish the iteration because the iterator will go out of scope.
1393 */
1394 iterator.finish();
1395 return elementArray[0];
1396 }
1397 index--;
1398 }
1399 /*
1400 The list was encountered shorter than necessary.
1401 */
1402 throw new IndexOutOfBoundsException();
1403 }
1404
1405 /**
1406 Removes the first occurrence of the specified element in this list.
1407
1408 If the list does not contain the element, it is unchanged.
1409 More formally, removes the element with the lowest index <tt>i</tt>
1410 such that <tt>(element==null ? get(i)==null : element.equals(get(i)))</tt>
1411 (if such an element exists).
1412
1413 @param element element to be removed from this list, if present.
1414 @return <tt>true</tt> if the list contained the specified element.
1415 @throws InterruptedException if the thread is interrupted while
1416 waiting for iterators releasing the item holding the element.
1417 */
1418 public boolean remove(Object element) throws InterruptedException {
1419 ListItr iterator=new ListItr();
1420 Object[] elementArray=new Object[1];
1421 /*
1422 Distinguish the cases whether to compare the reference or whether
1423 to compare using the equals method of the object.
1424 */
1425 if(element==null) {
1426 /*
1427 Step over the list unless no more elements are available.
1428 */
1429 while(iterator.nextItem(elementArray)!=null) {
1430 if(elementArray[0]==null) {
1431 /*
1432 Remove the item with the containg the element.
1433 */
1434 iterator.removeCurrent();
1435 /*
1436 Finish the iteration because the iterator will go out of scope.
1437 */
1438 iterator.finish();
1439 return true;
1440 }
1441 }
1442 }
1443 else {
1444 /*
1445 Step over the list unless no more elements are available.
1446 */
1447 while(iterator.nextItem(elementArray)!=null) {
1448 if(element.equals(elementArray[0])) {
1449 /*
1450 Remove the item with the containg the element.
1451 */
1452 iterator.removeCurrent();
1453 /*
1454 Finish the iteration because the iterator will go out of scope.
1455 */
1456 iterator.finish();
1457 return true;
1458 }
1459 }
1460 }
1461 /*
1462 The element was not found.
1463 */
1464 return false;
1465 }
1466
1467 // Bulk Operations
1468
1469 /**
1470 Appends all of the elements in the specified collection to the end of
1471 this list, in the order that they are returned by the specified
1472 collection's iterator (optional operation).
1473
1474 The behavior of this operation is unspecified if the specified
1475 collection is modified while the operation is in progress.
1476 (Note that this will occur if the specified collection is this list,
1477 and it's nonempty.)
1478
1479 @param c collection whose elements are to be added to this list.
1480 @return <tt>true</tt> if this list changed as a result of the call.
1481 @throws UnsupportedOperationException if the <tt>addAll()</tt> method is
1482 not supported by this list.
1483 @throws ClassCastException if the class of an element in the specified
1484 collection prevents it from being added to this list.
1485 @throws IllegalArgumentException if some aspect of an element in the
1486 specified collection prevents it from being added to this
1487 list.
1488 @see #add(Object)
1489 */
1490 public boolean addAll(Collection c) {
1491 throw new UnsupportedOperationException();
1492 }
1493
1494 /**
1495 Inserts all of the elements in the specified collection into this
1496 list at the specified position (optional operation).
1497
1498 Shifts the
1499 element currently at that position (if any) and any subsequent
1500 elements to the right (increases their indices). The new elements
1501 will appear in this list in the order that they are returned by the
1502 specified collection's iterator. The behavior of this operation is
1503 unspecified if the specified collection is modified while the
1504 operation is in progress. (Note that this will occur if the specified
1505 collection is this list, and it's nonempty.)
1506
1507 @param index index at which to insert first element from the specified
1508 collection.
1509 @param c elements to be inserted into this list.
1510 @return <tt>true</tt> if this list changed as a result of the call.
1511 @throws UnsupportedOperationException if the <tt>addAll()</tt> method is
1512 not supported by this list.
1513 @throws ClassCastException if the class of one of elements of the
1514 specified collection prevents it from being added to this
1515 list.
1516 @throws IllegalArgumentException if some aspect of one of elements of
1517 the specified collection prevents it from being added to
1518 this list.
1519 @throws IndexOutOfBoundsException if the index is out of range.
1520 */
1521 public boolean addAll(int index, Collection c) {
1522 throw new UnsupportedOperationException();
1523 }
1524
1525 /**
1526 Returns <tt>true</tt> if this list contains all of the elements of the
1527 specified collection.
1528
1529 @param c collection to be checked for containment in this list.
1530 @return <tt>true</tt> if this list contains all of the elements of the
1531 specified collection.
1532
1533 @see #contains(Object)
1534 */
1535 public boolean containsAll(Collection c) {
1536 throw new UnsupportedOperationException();
1537 }
1538
1539 /**
1540 Removes from this list all the elements that are contained in the
1541 specified collection (optional operation).
1542
1543 @param c collection that defines which elements will be removed from
1544 this list.
1545 @return <tt>true</tt> if this list changed as a result of the call.
1546 @throws UnsupportedOperationException if the <tt>removeAll()</tt> method
1547 is not supported by this list.
1548
1549 @see #remove(Object)
1550 @see #contains(Object)
1551 */
1552 public boolean removeAll(Collection c) {
1553 throw new UnsupportedOperationException();
1554 }
1555
1556 /**
1557 Retains only the elements in this list that are contained in the
1558 specified collection (optional operation).
1559
1560 In other words, removes
1561 from this list all the elements that are not contained in the specified
1562 collection.
1563
1564 @param c collection that defines which elements this set will retain.
1565 @return <tt>true</tt> if this list changed as a result of the call.
1566 @throws UnsupportedOperationException if the <tt>retainAll()</tt> method
1567 is not supported by this list.
1568
1569 @see #remove(Object)
1570 @see #contains(Object)
1571 */
1572 public boolean retainAll(Collection c) {
1573 throw new UnsupportedOperationException();
1574 }
1575
1576 /**
1577 Compares the specified object with this list for equality.
1578
1579 Returns
1580 <tt>true</tt> if and only if the specified object is also a list
1581 and all corresponding pairs of elements in
1582 the two lists are <i>equal</i>. (Two elements <tt>e1</tt> and
1583 <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null :
1584 e1.equals(e2))</tt>.) In other words, two lists are defined to be
1585 equal if they contain the same elements in the same order. This
1586 definition ensures that the equals method works properly across
1587 different implementations of the <tt>List</tt> interface.
1588
1589 @param obj the object to be compared for equality with this list.
1590 @return <tt>true</tt> if the specified object is equal to this list.
1591 @throws UnsupportedOperationException if the <tt>retainAll()</tt> method
1592 is not supported by this list.
1593 */
1594 public boolean equals(Object obj) {
1595 throw new UnsupportedOperationException();
1596 }
1597
1598 /**
1599 Returns the hash code value for this list.
1600
1601 The hash code of a list
1602 is defined to be the result of the following calculation:
1603 <pre>
1604 hashCode = 1;
1605 Iterator i = list.iterator();
1606 while (i.hasNext()) {
1607 Object obj = i.next();
1608 hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
1609 }
1610 </pre>
1611 This ensures that <tt>list1.equals(list2)</tt> implies that
1612 <tt>list1.hashCode()==list2.hashCode()</tt> for any two lists,
1613 <tt>list1</tt> and <tt>list2</tt>, as required by the general
1614 contract of <tt>Object.hashCode</tt>.
1615
1616 @return the hash code value for this list.
1617 @throws UnsupportedOperationException if the <tt>retainAll()</tt> method
1618 is not supported by this list.
1619
1620 @see Object#hashCode()
1621 @see Object#equals(Object)
1622 @see #equals(Object)
1623 */
1624 public int hashCode() {
1625 throw new UnsupportedOperationException();
1626 }
1627
1628 /**
1629 Returns the index in this list of the last occurrence of the specified
1630 element, or -1 if this list does not contain this element.
1631
1632 More formally, returns the highest index <tt>i</tt> such that
1633 <tt>(element==null ? get(i)==null : element.equals(get(i)))</tt>,
1634 or -1 if there is no such index.
1635
1636 @param element element to search for.
1637 @throws UnsupportedOperationException if the <tt>retainAll()</tt> method
1638 is not supported by this list.
1639 @return the index in this list of the last occurrence of the specified
1640 element, or -1 if this list does not contain this element.
1641 */
1642 public int lastIndexOf(Object element) {
1643 throw new UnsupportedOperationException();
1644 }
1645
1646 /**
1647 The size of a ConcurrentList is defined as the number of
1648 iterations currently needed by this thread to traverse this list.
1649
1650 Note that the information returned by this method is not reliable
1651 if other threads are concurrently manipulating this list.
1652 Hence, subsequent accesses to the list might see a different
1653 number of elements.
1654
1655 Note that the operation might be quite slow, because the
1656 number of elements must be counted on the fly.
1657
1658 @return the size of this list as currently seen by the thread.
1659 */
1660 public int size() {
1661 ListItr iterator=new ListItr();
1662 int index=0;
1663 while(iterator.nextItem()!=null) index++;
1664 return index;
1665 }
1666
1667 /**
1668 Returns an array containing all elements of this list as seen
1669 currently by an iteration of the thread over this list.
1670
1671 Note that due to the concurrent nature of a ConcurrentList the
1672 resulting array might be view of a list that never existed exactly
1673 like this during the execution of the program.
1674 However, if the list is not modified during the exection of this
1675 method, the array is an exact copy.
1676
1677 @return an array containing all elements of this list.
1678 */
1679 public Object[] toArray() {
1680 /*
1681 In order to establish the necessary size of the array and
1682 to avoid that another thread manipulates the list while this
1683 thread tries to copy the elements, clone the list as seen by
1684 this thread.
1685 */
1686 ConcurrentList newList=null;
1687 try {
1688 newList=(ConcurrentList)this.clone();
1689 }
1690 catch(CloneNotSupportedException e) {
1691 // we know it's implemented
1692 }
1693 Object[] a=new Object[newList.size()];
1694 /*
1695 Return an array of the local copy of this list.
1696 */
1697 return newList.toArray(a);
1698 }
1699
1700 /**
1701 Returns an array containing all elements of this list as seen
1702 currently by an iteration of the thread over this list.
1703
1704 Note that due to the concurrent nature of a ConcurrentList the
1705 resulting array might be a view of the list that never existed exactly
1706 like this during the execution of the program.
1707 However, if the list is not modified during the exection of this
1708 method, the array is an exact copy.
1709
1710 @param a the array to hold the elements of this list.
1711 @return an array containing all elements of this list.
1712 @throws IndexOutOfBoundsException if the array is not sufficiently
1713 large to hold all elements
1714 */
1715 Object[] toArray(Object a[]) {
1716 /*
1717 Construct a new iterator and collect all items in the list as seen
1718 by this iterator.
1719 */
1720 ListItr iterator=new ListItr();
1721 Object[] elementArray=new Object[1];
1722 int index=0;
1723 /*
1724 iterate over the list and add the elements to the array
1725 */
1726 while(iterator.nextItem(elementArray)!=null)
1727 a[index++]=elementArray[0];
1728 return a;
1729 }
1730
1731 /**
1732 Returns a view of the portion of this list between the specified
1733 <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
1734
1735 (If
1736 <tt>fromIndex</tt> and <tt>toIndex</tt> are equal, the returned list is
1737 empty.) The returned list is backed by this list, so changes in the
1738 returned list are reflected in this list, and vice-versa. The returned
1739 list supports all of the optional list operations supported by this
1740 list.<p>
1741
1742 This method eliminates the need for explicit range operations (of
1743 the sort that commonly exist for arrays). Any operation that expects
1744 a list can be used as a range operation by passing a subList view
1745 instead of a whole list. For example, the following idiom
1746 removes a range of elements from a list:
1747 <pre>
1748 list.subList(from, to).clear();
1749 </pre>
1750 Similar idioms may be constructed for <tt>indexOf</tt> and
1751 <tt>lastIndexOf</tt>, and all of the algorithms in the
1752 <tt>Collections</tt> class can be applied to a subList.<p>
1753
1754 The semantics of this list returned by this method become undefined if
1755 the backing list (i.e., this list) is <i>structurally modified</i> in
1756 any way other than via the returned list. (Structural modifications are
1757 those that change the size of this list, or otherwise perturb it in such
1758 a fashion that iterations in progress may yield incorrect results.)
1759
1760 @param fromIndex low endpoint (inclusive) of the subList.
1761 @param toIndex high endpoint (exclusive) of the subList.
1762 @return a view of the specified range within this list.
1763
1764 @throws IndexOutOfBoundsException for an illegal endpoint index value
1765 (fromIndex < 0 || toIndex > size || fromIndex > toIndex).
1766 @throws UnsupportedOperationException if the method
1767 is not supported by this list.
1768 */
1769 public ConcurrentList subList(int fromIndex, int toIndex) {
1770 throw new UnsupportedOperationException();
1771 }
1772 }