private Node<K,V> findNode(Comparable<? super K> key){
  for (; ; ) {
    Node<K,V> b=findPredecessor(key);
    Node<K,V> n=b.next;
    for (; ; ) {
      if (n == null)       return null;
      Node<K,V> f=n.next;
      if (n != b.next)       break;
      Object v=n.value;
      if (v == null) {
        n.helpDelete(b,f);
        break;
      }
      if (v == n || b.value == null)       break;
      int c=key.compareTo(n.key);
      if (c == 0)       return n;
      if (c < 0)       return null;
      b=n;
      n=f;
    }
  }
}

private Node < K , V > findNode ( Comparable < ? super K > key ) { for ( ; ; ) { Node < K , V > b = findPredecessor ( key ) ; Node < K , V > n = b . next ; for ( ; ; ) { if ( n == null ) return null ; Node < K , V > f = n . next ; if ( n != b . next ) break ; Object v = n . value ; if ( v == null ) { n . helpDelete ( b , f ) ; break ; } if ( v == n || b . value == null ) break ; int c = key . compareTo ( n . key ) ; if ( c == 0 ) return n ; if ( c < 0 ) return null ; b = n ; n = f ; } } }
returns node holding key or null if no such , clearing out any deleted nodes seen along the way . repeatedly traverses at base - level looking for key starting at predecessor returned from findpredecessor , processing base - level deletions as encountered . some callers rely on this side - effect of clearing deleted nodes . restarts occur , at traversal step centered on node n , if : ( 1 ) after reading n ' s next field , n is no longer assumed predecessor b ' s current successor , which means that we don ' t have a consistent 3 - node snapshot and so cannot unlink any subsequent deleted nodes encountered . ( 2 ) n ' s value field is null , indicating n is deleted , in which case we help out an ongoing structural deletion before retrying . even though there are cases where such unlinking doesn ' t require restart , they aren ' t sorted out here because doing so would not usually outweigh cost of restarting . ( 3 ) n is a marker or n ' s predecessor ' s value field is null , indicating ( among other possibilities ) that findpredecessor returned a deleted node . we can ' t unlink the node because we don ' t know its predecessor , so rely on another call to findpredecessor to notice and return some earlier predecessor , which it will do . this check is only strictly needed at beginning of loop , ( and the b . value check isn ' t strictly needed at all ) but is done each iteration to help avoid contention with other threads by callers that will fail to be able to change links , and so will retry anyway . the traversal loops in doput , doremove , and findnear all include the same three kinds of checks . and specialized versions appear in findfirst , and findlast and their variants . they can ' t easily share code because each uses the reads of fields held in locals occurring in the orders they were performed .
