Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8066070

PriorityQueue corrupted when adding non-Comparable

    XMLWordPrintable

Details

    Description

      FULL PRODUCT VERSION :
        Java 1.8.0_25

      ADDITIONAL OS VERSION INFORMATION :
        Windows 8

      A DESCRIPTION OF THE PROBLEM :
        If you add a non-comparable object to PriorityQueue it adds the first one, but any other objects throw an exception - but the size increases and a null object is inserted. Which can cause problems if the queue.poll() is called as a NPE occurs.

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
        Size is 0
      ACTUAL -
        NullPointerException

      ERROR MESSAGES/STACK TRACES THAT OCCUR :
        java.lang.NullPointerException
            at java.util.PriorityQueue.siftDownComparable(Unknown Source)
            at java.util.PriorityQueue.siftDown(Unknown Source)
            at java.util.PriorityQueue.poll(Unknown Source)

      REPRODUCIBILITY :
        This bug can be reproduced always.

      ---------- BEGIN SOURCE ----------
          public class NonComparableTest {
              public static void main(String[] args) {
                  PriorityQueue<Person> pq = new PriorityQueue<>();
                      for (int i=0; i<5; i++) {
                          try {
                              pq.add(new Person());
                          } catch(Exception ignored) { }
                      }
                      pq.poll();
                      System.out.println("The size is " + pq.size());
                      for (Iterator<Person> it = pq.iterator(); it.hasNext();) {
                          System.out.println(it.next());
                      }
              }
          }

          class Person { }
      ---------- END SOURCE ----------

      CUSTOMER SUBMITTED WORKAROUND :
          public boolean offer(E e) {
              if (e == null)
                  throw new NullPointerException();
              modCount++;
              int i = size;
              if (i >= queue.length)
                  grow(i + 1);
              
              if (i == 0)
                  queue[0] = e;
              else
                  siftUp(i+1, e);
              size = i + 1; // ONly increase size after adding to queue
              return true;
          }

      Attachments

        Issue Links

          Activity

            People

              martin Martin Buchholz
              webbuggrp Webbug Group
              Votes:
              0 Vote for this issue
              Watchers:
              10 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: