LinkedBlockingDeque

电玩女神 2022-09-05 15:54 97阅读 0赞

#### BlockingDeque ####

BlockingDeque定义了一个双端队列

public interface BlockingDeque<E> extends BlockingQueue<E>, Deque<E> {
        
        void putFirst(E e) throws InterruptedException;
        void putLast(E e) throws InterruptedException;
        E takeFirst() throws InterruptedException;
        E takeLast() throws InterruptedException;
    	// ...
    }

BlockingDeque只有一个实现类LinkedBlockingDeque

public class LinkedBlockingDeque<E> extends AbstractQueue<E> implements
    BlockingDeque<E>, java.io.Serializable {
        
        static final class Node<E> {
        
            E item;
    		Node<E> prev;   // 前一个node
    		Node<E> next;	//后一个node
    		Node(E x) {
        
                item = x;
    		} 
    	}
    	transient Node<E> first; // 队列头
    	transient Node<E> last;  // 队列尾
    	private transient int count; // 元素个数 
    	private final int capacity; // 容量
    	// 一把锁+两个条件
    	final ReentrantLock lock = new ReentrantLock(); 
    	private final Condition notEmpty = lock.netCondition(); 
    	private final Condition notFull = lock.newCondition(); 
    	// ...
    }

take实现

public E takeFirst() throws InterruptedException {
        
        final ReentrantLock lock = this.lock;
        //获得锁
        lock.lock();
        try {
        
            E x;
            while ( (x = unlinkFirst()) == null)
            	//取不出来阻塞
                notEmpty.await();
            return x;
        } finally {
        
            lock.unlock();
        }
    }
    
    private E unlinkFirst() {
        
        // assert lock.isHeldByCurrentThread();
        //拿到第一个元素
        Node<E> f = first;
        if (f == null)
            return null;
        //拿到第二个个元素
        Node<E> n = f.next;
        E item = f.item;
        //清空第一个元素的item
        f.item = null;
        //自己指向自己，即没有被别的node引用，就会被垃圾回收
        f.next = f; // help GC
        //把第二个元素设置成first
        first = n;
        if (n == null)
            last = null;
        else
            n.prev = null;
        --count;
        //通知生产者生产
        notFull.signal();
        return item;
    }
    
    public E takeLast() throws InterruptedException {
        
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
        
            E x;
            //unlinkLast()和unlinkFirst()类似
            while ( (x = unlinkLast()) == null)
                notEmpty.await();
            return x;
        } finally {
        
            lock.unlock();
        }
    }
    
    private E unlinkLast() {
        
        // assert lock.isHeldByCurrentThread();
        //拿到最后一个node并把它移除链表
        Node<E> l = last;
        if (l == null)
            return null;
        Node<E> p = l.prev;
        E item = l.item;
        l.item = null;
        l.prev = l; // help GC
        last = p;
        if (p == null)
            first = null;
        else
            p.next = null;
        --count;
        notFull.signal();
        return item;
    }

put实现

public void putFirst(E e) throws InterruptedException {
        
        if (e == null) throw new NullPointerException();
        //创建节点
        Node<E> node = new Node<E>(e);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
        
        	//加入链表第一个
            while (!linkFirst(node))
            	//放不进去阻塞
                notFull.await();
        } finally {
        
            lock.unlock();
        }
    }
    
    private boolean linkFirst(Node<E> node) {
        
        // assert lock.isHeldByCurrentThread();
        //如果数量达到容量的大小，则不能加入
        if (count >= capacity)
            return false;
        //获得第一个node
        Node<E> f = first;
        //把元素插入到原first之前
        node.next = f;
        //把插入的元素设置成新的first
        first = node;
        //如果本来就是空的设置node即是第一个也是最后一个
        if (last == null)
            last = node;
        else
        	//原first的前一个元素设置为插入的元素
            f.prev = node;
        ++count;
        //通知消费者消费
        notEmpty.signal();
        return true;
    }
    
    public void putLast(E e) throws InterruptedException {
        
        if (e == null) throw new NullPointerException();
        Node<E> node = new Node<E>(e);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
        
        	//加入链表最后一个
            while (!linkLast(node))
            	//放不进去阻塞
                notFull.await();
        } finally {
        
            lock.unlock();
        }
    }
    
    //同linkFirst类似
    private boolean linkLast(Node<E> node) {
        
        // assert lock.isHeldByCurrentThread();
        if (count >= capacity)
            return false;
        Node<E> l = last;
        node.prev = l;
        last = node;
        if (first == null)
            first = node;
        else
            l.next = node;
        ++count;
        notEmpty.signal();
        return true;
    }