Somewhere in this constructor of PriorityBlockingQueue is hard to understand

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Somewhere in this constructor of PriorityBlockingQueue is hard to understand

JSR166 Concurrency mailing list
In this constructor of PriorityBlockingQueue, some codes are hard to understand.

    public PriorityBlockingQueue(Collection<? extends E> c) {
        this.lock = new ReentrantLock();
        this.notEmpty = lock.newCondition();
        boolean heapify = true; // true if not known to be in heap order
        boolean screen = true;  // true if must screen for nulls
        if (c instanceof SortedSet<?>) {
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();
            heapify = false;
        }
        else if (c instanceof PriorityBlockingQueue<?>) {
            PriorityBlockingQueue<? extends E> pq =
                (PriorityBlockingQueue<? extends E>) c;
            this.comparator = (Comparator<? super E>) pq.comparator();
            screen = false;
            if (pq.getClass() == PriorityBlockingQueue.class) // first one
                heapify = false;
        }
        Object[] a = c.toArray();
        int n = a.length;
       
        if (a.getClass() != Object[].class)  // second one
            a = Arrays.copyOf(a, n, Object[].class);
        if (screen && (n == 1 || this.comparator != null)) {  //third one
            for (int i = 0; i < n; ++i)
                if (a[i] == null)
                    throw new NullPointerException();
        }
        this.queue = a;
        this.size = n;
        if (heapify)
            heapify();
    }

1. When "pq.getClass() == PriorityBlockingQueue.classExpression holds, 
    Then heapify operation is not need to do. Isn't "c instanceof PriorityBlockingQueue<?>
    enough to decide?

2. Why must make the actual type of array is Object[].class?

3. I just don't understand  this "&& (n == 1 || this.comparator != null)". Why is it written like this?

this constructor of PriorityBlockingQueue is same.



--------------------------------------------------------------------------------
Regards
Liu

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Somewhere in this constructor of PriorityBlockingQueue is hard to understand

JSR166 Concurrency mailing list
Liu,

1. Instanceof allows subclasses which could be coded to break the assumptions.  GetClass means this exact implementation for which the source code is known.
2. Collection.toArray() requires type Object[] but sometimes implementations are broken.  See: https://bugs.openjdk.java.net/browse/JDK-6260652 and https://bugs.openjdk.java.net/browse/JDK-8160406
3. PQ must not contain nulls.  If there is a comparator and the collection was not exactly of type PQ then that collection may contain null which needs to be screened.  If the size is one then the collection may contain null because it may not have been checked against another element (including itself). See: https://bugs.openjdk.java.net/browse/JDK-5045147  If the size is greater than one and there is no comparator heapify() will catch the null element.

Jason


________________________________________
From: Concurrency-interest <[hidden email]> on behalf of Liu via Concurrency-interest <[hidden email]>
Sent: Tuesday, August 4, 2020 7:10 AM
To: Concurrency-interest
Subject: [concurrency-interest] Somewhere in this constructor of PriorityBlockingQueue is hard to understand

In this constructor of PriorityBlockingQueue, some codes are hard to understand.

    public PriorityBlockingQueue(Collection<? extends E> c) {
        this.lock = new ReentrantLock();
        this.notEmpty = lock.newCondition();
        boolean heapify = true; // true if not known to be in heap order
        boolean screen = true;  // true if must screen for nulls
        if (c instanceof SortedSet<?>) {
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();
            heapify = false;
        }
        else if (c instanceof PriorityBlockingQueue<?>) {
            PriorityBlockingQueue<? extends E> pq =
                (PriorityBlockingQueue<? extends E>) c;
            this.comparator = (Comparator<? super E>) pq.comparator();
            screen = false;
            if (pq.getClass() == PriorityBlockingQueue.class) // first one
                heapify = false;
        }
        Object[] a = c.toArray();
        int n = a.length;

        if (a.getClass() != Object[].class)  // second one
            a = Arrays.copyOf(a, n, Object[].class);
        if (screen && (n == 1 || this.comparator != null)) {  //third one
            for (int i = 0; i < n; ++i)
                if (a[i] == null)
                    throw new NullPointerException();
        }
        this.queue = a;
        this.size = n;
        if (heapify)
            heapify();
    }

1. When "pq.getClass() == PriorityBlockingQueue.class" Expression holds,
    Then heapify operation is not need to do. Isn't "c instanceof PriorityBlockingQueue<?>"
    enough to decide?

2. Why must make the actual type of array is Object[].class?

3. I just don't understand  this "&& (n == 1 || this.comparator != null)". Why is it written like this?

In newest JDK, http://hg.openjdk.java.net/jdk/jdk15/file/d2c6eb3b2c8d/src/java.base/share/classes/java/util/concurrent/PriorityBlockingQueue.java#l242 ,
this constructor of PriorityBlockingQueue is same.



--------------------------------------------------------------------------------
Regards
Liu
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Somewhere in this constructor of PriorityBlockingQueue is hard to understand

JSR166 Concurrency mailing list
Thanks for your answer!

About first question, if you say so, then maybe Instanceof allows subclasses which could be coded to break the assumption that items are not null.
I mean, only when "pq.getClass() == PriorityBlockingQueue.class" Expression holds, then you could do "screen = false".
Am i wrong?

If the size is greater than one and there is no comparator heapify() will catch the null element.

About Third question, I think heapify() could not catch the null element that is at the back of array.
Because heapify() from last-non-leaf-node index to zero to invoke siftDownComparable(), 
so heapify() couldn't Traverse every node.
And siftDownComparable() has a "while (k < half)", which half means first-leaf-node index,
so when k become a leaf-node index, the siftDown will stop too.
To sum up, heapify() could not catch the null element that is at the back of array.

--------------------------------------------------------------------------------
Regards
Liu

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Somewhere in this constructor of PriorityBlockingQueue is hard to understand

JSR166 Concurrency mailing list
Liu,

Do you have a test case to show the behavior where null slips by and is allowed?  I think my test case here captures your intent but perhaps I'm missing a specific detail as I'm unable to make the test fail.

====
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.concurrent.PriorityBlockingQueue;

public class HeapifyTest {
       
        private static final int SIZE = 16;
       
        public static void main(String[] args) {
                for (int i=1; i<SIZE; i++) {
                        testArrayList(i);
                }
        }
       
        private static void testArrayList(int size) {
                for (int i=0; i<size; i++) {
                        ArrayList<Integer> al = new ArrayList<>(size);
                        for (int j=0; j<size; j++) {
                                if (i != j) {
                                        al.add(j);
                                } else {
                                        al.add(null);
                                }
                        }
                       
                        testNull(al);
                       
                        Collections.reverse(al);
                        testNull(al);
                       
                        Collections.shuffle(al);
                        testNull(al);
                       
                        Collections.reverse(al);
                        testNull(al);
                }
        }
       
        private static void testNull(Collection<Integer> c) {
                Objects.requireNonNull(c);
                try {
                        new PriorityQueue<>(c);
                        System.err.println("PQ FAIL contans null: " + c);
                } catch(NullPointerException expected) {
                        System.err.println("PASS: " + c);
                }
               
                try {
                        new PriorityBlockingQueue<>(c);
                        System.err.println("PBQ FAIL contains null: " + c);
                } catch(NullPointerException expected) {
                        System.err.println("PASS: " + c);
                }
        }
}
===

Jason

________________________________________
From: Liu <[hidden email]>
Sent: Tuesday, August 4, 2020 10:55 AM
To: [hidden email]
Cc: Concurrency-interest
Subject: Re:  [concurrency-interest] Somewhere in this constructor of PriorityBlockingQueue is hard to understand

Thanks for your answer!

About first question, if you say so, then maybe Instanceof allows subclasses which could be coded to break the assumption that items are not null.
I mean, only when "pq.getClass() == PriorityBlockingQueue.class" Expression holds, then you could do "screen = false".
Am i wrong?

> If the size is greater than one and there is no comparator heapify() will catch the null element.

About Third question, I think heapify() could not catch the null element that is at the back of array.
Because heapify() from last-non-leaf-node index to zero to invoke siftDownComparable(),
so heapify() couldn't Traverse every node.
And siftDownComparable() has a "while (k < half)", which half means first-leaf-node index,
so when k become a leaf-node index, the siftDown will stop too.
To sum up, heapify() could not catch the null element that is at the back of array.

--------------------------------------------------------------------------------
Regards
Liu
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Somewhere in this constructor of PriorityBlockingQueue is hard to understand

JSR166 Concurrency mailing list

import java.util.ArrayList;

import java.util.Queue;

import java.util.concurrent.PriorityBlockingQueue;


public class test16 {

    static class Holder implements Comparable<Holder> {

        int i;

        Holder(int i) {

            this.i = i;

        }

        public int compareTo(Holder h) {

            if(h == null)

                return  -1;

            return this.i - h.i;

        }

    }


    public static void main(String[] args) {

        ArrayList<Holder> al = new ArrayList<>(2);

        al.add(new Holder(1));

        al.add(new Holder(2));

        al.add(null);

        Queue a = new PriorityBlockingQueue<>(al);

    }

}


In this case, heapify() cound not find null item.


 


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Somewhere in this constructor of PriorityBlockingQueue is hard to understand

JSR166 Concurrency mailing list

"ArrayList<Holder> al = new ArrayList<>(2);" should be "ArrayList<Holder> al = new ArrayList<>();", be the way.


At 2020-08-05 10:07:29, "Liu" <[hidden email]> wrote:

import java.util.ArrayList;

import java.util.Queue;

import java.util.concurrent.PriorityBlockingQueue;


public class test16 {

    static class Holder implements Comparable<Holder> {

        int i;

        Holder(int i) {

            this.i = i;

        }

        public int compareTo(Holder h) {

            if(h == null)

                return  -1;

            return this.i - h.i;

        }

    }


    public static void main(String[] args) {

        ArrayList<Holder> al = new ArrayList<>(2);

        al.add(new Holder(1));

        al.add(new Holder(2));

        al.add(null);

        Queue a = new PriorityBlockingQueue<>(al);

    }

}


In this case, heapify() cound not find null item.


 



 


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Somewhere in this constructor of PriorityBlockingQueue is hard to understand

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Holder violates the spec of https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Comparable.html.  Per the docs:
"Note that null is not an instance of any class, and e.compareTo(null) should throw a NullPointerException even though e.equals(null) returns false"

The bug is not in PQ it is in the 3rd party Holder implementation.

Jason

________________________________________
From: Liu <[hidden email]>
Sent: Tuesday, August 4, 2020 9:07 PM
To: Jason Mehrens
Cc: Concurrency-interest
Subject: Re:Re:  [concurrency-interest] Somewhere in this constructor of PriorityBlockingQueue is hard to understand

import java.util.ArrayList;

import java.util.Queue;

import java.util.concurrent.PriorityBlockingQueue;


public class test16 {

    static class Holder implements Comparable<Holder> {

        int i;

        Holder(int i) {

            this.i = i;

        }

        public int compareTo(Holder h) {

            if(h == null)

                return  -1;

            return this.i - h.i;

        }

    }


    public static void main(String[] args) {

        ArrayList<Holder> al = new ArrayList<>(2);

        al.add(new Holder(1));

        al.add(new Holder(2));

        al.add(null);

        Queue a = new PriorityBlockingQueue<>(al);

    }

}

In this case, heapify() cound not find null item.




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Somewhere in this constructor of PriorityBlockingQueue is hard to understand

JSR166 Concurrency mailing list
i see, in this point, heapify() can find any null item.

But about first question, as I says,
only when "pq.getClass() == PriorityBlockingQueue.class" Expression holds, then you can do "screen = false".
Is this opinion wrong?
Maybe Instanceof allows subclasses which could be coded to allow null items.


 


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Somewhere in this constructor of PriorityBlockingQueue is hard to understand

JSR166 Concurrency mailing list

Of course, even subclasses are coded to allow null items, heapify() can find the null item.


At 2020-08-05 13:42:16, "Liu via Concurrency-interest" <[hidden email]> wrote:

i see, in this point, heapify() can find any null item.

But about first question, as I says,
only when "pq.getClass() == PriorityBlockingQueue.class" Expression holds, then you can do "screen = false".
Is this opinion wrong?
Maybe Instanceof allows subclasses which could be coded to allow null items.


 



 


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest