ConcurrentLinkedQueue有两个指针属性:head和tail,方便快速定位到当前线程认为的头节点和尾节点。
ConcurrentLinkedQueue的特性允许tail指针指向的不是最新的尾节点(高并发操作下要保证tail指针的同步,会影响性能吧?)
因为tail指针不能保证正确的同步,所以判断尾节点的方式是 node.next == null
出队poll操作
一般情况下,找到头一个非null的节点p,将节点p的内容获取后置null。
从源代码可以看出,更新head到p的下一个节点,不是每次都会做的。当头节点p的内容不是null,出队后,p的内容变成null,但head还是指向p的;只有当下一次出队,p已经是null的前提下,才会将p.next出队并置null,然后将head指向p.next的next。
满足上述head指针需要更新的条件下,将head指向出队节点p的下一个节点。此时,原来的头节点p的next是指向p本身,成为哨兵节点。(理论上,ConcurrentLinkedQueue的删除节点操作,都会把该节点设置成哨兵节点吧?)
updateHead 更新头节点的方法
1.先判断原来的头节点和要更新成头节点的节点是不是同一个
2.head指针指向新的节点
3.原来头节点没用了,next指向本身,变成哨兵节点
在高并发的场景下,在迭代节点过程中可能会指向哨兵节点,ConcurrentLikedQueue的策略就是重新从head指针开始迭代。
入队offer操作
casTail更新tail指针,比更新head指针的逻辑简单多了。更新head指针除了要移动head指针外,还需要将原head节点失效,设置成哨兵节点,而tail指针不需要后面一步。
在迭代寻找尾节点的时候,查到哨兵节点的时候,会先判断tail指针是不是已经被别的线程更新过了,如果更新过就从该tail开始迭代,很有可能该tail指针是正确指向尾节点的。如果没有被更新过,就从head的位置开始迭代。