findPredecessor
1560870538920.png
private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
if (key == null)
throw new NullPointerException(); // don't postpone errors
for (;;) {
// 从最上层的head开始，往右下方开始查找
for (Index<K,V> q = head, r = q.right, d;;) {
// 如果headindex的index存在
if (r != null) {
// 拿到index指定的node
Node<K,V> n = r.node;
K k = n.key;
// 如果index所引用的底层node是待删除的话
// 那么需要将r他的前驱节点q除关系，然后让p指向r的后继节点
if (n.value == null) {
if (!q.unlink(r))
break; // restart
r = q.right; // reread r
continue;
}
// 如果key要大于该index指向的node的key，那么继续往后移动，去跟该层的下一个index比较
if (cpr(cmp, key, k) > 0) {
q = r;
r = r.right;
continue;
}
}
// 到这里说明该level已经到最后了，要不就是key比下个index节点要小于或等于
// 那么这时候应该下沉到下一层继续往右找了，直到底层为止
if ((d = q.down) == null)
return q.node;
// 移动到下层headindex，继续往右找
q = d;
r = d.right;
}
}
}
doPut
1560925904531.png
private V doPut(K key, V value, boolean onlyIfAbsent) {
Node<K,V> z; // added node
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
outer: for (;;) {
// 从一开始，b和n的定义如下
// b称之为沿index往下能找到的离插入点最近的前驱节点
// n是b的后继节点
// 从全局来看，b是插入点的前驱节点，n是插入点的后继节点
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
// 如果b的后继不为空
// 换句话说，如果后继是空，说明已经到了底层的最后
if (n != null) {
Object v; int c;
// f是b的后继节点的后继节点
Node<K,V> f = n.next;
// 如果b的后继节点不再是n了，那么说明有别的线程更新了b的后继，那么再假定n是b的后继
// 就不成立了，那么退出内循环，再去找合适的前驱节点
if (n != b.next) // inconsistent read
break;
// 待删除 TODO
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
// 如果连b都被标记为待删除，那么可不得去重新去找合适的前驱节点么
if (b.value == null || v == n) // b is deleted
break;
// 正常来讲，key最好的情况是直接插到b和n之间
// 如果key比n节点大，那么继续向右查找最合适的插入点、
//
if ((c = cpr(cmp, key, n.key)) > 0) {
b = n;
n = f;
continue;
}
// 如果找到相同key的节点，说明是更新操作，那么cas更新value并返回更新后的值
if (c == 0) {
if (onlyIfAbsent || n.casValue(v, value)) {
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
// 如果更新失败，那么直接break，说明有竞争，重新来定位底层节点
break; // restart if lost race to replace value
}
// else c < 0; fall through
}
// 到这里，说明找到了插入点的前驱和后继节点
// 那么剩下来就是将新的节点加到b之后，n之前
// b -> z -> n
z = new Node<K,V>(key, value, n);
if (!b.casNext(n, z))
// 说明插入点有竞争，重走上面的流程，再找合适的插入点
break; // restart if lost race to append to b
// 插入成功，结束第一阶段工作，继续往下
break outer;
}
}
// 插入完成后，需要决定是否要增加层数
// 随机数
int rnd = ThreadLocalRandom.nextSecondarySeed();
// 随机数与1000 0000 0000 0000 0000 0000 0000 0001的结果是0
// 表示将只要0x80000001的最高位和最低位都是0，就满足一定概率进来进行index处理，否则不处理
if ((rnd & 0x80000001) == 0) { // test highest and lowest bits
int level = 1, max;
// 这里主要是看随机数从第二位开始，有多少个连续的1，记为本次的level数。
while (((rnd >>>= 1) & 1) != 0)
++level;
Index<K,V> idx = null;
HeadIndex<K,V> h = head;
// 如果本次计算的level数要小于现有的最大level的话，那么组装一个纵向的index列从level1到level
// 并指向底层的z节点
// 而最终的idx就代表最高level的Index节点，也就是纵向列表的最高level的节点
if (level <= (max = h.level)) {
for (int i = 1; i <= level; ++i)
idx = new Index<K,V>(z, idx, null);
}
// 如果说本次计算的level要大于当前最大的level数，新增一层
else { // try to grow by one level
level = max + 1; // hold in array and later pick the one to use
// 待定 TODO
@SuppressWarnings("unchecked")Index<K,V>[] idxs =
(Index<K,V>[])new Index<?,?>[level+1];
// 创建纵向的index列，指向底层z节点
// 而最终的idx就代表最高level的Index节点，也就是纵向列表的最高level的节点
// 而idxs列表就代表每个level对应位置的Index，跟idx相配合
for (int i = 1; i <= level; ++i)
idxs[i] = idx = new Index<K,V>(z, idx, null);
for (;;) {
h = head;
int oldLevel = h.level;
// 加入说新的level要小于或等于oldlevel
// 说明有其他线程也在新建level，有可能别人成功了，那么这里就没有继续自旋的必要了
if (level <= oldLevel) // lost race to add level
break;
HeadIndex<K,V> newh = h;
Node<K,V> oldbase = h.node;
for (int j = oldLevel+1; j <= level; ++j)
// 新建HeadIndex，down为oldHeadIndex
// right为上面的idxs的该层节点
newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
// cas更新headindex，如果失败，说明有竞争，且很可能别人会成功新增level。
// 那么重新自旋看看，是不是别人成功了，否则继续自旋，再尝试更新headindex
if (casHead(h, newh)) {
// 如果更新成功，首先先更新h
h = newh;
idx = idxs[level = oldLevel];
break;
}
}
}
// 从上面可知，idx就是待处理的位置，想想看，上面我们创建了纵队列，但是还没有跟横队列进行关联
// 除了新level外，因为创建新level的同时会关联该层的idx到headindex的right里面
// 而insertionLevel就是待处理的层数
// find insertion points and splice in
splice: for (int insertionLevel = level;;) {
int j = h.level;
// 从新的headindex开始，往右边移动
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;
// compare before deletion check avoids needing recheck
int c = cpr(cmp, key, n.key);
// 如果n是待删除，那么跳过，然后继续自旋
if (n.value == null) {
if (!q.unlink(r))
break;
r = q.right;
continue;
}
// 如果key比右节点要大，那么继续往右移动
if (c > 0) {
q = r;
r = r.right;
continue;
}
}
// 当自旋到待处理的level时
// 上面处理完，就是找到了合适的插入点，不然会继续自旋
if (j == insertionLevel) {
// 这里就插入节点q->t->r
// 如果link失败，那么说明有竞争，继续上面的自旋，找到合适的插入点再试
if (!q.link(r, t))
break; // restart
// 如果前面插入的新的t节点没了，那么继续也就没有意义了，直接break，插入结束
if (t.node.value == null) {
findNode(key);
break splice;
}
// 如果到底层了，结束处理
if (--insertionLevel == 0)
break splice;
}
// 从上往下处理，继续沿纵向往下处理，将新的index跟当前level的前驱和后继节点进行插入
if (--j >= insertionLevel && j < level)
t = t.down;
q = q.down;
r = q.right;
}
}
}
return null;
}
doGet
private V doGet(Object key) {
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
outer: for (;;) {
// 沿index找到底层key的前驱节点
// b是前驱节点
// n是后继节点
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
Object v; int c;
if (n == null)
break outer;
// f是n的后继节点
Node<K,V> f = n.next;
if (n != b.next) // inconsistent read
break;
// 如果n的value为空，那么n是待删除节点
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b is deleted
break;
// 找到key对应的节点，那么直接返回
if ((c = cpr(cmp, key, n.key)) == 0) {
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
// 如果往右查找的结果是比当前节点的key小，那么说明找不到对应的key，直接返回null
if (c < 0)
break outer;
// 到这里，说明还得继续往右查找
b = n;
n = f;
}
}
return null;
}
doRemove
final V doRemove(Object key, Object value) {
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
outer: for (;;) {
// 沿index往右下找到离key最近的前驱节点
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
Object v; int c;
if (n == null)
break outer;
Node<K,V> f = n.next;
if (n != b.next) // inconsistent read
break;
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b is deleted
break;
//正常情况下，key 应该等于 n.key
//key 大于 n.key 说明我们要找的结点可能在 n 的后面，往右移动即可
//key 小于 n.key 说明 key 所代表的结点根本不存在
if ((c = cpr(cmp, key, n.key)) < 0)
break outer;
if (c > 0) {
b = n;
n = f;
continue;
}
//如果删除是根据键和值两个参数来删除的话，value 是不为 null 的
//这种情况下，如果 n 的 value 属性不等于我们传入的 value ，那么是不进行删除的
if (value != null && !value.equals(v))
break outer;
// 一般说来，最好的情况是n就是待删除的节点，到这里说明n就是待删除的点
// 1. 将待删除节点的value设置为null
if (!n.casValue(v, null))
break;
// 而f是n的后继节点
// 2. appendMarker的意义在于在n和f之间添加一个Marker(key=null,value=n,next=f)
// 然后将b的next直接指向f，这两步全部成功才会继续往下，否则会去findNode
// 而findnode会再次重试设置market且将b指向f
if (!n.appendMarker(f) || !b.casNext(n, f))
findNode(key); // retry via findNode
else {
// 这里findPredecessor的意义在于上面设置了底层的待删除节点会影响到上层的index
// 如果index没人引用该node还好，不用处理
// 如果引用的话，那么还需要去删除对应index层的节点
findPredecessor(key, cmp); // clean index
if (head.right == null)
tryReduceLevel();
}
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
}
return null;
}
helpDelete
// 这个方法的意义是看this的后继是不是market节点，如果是，那么直接将b的后继指向market的next
// 如果不是的话，新建market节点为b的后继
// 而market节点的意义在于如果某节点后跟market，说明n->market->f的关系固定了
void helpDelete(Node<K,V> b, Node<K,V> f) {
/*
* Rechecking links and then doing only one of the
* help-out stages per call tends to minimize CAS
* interference among helping threads.
*/
// b是this的前驱，f是this的后继
// 而如果this是待删除节点的话，那么f很可能是marker节点
if (f == next && this == b.next) {
// 不明白为什么是f.value != f，如果是market节点，条件不应该是f.value!=this么？
// 求解答
if (f == null || f.value != f) // not already marked
casNext(f, new Node<K,V>(f));
else
b.casNext(this, f.next);
}
}
