Lines Matching refs:Node
113 * A node contains the expected E ("item") and links to predecessor
116 * class Node<E> { volatile Node<E> prev, next; volatile E item; }
118 * A node p is considered "live" if it contains a non-null item
122 * At any time, there is precisely one "first" node with a null
124 * starting at a live node. Similarly there is precisely one
125 * "last" node terminating any chain of next references starting at
126 * a live node. The "first" and "last" nodes may or may not be live.
130 * next reference in the first or last node to a fresh node
131 * containing the element. The element's node atomically becomes
134 * A node is considered "active" if it is a live node, or the
135 * first or last node. Active nodes cannot be unlinked.
137 * A "self-link" is a next or prev reference that is the same node:
139 * Self-links are used in the node unlinking process. Active nodes
142 * A node p is active if and only if:
148 * The deque object has two node references, "head" and "tail".
150 * nodes of the deque. The first node can always be found by
154 * any live node.
156 * There are 3 stages of node deletion;
160 * the element from the collection, and makes the containing node
163 * 2. "unlinking" makes a deleted node unreachable from active
167 * Physical node unlinking is merely an optimization (albeit a
171 * links from the first node is equal to the elements found via
172 * prev links from the last node. However, this is not true for
190 * When a node is dequeued at either end, e.g. via poll(), we would
191 * like to break any references from the node to active nodes. We
201 * safely is particularly tricky, since any node can be in use
218 * goto the first node (which in turn is reached by following prev
221 * dummy node, NEXT_TERMINATOR, and not the last active node.
225 * find the last (active) node, for enqueueing a new node, we need
226 * to check whether we have reached a TERMINATOR node; if so,
251 * A node from which the first node on list (that is, the unique node p
254 * - the first node is always O(1) reachable from head via prev links
255 * - all live nodes are reachable from the first node via succ()
261 * - head may not be reachable from the first or last node, or from tail
263 private transient volatile Node<E> head;
266 * A node from which the last node on list (that is, the unique node p
269 * - the last node is always O(1) reachable from tail via next links
270 * - all live nodes are reachable from the last node via pred()
275 * - tail may not be reachable from the first or last node, or from head
277 private transient volatile Node<E> tail;
279 private static final Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR;
282 Node<E> prevTerminator() {
283 return (Node<E>) PREV_TERMINATOR;
287 Node<E> nextTerminator() {
288 return (Node<E>) NEXT_TERMINATOR;
291 static final class Node<E> {
292 volatile Node<E> prev;
294 volatile Node<E> next;
296 Node() { // default constructor for NEXT_TERMINATOR, PREV_TERMINATOR
300 * Constructs a new node. Uses relaxed write because item can
303 Node(E item) {
311 void lazySetNext(Node<E> val) {
315 boolean casNext(Node<E> cmp, Node<E> val) {
319 void lazySetPrev(Node<E> val) {
323 boolean casPrev(Node<E> cmp, Node<E> val) {
337 (Node.class.getDeclaredField("prev"));
339 (Node.class.getDeclaredField("item"));
341 (Node.class.getDeclaredField("next"));
352 final Node<E> newNode = new Node<E>(Objects.requireNonNull(e));
356 for (Node<E> h = head, p = h, q;;) {
365 // p is first node
384 final Node<E> newNode = new Node<E>(Objects.requireNonNull(e));
388 for (Node<E> t = tail, p = t, q;;) {
397 // p is last node
415 * Unlinks non-null node x.
417 void unlink(Node<E> x) {
423 final Node<E> prev = x.prev;
424 final Node<E> next = x.next;
430 // Unlink interior node.
449 Node<E> activePred, activeSucc;
454 for (Node<E> p = prev; ; ++hops) {
460 Node<E> q = p.prev;
475 for (Node<E> p = next; ; ++hops) {
481 Node<E> q = p.next;
526 * Unlinks non-null first node.
528 private void unlinkFirst(Node<E> first, Node<E> next) {
532 for (Node<E> o = null, p = next, q;;) {
560 * Unlinks non-null last node.
562 private void unlinkLast(Node<E> last, Node<E> prev) {
566 for (Node<E> o = null, p = prev, q;;) {
594 * Guarantees that any node which was unlinked before a call to
597 * point to a node that was active while this method was running.
600 // Either head already points to an active node, or we keep
601 // trying to cas it to the first node until it does.
602 Node<E> h, p, q;
624 * Guarantees that any node which was unlinked before a call to
627 * point to a node that was active while this method was running.
630 // Either tail already points to an active node, or we keep
631 // trying to cas it to the last node until it does.
632 Node<E> t, p, q;
653 private void skipDeletedPredecessors(Node<E> x) {
656 Node<E> prev = x.prev;
660 Node<E> p = prev;
665 Node<E> q = p.prev;
684 private void skipDeletedSuccessors(Node<E> x) {
687 Node<E> next = x.next;
691 Node<E> p = next;
696 Node<E> q = p.next;
716 * Returns the successor of p, or the first node if p.next has been
720 final Node<E> succ(Node<E> p) {
722 Node<E> q = p.next;
727 * Returns the predecessor of p, or the last node if p.prev has been
731 final Node<E> pred(Node<E> p) {
732 Node<E> q = p.prev;
737 * Returns the first node, the unique node p for which:
739 * The returned node may or may not be logically deleted.
740 * Guarantees that head is set to the returned node.
742 Node<E> first() {
745 for (Node<E> h = head, p = h, q;;) {
762 * Returns the last node, the unique node p for which:
764 * The returned node may or may not be logically deleted.
765 * Guarantees that tail is set to the returned node.
767 Node<E> last() {
770 for (Node<E> t = tail, p = t, q;;) {
805 head = tail = new Node<E>(null);
819 Node<E> h = null, t = null;
821 Node<E> newNode = new Node<E>(Objects.requireNonNull(e));
836 private void initHeadTail(Node<E> h, Node<E> t) {
839 h = t = new Node<E>(null);
841 // Avoid edge case of a single Node with non-null item.
842 Node<E> newNode = new Node<E>(null);
903 for (Node<E> p = first(); p != null; p = succ(p)) {
912 for (Node<E> p = last(); p != null; p = pred(p)) {
935 for (Node<E> p = first(); p != null; p = succ(p)) {
946 for (Node<E> p = last(); p != null; p = pred(p)) {
1032 for (Node<E> p = first(); p != null; p = succ(p)) {
1056 for (Node<E> p = last(); p != null; p = pred(p)) {
1076 for (Node<E> p = first(); p != null; p = succ(p)) {
1113 for (Node<E> p = first(); p != null;) {
1160 Node<E> beginningOfTheEnd = null, last = null;
1162 Node<E> newNode = new Node<E>(Objects.requireNonNull(e));
1177 for (Node<E> t = tail, p = t, q;;) {
1186 // p is last node
1218 for (Node<E> p = first(); p != null;) {
1244 for (Node<E> p = first(); p != null;) {
1358 * Next node to return item for.
1360 private Node<E> nextNode;
1371 * Node returned by most recent call to next. Needed by remove.
1374 private Node<E> lastRet;
1376 abstract Node<E> startNode();
1377 abstract Node<E> nextNode(Node<E> p);
1384 * Sets nextNode and nextItem to next valid node, or to null
1390 Node<E> p = (nextNode == null) ? startNode() : nextNode(nextNode);
1393 // might be at active end or TERMINATOR node; both are OK
1419 Node<E> l = lastRet;
1429 Node<E> startNode() { return first(); }
1430 Node<E> nextNode(Node<E> p) { return succ(p); }
1435 Node<E> startNode() { return last(); }
1436 Node<E> nextNode(Node<E> p) { return pred(p); }
1443 Node<E> current; // current node; null until initialized
1451 Node<E> p;
1483 Node<E> p;
1500 Node<E> p;
1564 for (Node<E> p = first(); p != null; p = succ(p)) {
1586 Node<E> h = null, t = null;
1589 Node<E> newNode = new Node<E>((E) item);
1601 private boolean casHead(Node<E> cmp, Node<E> val) {
1605 private boolean casTail(Node<E> cmp, Node<E> val) {
1615 PREV_TERMINATOR = new Node<Object>();
1617 NEXT_TERMINATOR = new Node<Object>();
