[concurrency-interest] COWList snapshot.

Martin Buchholz martinrb at google.com
Fri Feb 21 18:44:45 EST 2014


v 0.2

Amazing how much immutability simplifies the life of a collections
implementer.

Index: src/main/java/util/concurrent/CopyOnWriteArrayList.java
===================================================================
RCS file:
/export/home/jsr166/jsr166/jsr166/src/main/java/util/concurrent/CopyOnWriteArrayList.java,v
retrieving revision 1.115
diff -u -r1.115 CopyOnWriteArrayList.java
--- src/main/java/util/concurrent/CopyOnWriteArrayList.java 31 Jan 2014
17:58:35 -0000 1.115
+++ src/main/java/util/concurrent/CopyOnWriteArrayList.java 21 Feb 2014
23:42:02 -0000
@@ -1628,6 +1628,104 @@
         }
     }

+    // Support for read-only snapshots
+
+    /**
+     * Returns an immutable list snapshot of this list.
+     * @return an immutable list snapshot of this list
+     */
+    public List<E> snapshot() {
+        return new Snapshot<E>(getArray());
+    }
+
+    @SuppressWarnings("unchecked")
+    private static class Snapshot<E> extends AbstractList<E>
+        implements RandomAccess {
+        private final Object[] elements;
+        public Snapshot(Object[] elements) { this.elements = elements; }
+        @Override public E get(int index) { return (E) elements[index]; }
+        @Override public int size() { return elements.length; }
+        @Override public Object[] toArray() { return elements.clone(); }
+        @Override  public <T> T[] toArray(T[] a) {
+            final int size = size();
+            if (a.length < size)
+                return (T[]) Arrays.copyOf(elements, size, a.getClass());
+            System.arraycopy(elements, 0, a, 0, size);
+            if (a.length > size)
+                a[size] = null;
+            return a;
+        }
+        @Override public int indexOf(Object o) {
+            final int size = size();
+            if (o == null) {
+                for (int i = 0; i < size; i++)
+                    if (elements[i] == null)
+                        return i;
+            } else {
+                for (int i = 0; i < size; i++)
+                    if (o.equals(elements[i]))
+                        return i;
+            }
+            return -1;
+        }
+        @Override public int lastIndexOf(Object o) {
+            final int size = size();
+            if (o == null) {
+                for (int i = size - 1; i >= 0; i++)
+                    if (elements[i] == null)
+                        return i;
+            } else {
+                for (int i = size - 1; i >= 0; i++)
+                    if (o.equals(elements[i]))
+                        return i;
+            }
+            return -1;
+        }
+        @Override public boolean contains(Object o) {
+            final int size = size();
+            if (o == null) {
+                for (int i = 0; i < size; i++)
+                    if (elements[i] == null)
+                        return true;
+            } else {
+                for (int i = 0; i < size; i++)
+                    if (o.equals(elements[i]))
+                        return true;
+            }
+            return false;
+        }
+        @Override public Iterator<E> iterator() { return new Itr(0); }
+        @Override public ListIterator<E> listIterator() { return new
Itr(0); }
+        @Override public ListIterator<E> listIterator(int index) { return
new Itr(index); }
+
+        private class Itr implements ListIterator<E> {
+            private int cursor;
+            private int lastRet = -1;
+            Itr(int cursor) { this.cursor = cursor; }
+            @Override public boolean hasNext() { return cursor < size(); }
+            @Override public boolean hasPrevious() { return cursor > 0; }
+            @Override public int nextIndex() { return cursor; }
+            @Override public int previousIndex() { return cursor - 1; }
+            @Override public E next() {
+                if (!hasNext()) throw new NoSuchElementException();
+                return (E) elements[lastRet = ++cursor];
+            }
+            @Override public E previous() {
+                if (!hasPrevious()) throw new NoSuchElementException();
+                return (E) elements[lastRet = --cursor];
+            }
+            @Override public void set(E e) {
+                throw new UnsupportedOperationException();
+            }
+            @Override public void add(E e) {
+                throw new UnsupportedOperationException();
+            }
+            @Override public void remove() {
+                throw new UnsupportedOperationException();
+            }
+        }
+    }
+
     // Support for resetting lock while deserializing
     private void resetLock() {
         UNSAFE.putObjectVolatile(this, lockOffset, new ReentrantLock());



On Fri, Feb 21, 2014 at 3:17 PM, Jason Mehrens <jason_mehrens at hotmail.com>wrote:

> Martin,
> Looks correct. Since the snapshot can't change I assume it should
> implement RandomAccess? Maybe override iterator() and listIterator() to
> return COWIterator for fun and profit?
> As Henri pointed out, you can use
> Collections.unmodifiableList(Arrays.asList(getArray())). Arrays.asList
> doesn't perform any safe coping of the input array.
>
> Jason
> ________________________________
> > Date: Fri, 21 Feb 2014 12:12:14 -0800
> > Subject: Re: [concurrency-interest] COWList snapshot.
> > From: martinrb at google.com
> > To: ppozerov at gmail.com
> > CC: jason_mehrens at hotmail.com; concurrency-interest at cs.oswego.edu
> >
> > The v0.1 implementation was surprisingly easy:
> >
> > Index: src/main/java/util/concurrent/CopyOnWriteArrayList.java
> > ===================================================================
> > RCS file:
> >
> /export/home/jsr166/jsr166/jsr166/src/main/java/util/concurrent/CopyOnWriteArrayList.java,v
> > retrieving revision 1.115
> > diff -u -r1.115 CopyOnWriteArrayList.java
> > --- src/main/java/util/concurrent/CopyOnWriteArrayList.java 31 Jan 2014
> > 17:58:35 -0000 1.115
> > +++ src/main/java/util/concurrent/CopyOnWriteArrayList.java 21 Feb 2014
> > 20:10:39 -0000
> > @@ -1644,4 +1644,22 @@
> > throw new Error(e);
> > }
> > }
> > +
> > + // Support for read-only snapshots
> > + /**
> > + * Returns an immutable list snapshot of this list.
> > + * @return an immutable list snapshot of this list
> > + */
> > + public List<E> snapshot() {
> > + return new Snapshot<E>(getArray());
> > + }
> > +
> > + @SuppressWarnings("unchecked")
> > + private static class Snapshot<E> extends AbstractList<E> {
> > + private final Object[] elements;
> > + public Snapshot(Object[] elements) { this.elements = elements; }
> > + @Override public E get(int index) { return (E) elements[index]; }
> > + @Override public int size() { return elements.length; }
> > + @Override public Object[] toArray() { return elements.clone(); }
> > + }
> > }
> >
> >
> >
> > On Fri, Feb 21, 2014 at 11:41 AM, Martin Buchholz
> > <martinrb at google.com<mailto:martinrb at google.com>> wrote:
> > Summary: I support Владимир's suggestion of creating
> > COWAList.snapshot(). I'm the obvious person to implement that, and I
> > hope to do so sometime during jdk9 development.
> >
> >
> >
> > On Wed, Feb 19, 2014 at 11:55 AM, Martin Buchholz
> > <martinrb at google.com<mailto:martinrb at google.com>> wrote:
> > Владимир,
> >
> > I agree that a snapshot method as you propose would be useful. As
> > always, implementing the List interface ends up being rather a lot of
> > tedious work, which may be a reason it never got done.
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20140221/dccb8df8/attachment-0001.html>


More information about the Concurrency-interest mailing list