ConcurrentLinkedQueue
非阻塞队列
采用先进先出的规则。
采用链表实现,由头节点和尾节点组成
当插入元素时,不会加锁,因此不会阻塞,当时会有一个死循环,直到插入成功,遍历链表,找到队尾,将元素插入
采用cas算法
public boolean offer(E e) { if (e == null) throw new NullPointerException(); //入队前,创建一个入队节点 Node</e><e> n = new Node</e><e>(e); retry: //死循环,入队不成功反复入队。 for (;;) { //创建一个指向tail节点的引用 Node</e><e> t = tail; //p用来表示队列的尾节点,默认情况下等于tail节点。 Node</e><e> p = t; for (int hops = 0; ; hops++) { //获得p节点的下一个节点。 Node</e><e> next = succ(p); //next节点不为空,说明p不是尾节点,需要更新p后在将它指向next节点 if (next != null) { //循环了两次及其以上,并且当前节点还是不等于尾节点 if (hops > HOPS && t != tail) continue retry; p = next; } //如果p是尾节点,则设置p节点的next节点为入队节点。 else if (p.casNext(null, n)) { //如果tail节点有大于等于1个next节点,则将入队节点设置成tair节点,更新失败了也没关系,因为失败了表示有其他线程成功更新了tair节点。 if (hops >= HOPS) casTail(t, n); // 更新tail节点,允许失败 return true; } // p有next节点,表示p的next节点是尾节点,则重新设置p节点 else { p = succ(p); } } } }
出队列时:
public E poll() { Node</e><e> h = head; // p表示头节点,需要出队的节点 Node</e><e> p = h; for (int hops = 0;; hops++) { // 获取p节点的元素 E item = p.getItem(); // 如果p节点的元素不为空,使用CAS设置p节点引用的元素为null,如果成功则返回p节点的元素。 if (item != null && p.casItem(item, null)) { if (hops >= HOPS) { //将p节点下一个节点设置成head节点 Node</e><e> q = p.getNext(); updateHead(h, (q != null) ? q : p); } return item; } // 如果头节点的元素为空或头节点发生了变化,这说明头节点已经被另外一个线程修改了。那么获取p节点的下一个节点 Node</e><e> next = succ(p); // 如果p的下一个节点也为空,说明这个队列已经空了 if (next == null) { // 更新头节点。 updateHead(h, p); break; } // 如果下一个元素不为空,则将头节点的下一个节点设置成头节点 p = next; } return null; }