数据结构之跳表SkipList、ConcurrentSkipListMap

/**
 * 指定全局比较器，用于比较两个元素的关键字大小并进行排序，如果在构造器中没有显式传入指定比较器，则默认对key按照自然顺序排序
 */
@SuppressWarnings("serial") // Conditionally serializable
final Comparator<? super K> comparator;
/** 最上层索引链表的头结点，延迟加载(包括下面几个属性)，即在使用时才会初始化 */
private transient Index<K,V> head;
/** 元素计数器 */
private transient LongAdder adder;
/** 保存key的set集合 */
private transient KeySet<K,V> keySet;
/** 保存value的集合 */
private transient Values<K,V> values;
/**  保存key-value的EntrySet集合 */
private transient EntrySet<K,V> entrySet;
/** 保存key-value结点的逆序排序的Map集合 */
private transient SubMap<K,V> descendingMap;

• 1.
• 2.
• 3.
• 4.
• 5.
• 6.
• 7.
• 8.
• 9.
• 10.
• 11.
• 12.
• 13.
• 14.
• 15.
• 16.
• 17.

static final class Node<K,V> {
	final K key; // currently, never detached
	V val;
	Node<K,V> next;
}

• 1.
• 2.
• 3.
• 4.
• 5.

static final class Index<K,V> {
	final Node<K,V> node;  // currently, never detached
	final Index<K,V> down;
	Index<K,V> right;
}

• 1.
• 2.
• 3.
• 4.
• 5.

abstract class Iter<T> implements Iterator<T> {
	/** next()方法返回的最后一个节点 */
	Node<K,V> lastReturned;
	/** next()方法返回的下一个节点 */
	Node<K,V> next;
	/** 缓存下一个值字段以保持弱一致性 */
	V nextValue;
	
	/** 初始化整个范围的升序迭代器 */
	Iter() {
		advance(baseHead());
	}
	
	public final boolean hasNext() {
		return next != null;
	}
	
	/** Advances next to higher entry. */
	final void advance(Node<K,V> b) {
		Node<K,V> n = null;
		V v = null;
		if ((lastReturned = b) != null) {
			while ((n = b.next) != null && (v = n.val) == null)
				b = n;
		}
		nextValue = v;
		next = n;
	}
	
	public final void remove() {
		Node<K,V> n; K k;
		if ((n = lastReturned) == null || (k = n.key) == null)
			throw new IllegalStateException();
		// It would not be worth all of the overhead to directly
		// unlink from here. Using remove is fast enough.
		ConcurrentSkipListMap.this.remove(k);
		lastReturned = null;
	}
}

• 1.
• 2.
• 3.
• 4.
• 5.
• 6.
• 7.
• 8.
• 9.
• 10.
• 11.
• 12.
• 13.
• 14.
• 15.
• 16.
• 17.
• 18.
• 19.
• 20.
• 21.
• 22.
• 23.
• 24.
• 25.
• 26.
• 27.
• 28.
• 29.
• 30.
• 31.
• 32.
• 33.
• 34.
• 35.
• 36.
• 37.
• 38.
• 39.

final V doRemove(Object key, Object value) {
	if (key == null)
	    throw new NullPointerException();
	Comparator<? super K> cmp = comparator;
	V result = null;
	Node<K,V> b;
	outer: while ((b = findPredecessor(key, cmp)) != null &&  result == null) {
	    for (;;) {
	        Node<K,V> n; K k; V v; int c;
	        if ((n = b.next) == null)
	            break outer;
	        else if ((k = n.key) == null)
	            break;
	        else if ((v = n.val) == null)
	            unlinkNode(b, n);
	        else if ((c = cpr(cmp, key, k)) > 0)
	            b = n;
	        else if (c < 0)
	            break outer;
	        else if (value != null && !value.equals(v))
	            break outer;
	        else if (VAL.compareAndSet(n, v, null)) {
	            result = v;
	            unlinkNode(b, n);
	            break; // loop to clean up
	        }
	    }
	}
	if (result != null) {
	    tryReduceLevel();
	    addCount(-1L);
	}
	return result;
}

• 1.
• 2.
• 3.
• 4.
• 5.
• 6.
• 7.
• 8.
• 9.
• 10.
• 11.
• 12.
• 13.
• 14.
• 15.
• 16.
• 17.
• 18.
• 19.
• 20.
• 21.
• 22.
• 23.
• 24.
• 25.
• 26.
• 27.
• 28.
• 29.
• 30.
• 31.
• 32.
• 33.
• 34.

public V replace(K key, V value) {
	if (key == null || value == null)
		throw new NullPointerException();
	for (;;) {
		Node<K,V> n; V v;
		if ((n = findNode(key)) == null)
			return null;
		if ((v = n.val) != null && VAL.compareAndSet(n, v, value))
			return v;
	}
}

• 1.
• 2.
• 3.
• 4.
• 5.
• 6.
• 7.
• 8.
• 9.
• 10.
• 11.

public boolean replace(K key, V oldValue, V newValue) {
	if (key == null || oldValue == null || newValue == null)
		throw new NullPointerException();
	for (;;) {
		Node<K,V> n; V v;
		if ((n = findNode(key)) == null)
			return false;
		if ((v = n.val) != null) {
			if (!oldValue.equals(v))
				return false;
			if (VAL.compareAndSet(n, v, newValue))
				return true;
		}
	}
}

• 1.
• 2.
• 3.
• 4.
• 5.
• 6.
• 7.
• 8.
• 9.
• 10.
• 11.
• 12.
• 13.
• 14.
• 15.

public boolean containsValue(Object value) {
	if (value == null)
		throw new NullPointerException();
	Node<K,V> b, n; V v;
	if ((b = baseHead()) != null) {
		while ((n = b.next) != null) {
			if ((v = n.val) != null && value.equals(v))
				return true;
		else
				b = n;
		}
	}
	return false;
}

• 1.
• 2.
• 3.
• 4.
• 5.
• 6.
• 7.
• 8.
• 9.
• 10.
• 11.
• 12.
• 13.
• 14.

public int size() {
	long c;
	return ((baseHead() == null) ? 0 : ((c = getAdderCount()) >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) c);
}

• 1.
• 2.
• 3.
• 4.

final long getAdderCount() {
    LongAdder a; long c;
    do {} while ((a = adder) == null && !ADDER.compareAndSet(this, null, a = new LongAdder()));
    return ((c = a.sum()) <= 0L) ? 0L : c; // ignore transient negatives
}

• 1.
• 2.
• 3.
• 4.
• 5.

public abstract class MultiLevelSkipListReader implements Closeable {
	/** the maximum number of skip levels possible for this index */
	protected int maxNumberOfSkipLevels;

	/** number of levels in this skip list */
	protected int numberOfSkipLevels;
	
	private int docCount;
	
	/** skipStream for each level. */
	private IndexInput[] skipStream;
	
	/** The start pointer of each skip level. */
	private long[] skipPointer;
	
	/** skipInterval of each level. */
	private int[] skipInterval;
	
	/**
	 * Number of docs skipped per level. It's possible for some values to overflow a signed int, but this has been accounted for.
	 */
	private int[] numSkipped;
	
	/** Doc id of current skip entry per level. */
	protected int[] skipDoc;
	
	/** Doc id of last read skip entry with docId <= target. */
	private int lastDoc;
	
	/** Child pointer of current skip entry per level. */
	private long[] childPointer;
	
	/** childPointer of last read skip entry with docId <= target. */
	private long lastChildPointer;
	
	private final int skipMultiplier;
}

• 1.
• 2.
• 3.
• 4.
• 5.
• 6.
• 7.
• 8.
• 9.
• 10.
• 11.
• 12.
• 13.
• 14.
• 15.
• 16.
• 17.
• 18.
• 19.
• 20.
• 21.
• 22.
• 23.
• 24.
• 25.
• 26.
• 27.
• 28.
• 29.
• 30.
• 31.
• 32.
• 33.
• 34.
• 35.
• 36.
• 37.