src/share/classes/java/util/concurrent/PriorityBlockingQueue.java

Print this page




  77  *     seqNum = seq.getAndIncrement();
  78  *     this.entry = entry;
  79  *   }
  80  *   public E getEntry() { return entry; }
  81  *   public int compareTo(FIFOEntry<E> other) {
  82  *     int res = entry.compareTo(other.entry);
  83  *     if (res == 0 && other.entry != this.entry)
  84  *       res = (seqNum < other.seqNum ? -1 : 1);
  85  *     return res;
  86  *   }
  87  * }}</pre>
  88  *
  89  * <p>This class is a member of the
  90  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  91  * Java Collections Framework</a>.
  92  *
  93  * @since 1.5
  94  * @author Doug Lea
  95  * @param <E> the type of elements held in this collection
  96  */

  97 public class PriorityBlockingQueue<E> extends AbstractQueue<E>
  98     implements BlockingQueue<E>, java.io.Serializable {
  99     private static final long serialVersionUID = 5595510919245408276L;
 100 
 101     /*
 102      * The implementation uses an array-based binary heap, with public
 103      * operations protected with a single lock. However, allocation
 104      * during resizing uses a simple spinlock (used only while not
 105      * holding main lock) in order to allow takes to operate
 106      * concurrently with allocation.  This avoids repeated
 107      * postponement of waiting consumers and consequent element
 108      * build-up. The need to back away from lock during allocation
 109      * makes it impossible to simply wrap delegated
 110      * java.util.PriorityQueue operations within a lock, as was done
 111      * in a previous version of this class. To maintain
 112      * interoperability, a plain PriorityQueue is still used during
 113      * serialization, which maintains compatibility at the espense of
 114      * transiently doubling overhead.
 115      */
 116 


 151     /**
 152      * Lock used for all public operations
 153      */
 154     private final ReentrantLock lock;
 155 
 156     /**
 157      * Condition for blocking when empty
 158      */
 159     private final Condition notEmpty;
 160 
 161     /**
 162      * Spinlock for allocation, acquired via CAS.
 163      */
 164     private transient volatile int allocationSpinLock;
 165 
 166     /**
 167      * A plain PriorityQueue used only for serialization,
 168      * to maintain compatibility with previous versions
 169      * of this class. Non-null only during serialization/deserialization.
 170      */
 171     private PriorityQueue q;
 172 
 173     /**
 174      * Creates a {@code PriorityBlockingQueue} with the default
 175      * initial capacity (11) that orders its elements according to
 176      * their {@linkplain Comparable natural ordering}.
 177      */
 178     public PriorityBlockingQueue() {
 179         this(DEFAULT_INITIAL_CAPACITY, null);
 180     }
 181 
 182     /**
 183      * Creates a {@code PriorityBlockingQueue} with the specified
 184      * initial capacity that orders its elements according to their
 185      * {@linkplain Comparable natural ordering}.
 186      *
 187      * @param initialCapacity the initial capacity for this priority queue
 188      * @throws IllegalArgumentException if {@code initialCapacity} is less
 189      *         than 1
 190      */
 191     public PriorityBlockingQueue(int initialCapacity) {


 951      * @param s the stream
 952      */
 953     private void readObject(java.io.ObjectInputStream s)
 954         throws java.io.IOException, ClassNotFoundException {
 955         try {
 956             s.defaultReadObject();
 957             this.queue = new Object[q.size()];
 958             comparator = q.comparator();
 959             addAll(q);
 960         } finally {
 961             q = null;
 962         }
 963     }
 964 
 965     // Unsafe mechanics
 966     private static final sun.misc.Unsafe UNSAFE;
 967     private static final long allocationSpinLockOffset;
 968     static {
 969         try {
 970             UNSAFE = sun.misc.Unsafe.getUnsafe();
 971             Class k = PriorityBlockingQueue.class;
 972             allocationSpinLockOffset = UNSAFE.objectFieldOffset
 973                 (k.getDeclaredField("allocationSpinLock"));
 974         } catch (Exception e) {
 975             throw new Error(e);
 976         }
 977     }
 978 }


  77  *     seqNum = seq.getAndIncrement();
  78  *     this.entry = entry;
  79  *   }
  80  *   public E getEntry() { return entry; }
  81  *   public int compareTo(FIFOEntry<E> other) {
  82  *     int res = entry.compareTo(other.entry);
  83  *     if (res == 0 && other.entry != this.entry)
  84  *       res = (seqNum < other.seqNum ? -1 : 1);
  85  *     return res;
  86  *   }
  87  * }}</pre>
  88  *
  89  * <p>This class is a member of the
  90  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  91  * Java Collections Framework</a>.
  92  *
  93  * @since 1.5
  94  * @author Doug Lea
  95  * @param <E> the type of elements held in this collection
  96  */
  97 @SuppressWarnings("unchecked")
  98 public class PriorityBlockingQueue<E> extends AbstractQueue<E>
  99     implements BlockingQueue<E>, java.io.Serializable {
 100     private static final long serialVersionUID = 5595510919245408276L;
 101 
 102     /*
 103      * The implementation uses an array-based binary heap, with public
 104      * operations protected with a single lock. However, allocation
 105      * during resizing uses a simple spinlock (used only while not
 106      * holding main lock) in order to allow takes to operate
 107      * concurrently with allocation.  This avoids repeated
 108      * postponement of waiting consumers and consequent element
 109      * build-up. The need to back away from lock during allocation
 110      * makes it impossible to simply wrap delegated
 111      * java.util.PriorityQueue operations within a lock, as was done
 112      * in a previous version of this class. To maintain
 113      * interoperability, a plain PriorityQueue is still used during
 114      * serialization, which maintains compatibility at the espense of
 115      * transiently doubling overhead.
 116      */
 117 


 152     /**
 153      * Lock used for all public operations
 154      */
 155     private final ReentrantLock lock;
 156 
 157     /**
 158      * Condition for blocking when empty
 159      */
 160     private final Condition notEmpty;
 161 
 162     /**
 163      * Spinlock for allocation, acquired via CAS.
 164      */
 165     private transient volatile int allocationSpinLock;
 166 
 167     /**
 168      * A plain PriorityQueue used only for serialization,
 169      * to maintain compatibility with previous versions
 170      * of this class. Non-null only during serialization/deserialization.
 171      */
 172     private PriorityQueue<E> q;
 173 
 174     /**
 175      * Creates a {@code PriorityBlockingQueue} with the default
 176      * initial capacity (11) that orders its elements according to
 177      * their {@linkplain Comparable natural ordering}.
 178      */
 179     public PriorityBlockingQueue() {
 180         this(DEFAULT_INITIAL_CAPACITY, null);
 181     }
 182 
 183     /**
 184      * Creates a {@code PriorityBlockingQueue} with the specified
 185      * initial capacity that orders its elements according to their
 186      * {@linkplain Comparable natural ordering}.
 187      *
 188      * @param initialCapacity the initial capacity for this priority queue
 189      * @throws IllegalArgumentException if {@code initialCapacity} is less
 190      *         than 1
 191      */
 192     public PriorityBlockingQueue(int initialCapacity) {


 952      * @param s the stream
 953      */
 954     private void readObject(java.io.ObjectInputStream s)
 955         throws java.io.IOException, ClassNotFoundException {
 956         try {
 957             s.defaultReadObject();
 958             this.queue = new Object[q.size()];
 959             comparator = q.comparator();
 960             addAll(q);
 961         } finally {
 962             q = null;
 963         }
 964     }
 965 
 966     // Unsafe mechanics
 967     private static final sun.misc.Unsafe UNSAFE;
 968     private static final long allocationSpinLockOffset;
 969     static {
 970         try {
 971             UNSAFE = sun.misc.Unsafe.getUnsafe();
 972             Class<?> k = PriorityBlockingQueue.class;
 973             allocationSpinLockOffset = UNSAFE.objectFieldOffset
 974                 (k.getDeclaredField("allocationSpinLock"));
 975         } catch (Exception e) {
 976             throw new Error(e);
 977         }
 978     }
 979 }