Java多线程（四）之ConcurrentSkipListMap深入分析 - JAVA

作相似
for (;;) {
if (n != null) {
Node f = n.next;
if (n != b.next) // 前后值不一致的情况下，跳转到第一层循环重新获得b和n
break;;
Object v = n.value;
if (v == null) { // n被delete的情况下
n.helpDelete(b, f);
break;
}
if (v == n || b.value == null) // b 被delete的情况，重新获取b和n
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 z = new Node(kkey, value, n);
if (!b.casNext(n, z))
break; // restart if lost race to append to b
int level = randomLevel();//得到一个随机的level作为该key-value插入的最高level
if (level > 0)
insertIndex(z, level);//进行插入操作
return null;
}
}
}

/**
* 获得一个随机的level值
*/
private int randomLevel() {
int x = randomSeed;
x ^= x << 13;
x ^= x >>> 17;
randomSeed = x ^= x << 5;
if ((x & 0x8001) != 0) // test highest and lowest bits
return 0;
int level = 1;
while (((x >>>= 1) & 1) != 0) ++level;

return level;
}
//执行插入操作：如上图所示，有两种可能的情况：
//1.当level存在时，对level<=n都执行insert操作
//2.当level不存在（大于目前的最大level）时，首先添加新的level，然后在执行操作1
private void insertIndex(Node z, int level) {
HeadIndex h = head;
int max = h.level;
if (level <= max) {//情况1
Index idx = null;
for (int i = 1; i <= level; ++i)//首先得到一个包含1~level个级别的down关系的链表，最后的inx为最高level
idx = new Index(z, idx, null);
addIndex(idx, h, level);//把最高level的idx传给addIndex方法
} else { // 情况2 增加一个新的级别
level = max + 1;
Index[] idxs = (Index[])new Index[level+1];
Index idx = null;
for (int i = 1; i <= level; ++i)//该步骤和情况1类似
idxs[i] = idx = new Index(z, idx, null);
HeadIndex oldh;
int k;
for (;;) {
oldh = head;
int oldLevel = oldh.level;
if (level <= oldLevel) { // lost race to add level
k = level;
break;
}
HeadIndex newh = oldh;
Node oldbase = oldh.node;
for (int j = oldLevel+1; j <= level; ++j)
newh = new HeadIndex(oldbase, newh, idxs[j], j);//创建新的
if (casHead(oldh, newh)) {
k = oldLevel;
break;
}
}
addIndex(idxs[k], oldh, k);
}
}
/**
*在1~indexlevel层中插入数据
*/
private void addIndex(Index idx, HeadIndex h, int indexLevel) {
// insertionLevel 代表要插入的level，该值会在indexLevel~1间遍历一遍
int insertionLevel = indexLevel;
Comparable< super K> key = comparable(idx.node.key);
if (key == null) throw new NullPointerException();
/

Java多线程（四）之ConcurrentSkipListMap深入分析(四)