Lines Matching refs:node
133 * (predecessor, node, successor) in order to detect when and how
139 * marking a pointer, they splice in another node that can be
147 * because any search need only read ahead one more node than
152 * algorithm of changing the next-pointer of a deleted node so
154 * changing the pointer to point to a different node, not by
164 * similar to typical lazy-deletion schemes. If a node's value is
177 * Here's the sequence of events for a deletion of node n with
186 * the node consider this mapping to exist. However, other
190 * 2. CAS n's next pointer to point to a new marker node.
207 * thread noticed during a traversal a node with null value and
227 * operations that can (rarely) fail to link in a new index node
255 * out node fields referencing user keys since they might still be
313 * Node: b, n, f for predecessor, node, successor
314 * Index: q, r, d for index node, right, down.
315 * t for another index node
379 * compareAndSet head node
390 * headed by a dummy node accessible as head.node. The value field
400 * Creates a new regular node.
409 * Creates a new marker node. A marker is distinguished by
413 * header node (head.node), which also has a null key.
436 * Returns true if this node is a marker. This method isn't
440 * test if value points to node.
441 * @param n a possibly null reference to a node
442 * @return true if this node is a marker node
449 * Returns true if this node is the header of base-level list.
450 * @return true if this node is header node
457 * Tries to append a deletion marker to this node.
458 * @param f the assumed current successor of this node
487 * Returns value if this node contains a valid key-value pair,
489 * @return this node's value if it isn't a marker or header or
501 * mapping if this node holds a valid value, else null.
541 final Node<K,V> node;
546 * Creates index node with given values.
548 Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
549 this.node = node;
562 * Returns true if the node this indexes has been deleted.
563 * @return true if indexed node is known to be deleted
566 return node.value == null;
571 * unlink that may lose this index node, if the node being
578 Node<K,V> n = node;
585 * succ. Fails (forcing a retraversal by caller) if this node
616 HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
617 super(node, down, right);
704 * Returns a base-level node with key strictly less than given key,
705 * or the base-level header if there is no such node. Also
719 Node<K,V> n = r.node;
738 return q.node;
744 * Returns node holding key or null if no such, clearing out any
751 * Restarts occur, at traversal step centered on node n, if:
755 * we don't have a consistent 3-node snapshot and so cannot
767 * findPredecessor returned a deleted node. We can't unlink
768 * the node because we don't know its predecessor, so rely
785 * @return node holding key, or null if no such
891 * Returns a random level for inserting a new node.
912 * Creates and adds index nodes for the given node.
913 * @param z the node
951 Node<K,V> oldbase = oldh.node;
965 * @param idx the topmost index node being inserted
973 Comparable<? super K> key = comparable(idx.node.key);
985 Node<K,V> n = r.node;
1002 // Don't insert index if node already deleted
1028 * Main deletion method. Locates node, nulls value, appends a
1034 * which will include the indexes to this node. This is done
1037 * indexes hadn't been inserted yet for this node during initial
1044 * @return the node, or null if not found
1126 * Specialized variant of findNode to get first valid node.
1127 * @return first node or null if empty
1131 Node<K,V> b = head.node;
1147 Node<K,V> b = head.node;
1191 * Specialized version of find to get last valid node.
1192 * @return last node or null if empty
1213 Node<K,V> b = q.node;
1238 * valid node. Needed when removing the last entry. It is possible
1239 * that all successors of returned node will have been deleted upon
1241 * @return likely predecessor of last node
1254 if (r.node.next != null) {
1262 return q.node;
1326 * @return nearest node fitting relation, or null if no such
1461 Node<K,V> basepred = h.node;
1463 // Track the current rightmost node at each level. Uses an
1494 h = new HeadIndex<K,V>(h.node, h, idx, i);
1553 Node<K,V> basepred = h.node;
1582 h = new HeadIndex<K,V>(h.node, h, idx, i);
2196 /** the last node returned by next() */
2198 /** the next node to return from next(); */
2547 * Returns true if node key is less than upper bound of range
2564 * Returns lowest node. This node might not be in range, so
2577 * Returns highest node. This node might not be in range, so
3001 /** the last node returned by next() */
3003 /** the next node to return from next(); */