ConcurrentLinkedDeque--未完成

1、简介

1.1 介绍

基于链接节点的无界并发deque 。 并发插入，删除和访问操作可以跨多个线程安全执行。 A ConcurrentLinkedDeque是许多线程将共享对公共集合的访问的适当选择。 像大多数其他并发集合实现一样，此类不允许使用null元素。 这是一个双向链表 size方法不是一个准确的操作

1.2 构造

//构造一个空的构造。 ConcurrentLinkedDeque() //构造最初包含给定集合的元素的deque，以集合的迭代器的遍历顺序添加。 ConcurrentLinkedDeque(Collection<? extends E> c)

1.3 继承

java.lang.Object java.util.AbstractCollection<E> java.util.concurrent.ConcurrentLinkedDeque<E>

1.4 主要方法

boolean add(E e) //在此deque的尾部插入指定的元素。 boolean addAll(Collection<? extends E> c) //按指定集合的迭代器返回的顺序将指定集合中的所有元素追加到该deque的末尾。 void addFirst(E e) //在此deque前面插入指定的元素。 void addLast(E e) //在此deque的末尾插入指定的元素。 void clear() //从这个deque中删除所有的元素。 boolean contains(Object o) //返回 true如果这个deque包含至少一个元素 e ，这样 o.equals(e) 。 E element() //检索但不删除由此deque表示的队列的头部（换句话说，该deque的第一个元素）。 E getFirst() //检索，但不删除，这个deque的第一个元素。 E getLast() //检索，但不删除，这个deque的最后一个元素。 boolean offer(E e) //在此deque的尾部插入指定的元素。 boolean offerFirst(E e) //在此deque前面插入指定的元素。 boolean offerLast(E e) //在此deque的末尾插入指定的元素。 E peek() //检索但不删除由此deque表示的队列的头（换句话说，该deque的第一个元素），如果此deque为空，则返回 null 。 E peekFirst() //检索但不删除此deque的第一个元素，如果此deque为空，则返回 null 。 E peekLast() //检索但不删除此deque的最后一个元素，如果此deque为空，则返回 null 。 E poll() //检索并删除由此deque表示的队列的头部（换句话说，该deque的第一个元素），如果此deque为空，则返回 null 。 E pollFirst() //检索并删除此deque的第一个元素，如果此deque为空，则返回 null 。 E pollLast() //检索并删除此deque的最后一个元素，如果此deque为空，则返回 null 。 E pop() //从这个deque表示的堆栈中弹出一个元素。 void push(E e) //将元素推送到由此deque代表的堆栈（换句话说，在该deque的头部），如果可以立即执行，而不违反容量限制，则抛出 IllegalStateException如果当前没有可用空间）。 E remove() //检索并删除由此deque表示的队列的头（换句话说，该deque的第一个元素）。 boolean remove(Object o) //删除第一个元素 e ，使 o.equals(e) ，如果这样一个元素存在于这个deque。 E removeFirst() //检索并删除此deque的第一个元素。 boolean removeFirstOccurrence(Object o) //删除第一个元素 e ，使 o.equals(e) ，如果这样一个元素存在于这个deque。 E removeLast() //检索并删除此deque的最后一个元素。 boolean removeLastOccurrence(Object o) //删除最后一个元素 e ，使 o.equals(e) ，如果这样的元素存在于这个deque。

2、源代码

public class ConcurrentLinkedDeque<E> extends AbstractCollection<E> implements Deque<E>, java.io.Serializable { //头节点 private transient volatile Node<E> head; //尾节点 private transient volatile Node<E> tail; //节点类 static final class Node<E> { //双向 volatile Node<E> prev; volatile E item; volatile Node<E> next; Node() { // default constructor for NEXT_TERMINATOR, PREV_TERMINATOR } /** * Constructs a new node. Uses relaxed write because item can * only be seen after publication via casNext or casPrev. */ Node(E item) { UNSAFE.putObject(this, itemOffset, item); } boolean casItem(E cmp, E val) { return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val); } //设置next节点 void lazySetNext(Node<E> val) { UNSAFE.putOrderedObject(this, nextOffset, val); } //替换next节点 boolean casNext(Node<E> cmp, Node<E> val) { return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val); } void lazySetPrev(Node<E> val) { UNSAFE.putOrderedObject(this, prevOffset, val); } boolean casPrev(Node<E> cmp, Node<E> val) { return UNSAFE.compareAndSwapObject(this, prevOffset, cmp, val); } // Unsafe mechanics private static final sun.misc.Unsafe UNSAFE; private static final long prevOffset; private static final long itemOffset; private static final long nextOffset; static { try { UNSAFE = sun.misc.Unsafe.getUnsafe(); Class<?> k = Node.class; prevOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("prev")); itemOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("item")); nextOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("next")); } catch (Exception e) { throw new Error(e); } } } //插入头元素 private void linkFirst(E e) { checkNotNull(e); //新建节点 final Node<E> newNode = new Node<E>(e); restartFromHead: for (;;) for (Node<E> h = head, p = h, q;;) { if ((q = p.prev) != null && (q = (p = q).prev) != null) // Check for head updates every other hop. // If p == q, we are sure to follow head instead. p = (h != (h = head)) ? h : q; else if (p.next == p) // PREV_TERMINATOR continue restartFromHead; else { // p is first node //将p添加到队列头 newNode.lazySetNext(p); // CAS piggyback if (p.casPrev(null, newNode)) { // Successful CAS is the linearization point // for e to become an element of this deque, // and for newNode to become "live". if (p != h) // hop two nodes at a time //将head赋给newNode casHead(h, newNode); // Failure is OK. return; } // Lost CAS race to another thread; re-read prev } } } //添加到队列尾 private void linkLast(E e) { checkNotNull(e); final Node<E> newNode = new Node<E>(e); restartFromTail: for (;;) for (Node<E> t = tail, p = t, q;;) { if ((q = p.next) != null && (q = (p = q).next) != null) // Check for tail updates every other hop. // If p == q, we are sure to follow tail instead. p = (t != (t = tail)) ? t : q; else if (p.prev == p) // NEXT_TERMINATOR continue restartFromTail; else { // p is last node newNode.lazySetPrev(p); // CAS piggyback if (p.casNext(null, newNode)) { // Successful CAS is the linearization point // for e to become an element of this deque, // and for newNode to become "live". if (p != t) // hop two nodes at a time casTail(t, newNode); // Failure is OK. return; } // Lost CAS race to another thread; re-read next } } } }