private V doPut(K key,V value,boolean onlyIfAbsent){
  Node<K,V> z;
  if (key == null)   throw new NullPointerException();
  Comparator<? super K> cmp=comparator;
  outer:   for (; ; ) {
    for (Node<K,V> b=findPredecessor(key,cmp), n=b.next; ; ) {
      if (n != null) {
        Object v;
        int c;
        Node<K,V> f=n.next;
        if (n != b.next)         break;
        if ((v=n.value) == null) {
          n.helpDelete(b,f);
          break;
        }
        if (b.value == null || v == n)         break;
        if ((c=cpr(cmp,key,n.key)) > 0) {
          b=n;
          n=f;
          continue;
        }
        if (c == 0) {
          if (onlyIfAbsent || n.casValue(v,value)) {
            @SuppressWarnings("unchecked") V vv=(V)v;
            return vv;
          }
          break;
        }
      }
      z=new Node<K,V>(key,value,n);
      if (!b.casNext(n,z))       break;
      break outer;
    }
  }
  int rnd=ThreadLocalRandom.nextSecondarySeed();
  if ((rnd & 0x80000001) == 0) {
    int level=1, max;
    while (((rnd>>>=1) & 1) != 0)     ++level;
    Index<K,V> idx=null;
    HeadIndex<K,V> h=head;
    if (level <= (max=h.level)) {
      for (int i=1; i <= level; ++i)       idx=new Index<K,V>(z,idx,null);
    }
 else {
      level=max + 1;
      @SuppressWarnings("unchecked") Index<K,V>[] idxs=(Index<K,V>[])new Index<?,?>[level + 1];
      for (int i=1; i <= level; ++i)       idxs[i]=idx=new Index<K,V>(z,idx,null);
      for (; ; ) {
        h=head;
        int oldLevel=h.level;
        if (level <= oldLevel)         break;
        HeadIndex<K,V> newh=h;
        Node<K,V> oldbase=h.node;
        for (int j=oldLevel + 1; j <= level; ++j)         newh=new HeadIndex<K,V>(oldbase,newh,idxs[j],j);
        if (casHead(h,newh)) {
          h=newh;
          idx=idxs[level=oldLevel];
          break;
        }
      }
    }
    splice:     for (int insertionLevel=level; ; ) {
      int j=h.level;
      for (Index<K,V> q=h, r=q.right, t=idx; ; ) {
        if (q == null || t == null)         break splice;
        if (r != null) {
          Node<K,V> n=r.node;
          int c=cpr(cmp,key,n.key);
          if (n.value == null) {
            if (!q.unlink(r))             break;
            r=q.right;
            continue;
          }
          if (c > 0) {
            q=r;
            r=r.right;
            continue;
          }
        }
        if (j == insertionLevel) {
          if (!q.link(r,t))           break;
          if (t.node.value == null) {
            findNode(key);
            break splice;
          }
          if (--insertionLevel == 0)           break splice;
        }
        if (--j >= insertionLevel && j < level)         t=t.down;
        q=q.down;
        r=q.right;
      }
    }
  }
  return null;
}

private V doPut ( K key , V value , boolean onlyIfAbsent ) { Node < K , V > z ; if ( key == null ) throw new NullPointerException ( ) ; Comparator < ? super K > cmp = comparator ; outer : for ( ; ; ) { for ( Node < K , V > b = findPredecessor ( key , cmp ) , n = b . next ; ; ) { if ( n != null ) { Object v ; int c ; Node < K , V > f = n . next ; if ( n != b . next ) break ; if ( ( v = n . value ) == null ) { n . helpDelete ( b , f ) ; break ; } if ( b . value == null || v == n ) break ; if ( ( c = cpr ( cmp , key , n . key ) ) > 0 ) { b = n ; n = f ; continue ; } if ( c == 0 ) { if ( onlyIfAbsent || n . casValue ( v , value ) ) { @ SuppressWarnings ( "unchecked" ) V vv = ( V ) v ; return vv ; } break ; } } z = new Node < K , V > ( key , value , n ) ; if ( ! b . casNext ( n , z ) ) break ; break outer ; } } int rnd = ThreadLocalRandom . nextSecondarySeed ( ) ; if ( ( rnd & 0x80000001 ) == 0 ) { int level = 1 , max ; while ( ( ( rnd >>>= 1 ) & 1 ) != 0 ) ++ level ; Index < K , V > idx = null ; HeadIndex < K , V > h = head ; if ( level <= ( max = h . level ) ) { for ( int i = 1 ; i <= level ; ++ i ) idx = new Index < K , V > ( z , idx , null ) ; } else { level = max + 1 ; @ SuppressWarnings ( "unchecked" ) Index < K , V > [ ] idxs = ( Index < K , V > [ ] ) new Index < ? , ? > [ level + 1 ] ; for ( int i = 1 ; i <= level ; ++ i ) idxs [ i ] = idx = new Index < K , V > ( z , idx , null ) ; for ( ; ; ) { h = head ; int oldLevel = h . level ; if ( level <= oldLevel ) break ; HeadIndex < K , V > newh = h ; Node < K , V > oldbase = h . node ; for ( int j = oldLevel + 1 ; j <= level ; ++ j ) newh = new HeadIndex < K , V > ( oldbase , newh , idxs [ j ] , j ) ; if ( casHead ( h , newh ) ) { h = newh ; idx = idxs [ level = oldLevel ] ; break ; } } } splice : for ( int insertionLevel = level ; ; ) { int j = h . level ; for ( Index < K , V > q = h , r = q . right , t = idx ; ; ) { if ( q == null || t == null ) break splice ; if ( r != null ) { Node < K , V > n = r . node ; int c = cpr ( cmp , key , n . key ) ; if ( n . value == null ) { if ( ! q . unlink ( r ) ) break ; r = q . right ; continue ; } if ( c > 0 ) { q = r ; r = r . right ; continue ; } } if ( j == insertionLevel ) { if ( ! q . link ( r , t ) ) break ; if ( t . node . value == null ) { findNode ( key ) ; break splice ; } if ( -- insertionLevel == 0 ) break splice ; } if ( -- j >= insertionLevel && j < level ) t = t . down ; q = q . down ; r = q . right ; } } } return null ; }
main insertion method . adds element if not present , or replaces value if present and onlyifabsent is false .
