David, Of course you're right. I didn't realize that the hole was one-element nulls.
(Why is software always 10 times harder than you'd think?) Updated webrev, with lots more tests for corner cases. I still need a bug filed in bugtraq. Martin On Thu, May 6, 2010 at 16:53, David Holmes <david.hol...@oracle.com> wrote: > Hi Martin, > > Martin Buchholz said the following on 05/07/10 09:13: >> >> On Thu, May 6, 2010 at 15:58, David Holmes <david.hol...@oracle.com> >> wrote: >>>> >>>> Fix: >>>> >>>> >>>> http://cr.openjdk.java.net/~martin/webrevs/openjdk7/PriorityQueueConstructor/ >>> >>> I'm not sure this is necessarily the right fix. It seems to me that >>> incidental nulls will be caught in many/most cases by the sorting code >>> for >>> collections assumed to contain Comparable's. >> >> The comparator might accept nulls. > > True but a Comparator is only used if the Collection is a SortedSet or a > PriorityQueue. For any other Collection the elements must implement > Comparable and the code in: > > private void siftDownComparable(int k, E x) { > Comparable<? super E> key = (Comparable<? super E>)x; > int half = size >>> 1; // loop while a non-leaf > while (k < half) { > int child = (k << 1) + 1; // assume left child is least > Object c = queue[child]; > int right = child + 1; > if (right < size && > ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) > c = queue[child = right]; > if (key.compareTo((E) c) <= 0) > break; > queue[k] = c; > k = child; > } > queue[k] = key; > } > > will throw NPE at key.compareTo if the item is null. (There's probably a > missed case where the collection contains only a null element). > >> But even if it doesn't, it is possible to create a "corrupted" PQ >> using the PQ(collection) constructor, and we don't allow >> that sort of thing in java.util. > > But that's the hole we're fixing now. > >>> And we don't need to check when >>> filling from an existing PriorityQueue. >> >> Strictly speaking, the source PriorityQueue might be a subclass that >> has been modified to accept nulls. > > Yes I suppose. So we could change from an instanceof test to a getClass() > test. > >> But yes, we could have a version of the fix that only checks for nulls >> if the source is not a PQ. >> >>> So is it only the case for filling >>> from a SortedSet that needs the explicit null check? >> >> The source can be an arbitrary Collection. > > But as noted above for anything other than a SortedSet (or corrupt PQ) the > sorting code will already catch nulls. > > Cheers, > David > >> Martin >> >>> David >>> >
