| 719 |
|
} |
| 720 |
|
|
| 721 |
|
/** |
| 722 |
< |
* Shared data between iterators and their queue. Allows queue |
| 722 |
> |
* Shared data between iterators and their queue, allowing queue |
| 723 |
|
* modifications to update iterators when elements are removed. |
| 724 |
|
* |
| 725 |
< |
* We track all active iterators in a linked list of weak references |
| 726 |
< |
* to Itr, so that queue operations can update the iterators. The |
| 727 |
< |
* list is cleaned up using 3 different mechanisms: |
| 725 |
> |
* This adds a lot of complexity for the sake of correctly |
| 726 |
> |
* handling some uncommon operations, but the combination of |
| 727 |
> |
* circular-arrays and supporting interior removes (i.e., those |
| 728 |
> |
* not at head) would cause iterators to sometimes lose their |
| 729 |
> |
* places and/or (re)report elements they shouldn't. To avoid |
| 730 |
> |
* this, when a queue has one or more iterators, it keeps iterator |
| 731 |
> |
* state consistent by: |
| 732 |
> |
* |
| 733 |
> |
* (1) keeping track of the number of "cycles", that is, the |
| 734 |
> |
* number of times takeIndex has wrapped around to 0. |
| 735 |
> |
* (2) notifying all iterators via the callback removedAt whenever |
| 736 |
> |
* an interior element is removed (and thus other elements may |
| 737 |
> |
* be shifted). |
| 738 |
> |
* |
| 739 |
> |
* These suffice to eliminate iterator inconsistencies, but |
| 740 |
> |
* unfortunately add the secondary responsibility of maintaining |
| 741 |
> |
* the list of iterators. We track all active iterators in a |
| 742 |
> |
* simple linked list (accessed only when the queue's lock is |
| 743 |
> |
* held) of weak references to Itr. The list is cleaned up using |
| 744 |
> |
* 3 different mechanisms: |
| 745 |
|
* |
| 746 |
|
* (1) Whenever a new iterator is created, do some O(1) checking for |
| 747 |
|
* stale list elements. |
| 752 |
|
* (3) Whenever the queue becomes empty, all iterators are notified |
| 753 |
|
* and this entire data structure is discarded. |
| 754 |
|
* |
| 755 |
< |
* Whenever a list element is examined, it is expunged if either the |
| 756 |
< |
* GC has determined that the iterator is discarded, or if the |
| 757 |
< |
* iterator reports that it is "detached" (does not need any further |
| 758 |
< |
* state updates). |
| 759 |
< |
* |
| 760 |
< |
* This achieves our goals of a high-reliability iterator that adds |
| 761 |
< |
* very little overhead if users don't create iterators. The most |
| 762 |
< |
* overhead is seen if takeIndex never advances, iterators are |
| 763 |
< |
* discarded before they are exhausted, and all removals are |
| 764 |
< |
* interior removes, in which case all stale iterators are |
| 765 |
< |
* discovered by the GC. But even in this case we don't increase |
| 766 |
< |
* the amortized complexity. |
| 755 |
> |
* So in addition to the removedAt callback that is necessary for |
| 756 |
> |
* correctness, iterators have the shutdown and takeIndexWrapped |
| 757 |
> |
* callbacks that help remove stale iterators from the list. |
| 758 |
> |
* |
| 759 |
> |
* Whenever a list element is examined, it is expunged if either |
| 760 |
> |
* the GC has determined that the iterator is discarded, or if the |
| 761 |
> |
* iterator reports that it is "detached" (does not need any |
| 762 |
> |
* further state updates). Overhead is maximal when takeIndex |
| 763 |
> |
* never advances, iterators are discarded before they are |
| 764 |
> |
* exhausted, and all removals are interior removes, in which case |
| 765 |
> |
* all stale iterators are discovered by the GC. But even in this |
| 766 |
> |
* case we don't increase the amortized complexity. |
| 767 |
> |
* |
| 768 |
> |
* Care must be taken to keep list sweeping methods from |
| 769 |
> |
* reentrantly invoking another such method, causing subtle |
| 770 |
> |
* corruption bugs. |
| 771 |
|
*/ |
| 772 |
|
class Itrs { |
| 773 |
|
|
| 802 |
|
/** |
| 803 |
|
* Sweeps itrs, looking for and expunging stale iterators. |
| 804 |
|
* If at least one was found, tries harder to find more. |
| 805 |
+ |
* Called only from iterating thread. |
| 806 |
|
* |
| 807 |
|
* @param tryHarder whether to start in try-harder mode, because |
| 808 |
|
* there is known to be at least one iterator to collect |
