[concurrency-interest] ReadMostlyVector ListIterator bug

Stanimir Simeonoff stanimir at riflexo.com
Sun Aug 12 15:33:17 EDT 2012


ReadMostlyVector contains a bug in the iterator logic if previous() and
next() are used together.
Below there is a simple test case to reproduce the behavior. The problem is
that validNext and validPrev are not cleared if the iterator is used in
both directions simultaneously. While it's rare behavior to do so, it's
useful to look for an element and return previous/next.
Another side effect is that calling hasPrevious/hasNext may keep reference
(leak) an already removed object but I presume that's ok even for large
lists.

public class RMTest {
    public static void main(String[] args) {
        testList(new jsr166e.extra.ReadMostlyVector<Integer>());
        testList(new java.util.ArrayList<Integer>());
        testList(new java.util.Vector<Integer>());

    }
    private static void testList(java.util.List<Integer> v) {
        out("Testing: "+v.getClass().getName());
        v.add(1);v.add(2);v.add(3);v.add(4);
        ListIterator<Integer> i = v.listIterator();
        out(i.next());
        i.hasPrevious();//ReadMostlyVector remembers the prev value here
        out(i.next());
        out(i.next());
        out(i.previous());//must be 3, not 1 for ReadMostlyVector
    }
    static void out(Object n){
        System.out.println(n);
    }
}

Testing: jsr166e.extra.ReadMostlyVector
1
2
3
1
Testing: java.util.ArrayList
1
2
3
3
Testing: java.util.Vector
1
2
3
3
===================================

Fixing is simple by clearing the flags:
        public E next() {
            if (validNext || hasNext()) {
                *validNext = validPrev = false;**
*                lastRet = cursor++;
                return next;
            }
            throw new NoSuchElementException();
        }

        public E previous() {
            if (validPrev || hasPrevious()) {
                *validNext = validPrev = false;*
                lastRet = cursor--;
                return prev;
            }
            throw new NoSuchElementException();
        }
SubItr methods need the same code
___
Testing: jsr166e.extra.ReadMostlyVector
1
2
3
3
Testing: java.util.ArrayList
1
2
3
3
Testing: java.util.Vector
1
2
3
3
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20120812/da9b9552/attachment.html>


More information about the Concurrency-interest mailing list