[concurrency-interest] Descending Iterator on ConcurrentSkipListSet is skipping 2 elements after one changed

Doug Lea dl at cs.oswego.edu
Sun Feb 19 10:58:28 EST 2012


On 02/19/12 10:42, serge masse wrote:
> Using jsr166x.jar from Feb. 11, 2012, in an Android app with latest SDK. This
> happens on a device with Android 2.2 and in an emulator with Android 2.3.1. The
> jar is at the top of the Java Build Path library list in Eclipse.
>
> Tested with a ConcurrentSkipListSet with 5 objects. The first use of the
> Iterator is fine, then one object is changed (i.e., one of the values used in
> the comparator is changed), then on the second pass the descending iterator is
> not showing the changed object and one next to it. Similar code using the
> ascending iterator does not have this behavior.

Comparators in all java.util.* collections are required to be idempotent,
but yours appears not to be -- its value can change asynchronously
(in a way that no data structure could cope with).

As a separate issue though, we haven't reconciled the old jsr166x
source with Java6+ in a while. We'll do this.

-Doug



>
> The output:
>
> testDesc first pass:
> a5 0
> a4 0
> a3 0
> a2 0
> a1 0
> testDesc *a3.a.incrementAndGet()*
> testDesc second pass:
> a5 0
> a2 0
> a1 0
>
>
> testAsc first pass:
> a1 0
> a2 0
> a3 0
> a4 0
> a5 0
> testAsc *a3.a.incrementAndGet()*
> testAsc second pass:
> a1 0
> a2 0
> a3 1
> a4 0
> a5 0
>
>
> The code:
>
> private class Testob {
> public volatile String id = "0";
> public final AtomicInteger a = new AtomicInteger(0);
> }
>
> /** the signal with the most hits is ranked ahead. */
> private static final Comparator<Testob> TESTOB_COMPARATOR = new
> Comparator<Testob>(){
> public int compare(Testob arg0, Testob arg1) {
> final int a0 = arg0.a.get();
> final int a1 = arg1.a.get();
> if(a0 == a1){
> return arg0.id.compareTo(arg1.id);
> }
> if(a0 < a1)return -1;
> return 1;
> }
> };
> /**
> * ordered by a
> */
> static final ConcurrentSkipListSet<Testob> TEST_OBS_DESC =
> new ConcurrentSkipListSet<Testob>(TESTOB_COMPARATOR);
> static final ConcurrentSkipListSet<Testob> TEST_OBS_ASC =
> new ConcurrentSkipListSet<Testob>(TESTOB_COMPARATOR);
>
> private void test(){
> testDesc();
> testAsc();
> }
> private void testDesc(){
> //create instances
> Testob a1 = new Testob();
> a1.id="a1";
> Testob a2 = new Testob();
> a2.id="a2";
> Testob a3 = new Testob();
> a3.id="a3";
> Testob a4 = new Testob();
> a4.id="a4";
> Testob a5 = new Testob();
> a5.id="a5";
> TEST_OBS_DESC.add(a1);
> TEST_OBS_DESC.add(a2);
> TEST_OBS_DESC.add(a3);
> TEST_OBS_DESC.add(a4);
> TEST_OBS_DESC.add(a5);
> //get descending iterator and list ids
> Log.d("testob","testDesc first pass:");
> Iterator<Testob> it1 = TEST_OBS_DESC.descendingIterator();
> while(it1.hasNext()){
> Testob ob = it1.next();
> Log.d("testob",ob.id+" "+ob.a.get());
> }
> //inc a for one
> Log.d("testob","testDesc *a3.a.incrementAndGet()*");
> a3.a.incrementAndGet();
> //get descending iterator and list ids
> Log.d("testob","testDesc second pass:");
> Iterator<Testob> it2 = TEST_OBS_DESC.descendingIterator();
> while(it2.hasNext()){
> Testob ob = it2.next();
> Log.d("testob",ob.id+" "+ob.a.get());
> }
> }
>
> private void testAsc(){
> //create instances
> Testob a1 = new Testob();
> a1.id="a1";
> Testob a2 = new Testob();
> a2.id="a2";
> Testob a3 = new Testob();
> a3.id="a3";
> Testob a4 = new Testob();
> a4.id="a4";
> Testob a5 = new Testob();
> a5.id="a5";
> TEST_OBS_ASC.add(a1);
> TEST_OBS_ASC.add(a2);
> TEST_OBS_ASC.add(a3);
> TEST_OBS_ASC.add(a4);
> TEST_OBS_ASC.add(a5);
> //get descending iterator and list ids
> Log.d("testob","testAsc first pass:");
> Iterator<Testob> it1 = TEST_OBS_ASC.iterator();
> while(it1.hasNext()){
> Testob ob = it1.next();
> Log.d("testob",ob.id+" "+ob.a.get());
> }
> //inc a for one
> Log.d("testob","testAsc *a3.a.incrementAndGet()*");
> a3.a.incrementAndGet();
> //get descending iterator and list ids
> Log.d("testob","testAsc second pass:");
> Iterator<Testob> it2 = TEST_OBS_ASC.iterator();
> while(it2.hasNext()){
> Testob ob = it2.next();
> Log.d("testob",ob.id+" "+ob.a.get());
> }
> }
>
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest



More information about the Concurrency-interest mailing list