[concurrency-interest] RFR: CopyOnWriteArrayNavigableSet for Java 9

Mike Duigou openjdk at duigou.org
Thu Dec 31 15:21:45 EST 2015


Jason Mehrens <jason_mehrens at hotmail.com> wrote:
> Mike,
> 
> It appears that this code recreates bug
> https://bugs.openjdk.java.net/browse/JDK-5045147. When the collection
> is empty you have to perform a reflexive compare on the given element
> to screen null and other types that are rejected by the comparator.
> 
> Jason

5045147 is one of my favourite bugs!

Null elements aren't allowed by this implementation, but you are 
certainly correct about incompatible elements being incorrectly accepted 
into an empty Set. When I added the requireNonNull() I foolishly removed 
the forced comparison for empty set. Thank you for noticing.

The internal add() method becomes :

private static <E> boolean add(CopyOnWriteArrayNavigableSet<E> cowans, E 
e) {
     Objects.requireNonNull(e, "e");
     synchronized(cowans.al.lock) {
         @SuppressWarnings("unchecked")
         E[] array = (E[]) cowans.al.getArray();
         int loc = (array.length != 0)
                 ? Arrays.binarySearch(array, e, cowans.comparator)
                 : cowans.comparator().compare(e, e) == 0 ? -1 : 
Integer.MIN_VALUE;
         if(loc < 0) {
             // MIN_VALUE is an impossible index we use as a sentinel for 
bad comparator.
             if (loc == Integer.MIN_VALUE)
                 throw new IllegalArgumentException(
                 "Comparison method violates its general contract!");
             cowans.al.add(-1 - loc, e);
             return true;
         }
         return false;
     }
}

with a similar change in the addAll() method. I opted to use the same 
exception message as thrown by TimSort because that will hopefully 
generate search results pointing unfortunate developers in the direction 
of a solution.

Thanks!

Mike


More information about the Concurrency-interest mailing list