RFR: CopyOnWriteArrayNavigableSet for Java 9

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

RFR: CopyOnWriteArrayNavigableSet for Java 9

Mike Duigou
Hello All;

Enclosed is a new draft of the CopyOnWriteArrayNavigableSet
implementation I have been working on for Java 9. This version
incorporates review feedback from November and should be very nearly
complete and ready for submission. It is not to late to provide feedback
though, so if you have any comments or suggestions feel free to send
them to this list.

I am planning to post a standalone version of this class on github and
probably will publish it as a maven package for use with Java 7 and Java
8. This version will have he same class name and API but will be in a
different package.

Cheers,

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

CopyOnWriteArrayNavigableSet.java (44K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: RFR: CopyOnWriteArrayNavigableSet for Java 9

Dr Heinz M. Kabutz
In your constructor that takes an Iterable, I would probably have the last case first add the elements to an ArrayList and then add those to with your clever addAll() bulk method:

        } else {
            this.comparator = (Comparator<? super E>) Comparator.naturalOrder();
            this.al = new CopyOnWriteArrayList<>();
            if (c instanceof Collection) {
                CopyOnWriteArrayNavigableSet.addAll(this, ((Collection) c));
            } else {
                ArrayList<E> elements = new ArrayList<>();
                for(E e : c) {
                    elements.add(e);
                }
                CopyOnWriteArrayNavigableSet.addAll(this, elements);

            }
        }

Regards

Heinz
-- 
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion since 2005
JavaOne Rock Star Speaker 2012
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz


Mike Duigou wrote:
Hello All;

Enclosed is a new draft of the CopyOnWriteArrayNavigableSet implementation I have been working on for Java 9. This version incorporates review feedback from November and should be very nearly complete and ready for submission. It is not to late to provide feedback though, so if you have any comments or suggestions feel free to send them to this list.

I am planning to post a standalone version of this class on github and probably will publish it as a maven package for use with Java 7 and Java 8. This version will have he same class name and API but will be in a different package.

Cheers,

Mike



/* * Written by Doug Lea & Mike Duigou with assistance from members of JCP JSR-166 * Expert Group and released to the public domain, as explained at * http://creativecommons.org/publicdomain/zero/1.0/ */ package java.util.concurrent; import java.lang.reflect.Array; import java.util.Collection; import java.util.AbstractSet; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; import java.util.Iterator; import java.util.List; import java.util.NavigableSet; import java.util.NoSuchElementException; import java.util.Objects; import java.util.SortedSet; import java.util.Spliterator; import java.util.Spliterators; import java.util.function.Predicate; import java.util.function.Consumer; /** * A {@link java.util.NavigableSet} that uses an internal {@link CopyOnWriteArrayList} * for all of its operations. Thus, it shares the same basic properties: *
    *
  • It is best suited for applications in which set sizes generally * stay small, read-only operations * vastly outnumber mutative operations, and you need * to prevent interference among threads during traversal. *
  • It is thread-safe. *
  • Mutative operations ({@code add}, {@code set}, {@code remove}, etc.) * are expensive since they usually entail copying the entire underlying * array. *
  • Iterators do not support the mutative {@code remove} operation. *
  • Traversal via iterators is fast and cannot encounter * interference from other threads. Iterators rely on * unchanging snapshots of the array at the time the iterators were * constructed. *
* *

Sample Usage. The following code sketch uses a * copy-on-write navigable set to maintain a set of ordered Handler objects that * perform some action upon state updates until one of the handlers returns * true indicating that the update has been handled. * *

 {@code
 * class Handler implements Comparable {
 *   // returns true if update has been handled
 *   boolean handle();
 *
 *   // ordered from highest to lowest
 *   public int compareTo(Handler other) { return Integer.compare(priority, other.priority); }
 * }
 *
 * class X {
 *   // Will use "Natural Order" of Comparables
 *   private final CopyOnWriteArrayNavigableSet handlers
 *     = new CopyOnWriteArrayNavigableSet<>();
 *   public void addHandler(Handler h) { handlers.add(h); }
 *
 *   private long internalState;
 *   private synchronized void changeState() { internalState = ...; }
 *
 *   public void update() {
 *     changeState();
 *     for (Handler handler : handlers)
 *       if(handler.handle()) break;
 *   }
 * }}
* *

This class is a member of the * * Java Collections Framework. * * @see CopyOnWriteArrayList * @since 9 * @author Doug Lea * @author Mike Duigou * @param the type of elements held in this collection */ public class CopyOnWriteArrayNavigableSet extends AbstractSet implements java.io.Serializable, NavigableSet { private static final long serialVersionUID = -3680134489612968105L; /** * Comparator for elements. */ final Comparator comparator; /** * Embedded CopyOnWriteArrayList used to hold the storage of this set. */ final CopyOnWriteArrayList al; /** * Creates a set using the provided comparator with the initial elements * of the provided COWAL. * * @param comparator * @param al */ CopyOnWriteArrayNavigableSet(Comparator comparator, CopyOnWriteArrayList al) { this.comparator = Objects.requireNonNull(comparator, "comparator"); this.al = al; } /** * Creates an empty set which can be used for mutually * {@link java.lang.Comparable Comparable} objects. */ @SuppressWarnings("unchecked") public CopyOnWriteArrayNavigableSet() { this((Comparator) Comparator.naturalOrder()); } /** * Creates an empty set with the specified comparator. * * @param comparator Used for ordering elements. For * {@link java.lang.Comparable Comparable} objects use * {@link Comparator#naturalOrder()} */ public CopyOnWriteArrayNavigableSet(Comparator comparator) { this(comparator, new CopyOnWriteArrayList<>()); } /** * Creates a set containing all of the elements of the specified * Iterable. If c is a {@link SortedSet sorted set} then the same * Comparator is used. * * @param c the elements to initially contain * @throws NullPointerException if the specified collection is null */ @SuppressWarnings("unchecked") public CopyOnWriteArrayNavigableSet(Iterable c) { if (c.getClass() == CopyOnWriteArrayNavigableSet.class) { this.comparator = ((CopyOnWriteArrayNavigableSet) c).comparator; this.al = new CopyOnWriteArrayList<>(); this.al.setArray(((CopyOnWriteArrayNavigableSet) c).al.getArray()); } else if (c instanceof SortedSet) { Comparator compare = ((SortedSet) c).comparator(); this.comparator = compare == null ? (Comparator) Comparator.naturalOrder() : compare; this.al = new CopyOnWriteArrayList<>(((SortedSet) c)); } else { this.comparator = (Comparator) Comparator.naturalOrder(); this.al = new CopyOnWriteArrayList<>(); if (c instanceof Collection) { CopyOnWriteArrayNavigableSet.addAll(this, ((Collection) c)); } else { for(E e : c) { add(this, e); } } } } /** * Creates a new empty CopyOnWriteArrayNavigableSet using natural order * ordering. * @param Type of elements * @return new CopyOnWriteArrayNavigableSet */ public static > CopyOnWriteArrayNavigableSet create() { return new CopyOnWriteArrayNavigableSet<>(); } /** * Creates a new CopyOnWriteArrayNavigableSet of the provided elements using * natural order ordering. * @param Type of elements * @param contents initial elements for the set. * @return new CopyOnWriteArrayNavigableSet */ public static > CopyOnWriteArrayNavigableSet create(Iterable contents) { return new CopyOnWriteArrayNavigableSet<>(contents); } /** * Creates a new empty CopyOnWriteArrayNavigableSet using provided * comparator for ordering. * @param Type of elements * @param comparator The comparator to use for ordering. * @return new CopyOnWriteArrayNavigableSet */ public static CopyOnWriteArrayNavigableSet create(Comparator comparator) { return new CopyOnWriteArrayNavigableSet<>(comparator); } @Override @SuppressWarnings("unchecked") public boolean contains(Object o) { return Arrays.binarySearch((E[]) al.getArray(), (E) o, comparator) >= 0; } @Override public boolean remove(Object o) { synchronized(al.lock) { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); @SuppressWarnings("unchecked") int loc = Arrays.binarySearch(array, (E) o, comparator); if(loc >= 0) { al.remove(loc); return true; } return false; } } @Override public boolean add(E e) { return add(this, e); } private static boolean add(CopyOnWriteArrayNavigableSet cowans, E e) { Objects.requireNonNull(e, "e"); synchronized(cowans.al.lock) { @SuppressWarnings("unchecked") E[] array = (E[]) cowans.al.getArray(); int loc = Arrays.binarySearch(array, e, cowans.comparator); if(loc < 0) { cowans.al.add(-1 - loc, e); return true; } return false; } } @Override @SuppressWarnings("unchecked") public boolean containsAll(Collection c) { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); for(Object each : c) { if(Arrays.binarySearch(array, (E) each, comparator) < 0) { return false; } } return true; } @Override public boolean addAll(Collection c) { return CopyOnWriteArrayNavigableSet.addAll(this, c); } @SuppressWarnings("unchecked") private static boolean addAll(CopyOnWriteArrayNavigableSet cowans, Collection c) { Object[] cs = c.toArray(); if (cs.length == 0) return false; if(cs.length == 1) { return cowans.add((E) cs[0]); } synchronized (cowans.al.lock) { E[] array = (E[]) cowans.al.getArray(); int len = array.length; int added = 0; // uniquify and compact elements in cs for (int i = 0; i < cs.length; ++i) { Object e = Objects.requireNonNull(cs[i]); if (Arrays.binarySearch(array, (E) e, cowans.comparator) < 0) { int at = Arrays.binarySearch((E[]) cs, 0, added, (E) e, cowans.comparator); if(at < 0) { // insertion sort it into low portion of cs. at = -at - 1; //System.out.println( Arrays.asList(cs) + " len:" + cs.length + " e:" + e + " at:" + at + " added:" + added); System.arraycopy(cs, at, cs, at + 1, added++ - at); cs[at] = e; } } } if (added > 0) { Object[] newElements = (Object[]) Array.newInstance(array.getClass().getComponentType(), len + added); --len; --added; for(int i = newElements.length - 1; i >= 0; i--) { // merge into resulting array. Both array and cs are sorted. newElements[i] = len >= 0 && (added < 0 || cowans.comparator.compare(array[len], (E) cs[added]) > 0) ? array[len--] : cs[added--]; } cowans.al.setArray(newElements); return true; } return false; } } @Override public Iterator iterator() { return al.iterator(); } @Override public int size() { return al.size(); } @Override public boolean removeIf(Predicate filter) { return al.removeIf(filter); } @Override public void forEach(Consumer action) { al.forEach(action); } @Override public boolean retainAll(Collection c) { return al.retainAll(c); } @Override public boolean removeAll(Collection c) { return al.removeAll(c); } @Override public Object[] toArray() { return al.toArray(); } @Override public T[] toArray(T[] a) { return al.toArray(a); } @Override public void clear() { al.clear(); } /** * Returns a {@link Spliterator} over the elements in this set in the order * in which these elements were added. * *

The {@code Spliterator} reports {@link Spliterator#ORDERED}, * {@link Spliterator#NONNULL}, {@link Spliterator#IMMUTABLE}, * {@link Spliterator#DISTINCT}, and {@link Spliterator#SIZED}. * *

The spliterator provides a snapshot of the state of the set * when the spliterator was constructed. No synchronization is needed while * operating on the spliterator. * * @return a {@code Spliterator} over the elements in this set */ @Override public Spliterator spliterator() { return Spliterators.spliterator (al.getArray(), Spliterator.ORDERED | Spliterator.NONNULL | Spliterator.IMMUTABLE | Spliterator.DISTINCT); } // +---+---+---+---+ // | 2 | 4 | 6 | 8 | // +---+---+---+---+ // lower(0) = null // lower(2) = null // lower(3) = 2 // lower(8) = 6 // lower(9) = 8 @Override @SuppressWarnings("unchecked") public E lower(E e) { E[] array = (E[]) al.getArray(); int loc = Arrays.binarySearch(array, e, comparator); return loc > 0 ? array[loc - 1] : loc < -1 // zero or minus one means nothing strictly lower. ? array[-2 - loc] : null; } // +---+---+---+---+ // | 2 | 4 | 6 | 8 | // +---+---+---+---+ // floor(0) = null // floor(2) = 2 // floor(3) = 2 // floor(8) = 8 // floor(9) = 8 @Override @SuppressWarnings("unchecked") public E floor(E e) { E[] array = (E[]) al.getArray(); int loc = Arrays.binarySearch(array, e, comparator); return loc >= 0 ? array[loc] : loc < -1 // minus one means nothing matching or lower. ? array[-2 - loc] : null; } // +---+---+---+---+ // | 2 | 4 | 6 | 8 | // +---+---+---+---+ // ceiling(0) = 2 // ceiling(2) = 2 // ceiling(3) = 4 // ceiling(8) = 8 // ceiling(9) = null @Override @SuppressWarnings("unchecked") public E ceiling(E e) { E[] array = (E[]) al.getArray(); int loc = Arrays.binarySearch(array, e, comparator); return loc >= 0 ? array[loc] : -loc < array.length ? array[-1 - loc] : null; } // +---+---+---+---+ // | 2 | 4 | 6 | 8 | // +---+---+---+---+ // higher(0) = 2 // higher(2) = 4 // higher(3) = 4 // higher(8) = null // higher(9) = null @Override @SuppressWarnings("unchecked") public E higher(E e) { E[] array = (E[]) al.getArray(); int loc = Arrays.binarySearch(array, e, comparator); return loc >= 0 ? (loc < array.length - 1 ) ? array[loc + 1] : null : -loc < array.length ? array[-1 - loc] : null; } @Override public E pollFirst() { if(al.isEmpty()) return null; synchronized(al.lock) { if(al.isEmpty()) return null; E result = al.remove(0); return result; } } @Override public E pollLast() { if(al.isEmpty()) return null; synchronized(al.lock) { if(al.isEmpty()) return null; E result = al.remove(al.size() - 1); return result; } } @Override public NavigableSet descendingSet() { return new BoundedNavigableSet<>(comparator, al, false, null, false, false, null, false, true); } @Override @SuppressWarnings("unchecked") public Iterator descendingIterator() { final Object[] array = al.getArray(); return array.length == 0 ? Collections.emptyIterator() : new Iterator() { int index = array.length - 1; @Override public boolean hasNext() { return index >= 0; } @Override public E next() { if (hasNext()) { return (E) array[index--]; } else { throw new NoSuchElementException(); } } }; } @Override public NavigableSet subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { return new BoundedNavigableSet<>(comparator, al, true, fromElement, fromInclusive, true, toElement, toInclusive, false); } @Override public NavigableSet headSet(E toElement, boolean inclusive) { return new BoundedNavigableSet<>(comparator, al, false, null, false, true, toElement, inclusive, false); } @Override public NavigableSet tailSet(E fromElement, boolean inclusive) { return new BoundedNavigableSet<>(comparator, al, true, fromElement, inclusive, false, null, false, false); } @Override public SortedSet subSet(E fromElement, E toElement) { return subSet(fromElement, true, toElement, false); } @Override public SortedSet headSet(E toElement) { return headSet(toElement, false); } @Override public SortedSet tailSet(E fromElement) { return tailSet(fromElement, true); } @Override public Comparator comparator() { return comparator; } @Override public E first() { if(al.isEmpty()) throw new NoSuchElementException(); @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); if(array.length == 0) throw new NoSuchElementException(); return array[0]; } @Override public E last() { if(al.isEmpty()) throw new NoSuchElementException(); @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); if(array.length == 0) throw new NoSuchElementException(); return array[array.length - 1]; } private static class BoundedNavigableSet extends CopyOnWriteArrayNavigableSet { private static final long serialVersionUID = 3830104881368453055L; /** * If true then iteration is done in descending order. */ final boolean descending; /** * If true then a lower bound relative to the super set. */ final boolean lowerBounded; /** * If true then we have an upper bound relative to the super set. */ final boolean upperBounded; /** * If true then the lower bound is included in the set. */ final boolean lowerInclusive; /** * If true then the upper bound is included in the set. */ final boolean upperInclusive; /** * The value of the lower bound. */ final E lowerBound; /** * The value of the upper bound. */ final E upperBound; @SuppressWarnings("unchecked") public BoundedNavigableSet( Comparator comparator, CopyOnWriteArrayList al, boolean lowerBounded, E fromElement, boolean lowerInclusive, boolean upperBounded, E toElement, boolean upperInclusive, boolean descending) { super(comparator, al); this.descending = descending; if (lowerBounded && upperBounded) { int fromCompared = Integer.signum(comparator.compare(fromElement,toElement)); int toCompared = Integer.signum(comparator.compare(toElement,fromElement)); if(fromCompared != -toCompared) { throw new IllegalArgumentException("inconsistent comparator"); } if (!descending) { if (fromCompared > 0) { throw new IllegalArgumentException("upper < lower"); } } else { if (fromCompared < 0) { throw new IllegalArgumentException("upper < lower"); } } } this.lowerBounded = lowerBounded; this.lowerBound = fromElement; this.lowerInclusive = lowerInclusive; this.upperBounded = upperBounded; this.upperBound = toElement; this.upperInclusive = upperInclusive; } @Override public boolean add(E e) { return super.add(inBounds(e)); } @Override @SuppressWarnings("unchecked") public boolean contains(Object o) { return checkInBounds((E) o) && super.contains(o); } @Override @SuppressWarnings("unchecked") public Comparator comparator() { return (Comparator) (descending ? comparator.reversed() : comparator); } @Override public NavigableSet descendingSet() { return new BoundedNavigableSet<>( comparator, al, upperBounded, upperBound, upperInclusive, lowerBounded, lowerBound, lowerInclusive, !descending); } @Override public NavigableSet subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { return new BoundedNavigableSet<>( comparator, al, true, inBounds(fromElement), fromInclusive, true, inBounds(toElement), toInclusive, descending); } @Override public NavigableSet headSet(E toElement, boolean inclusive) { return new BoundedNavigableSet<>( comparator, al, lowerBounded, lowerBound, lowerInclusive, true, inBounds(toElement), inclusive, descending); } @Override public NavigableSet tailSet(E fromElement, boolean inclusive) { return new BoundedNavigableSet<>( comparator, al, true, inBounds(fromElement), inclusive, upperBounded, upperBound, upperInclusive, descending); } @Override public SortedSet subSet(E fromElement, E toElement) { return subSet(fromElement, true, toElement, false); } @Override public SortedSet headSet(E toElement) { return headSet(toElement, false); } @Override public SortedSet tailSet(E fromElement) { return tailSet(fromElement, true); } private E inBounds(E element) { if (lowerBounded) { if (lowerInclusive) { if (comparator.compare(lowerBound,element) > 0) { throw new IllegalArgumentException("out of bounds: " + element + " < " + lowerBound); } } else { if (comparator.compare(lowerBound, element) >= 0) { throw new IllegalArgumentException("out of bounds: " + element + " <= " + lowerBound); } } } if (upperBounded) { if (upperInclusive) { if (comparator.compare(upperBound, element) < 0) { throw new IllegalArgumentException("out of bounds: " + element + " > " + upperBound); } } else { if (comparator.compare(upperBound, element) <= 0) { throw new IllegalArgumentException("out of bounds: " + element + " >= " + upperBound); } } } return element; } private boolean checkInBounds(E element) { if (lowerBounded) { if (lowerInclusive) { if (comparator.compare(lowerBound,element) > 0) { return false; } } else { if (comparator.compare(lowerBound, element) >= 0) { return false; } } } if (upperBounded) { if (upperInclusive) { if (comparator.compare(upperBound, element) < 0) { return false; } } else { if (comparator.compare(upperBound, element) <= 0) { return false; } } } return true; } @Override public Iterator descendingIterator() { return makeIterator(!descending); } @Override public void forEach(Consumer action) { Objects.requireNonNull(action, "action"); @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end = toLoc(array); for(int each=start;each filter) { Objects.requireNonNull(filter, "filter"); synchronized(al.lock) { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end = toLoc(array); return al.subList(start, end).removeIf(filter); } } @Override public boolean retainAll(Collection c) { synchronized(al.lock) { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end = toLoc(array); return al.subList(start, end).retainAll(c); } } @Override public boolean removeAll(Collection c) { synchronized(al.lock) { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end = toLoc(array); return al.subList(start, end).removeAll(c); } } @Override public boolean addAll(Collection c) { for (E e : c) inBounds(e); return CopyOnWriteArrayNavigableSet.addAll(this, c); } @Override @SuppressWarnings("unchecked") public boolean containsAll(Collection c) { E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end = toLoc(array); for (Object each : c) { if (Arrays.binarySearch(array, start, end, (E) each, comparator) < 0) { return false; } } return true; } @Override @SuppressWarnings("unchecked") public boolean remove(Object o) { return checkInBounds((E) o) && super.remove(o); } @Override public void clear() { synchronized(al.lock) { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end = toLoc(array); al.removeRange(start, end); } } @SuppressWarnings("unchecked") private int fromLoc(E[] array) { int start; if(lowerBounded) { start = Arrays.binarySearch(array, lowerBound, comparator == null ? descending ? (Comparator) Comparator.reverseOrder() : null : descending ? comparator.reversed() : comparator); start = start >= 0 ? lowerInclusive ? start : start + 1 : -1 - start; } else { start = 0; } return start; } @SuppressWarnings("unchecked") private int toLoc(E[] array) { int end; if(upperBounded) { end = Arrays.binarySearch(array, upperBound, descending ? comparator.reversed() : comparator); end = end >= 0 ? upperInclusive ? end + 1 : end : -1 - end; } else { end = array.length; } return end; } @Override public T[] toArray(T[] a) { return makeArray(a, descending); } @SuppressWarnings("unchecked") public T[] makeArray(T[] a, boolean inDescending) { E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end = toLoc(array); int len = end - start; if (a.length < len) { a = (T[]) Array.newInstance(a.getClass().getComponentType(), len); } System.arraycopy(array, start, a, 0, len); if(len < a.length) a[len] = null; if(inDescending) Collections.reverse(Arrays.asList(a).subList(0, len)); return a; } @Override public Object[] toArray() { return makeArray(new Object[0], descending); } @Override public Iterator iterator() { return makeIterator(descending); } @SuppressWarnings("unchecked") private Iterator makeIterator(boolean inDescending) { List asList; if(inDescending) { asList = Arrays.asList((E[]) makeArray(new Object[0], inDescending)); } else { E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end = toLoc(array); asList = Arrays.asList(array).subList(start, end); } return Collections.unmodifiableList(asList).iterator(); } @Override public int size() { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); return toLoc(array) - fromLoc(array); } @Override @SuppressWarnings("unchecked") public E lower(E e) { E result = descending ? super.higher(e) : super.lower(e); return result != null && checkInBounds(result) ? result : null; } @Override @SuppressWarnings("unchecked") public E floor(E e) { E result = descending ? super.ceiling(e) : super.floor(e); return result != null && checkInBounds(result) ? result : null; } @Override @SuppressWarnings("unchecked") public E ceiling(E e) { E result = descending ? super.floor(e) : super.ceiling(e); return result != null && checkInBounds(result) ? result : null; } @Override @SuppressWarnings("unchecked") public E higher(E e) { E result = descending ? super.lower(e) : super.higher(e); return result != null && checkInBounds(result) ? result : null; } @Override public E pollFirst() { return descending ? doPollLast() : doPollFirst(); } private E doPollFirst() { if(lowerBounded) synchronized(al.lock) { E remove = lowerInclusive ? floor(lowerBound) : higher(lowerBound); if(null != remove) { super.remove(remove); } return remove; } else return super.pollFirst(); } @Override public E pollLast() { return descending ? doPollFirst() : doPollLast(); } private E doPollLast() { if(upperBounded) synchronized(al.lock) { E remove = upperInclusive ? floor(upperBound) : lower(upperBound); if(null != remove) { super.remove(remove); } return remove; } else return super.pollLast(); } @Override public E first() { return descending ? doLast() : doFirst(); } private E doFirst() { E result = lowerInclusive ? ceiling(lowerBound) : higher(lowerBound); if(null == result) { throw new NoSuchElementException(); } return result; } @Override public E last() { return descending ? doFirst() : doLast(); } private E doLast() { E result = upperInclusive ? floor(upperBound) : lower(upperBound); if(null == result) { throw new NoSuchElementException(); } return result; } @Override public Spliterator spliterator() { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); return Spliterators.spliterator( array, fromLoc(array), toLoc(array), Spliterator.ORDERED | Spliterator.NONNULL | Spliterator.IMMUTABLE | Spliterator.DISTINCT); } } }


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

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

Re: RFR: CopyOnWriteArrayNavigableSet for Java 9

Dr Heinz M. Kabutz
May I ask why you made CopyOnWriteArrayNavigableSet.addAll() static, considering that you are always passing in "this" as a parameter?
Regards

Heinz
-- 
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion since 2005
JavaOne Rock Star Speaker 2012
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz


Dr Heinz M. Kabutz wrote:
In your constructor that takes an Iterable, I would probably have the last case first add the elements to an ArrayList and then add those to with your clever addAll() bulk method:

        } else {
            this.comparator = (Comparator<? super E>) Comparator.naturalOrder();
            this.al = new CopyOnWriteArrayList<>();
            if (c instanceof Collection) {
                CopyOnWriteArrayNavigableSet.addAll(this, ((Collection) c));
            } else {
                ArrayList<E> elements = new ArrayList<>();
                for(E e : c) {
                    elements.add(e);
                }
                CopyOnWriteArrayNavigableSet.addAll(this, elements);

            }
        }

Regards

Heinz
-- 
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion since 2005
JavaOne Rock Star Speaker 2012
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz
  


Mike Duigou wrote:
Hello All;

Enclosed is a new draft of the CopyOnWriteArrayNavigableSet implementation I have been working on for Java 9. This version incorporates review feedback from November and should be very nearly complete and ready for submission. It is not to late to provide feedback though, so if you have any comments or suggestions feel free to send them to this list.

I am planning to post a standalone version of this class on github and probably will publish it as a maven package for use with Java 7 and Java 8. This version will have he same class name and API but will be in a different package.

Cheers,

Mike



/* * Written by Doug Lea & Mike Duigou with assistance from members of JCP JSR-166 * Expert Group and released to the public domain, as explained at * http://creativecommons.org/publicdomain/zero/1.0/ */ package java.util.concurrent; import java.lang.reflect.Array; import java.util.Collection; import java.util.AbstractSet; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; import java.util.Iterator; import java.util.List; import java.util.NavigableSet; import java.util.NoSuchElementException; import java.util.Objects; import java.util.SortedSet; import java.util.Spliterator; import java.util.Spliterators; import java.util.function.Predicate; import java.util.function.Consumer; /** * A {@link java.util.NavigableSet} that uses an internal {@link CopyOnWriteArrayList} * for all of its operations. Thus, it shares the same basic properties: *
    *
  • It is best suited for applications in which set sizes generally * stay small, read-only operations * vastly outnumber mutative operations, and you need * to prevent interference among threads during traversal. *
  • It is thread-safe. *
  • Mutative operations ({@code add}, {@code set}, {@code remove}, etc.) * are expensive since they usually entail copying the entire underlying * array. *
  • Iterators do not support the mutative {@code remove} operation. *
  • Traversal via iterators is fast and cannot encounter * interference from other threads. Iterators rely on * unchanging snapshots of the array at the time the iterators were * constructed. *
* *

Sample Usage. The following code sketch uses a * copy-on-write navigable set to maintain a set of ordered Handler objects that * perform some action upon state updates until one of the handlers returns * true indicating that the update has been handled. * *

 {@code
 * class Handler implements Comparable {
 *   // returns true if update has been handled
 *   boolean handle();
 *
 *   // ordered from highest to lowest
 *   public int compareTo(Handler other) { return Integer.compare(priority, other.priority); }
 * }
 *
 * class X {
 *   // Will use "Natural Order" of Comparables
 *   private final CopyOnWriteArrayNavigableSet handlers
 *     = new CopyOnWriteArrayNavigableSet<>();
 *   public void addHandler(Handler h) { handlers.add(h); }
 *
 *   private long internalState;
 *   private synchronized void changeState() { internalState = ...; }
 *
 *   public void update() {
 *     changeState();
 *     for (Handler handler : handlers)
 *       if(handler.handle()) break;
 *   }
 * }}
* *

This class is a member of the * * Java Collections Framework. * * @see CopyOnWriteArrayList * @since 9 * @author Doug Lea * @author Mike Duigou * @param the type of elements held in this collection */ public class CopyOnWriteArrayNavigableSet extends AbstractSet implements java.io.Serializable, NavigableSet { private static final long serialVersionUID = -3680134489612968105L; /** * Comparator for elements. */ final Comparator comparator; /** * Embedded CopyOnWriteArrayList used to hold the storage of this set. */ final CopyOnWriteArrayList al; /** * Creates a set using the provided comparator with the initial elements * of the provided COWAL. * * @param comparator * @param al */ CopyOnWriteArrayNavigableSet(Comparator comparator, CopyOnWriteArrayList al) { this.comparator = Objects.requireNonNull(comparator, "comparator"); this.al = al; } /** * Creates an empty set which can be used for mutually * {@link java.lang.Comparable Comparable} objects. */ @SuppressWarnings("unchecked") public CopyOnWriteArrayNavigableSet() { this((Comparator) Comparator.naturalOrder()); } /** * Creates an empty set with the specified comparator. * * @param comparator Used for ordering elements. For * {@link java.lang.Comparable Comparable} objects use * {@link Comparator#naturalOrder()} */ public CopyOnWriteArrayNavigableSet(Comparator comparator) { this(comparator, new CopyOnWriteArrayList<>()); } /** * Creates a set containing all of the elements of the specified * Iterable. If c is a {@link SortedSet sorted set} then the same * Comparator is used. * * @param c the elements to initially contain * @throws NullPointerException if the specified collection is null */ @SuppressWarnings("unchecked") public CopyOnWriteArrayNavigableSet(Iterable c) { if (c.getClass() == CopyOnWriteArrayNavigableSet.class) { this.comparator = ((CopyOnWriteArrayNavigableSet) c).comparator; this.al = new CopyOnWriteArrayList<>(); this.al.setArray(((CopyOnWriteArrayNavigableSet) c).al.getArray()); } else if (c instanceof SortedSet) { Comparator compare = ((SortedSet) c).comparator(); this.comparator = compare == null ? (Comparator) Comparator.naturalOrder() : compare; this.al = new CopyOnWriteArrayList<>(((SortedSet) c)); } else { this.comparator = (Comparator) Comparator.naturalOrder(); this.al = new CopyOnWriteArrayList<>(); if (c instanceof Collection) { CopyOnWriteArrayNavigableSet.addAll(this, ((Collection) c)); } else { for(E e : c) { add(this, e); } } } } /** * Creates a new empty CopyOnWriteArrayNavigableSet using natural order * ordering. * @param Type of elements * @return new CopyOnWriteArrayNavigableSet */ public static > CopyOnWriteArrayNavigableSet create() { return new CopyOnWriteArrayNavigableSet<>(); } /** * Creates a new CopyOnWriteArrayNavigableSet of the provided elements using * natural order ordering. * @param Type of elements * @param contents initial elements for the set. * @return new CopyOnWriteArrayNavigableSet */ public static > CopyOnWriteArrayNavigableSet create(Iterable contents) { return new CopyOnWriteArrayNavigableSet<>(contents); } /** * Creates a new empty CopyOnWriteArrayNavigableSet using provided * comparator for ordering. * @param Type of elements * @param comparator The comparator to use for ordering. * @return new CopyOnWriteArrayNavigableSet */ public static CopyOnWriteArrayNavigableSet create(Comparator comparator) { return new CopyOnWriteArrayNavigableSet<>(comparator); } @Override @SuppressWarnings("unchecked") public boolean contains(Object o) { return Arrays.binarySearch((E[]) al.getArray(), (E) o, comparator) >= 0; } @Override public boolean remove(Object o) { synchronized(al.lock) { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); @SuppressWarnings("unchecked") int loc = Arrays.binarySearch(array, (E) o, comparator); if(loc >= 0) { al.remove(loc); return true; } return false; } } @Override public boolean add(E e) { return add(this, e); } private static boolean add(CopyOnWriteArrayNavigableSet cowans, E e) { Objects.requireNonNull(e, "e"); synchronized(cowans.al.lock) { @SuppressWarnings("unchecked") E[] array = (E[]) cowans.al.getArray(); int loc = Arrays.binarySearch(array, e, cowans.comparator); if(loc < 0) { cowans.al.add(-1 - loc, e); return true; } return false; } } @Override @SuppressWarnings("unchecked") public boolean containsAll(Collection c) { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); for(Object each : c) { if(Arrays.binarySearch(array, (E) each, comparator) < 0) { return false; } } return true; } @Override public boolean addAll(Collection c) { return CopyOnWriteArrayNavigableSet.addAll(this, c); } @SuppressWarnings("unchecked") private static boolean addAll(CopyOnWriteArrayNavigableSet cowans, Collection c) { Object[] cs = c.toArray(); if (cs.length == 0) return false; if(cs.length == 1) { return cowans.add((E) cs[0]); } synchronized (cowans.al.lock) { E[] array = (E[]) cowans.al.getArray(); int len = array.length; int added = 0; // uniquify and compact elements in cs for (int i = 0; i < cs.length; ++i) { Object e = Objects.requireNonNull(cs[i]); if (Arrays.binarySearch(array, (E) e, cowans.comparator) < 0) { int at = Arrays.binarySearch((E[]) cs, 0, added, (E) e, cowans.comparator); if(at < 0) { // insertion sort it into low portion of cs. at = -at - 1; //System.out.println( Arrays.asList(cs) + " len:" + cs.length + " e:" + e + " at:" + at + " added:" + added); System.arraycopy(cs, at, cs, at + 1, added++ - at); cs[at] = e; } } } if (added > 0) { Object[] newElements = (Object[]) Array.newInstance(array.getClass().getComponentType(), len + added); --len; --added; for(int i = newElements.length - 1; i >= 0; i--) { // merge into resulting array. Both array and cs are sorted. newElements[i] = len >= 0 && (added < 0 || cowans.comparator.compare(array[len], (E) cs[added]) > 0) ? array[len--] : cs[added--]; } cowans.al.setArray(newElements); return true; } return false; } } @Override public Iterator iterator() { return al.iterator(); } @Override public int size() { return al.size(); } @Override public boolean removeIf(Predicate filter) { return al.removeIf(filter); } @Override public void forEach(Consumer action) { al.forEach(action); } @Override public boolean retainAll(Collection c) { return al.retainAll(c); } @Override public boolean removeAll(Collection c) { return al.removeAll(c); } @Override public Object[] toArray() { return al.toArray(); } @Override public T[] toArray(T[] a) { return al.toArray(a); } @Override public void clear() { al.clear(); } /** * Returns a {@link Spliterator} over the elements in this set in the order * in which these elements were added. * *

The {@code Spliterator} reports {@link Spliterator#ORDERED}, * {@link Spliterator#NONNULL}, {@link Spliterator#IMMUTABLE}, * {@link Spliterator#DISTINCT}, and {@link Spliterator#SIZED}. * *

The spliterator provides a snapshot of the state of the set * when the spliterator was constructed. No synchronization is needed while * operating on the spliterator. * * @return a {@code Spliterator} over the elements in this set */ @Override public Spliterator spliterator() { return Spliterators.spliterator (al.getArray(), Spliterator.ORDERED | Spliterator.NONNULL | Spliterator.IMMUTABLE | Spliterator.DISTINCT); } // +---+---+---+---+ // | 2 | 4 | 6 | 8 | // +---+---+---+---+ // lower(0) = null // lower(2) = null // lower(3) = 2 // lower(8) = 6 // lower(9) = 8 @Override @SuppressWarnings("unchecked") public E lower(E e) { E[] array = (E[]) al.getArray(); int loc = Arrays.binarySearch(array, e, comparator); return loc > 0 ? array[loc - 1] : loc < -1 // zero or minus one means nothing strictly lower. ? array[-2 - loc] : null; } // +---+---+---+---+ // | 2 | 4 | 6 | 8 | // +---+---+---+---+ // floor(0) = null // floor(2) = 2 // floor(3) = 2 // floor(8) = 8 // floor(9) = 8 @Override @SuppressWarnings("unchecked") public E floor(E e) { E[] array = (E[]) al.getArray(); int loc = Arrays.binarySearch(array, e, comparator); return loc >= 0 ? array[loc] : loc < -1 // minus one means nothing matching or lower. ? array[-2 - loc] : null; } // +---+---+---+---+ // | 2 | 4 | 6 | 8 | // +---+---+---+---+ // ceiling(0) = 2 // ceiling(2) = 2 // ceiling(3) = 4 // ceiling(8) = 8 // ceiling(9) = null @Override @SuppressWarnings("unchecked") public E ceiling(E e) { E[] array = (E[]) al.getArray(); int loc = Arrays.binarySearch(array, e, comparator); return loc >= 0 ? array[loc] : -loc < array.length ? array[-1 - loc] : null; } // +---+---+---+---+ // | 2 | 4 | 6 | 8 | // +---+---+---+---+ // higher(0) = 2 // higher(2) = 4 // higher(3) = 4 // higher(8) = null // higher(9) = null @Override @SuppressWarnings("unchecked") public E higher(E e) { E[] array = (E[]) al.getArray(); int loc = Arrays.binarySearch(array, e, comparator); return loc >= 0 ? (loc < array.length - 1 ) ? array[loc + 1] : null : -loc < array.length ? array[-1 - loc] : null; } @Override public E pollFirst() { if(al.isEmpty()) return null; synchronized(al.lock) { if(al.isEmpty()) return null; E result = al.remove(0); return result; } } @Override public E pollLast() { if(al.isEmpty()) return null; synchronized(al.lock) { if(al.isEmpty()) return null; E result = al.remove(al.size() - 1); return result; } } @Override public NavigableSet descendingSet() { return new BoundedNavigableSet<>(comparator, al, false, null, false, false, null, false, true); } @Override @SuppressWarnings("unchecked") public Iterator descendingIterator() { final Object[] array = al.getArray(); return array.length == 0 ? Collections.emptyIterator() : new Iterator() { int index = array.length - 1; @Override public boolean hasNext() { return index >= 0; } @Override public E next() { if (hasNext()) { return (E) array[index--]; } else { throw new NoSuchElementException(); } } }; } @Override public NavigableSet subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { return new BoundedNavigableSet<>(comparator, al, true, fromElement, fromInclusive, true, toElement, toInclusive, false); } @Override public NavigableSet headSet(E toElement, boolean inclusive) { return new BoundedNavigableSet<>(comparator, al, false, null, false, true, toElement, inclusive, false); } @Override public NavigableSet tailSet(E fromElement, boolean inclusive) { return new BoundedNavigableSet<>(comparator, al, true, fromElement, inclusive, false, null, false, false); } @Override public SortedSet subSet(E fromElement, E toElement) { return subSet(fromElement, true, toElement, false); } @Override public SortedSet headSet(E toElement) { return headSet(toElement, false); } @Override public SortedSet tailSet(E fromElement) { return tailSet(fromElement, true); } @Override public Comparator comparator() { return comparator; } @Override public E first() { if(al.isEmpty()) throw new NoSuchElementException(); @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); if(array.length == 0) throw new NoSuchElementException(); return array[0]; } @Override public E last() { if(al.isEmpty()) throw new NoSuchElementException(); @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); if(array.length == 0) throw new NoSuchElementException(); return array[array.length - 1]; } private static class BoundedNavigableSet extends CopyOnWriteArrayNavigableSet { private static final long serialVersionUID = 3830104881368453055L; /** * If true then iteration is done in descending order. */ final boolean descending; /** * If true then a lower bound relative to the super set. */ final boolean lowerBounded; /** * If true then we have an upper bound relative to the super set. */ final boolean upperBounded; /** * If true then the lower bound is included in the set. */ final boolean lowerInclusive; /** * If true then the upper bound is included in the set. */ final boolean upperInclusive; /** * The value of the lower bound. */ final E lowerBound; /** * The value of the upper bound. */ final E upperBound; @SuppressWarnings("unchecked") public BoundedNavigableSet( Comparator comparator, CopyOnWriteArrayList al, boolean lowerBounded, E fromElement, boolean lowerInclusive, boolean upperBounded, E toElement, boolean upperInclusive, boolean descending) { super(comparator, al); this.descending = descending; if (lowerBounded && upperBounded) { int fromCompared = Integer.signum(comparator.compare(fromElement,toElement)); int toCompared = Integer.signum(comparator.compare(toElement,fromElement)); if(fromCompared != -toCompared) { throw new IllegalArgumentException("inconsistent comparator"); } if (!descending) { if (fromCompared > 0) { throw new IllegalArgumentException("upper < lower"); } } else { if (fromCompared < 0) { throw new IllegalArgumentException("upper < lower"); } } } this.lowerBounded = lowerBounded; this.lowerBound = fromElement; this.lowerInclusive = lowerInclusive; this.upperBounded = upperBounded; this.upperBound = toElement; this.upperInclusive = upperInclusive; } @Override public boolean add(E e) { return super.add(inBounds(e)); } @Override @SuppressWarnings("unchecked") public boolean contains(Object o) { return checkInBounds((E) o) && super.contains(o); } @Override @SuppressWarnings("unchecked") public Comparator comparator() { return (Comparator) (descending ? comparator.reversed() : comparator); } @Override public NavigableSet descendingSet() { return new BoundedNavigableSet<>( comparator, al, upperBounded, upperBound, upperInclusive, lowerBounded, lowerBound, lowerInclusive, !descending); } @Override public NavigableSet subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { return new BoundedNavigableSet<>( comparator, al, true, inBounds(fromElement), fromInclusive, true, inBounds(toElement), toInclusive, descending); } @Override public NavigableSet headSet(E toElement, boolean inclusive) { return new BoundedNavigableSet<>( comparator, al, lowerBounded, lowerBound, lowerInclusive, true, inBounds(toElement), inclusive, descending); } @Override public NavigableSet tailSet(E fromElement, boolean inclusive) { return new BoundedNavigableSet<>( comparator, al, true, inBounds(fromElement), inclusive, upperBounded, upperBound, upperInclusive, descending); } @Override public SortedSet subSet(E fromElement, E toElement) { return subSet(fromElement, true, toElement, false); } @Override public SortedSet headSet(E toElement) { return headSet(toElement, false); } @Override public SortedSet tailSet(E fromElement) { return tailSet(fromElement, true); } private E inBounds(E element) { if (lowerBounded) { if (lowerInclusive) { if (comparator.compare(lowerBound,element) > 0) { throw new IllegalArgumentException("out of bounds: " + element + " < " + lowerBound); } } else { if (comparator.compare(lowerBound, element) >= 0) { throw new IllegalArgumentException("out of bounds: " + element + " <= " + lowerBound); } } } if (upperBounded) { if (upperInclusive) { if (comparator.compare(upperBound, element) < 0) { throw new IllegalArgumentException("out of bounds: " + element + " > " + upperBound); } } else { if (comparator.compare(upperBound, element) <= 0) { throw new IllegalArgumentException("out of bounds: " + element + " >= " + upperBound); } } } return element; } private boolean checkInBounds(E element) { if (lowerBounded) { if (lowerInclusive) { if (comparator.compare(lowerBound,element) > 0) { return false; } } else { if (comparator.compare(lowerBound, element) >= 0) { return false; } } } if (upperBounded) { if (upperInclusive) { if (comparator.compare(upperBound, element) < 0) { return false; } } else { if (comparator.compare(upperBound, element) <= 0) { return false; } } } return true; } @Override public Iterator descendingIterator() { return makeIterator(!descending); } @Override public void forEach(Consumer action) { Objects.requireNonNull(action, "action"); @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end = toLoc(array); for(int each=start;each filter) { Objects.requireNonNull(filter, "filter"); synchronized(al.lock) { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end = toLoc(array); return al.subList(start, end).removeIf(filter); } } @Override public boolean retainAll(Collection c) { synchronized(al.lock) { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end = toLoc(array); return al.subList(start, end).retainAll(c); } } @Override public boolean removeAll(Collection c) { synchronized(al.lock) { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end = toLoc(array); return al.subList(start, end).removeAll(c); } } @Override public boolean addAll(Collection c) { for (E e : c) inBounds(e); return CopyOnWriteArrayNavigableSet.addAll(this, c); } @Override @SuppressWarnings("unchecked") public boolean containsAll(Collection c) { E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end = toLoc(array); for (Object each : c) { if (Arrays.binarySearch(array, start, end, (E) each, comparator) < 0) { return false; } } return true; } @Override @SuppressWarnings("unchecked") public boolean remove(Object o) { return checkInBounds((E) o) && super.remove(o); } @Override public void clear() { synchronized(al.lock) { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end = toLoc(array); al.removeRange(start, end); } } @SuppressWarnings("unchecked") private int fromLoc(E[] array) { int start; if(lowerBounded) { start = Arrays.binarySearch(array, lowerBound, comparator == null ? descending ? (Comparator) Comparator.reverseOrder() : null : descending ? comparator.reversed() : comparator); start = start >= 0 ? lowerInclusive ? start : start + 1 : -1 - start; } else { start = 0; } return start; } @SuppressWarnings("unchecked") private int toLoc(E[] array) { int end; if(upperBounded) { end = Arrays.binarySearch(array, upperBound, descending ? comparator.reversed() : comparator); end = end >= 0 ? upperInclusive ? end + 1 : end : -1 - end; } else { end = array.length; } return end; } @Override public T[] toArray(T[] a) { return makeArray(a, descending); } @SuppressWarnings("unchecked") public T[] makeArray(T[] a, boolean inDescending) { E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end = toLoc(array); int len = end - start; if (a.length < len) { a = (T[]) Array.newInstance(a.getClass().getComponentType(), len); } System.arraycopy(array, start, a, 0, len); if(len < a.length) a[len] = null; if(inDescending) Collections.reverse(Arrays.asList(a).subList(0, len)); return a; } @Override public Object[] toArray() { return makeArray(new Object[0], descending); } @Override public Iterator iterator() { return makeIterator(descending); } @SuppressWarnings("unchecked") private Iterator makeIterator(boolean inDescending) { List asList; if(inDescending) { asList = Arrays.asList((E[]) makeArray(new Object[0], inDescending)); } else { E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end = toLoc(array); asList = Arrays.asList(array).subList(start, end); } return Collections.unmodifiableList(asList).iterator(); } @Override public int size() { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); return toLoc(array) - fromLoc(array); } @Override @SuppressWarnings("unchecked") public E lower(E e) { E result = descending ? super.higher(e) : super.lower(e); return result != null && checkInBounds(result) ? result : null; } @Override @SuppressWarnings("unchecked") public E floor(E e) { E result = descending ? super.ceiling(e) : super.floor(e); return result != null && checkInBounds(result) ? result : null; } @Override @SuppressWarnings("unchecked") public E ceiling(E e) { E result = descending ? super.floor(e) : super.ceiling(e); return result != null && checkInBounds(result) ? result : null; } @Override @SuppressWarnings("unchecked") public E higher(E e) { E result = descending ? super.lower(e) : super.higher(e); return result != null && checkInBounds(result) ? result : null; } @Override public E pollFirst() { return descending ? doPollLast() : doPollFirst(); } private E doPollFirst() { if(lowerBounded) synchronized(al.lock) { E remove = lowerInclusive ? floor(lowerBound) : higher(lowerBound); if(null != remove) { super.remove(remove); } return remove; } else return super.pollFirst(); } @Override public E pollLast() { return descending ? doPollFirst() : doPollLast(); } private E doPollLast() { if(upperBounded) synchronized(al.lock) { E remove = upperInclusive ? floor(upperBound) : lower(upperBound); if(null != remove) { super.remove(remove); } return remove; } else return super.pollLast(); } @Override public E first() { return descending ? doLast() : doFirst(); } private E doFirst() { E result = lowerInclusive ? ceiling(lowerBound) : higher(lowerBound); if(null == result) { throw new NoSuchElementException(); } return result; } @Override public E last() { return descending ? doFirst() : doLast(); } private E doLast() { E result = upperInclusive ? floor(upperBound) : lower(upperBound); if(null == result) { throw new NoSuchElementException(); } return result; } @Override public Spliterator spliterator() { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); return Spliterators.spliterator( array, fromLoc(array), toLoc(array), Spliterator.ORDERED | Spliterator.NONNULL | Spliterator.IMMUTABLE | Spliterator.DISTINCT); } } }


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

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

Re: RFR: CopyOnWriteArrayNavigableSet for Java 9

Jason Mehrens
In reply to this post by Mike Duigou
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

________________________________________
From: [hidden email] <[hidden email]> on behalf of Mike Duigou <[hidden email]>
Sent: Wednesday, December 30, 2015 4:53 PM
To: Concurrency Interest
Subject: [concurrency-interest] RFR: CopyOnWriteArrayNavigableSet for Java 9

Hello All;

Enclosed is a new draft of the CopyOnWriteArrayNavigableSet
implementation I have been working on for Java 9. This version
incorporates review feedback from November and should be very nearly
complete and ready for submission. It is not to late to provide feedback
though, so if you have any comments or suggestions feel free to send
them to this list.

I am planning to post a standalone version of this class on github and
probably will publish it as a maven package for use with Java 7 and Java
8. This version will have he same class name and API but will be in a
different package.

Cheers,

Mike

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

Re: RFR: CopyOnWriteArrayNavigableSet for Java 9

Mike Duigou
In reply to this post by Mike Duigou
Jason Mehrens <[hidden email]> 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
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: RFR: CopyOnWriteArrayNavigableSet for Java 9

Jason Mehrens
Agreed.  In the BoundedNavigableSet constructor the "inconsistent comparator" message could be replaced with the same TimSort message.  I always wished that TimSort message included the comparator class and the types of both arguments.  However, I agree with your approach of just using the exact message.

Jason

________________________________________
From: [hidden email] <[hidden email]> on behalf of Mike Duigou <[hidden email]>
Sent: Thursday, December 31, 2015 2:21 PM
To: [hidden email]
Subject: Re: [concurrency-interest] RFR: CopyOnWriteArrayNavigableSet for       Java 9

Jason Mehrens <[hidden email]> 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
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

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