读ConcurrentSkipListMap源码

//数据结构是跳表 关于数据结构http://blog.csdn.net/coslay/article/details/44819823这篇文章写得很好
//另外ConcurrentSkipListSet底层也是用ConcurrentSkipListMap实现的。
//先看构造函数
public ConcurrentSkipListMap() {
        this.comparator = null;
        initialize();
    }

public ConcurrentSkipListMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
        initialize();
    }

 public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
        this.comparator = null;
        initialize();
        putAll(m);
    }
public void putAll(Map<? extends K, ? extends V> m) {
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
            put(e.getKey(), e.getValue());
    }
 public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
        this.comparator = m.comparator();
        initialize();
        buildFromSorted(m);
    }
final void initialize() {
        keySet = null;
        entrySet = null;
        values = null;
        descendingMap = null;
        randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero
	//初始化头节点
        head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
                                  null, null, 1);
    }

 private void buildFromSorted(SortedMap<K, ? extends V> map) {
        if (map == null)
            throw new NullPointerException();

        HeadIndex<K,V> h = head;
        Node<K,V> basepred = h.node;

        ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();

        // 初始化
        for (int i = 0; i <= h.level; ++i)
            preds.add(null);
        Index<K,V> q = h;
        for (int i = h.level; i > 0; --i) {
            preds.set(i, q);
            q = q.down;
        }

        Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
            map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<? extends K, ? extends V> e = it.next();
            int j = randomLevel();
            if (j > h.level) j = h.level + 1;
            K k = e.getKey();
            V v = e.getValue();
            if (k == null || v == null)
                throw new NullPointerException();
            Node<K,V> z = new Node<K,V>(k, v, null);
            basepred.next = z;
            basepred = z;
            if (j > 0) {
                Index<K,V> idx = null;
                for (int i = 1; i <= j; ++i) {
                    idx = new Index<K,V>(z, idx, null);
                    if (i > h.level)
                        h = new HeadIndex<K,V>(h.node, h, idx, i);

                    if (i < preds.size()) {
                        preds.get(i).right = idx;
                        preds.set(i, idx);
                    } else
                        preds.add(idx);
                }
            }
        }
        head = h;
    }
//新增元素
public V put(K key, V value) {
        if (value == null)
            throw new NullPointerException();
        return doPut(key, value, false);
    }

private V doPut(K kkey, V value, boolean onlyIfAbsent) {
       //转换比较器
        Comparable<? super K> key = comparable(kkey);
        for (;;) {
	  //找到前驱节点
            Node<K,V> b = findPredecessor(key);
	    //拿到下一个节点
            Node<K,V> n = b.next;
	    //插入到b n之间,循环找到n
            for (;;) {
                if (n != null) {
                    Node<K,V> f = n.next;
		    //再次确认没有人修改过
                    if (n != b.next)               // inconsistent read
                        break;
                    Object v = n.value;
		    //删除节点
                    if (v == null) {               // n is deleted
                        n.helpDelete(b, f);
                        break;
                    }
		    //b被删除了
                    if (v == n || b.value == null) // b is deleted
                        break;
                    int c = key.compareTo(n.key);
		    //继续循环
                    if (c > 0) {
                        b = n;
                        n = f;
                        continue;
                    }
		    //相等直接设置值
                    if (c == 0) {
                        if (onlyIfAbsent || n.casValue(v, value))
                            return (V)v;
                        else
                            break; // restart if lost race to replace value
                    }
                    // else c < 0; fall through
                }

                Node<K,V> z = new Node<K,V>(kkey, value, n);
		//设置不成功则继续循环
                if (!b.casNext(n, z))
                    break;         // restart if lost race to append to b
		//随机计算一个层级
                int level = randomLevel();
		
                if (level > 0)
		    //将z插入到该层级
                    insertIndex(z, level);
                return null;
            }
        }
    }

 private Comparable<? super K> comparable(Object key)
            throws ClassCastException {
        if (key == null)
            throw new NullPointerException();
        if (comparator != null)
            return new ComparableUsingComparator<K>((K)key, comparator);
        else
            return (Comparable<? super K>)key;
    }

static final class ComparableUsingComparator<K> implements Comparable<K> {
        final K actualKey;
        final Comparator<? super K> cmp;
        ComparableUsingComparator(K key, Comparator<? super K> cmp) {
            this.actualKey = key;
            this.cmp = cmp;
        }
        public int compareTo(K k2) {
            return cmp.compare(actualKey, k2);
        }
    }

//找到前驱节点
private Node<K,V> findPredecessor(Comparable<? super K> key) {
        if (key == null)
            throw new NullPointerException(); // don't postpone errors
	//先横着找
        for (;;) {
            Index<K,V> q = head;
            Index<K,V> r = q.right;
            for (;;) {
	        //右边还有节点
                if (r != null) {
                    Node<K,V> n = r.node;
                    K k = n.key;
		    //如果节点的值为null删掉该节点
                    if (n.value == null) {
		       //删除失败重新横着找
                        if (!q.unlink(r))
                            break;        // restart
			//成功接着横着找
                        r = q.right;         // reread r
                        continue;
                    }
		    //如果key比当前节点大继续找
                    if (key.compareTo(k) > 0) {
                        q = r;
                        r = r.right;
                        continue;
                    }
                }
		//横着找完了往下一级找
                Index<K,V> d = q.down;
                if (d != null) {
                    q = d;
                    r = d.right;
                } else
                    return q.node;
            }
        }
    }

final boolean unlink(Index<K,V> succ) {
            return !indexesDeletedNode() && casRight(succ, succ.right);
        }

final boolean indexesDeletedNode() {
            return node.value == null;
        }

final boolean casRight(Index<K,V> cmp, Index<K,V> val) {
            return UNSAFE.compareAndSwapObject(this, rightOffset, cmp, val);
        }

//插入到层级中
private void insertIndex(Node<K,V> z, int level) {
        HeadIndex<K,V> h = head;
        int max = h.level;
        //如果小于当前的最大层级
        if (level <= max) {
            Index<K,V> idx = null;
            for (int i = 1; i <= level; ++i)
                idx = new Index<K,V>(z, idx, null);
            addIndex(idx, h, level);

        } else { 
           //新增层级
            level = max + 1;
            Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1];
            Index<K,V> idx = null;
            for (int i = 1; i <= level; ++i)
                idxs[i] = idx = new Index<K,V>(z, idx, null);

            HeadIndex<K,V> oldh;
            int k;
            for (;;) {
                oldh = head;
                int oldLevel = oldh.level;
		//其他线程新增了层级
                if (level <= oldLevel) { // lost race to add level
                    k = level;
                    break;
                }
                HeadIndex<K,V> newh = oldh;
                Node<K,V> oldbase = oldh.node;
                for (int j = oldLevel+1; j <= level; ++j)
                    newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
               //设置头
		if (casHead(oldh, newh)) {
                    k = oldLevel;
                    break;
                }
            }
            addIndex(idxs[k], oldh, k);
        }
    }

//插入到层级
private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) {
        int insertionLevel = indexLevel;
        Comparable<? super K> key = comparable(idx.node.key);
        if (key == null) throw new NullPointerException();

        // Similar to findPredecessor, but adding index nodes along
        // path to key.
        for (;;) {
            int j = h.level;
            Index<K,V> q = h;
            Index<K,V> r = q.right;
            Index<K,V> t = idx;
            for (;;) {
                if (r != null) {
                    Node<K,V> n = r.node;
                    // compare before deletion check avoids needing recheck
                    int c = key.compareTo(n.key);
		    
                    if (n.value == null) {
		     //移除r
                        if (!q.unlink(r))
                            break;
                        r = q.right;
			继续循环
                        continue;
                    }
		    //如果比他大继续循环
                    if (c > 0) {
                        q = r;
                        r = r.right;
                        continue;
                    }
                }
                //如果刚好在插入的层级
                if (j == insertionLevel) {
		    //t的node value值为null t是要被删除的节点所以不插入
                    if (t.indexesDeletedNode()) {
		        //寻找节点并且删除其中的null节点
                        findNode(key); // cleans up
                        return;
                    }
		    //插入新节点失败
                    if (!q.link(r, t))
                        break; // restart
	            //如果现在是最底层了
                    if (--insertionLevel == 0) {
                        // need final deletion check before return
                        if (t.indexesDeletedNode())
                            findNode(key);
                        return;
                    }
                }
                //当--insertionLevel后如果满足,说明该层需要插入节点
                if (--j >= insertionLevel && j < indexLevel)
                    t = t.down;
                q = q.down;
                r = q.right;
            }
        }
    }

//寻找相等节点并且移除空节点
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;
		//n变了说明其他线程操作过了
                if (n != b.next)                // inconsistent read
                    break;
                Object v = n.value;
		//删掉该节点继续循环
                if (v == null) {                // n is deleted
                    n.helpDelete(b, f);
                    break;
                }
                if (v == n || b.value == null)  // b is deleted
                    break;
		 //相等
                int c = key.compareTo(n.key);
                if (c == 0)
                    return n;
                if (c < 0)
                    return null;
                b = n;
                n = f;
            }
        }
    }


//删除节点
void helpDelete(Node<K,V> b, Node<K,V> f) {
            
            if (f == next && this == b.next) {
	        //说明f已经被修改
                if (f == null || f.value != f) // not already marked
                    appendMarker(f);
                else
                    b.casNext(this, f.next);
            }
        }


 boolean appendMarker(Node<K,V> f) {
            return casNext(f, new Node<K,V>(f));
        }

//在node与succ之间插入新节点
final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
            Node<K,V> n = node;
            newSucc.right = succ;
            return n.value != null && casRight(succ, newSucc);
        }

//删除某个节点
public V remove(Object key) {
        return doRemove(key, null);
    }


final V doRemove(Object okey, Object value) {
        Comparable<? super K> key = comparable(okey);
        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)                    // inconsistent read
                    break;
                Object v = n.value;
                if (v == null) {                    // n is deleted
                    n.helpDelete(b, f);
                    break;
                }
                if (v == n || b.value == null)      // b is deleted
                    break;
                int c = key.compareTo(n.key);
		//找完了都没有找到返回null
                if (c < 0)
                    return null;
		//继续找
                if (c > 0) {
                    b = n;
                    n = f;
                    continue;
                }
		//如果value不相等返回null
                if (value != null && !value.equals(v))
                    return null;
		//设置null失败重新循环
                if (!n.casValue(v, null))
                    break;
		  //添加删除标记
                if (!n.appendMarker(f) || !b.casNext(n, f))
                    findNode(key);                  // Retry via findNode
                else {
		    //删除节点
                    findPredecessor(key);           // Clean index
		    //最顶层的节点删完了尝试降低层级
                    if (head.right == null)
                        tryReduceLevel();
                }
                return (V)v;
            }
        }
    }

    private void tryReduceLevel() {
        HeadIndex<K,V> h = head;
        HeadIndex<K,V> d;
        HeadIndex<K,V> e;
        if (h.level > 3 &&
            (d = (HeadIndex<K,V>)h.down) != null &&
            (e = (HeadIndex<K,V>)d.down) != null &&
            e.right == null &&
            d.right == null &&
            h.right == null &&
            casHead(h, d) && // try to set
            h.right != null) // recheck
            casHead(d, h);   // try to backout
    }

    //只有key不在列表中时才设置值
    public V putIfAbsent(K key, V value) {
        if (value == null)
            throw new NullPointerException();
        return doPut(key, value, true);
    }

//根据key获取值
 public V get(Object key) {
        return doGet(key);
    }

private V doGet(Object okey) {
        Comparable<? super K> key = comparable(okey);
        
        for (;;) {
            Node<K,V> n = findNode(key);
            if (n == null)
                return null;
            Object v = n.value;
            if (v != null)
                return (V)v;
        }
    }

//根据key和value值删除
 public boolean remove(Object key, Object value) {
        if (key == null)
            throw new NullPointerException();
        if (value == null)
            return false;
        return doRemove(key, value) != null;
    }

//根据key替换值
  public V replace(K key, V value) {
        if (value == null)
            throw new NullPointerException();
        Comparable<? super K> k = comparable(key);
        for (;;) {
            Node<K,V> n = findNode(k);
            if (n == null)
                return null;
            Object v = n.value;
            if (v != null && n.casValue(v, value))
                return (V)v;
        }
    }


//只有和期望的值相等时才删除
    public boolean replace(K key, V oldValue, V newValue) {
        if (oldValue == null || newValue == null)
            throw new NullPointerException();
        Comparable<? super K> k = comparable(key);
        for (;;) {
            Node<K,V> n = findNode(k);
            if (n == null)
                return false;
            Object v = n.value;
            if (v != null) {
                if (!oldValue.equals(v))
                    return false;
		//尝试成功返回true,失败接着尝试
                if (n.casValue(v, newValue))
                    return true;
            }
        }
    }


//是否包含某个键
public boolean containsKey(Object key) {
        return doGet(key) != null;
    }

//是否包含某个值
 public boolean containsValue(Object value) {
        if (value == null)
            throw new NullPointerException();
        for (Node<K,V> n = findFirst(); n != null; n = n.next) {
            V v = n.getValidValue();
            if (v != null && value.equals(v))
                return true;
        }
        return false;
    }

//找到头几点的下一个节点也就是第一个节点
 Node<K,V> findFirst() {
        for (;;) {
            Node<K,V> b = head.node;
            Node<K,V> n = b.next;
            if (n == null)
                return null;
            if (n.value != null)
                return n;
	    //n.value==null
            n.helpDelete(b, n.next);
        }
    }

V getValidValue() {
            Object v = value;
            if (v == this || v == BASE_HEADER)
                return null;
            return (V)v;
        }

//获取长度
 public int size() {
        long count = 0;
        for (Node<K,V> n = findFirst(); n != null; n = n.next) {
            if (n.getValidValue() != null)
                ++count;
        }
        return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) count;
    }

//队列是否为空
public boolean isEmpty() {
        return findFirst() == null;
    }

//清空队列
public void clear() {
        initialize();
    }

//返回第一个key
public K firstKey() {
        Node<K,V> n = findFirst();
        if (n == null)
            throw new NoSuchElementException();
        return n.key;
    }

//获取最后一个node
 Node<K,V> findLast() {
        
        Index<K,V> q = head;
        for (;;) {
            Index<K,V> d, r;
	    //如果右边有元素
            if ((r = q.right) != null) {
	        //该元素是否需要被删除
                if (r.indexesDeletedNode()) {
                    q.unlink(r);
		    //重新循环
                    q = head; // restart
                }
                else
		   //将r赋值q继续循环
                    q = r;
              //循环到下一层级
            } else if ((d = q.down) != null) {
                q = d;
            } else {
	      //最底层了
                Node<K,V> b = q.node;
                Node<K,V> n = b.next;
                for (;;) {
                    if (n == null)
                        return b.isBaseHeader() ? null : b;
                    Node<K,V> f = n.next;            // inconsistent read
                    if (n != b.next)
                        break;
                    Object v = n.value;
                    if (v == null) {                 // n is deleted
                        n.helpDelete(b, f);
                        break;
                    }
                    if (v == n || b.value == null)   // b is deleted
                        break;
                    b = n;
                    n = f;
                }
                q = head; // restart
            }
        }
    }

//是否是头几点包含的元素
boolean isBaseHeader() {
            return value == BASE_HEADER;
        }

//获取最后一个node的key值
public K lastKey() {
        Node<K,V> n = findLast();
        if (n == null)
            throw new NoSuchElementException();
        return n.key;
    }

//返回小于当前key的entry值
public Map.Entry<K,V> lowerEntry(K key) {
        return getNear(key, LT);
    }


AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) {
        for (;;) {
	    //找到最相等的那个节点
            Node<K,V> n = findNear(key, rel);
            if (n == null)
                return null;
            AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
            if (e != null)
                return e;
        }
    }

 Node<K,V> findNear(K kkey, int rel) {
        Comparable<? super K> key = comparable(kkey);
        for (;;) {
            Node<K,V> b = findPredecessor(key);
            Node<K,V> n = b.next;
            for (;;) {
	       //b的后面没了
                if (n == null)
                    return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b;
                Node<K,V> f = n.next;
                if (n != b.next)                  // inconsistent read
                    break;
                Object v = n.value;
                if (v == null) {                  // n is deleted
                    n.helpDelete(b, f);
                    break;
                }
                if (v == n || b.value == null)    // b is deleted
                    break;
                int c = key.compareTo(n.key);
                if ((c == 0 && (rel & EQ) != 0) ||
                    (c <  0 && (rel & LT) == 0))
                    return n;
                if ( c <= 0 && (rel & LT) != 0)
                    return b.isBaseHeader() ? null : b;
                b = n;
                n = f;
            }
        }
    }

AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {
            V v = getValidValue();
            if (v == null)
                return null;
            return new AbstractMap.SimpleImmutableEntry<K,V>(key, v);
        }

//返回小于当前key的key值
public K lowerKey(K key) {
        Node<K,V> n = findNear(key, LT);
        return (n == null) ? null : n.key;
    }

//返回小于或等于当前key的entry
 public Map.Entry<K,V> floorEntry(K key) {
        return getNear(key, LT|EQ);
    }
//返回小于或等于当前key的key
public K floorKey(K key) {
        Node<K,V> n = findNear(key, LT|EQ);
        return (n == null) ? null : n.key;
    }
//返回大于或等于当前key的entry
public Map.Entry<K,V> ceilingEntry(K key) {
        return getNear(key, GT|EQ);
    }
//返回大于或等于当前key的key值
public K ceilingKey(K key) {
        Node<K,V> n = findNear(key, GT|EQ);
        return (n == null) ? null : n.key;
    }

//返回大于当前key的entry
 public Map.Entry<K,V> higherEntry(K key) {
        return getNear(key, GT);
    }
//返回大于当前key的key值   
 public K higherKey(K key) {
        Node<K,V> n = findNear(key, GT);
        return (n == null) ? null : n.key;
    }

//获取并移除第一个entry
 public Map.Entry<K,V> pollFirstEntry() {
        return doRemoveFirstEntry();
    }

Map.Entry<K,V> doRemoveFirstEntry() {
        for (;;) {
            Node<K,V> b = head.node;
            Node<K,V> n = b.next;
            if (n == null)
                return null;
            Node<K,V> f = n.next;
            if (n != b.next)
                continue;
            Object v = n.value;
            if (v == null) {
                n.helpDelete(b, f);
                continue;
            }
	    //cas将值设置为null
            if (!n.casValue(v, null))
                continue;
            if (!n.appendMarker(f) || !b.casNext(n, f))
                findFirst(); // retry
            clearIndexToFirst();
            return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, (V)v);
        }
    }

  private void clearIndexToFirst() {
        for (;;) {
            Index<K,V> q = head;
            for (;;) {
                Index<K,V> r = q.right;
                if (r != null && r.indexesDeletedNode() && !q.unlink(r))
                    break;
		//尝试降级
                if ((q = q.down) == null) {
                    if (head.right == null)
                        tryReduceLevel();
                    return;
                }
            }
        }
    }

//获取并移除最后一个entry
public Map.Entry<K,V> pollLastEntry() {
        return doRemoveLastEntry();
    }

Map.Entry<K,V> doRemoveLastEntry() {
        for (;;) {
	    //找到最后一个节点
            Node<K,V> b = findPredecessorOfLast();
            Node<K,V> n = b.next;
            if (n == null) {
                if (b.isBaseHeader())               // empty
                    return null;
                else
                    continue; // all b's successors are deleted; retry
            }
            for (;;) {
                Node<K,V> f = n.next;
                if (n != b.next)                    // inconsistent read
                    break;
                Object v = n.value;
                if (v == null) {                    // n is deleted
                    n.helpDelete(b, f);
                    break;
                }
                if (v == n || b.value == null)      // b is deleted
                    break;
                if (f != null) {
                    b = n;
                    n = f;
                    continue;
                }
                if (!n.casValue(v, null))
                    break;
                K key = n.key;
                Comparable<? super K> ck = comparable(key);
                if (!n.appendMarker(f) || !b.casNext(n, f))
                    findNode(ck);                  // Retry via findNode
                else {
                    findPredecessor(ck);           // Clean index
                    if (head.right == null)
                        tryReduceLevel();
                }
                return new AbstractMap.SimpleImmutableEntry<K,V>(key, (V)v);
            }
        }
    }


 private Node<K,V> findPredecessorOfLast() {
        for (;;) {
            Index<K,V> q = head;
            for (;;) {
                Index<K,V> d, r;
                if ((r = q.right) != null) {
                    if (r.indexesDeletedNode()) {
                        q.unlink(r);
                        break;    // must restart
                    }
                    // proceed as far across as possible without overshooting
                    if (r.node.next != null) {
                        q = r;
                        continue;
                    }
                }
                if ((d = q.down) != null)
                    q = d;
                else
                    return q.node;
            }
        }
    }
//将值封装到集合
public Collection<V> values() {
        Values vs = values;
        return (vs != null) ? vs : (values = new Values(this));
    }