TreeMap.navigableKeySet().descendingIterator() sequence ?
Been looking at TreeMap's implementation rather closely and observed something I don't understand. %-) TreeMap (as of JDK 6 and later) implements NavigableMap. NavigableMap requires an implementation of a navigableKeySet() method which returns a NavigableSet<K>. So, in TreeMap I see: public NavigableSet<K> navigableKeySet() Then, the NavigableSet interface has an Iterator<E> descendingIterator() and Iterator<E>iterator(). The former returns an iterator over the elements in descending order. The latter in ascending order. I also noticed in TreeMap, NavigableMap requires an implementation of a descendingKeySet(), i.e. public NavigableSet<K> descendingKeySet(). Again, the NavigableSet interface has an Iterator<E> descendingIterator() and iterator() as described above. When I populate a TreeMap with some dummy data, let's say I populate it with 15 Integer keys and String's representing those Integer keys as values, I observe something I don't understand when using the navigableKeySet().descendingIterator(). When, I try to iterate over the returned NavigableKeySet, I see the lowest key printed and that's it. Nothing else prints. From looking at the JavaDoc for TreeMap and NavigableSet, this doesn't seem right. Shouldn't it iterate over the entire set in descending order? I looked at the source and it creates an Iterator that starts at the lowest key and then tries to find the next lowest key (which obviously doesn't exist). Am I not reading something right in the JavaDoc? When iterating using navigableKeySet().iterator() I see all 15 keys printed in ascending order, (as expected). When I iterate with descendingKeySet().descendingIterator() I see the 15 keys printed in ascending order, (as expected since descending set followed by a descending iterator should give me ascending order). When iterating using descendingKeySet().iterator, I see the 15 keys printed in descending order, (as expected). I've attached a very simple program that illustrates what I'm describing. Could someone clarify this behavior? thanks, charlie ...
Wow. TreeMap.java line 1024: return new DescendingKeyIterator(getFirstEntry()); Sure does look fishy. On Thu, Apr 17, 2008 at 2:54 PM, charlie hunt <charlie.hunt@sun.com> wrote:
Been looking at TreeMap's implementation rather closely and observed something I don't understand. %-)
TreeMap (as of JDK 6 and later) implements NavigableMap. NavigableMap requires an implementation of a navigableKeySet() method which returns a NavigableSet<K>. So, in TreeMap I see:
public NavigableSet<K> navigableKeySet()
Then, the NavigableSet interface has an Iterator<E> descendingIterator() and Iterator<E>iterator(). The former returns an iterator over the elements in descending order. The latter in ascending order.
I also noticed in TreeMap, NavigableMap requires an implementation of a descendingKeySet(), i.e. public NavigableSet<K> descendingKeySet(). Again, the NavigableSet interface has an Iterator<E> descendingIterator() and iterator() as described above.
When I populate a TreeMap with some dummy data, let's say I populate it with 15 Integer keys and String's representing those Integer keys as values, I observe something I don't understand when using the navigableKeySet().descendingIterator().
When, I try to iterate over the returned NavigableKeySet, I see the lowest key printed and that's it. Nothing else prints. From looking at the JavaDoc for TreeMap and NavigableSet, this doesn't seem right. Shouldn't it iterate over the entire set in descending order? I looked at the source and it creates an Iterator that starts at the lowest key and then tries to find the next lowest key (which obviously doesn't exist). Am I not reading something right in the JavaDoc?
When iterating using navigableKeySet().iterator() I see all 15 keys printed in ascending order, (as expected).
When I iterate with descendingKeySet().descendingIterator() I see the 15 keys printed in ascending order, (as expected since descending set followed by a descending iterator should give me ascending order).
When iterating using descendingKeySet().iterator, I see the 15 keys printed in descending order, (as expected).
I've attached a very simple program that illustrates what I'm describing.
Could someone clarify this behavior?
thanks,
charlie ...
-- Kevin Bourrillion @ Google internal: go/javalibraries google-collections.googlecode.com google-guice.googlecode.com
Yes, sad to say, looks like a serious and embarrassing bug. This bit of code has no existing test case. More tests should be added to MOAT.java. Charlie, please file a bug. In our defense, there are very many methods in the NavigableFoo interfaces, and for completeness they have to be tested on subsets and submaps, and Sun engineers have not historically had good code coverage tool support. Martin On Fri, Apr 18, 2008 at 2:39 PM, kevin bourrillion <kevinb@google.com> wrote:
Wow. TreeMap.java line 1024:
return new DescendingKeyIterator(getFirstEntry());
Sure does look fishy.
On Thu, Apr 17, 2008 at 2:54 PM, charlie hunt <charlie.hunt@sun.com> wrote:
Been looking at TreeMap's implementation rather closely and observed something I don't understand. %-)
TreeMap (as of JDK 6 and later) implements NavigableMap. NavigableMap requires an implementation of a navigableKeySet() method which returns a NavigableSet<K>. So, in TreeMap I see:
public NavigableSet<K> navigableKeySet()
Then, the NavigableSet interface has an Iterator<E> descendingIterator() and Iterator<E>iterator(). The former returns an iterator over the elements in descending order. The latter in ascending order.
I also noticed in TreeMap, NavigableMap requires an implementation of a descendingKeySet(), i.e. public NavigableSet<K> descendingKeySet(). Again, the NavigableSet interface has an Iterator<E> descendingIterator() and iterator() as described above.
When I populate a TreeMap with some dummy data, let's say I populate it with 15 Integer keys and String's representing those Integer keys as values, I observe something I don't understand when using the navigableKeySet().descendingIterator().
When, I try to iterate over the returned NavigableKeySet, I see the lowest key printed and that's it. Nothing else prints. From looking at the JavaDoc for TreeMap and NavigableSet, this doesn't seem right. Shouldn't it iterate over the entire set in descending order? I looked at the source and it creates an Iterator that starts at the lowest key and then tries to find the next lowest key (which obviously doesn't exist). Am I not reading something right in the JavaDoc?
When iterating using navigableKeySet().iterator() I see all 15 keys printed in ascending order, (as expected).
When I iterate with descendingKeySet().descendingIterator() I see the 15 keys printed in ascending order, (as expected since descending set followed by a descending iterator should give me ascending order).
When iterating using descendingKeySet().iterator, I see the 15 keys printed in descending order, (as expected).
I've attached a very simple program that illustrates what I'm describing.
Could someone clarify this behavior?
thanks,
charlie ...
-- Kevin Bourrillion @ Google internal: go/javalibraries google-collections.googlecode.com google-guice.googlecode.com
I'll file a bug. I'll also suggest in the bug report additional tests be added to MOAT.java. You are right, there are very many Navigable* interface methods ("very many" doesn't seem to do justice to describe the number of methods). TreeMap is rather complex beast! It's complexity really increased between Java 5 and Java 6. In looking at TreeMap closely over the last week, writing a complete suite of tests for TreeMap would be lengthy and difficult task. It's easy to see how this bug could have slipped through. Looks like the fix is changing TreeMap line 1024, from "return DescendingKeyIterator(getFirstEntry())" to "return DescendingKeyIterator(getLastEntry())". thanks, charlie ... Martin Buchholz wrote:
Yes, sad to say, looks like a serious and embarrassing bug. This bit of code has no existing test case. More tests should be added to MOAT.java. Charlie, please file a bug.
In our defense, there are very many methods in the NavigableFoo interfaces, and for completeness they have to be tested on subsets and submaps, and Sun engineers have not historically had good code coverage tool support.
Martin
On Fri, Apr 18, 2008 at 2:39 PM, kevin bourrillion <kevinb@google.com <mailto:kevinb@google.com>> wrote:
Wow. TreeMap.java line 1024:
return new DescendingKeyIterator(getFirstEntry());
Sure does look fishy.
On Thu, Apr 17, 2008 at 2:54 PM, charlie hunt <charlie.hunt@sun.com <mailto:charlie.hunt@sun.com>> wrote: > Been looking at TreeMap's implementation rather closely and observed > something I don't understand. %-) > > TreeMap (as of JDK 6 and later) implements NavigableMap. NavigableMap > requires an implementation of a navigableKeySet() method which returns a > NavigableSet<K>. So, in TreeMap I see: > > public NavigableSet<K> navigableKeySet() > > Then, the NavigableSet interface has an Iterator<E> descendingIterator() > and Iterator<E>iterator(). The former returns an iterator over the elements > in descending order. The latter in ascending order. > > I also noticed in TreeMap, NavigableMap requires an implementation of a > descendingKeySet(), i.e. public NavigableSet<K> descendingKeySet(). Again, > the NavigableSet interface has an Iterator<E> descendingIterator() and > iterator() as described above. > > When I populate a TreeMap with some dummy data, let's say I populate it > with 15 Integer keys and String's representing those Integer keys as values, > I observe something I don't understand when using the > navigableKeySet().descendingIterator(). > > When, I try to iterate over the returned NavigableKeySet, I see the lowest > key printed and that's it. Nothing else prints. From looking at the JavaDoc > for TreeMap and NavigableSet, this doesn't seem right. Shouldn't it iterate > over the entire set in descending order? I looked at the source and it > creates an Iterator that starts at the lowest key and then tries to find the > next lowest key (which obviously doesn't exist). Am I not reading something > right in the JavaDoc? > > When iterating using navigableKeySet().iterator() I see all 15 keys printed > in ascending order, (as expected). > > When I iterate with descendingKeySet().descendingIterator() I see the 15 > keys printed in ascending order, (as expected since descending set followed > by a descending iterator should give me ascending order). > > When iterating using descendingKeySet().iterator, I see the 15 keys printed > in descending order, (as expected). > > I've attached a very simple program that illustrates what I'm describing. > > Could someone clarify this behavior? > > thanks, > > charlie ... > >
-- Kevin Bourrillion @ Google internal: go/javalibraries google-collections.googlecode.com <http://google-collections.googlecode.com> google-guice.googlecode.com <http://google-guice.googlecode.com>
-- Charlie Hunt Java Performance Engineer <http://java.sun.com/docs/performance/>
Martin Buchholz wrote:
Yes, sad to say, looks like a serious and embarrassing bug.
And dumb! "First" => "Last" on line 1024. Ugh.
This bit of code has no existing test case.
Well, it did, but that TCK test only checked that elements were in order, not that #elements == size. Now it does.
Charlie, please file a bug.
We can use this as a good test case to find out if we can quickly get a one line fix committed. Martin? -Doug
I'll take care of making a fix. Patch to follow. Martin On Sat, Apr 19, 2008 at 8:12 AM, Doug Lea <dl@cs.oswego.edu> wrote:
Martin Buchholz wrote:
Yes, sad to say, looks like a serious and embarrassing bug.
And dumb! "First" => "Last" on line 1024. Ugh.
This bit of code has no existing test case.
Well, it did, but that TCK test only checked that elements were in order, not that #elements == size. Now it does.
Charlie, please file a bug.
We can use this as a good test case to find out if we can quickly get a one line fix committed. Martin?
-Doug
Below is the proposed patch. We had alredy been testing m.descendingKeySet().iterator() but not the equivalent m.navigableKeySet().descendingIterator() which goes down a different code path. To get this into the JDK, we will need: 1. Review from Doug (or some other person empowered to do so) 2. Bug creation from Charlie (or some other person empowered to do so) I suggest making this bug P2-S2. I will need the bug id and synopsis to create the proper mercurial comment. 3. Someone at Sun will need to backport this to JDK 6. It's time to appoint a Sun engineer to the Collections/Concurrency area for tasks such as this. (I would have used webrev if that was publically available, and there was a place to store it) The added tests are rather more than strictly necessary to expose the bug, but that's no defect. diff --git a/src/share/classes/java/util/TreeMap.java b/src/share/classes/java/util/TreeMap.java --- a/src/share/classes/java/util/TreeMap.java +++ b/src/share/classes/java/util/TreeMap.java @@ -1021,7 +1021,7 @@ public class TreeMap<K,V> } Iterator<K> descendingKeyIterator() { - return new DescendingKeyIterator(getFirstEntry()); + return new DescendingKeyIterator(getLastEntry()); } static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> { diff --git a/test/java/util/Collection/MOAT.java b/test/java/util/Collection/MOAT.java --- a/test/java/util/Collection/MOAT.java +++ b/test/java/util/Collection/MOAT.java @@ -155,7 +155,7 @@ public class MOAT { check(c.containsAll(new ArrayList<Integer>())); } - private static void testEmptyCollection(Collection<?> c) { + private static <T> void testEmptyCollection(Collection<T> c) { check(c.isEmpty()); equal(c.size(), 0); equal(c.toString(),"[]"); @@ -165,6 +165,23 @@ public class MOAT { Object[] a = new Object[1]; a[0] = Boolean.TRUE; equal(c.toArray(a), a); equal(a[0], null); + testEmptyIterator(c.iterator()); + } + + static <T> void testEmptyIterator(final Iterator<T> it) { + if (rnd.nextBoolean()) + check(! it.hasNext()); + + THROWS(NoSuchElementException.class, + new Fun(){void f(){ it.next(); }}); + + try { it.remove(); } + catch (IllegalStateException _) { pass(); } + catch (UnsupportedOperationException _) { pass(); } + catch (Throwable t) { unexpected(t); } + + if (rnd.nextBoolean()) + check(! it.hasNext()); } private static void testEmptyList(List<?> c) { @@ -173,10 +190,12 @@ public class MOAT { equal2(c, Collections.<Integer>emptyList()); } - private static void testEmptySet(Set<?> c) { + private static <T> void testEmptySet(Set<T> c) { testEmptyCollection(c); equal(c.hashCode(), 0); equal2(c, Collections.<Integer>emptySet()); + if (c instanceof NavigableSet<?>) + testEmptyIterator(((NavigableSet<T>)c).descendingIterator()); } private static void testImmutableCollection(final Collection<Integer> c) { @@ -221,7 +240,7 @@ public class MOAT { testEmptyCollection(c); } - private static void testEmptyMap(final Map<?,?> m) { + private static <K,V> void testEmptyMap(final Map<K,V> m) { check(m.isEmpty()); equal(m.size(), 0); equal(m.toString(),"{}"); @@ -433,8 +452,18 @@ public class MOAT { if (! supportsAdd(c)) return; //System.out.println("add() supported"); - if (c instanceof NavigableSet) - testNavigableSet((NavigableSet<Integer>)c); + if (c instanceof NavigableSet) { + System.out.println("NavigableSet tests..."); + + NavigableSet<Integer> ns = (NavigableSet<Integer>)c; + testNavigableSet(ns); + testNavigableSet(ns.headSet(6, false)); + testNavigableSet(ns.headSet(5, true)); + testNavigableSet(ns.tailSet(0, false)); + testNavigableSet(ns.tailSet(1, true)); + testNavigableSet(ns.subSet(0, false, 5, true)); + testNavigableSet(ns.subSet(1, true, 6, false)); + } if (c instanceof Queue) testQueue((Queue<Integer>)c); @@ -514,8 +543,19 @@ public class MOAT { if (m instanceof ConcurrentMap) testConcurrentMap((ConcurrentMap<Integer,Integer>) m); - if (m instanceof NavigableMap) - testNavigableMap((NavigableMap<Integer,Integer>) m); + if (m instanceof NavigableMap) { + System.out.println("NavigableMap tests..."); + + NavigableMap<Integer,Integer> nm = + (NavigableMap<Integer,Integer>) m; + testNavigableMap(nm); + testNavigableMap(nm.headMap(6, false)); + testNavigableMap(nm.headMap(5, true)); + testNavigableMap(nm.tailMap(0, false)); + testNavigableMap(nm.tailMap(1, true)); + testNavigableMap(nm.subMap(1, true, 6, false)); + testNavigableMap(nm.subMap(0, false, 5, true)); + } checkFunctionalInvariants(m); @@ -697,8 +737,6 @@ public class MOAT { private static void testNavigableMap(NavigableMap<Integer,Integer> m) { - System.out.println("NavigableMap tests..."); - clear(m); checkNavigableMapKeys(m, 1, null, null, null, null); @@ -717,9 +755,11 @@ public class MOAT { checkNavigableMapKeys(m, 5, 3, 5, 5, null); checkNavigableMapKeys(m, 6, 5, 5, null, null); - { - final Iterator<Integer> it - = m.descendingKeySet().iterator(); + for (final Iterator<Integer> it : + (Iterator<Integer>[]) + new Iterator<?>[] { + m.descendingKeySet().iterator(), + m.navigableKeySet().descendingIterator()}) { equalNext(it, 5); equalNext(it, 3); equalNext(it, 1); @@ -742,8 +782,6 @@ public class MOAT { private static void testNavigableSet(NavigableSet<Integer> s) { - System.out.println("NavigableSet tests..."); - clear(s); checkNavigableSetKeys(s, 1, null, null, null, null); @@ -762,8 +800,11 @@ public class MOAT { checkNavigableSetKeys(s, 5, 3, 5, 5, null); checkNavigableSetKeys(s, 6, 5, 5, null, null); - { - final Iterator<Integer> it = s.descendingIterator(); + for (final Iterator<Integer> it : + (Iterator<Integer>[]) + new Iterator<?>[] { + s.descendingIterator(), + s.descendingSet().iterator()}) { equalNext(it, 5); equalNext(it, 3); equalNext(it, 1);
Martin Buchholz wrote:
Below is the proposed patch.
I also checked in the JSR166 TCK improvements I mentioned. (These aren't yet part of openjdk.) And also applied to ConcurrentSkipListMapTest. See http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/test/tck/TreeMapTest... http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/test/tck/ConcurrentS... -Doug
Martin Buchholz wrote:
:
2. Bug creation from Charlie (or some other person empowered to do so) I suggest making this bug P2-S2.
I will need the bug id and synopsis to create the proper mercurial comment.
I don't know if Charlie is online today, but as you seem to be ready to create the change-set, I've created java/classes_util bug: 6691185: (coll) TreeMap.navigableKeySet's descendingIterator method starts at first instead of last entry with a link to this thread. The synopsis can be changed if you want something different. -Alan.
Alan Bateman wrote:
Martin Buchholz wrote:
:
2. Bug creation from Charlie (or some other person empowered to do so) I suggest making this bug P2-S2.
I will need the bug id and synopsis to create the proper mercurial comment.
I don't know if Charlie is online today, but as you seem to be ready to create the change-set, I've created java/classes_util bug:
6691185: (coll) TreeMap.navigableKeySet's descendingIterator method starts at first instead of last entry
with a link to this thread. The synopsis can be changed if you want something different.
-Alan.
Alan, thanks for filing the bug. One less item on my list of things to do. :-) Fwiw, I've looked at Martin's proposed changes. From the familiarity I've gotten with TreeMap over the past week or two, the changes look good to me. charlie ...
Alan, thanks for filing the bug. Charlie, thanks for the review. However, since you are not (yet?) an OpenJDK committer, I will still need an official review from Doug (or Alan?) I noticed there was another test case, NavigableMap/LockStep.java, that "almost" tested the faulty code. I include a change to that test case as well, below (as well as making the test case a little more maintainble). diff --git a/test/java/util/NavigableMap/LockStep.java b/test/java/util/NavigableMap/LockStep.java --- a/test/java/util/NavigableMap/LockStep.java +++ b/test/java/util/NavigableMap/LockStep.java @@ -159,6 +159,7 @@ public class LockStep { Object[] a = new Object[1]; a[0] = Boolean.TRUE; equal(c.toArray(a), a); equal(a[0], null); + check(! c.iterator().hasNext()); } static void testEmptySet(Set<?> c) { @@ -262,6 +263,16 @@ public class LockStep { } } + static void equalIterators(final Iterator<?> it1, + final Iterator<?> it2) { + while (it1.hasNext()) { + if (maybe(2)) + check(it2.hasNext()); + equal(it1.next(), it2.next()); + } + check(! it2.hasNext()); + } + static void equalNavigableSetsLeaf(final NavigableSet s1, final NavigableSet s2) { equal2(s1, s2); @@ -273,6 +284,8 @@ public class LockStep { equal(s1.first(), s2.first()); equal(s1.last(), s2.last()); } + equalIterators(s1.iterator(), s2.iterator()); + equalIterators(s1.descendingIterator(), s2.descendingIterator()); checkNavigableSet(s1); checkNavigableSet(s2); } @@ -493,30 +506,23 @@ public class LockStep { static MapFrobber randomAdder(NavigableMap m) { final Integer k = unusedKey(m); - MapFrobber f; - switch (rnd.nextInt(4)) { - case 0: f = new MapFrobber() {void frob(NavigableMap m) { - equal(m.put(k, k+1), null); - equal(m.get(k), k+1); - if (maybe(4)) { - equal(m.put(k, k+1), k+1); - equal(m.get(k), k+1);}}}; - break; - case 1: f = new MapFrobber() {void frob(NavigableMap m) { - m.descendingMap().put(k, k+1); - equal(m.get(k), k+1);}}; - break; - case 2: f = new MapFrobber() {void frob(NavigableMap m) { - m.tailMap(k,true).headMap(k,true).put(k,k+1);}}; - break; - case 3: f = new MapFrobber() {void frob(NavigableMap m) { - m.tailMap(k,true).headMap(k,true).descendingMap().put(k,k+1);}}; - break; - default: throw new Error(); - } - final MapFrobber ff = f; + final MapFrobber[] randomAdders = { + new MapFrobber() {void frob(NavigableMap m) { + equal(m.put(k, k+1), null); + equal(m.get(k), k+1); + if (maybe(4)) { + equal(m.put(k, k+1), k+1); + equal(m.get(k), k+1);}}}, + new MapFrobber() {void frob(NavigableMap m) { + m.descendingMap().put(k, k+1); + equal(m.get(k), k+1);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.tailMap(k,true).headMap(k,true).put(k,k+1);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.tailMap(k,true).headMap(k,true).descendingMap().put(k,k+1);}} + }; return new MapFrobber() {void frob(NavigableMap m) { - ff.frob(m); + randomAdders[rnd.nextInt(randomAdders.length)].frob(m); if (maybe(2)) equal(m.get(k), k+1); if (maybe(4)) { equal(m.put(k, k+1), k+1); @@ -525,26 +531,19 @@ public class LockStep { static SetFrobber randomAdder(NavigableSet s) { final Integer e = unusedElt(s); - SetFrobber f; - switch (rnd.nextInt(4)) { - case 0: f = new SetFrobber() {void frob(NavigableSet s) { - check(s.add(e));}}; - break; - case 1: f = new SetFrobber() {void frob(NavigableSet s) { - s.descendingSet().add(e);}}; - break; - case 2: f = new SetFrobber() {void frob(NavigableSet s) { - s.tailSet(e,true).headSet(e,true).add(e);}}; - break; - case 3: f = new SetFrobber() {void frob(NavigableSet s) { - s.descendingSet().tailSet(e,true).headSet(e,true).add(e);}}; - break; - default: throw new Error(); - } - final SetFrobber ff = f; + final SetFrobber[] randomAdders = { + new SetFrobber() {void frob(NavigableSet s) { + check(s.add(e));}}, + new SetFrobber() {void frob(NavigableSet s) { + s.descendingSet().add(e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.tailSet(e,true).headSet(e,true).add(e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.descendingSet().tailSet(e,true).headSet(e,true).add(e);}} + }; return new SetFrobber() {void frob(NavigableSet s) { if (maybe(2)) check(! s.contains(e)); - ff.frob(s); + randomAdders[rnd.nextInt(randomAdders.length)].frob(s); if (maybe(2)) check(! s.add(e)); if (maybe(2)) check(s.contains(e));}}; } @@ -605,89 +604,112 @@ public class LockStep { static MapFrobber randomRemover(NavigableMap m) { final Integer k = usedKey(m); - switch (rnd.nextInt(7)) { - default: throw new Error(); - case 0: return new MapFrobber() {void frob(NavigableMap m) { - Map.Entry e = m.firstEntry(); - equal(m.pollFirstEntry(), e); - checkUnusedKey(m, e.getKey());}}; - case 1: return new MapFrobber() {void frob(NavigableMap m) { - Map.Entry e = m.lastEntry(); - equal(m.pollLastEntry(), e); - checkUnusedKey(m, e.getKey());}}; - case 2: return new MapFrobber() {void frob(NavigableMap m) { - check(m.remove(k) != null); - checkUnusedKey(m, k);}}; - case 3: return new MapFrobber() {void frob(NavigableMap m) { - m.subMap(k, true, k, true).clear(); - checkUnusedKey(m, k);}}; - case 4: return new MapFrobber() {void frob(NavigableMap m) { - m.descendingMap().subMap(k, true, k, true).clear(); - checkUnusedKey(m, k);}}; - case 5: return new MapFrobber() {void frob(NavigableMap m) { - final Iterator it = m.keySet().iterator(); - while (it.hasNext()) - if (it.next().equals(k)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, - new Fun(){void f(){ it.remove(); }}); - } - checkUnusedKey(m, k);}}; - case 6: return new MapFrobber() {void frob(NavigableMap m) { - final Iterator<Map.Entry> it = m.entrySet().iterator(); - while (it.hasNext()) - if (it.next().getKey().equals(k)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, remover(it)); - } - checkUnusedKey(m, k);}}; - } + final MapFrobber[] randomRemovers = { + new MapFrobber() {void frob(NavigableMap m) { + Map.Entry e = m.firstEntry(); + equal(m.pollFirstEntry(), e); + checkUnusedKey(m, e.getKey());}}, + new MapFrobber() {void frob(NavigableMap m) { + Map.Entry e = m.lastEntry(); + equal(m.pollLastEntry(), e); + checkUnusedKey(m, e.getKey());}}, + new MapFrobber() {void frob(NavigableMap m) { + check(m.remove(k) != null); + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.subMap(k, true, k, true).clear(); + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.descendingMap().subMap(k, true, k, true).clear(); + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + final Iterator it = m.keySet().iterator(); + while (it.hasNext()) + if (it.next().equals(k)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + final Iterator it = m.navigableKeySet().descendingIterator(); + while (it.hasNext()) + if (it.next().equals(k)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + final Iterator<Map.Entry> it = m.entrySet().iterator(); + while (it.hasNext()) + if (it.next().getKey().equals(k)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, remover(it)); + } + checkUnusedKey(m, k);}}, + }; + + return randomRemovers[rnd.nextInt(randomRemovers.length)]; } static SetFrobber randomRemover(NavigableSet s) { final Integer e = usedElt(s); - switch (rnd.nextInt(7)) { - default: throw new Error(); - case 0: return new SetFrobber() {void frob(NavigableSet s) { - Object e = s.first(); - equal(s.pollFirst(), e); - checkUnusedElt(s, e);}}; - case 1: return new SetFrobber() {void frob(NavigableSet s) { - Object e = s.last(); - equal(s.pollLast(), e); - checkUnusedElt(s, e);}}; - case 2: return new SetFrobber() {void frob(NavigableSet s) { - check(s.remove(e)); - checkUnusedElt(s, e);}}; - case 3: return new SetFrobber() {void frob(NavigableSet s) { - s.subSet(e, true, e, true).clear(); - checkUnusedElt(s, e);}}; - case 4: return new SetFrobber() {void frob(NavigableSet s) { - s.descendingSet().subSet(e, true, e, true).clear(); - checkUnusedElt(s, e);}}; - case 5: return new SetFrobber() {void frob(NavigableSet s) { - final Iterator it = s.iterator(); - while (it.hasNext()) - if (it.next().equals(e)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, - new Fun(){void f(){ it.remove(); }}); - } - checkUnusedElt(s, e);}}; - case 6: return new SetFrobber() {void frob(NavigableSet s) { - final Iterator it = s.descendingSet().iterator(); - while (it.hasNext()) - if (it.next().equals(e)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, - new Fun(){void f(){ it.remove(); }}); - } - checkUnusedElt(s, e);}}; - } + + final SetFrobber[] randomRemovers = { + new SetFrobber() {void frob(NavigableSet s) { + Object e = s.first(); + equal(s.pollFirst(), e); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + Object e = s.last(); + equal(s.pollLast(), e); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + check(s.remove(e)); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.subSet(e, true, e, true).clear(); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.descendingSet().subSet(e, true, e, true).clear(); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + final Iterator it = s.iterator(); + while (it.hasNext()) + if (it.next().equals(e)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + final Iterator it = s.descendingSet().iterator(); + while (it.hasNext()) + if (it.next().equals(e)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + final Iterator it = s.descendingIterator(); + while (it.hasNext()) + if (it.next().equals(e)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedElt(s, e);}} + }; + + return randomRemovers[rnd.nextInt(randomRemovers.length)]; } static void lockStep(NavigableMap m1, Martin On Sat, Apr 19, 2008 at 2:07 PM, charlie hunt <charlie.hunt@sun.com> wrote:
Alan Bateman wrote:
Martin Buchholz wrote:
:
2. Bug creation from Charlie (or some other person empowered to do so) I suggest making this bug P2-S2.
I will need the bug id and synopsis to create the proper mercurial comment.
I don't know if Charlie is online today, but as you seem to be ready to create the change-set, I've created java/classes_util bug:
6691185: (coll) TreeMap.navigableKeySet's descendingIterator method starts at first instead of last entry
with a link to this thread. The synopsis can be changed if you want something different.
-Alan.
Alan, thanks for filing the bug. One less item on my list of things to do. :-)
Fwiw, I've looked at Martin's proposed changes. From the familiarity I've gotten with TreeMap over the past week or two, the changes look good to me.
charlie ...
FWIW, I probably wrote the broken code. I wrote NavigableMap and retrofitted TreeMap. Doug wrote ConcurrentSkipListMap. Sorry 'bout that. Josh On Sat, Apr 19, 2008 at 5:56 PM, Martin Buchholz <martinrb@google.com> wrote:
Alan, thanks for filing the bug.
Charlie, thanks for the review. However, since you are not (yet?) an OpenJDK committer, I will still need an official review from Doug (or Alan?)
I noticed there was another test case, NavigableMap/LockStep.java, that "almost" tested the faulty code.
I include a change to that test case as well, below (as well as making the test case a little more maintainble).
diff --git a/test/java/util/NavigableMap/LockStep.java b/test/java/util/NavigableMap/LockStep.java --- a/test/java/util/NavigableMap/LockStep.java +++ b/test/java/util/NavigableMap/LockStep.java @@ -159,6 +159,7 @@ public class LockStep { Object[] a = new Object[1]; a[0] = Boolean.TRUE; equal(c.toArray(a), a); equal(a[0], null); + check(! c.iterator().hasNext()); }
static void testEmptySet(Set<?> c) { @@ -262,6 +263,16 @@ public class LockStep { } }
+ static void equalIterators(final Iterator<?> it1, + final Iterator<?> it2) { + while (it1.hasNext()) { + if (maybe(2)) + check(it2.hasNext()); + equal(it1.next(), it2.next()); + } + check(! it2.hasNext()); + } + static void equalNavigableSetsLeaf(final NavigableSet s1, final NavigableSet s2) { equal2(s1, s2); @@ -273,6 +284,8 @@ public class LockStep { equal(s1.first(), s2.first()); equal(s1.last(), s2.last()); } + equalIterators(s1.iterator(), s2.iterator()); + equalIterators(s1.descendingIterator(), s2.descendingIterator()); checkNavigableSet(s1); checkNavigableSet(s2); } @@ -493,30 +506,23 @@ public class LockStep {
static MapFrobber randomAdder(NavigableMap m) { final Integer k = unusedKey(m); - MapFrobber f; - switch (rnd.nextInt(4)) { - case 0: f = new MapFrobber() {void frob(NavigableMap m) { - equal(m.put(k, k+1), null); - equal(m.get(k), k+1); - if (maybe(4)) { - equal(m.put(k, k+1), k+1); - equal(m.get(k), k+1);}}}; - break; - case 1: f = new MapFrobber() {void frob(NavigableMap m) { - m.descendingMap().put(k, k+1); - equal(m.get(k), k+1);}}; - break; - case 2: f = new MapFrobber() {void frob(NavigableMap m) { - m.tailMap(k,true).headMap(k,true).put(k,k+1);}}; - break; - case 3: f = new MapFrobber() {void frob(NavigableMap m) { - m.tailMap(k,true).headMap(k,true).descendingMap().put(k,k+1);}}; - break; - default: throw new Error(); - } - final MapFrobber ff = f; + final MapFrobber[] randomAdders = { + new MapFrobber() {void frob(NavigableMap m) { + equal(m.put(k, k+1), null); + equal(m.get(k), k+1); + if (maybe(4)) { + equal(m.put(k, k+1), k+1); + equal(m.get(k), k+1);}}}, + new MapFrobber() {void frob(NavigableMap m) { + m.descendingMap().put(k, k+1); + equal(m.get(k), k+1);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.tailMap(k,true).headMap(k,true).put(k,k+1);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.tailMap(k,true).headMap(k,true).descendingMap().put(k,k+1);}} + }; return new MapFrobber() {void frob(NavigableMap m) { - ff.frob(m); + randomAdders[rnd.nextInt(randomAdders.length)].frob(m); if (maybe(2)) equal(m.get(k), k+1); if (maybe(4)) { equal(m.put(k, k+1), k+1); @@ -525,26 +531,19 @@ public class LockStep {
static SetFrobber randomAdder(NavigableSet s) { final Integer e = unusedElt(s); - SetFrobber f; - switch (rnd.nextInt(4)) { - case 0: f = new SetFrobber() {void frob(NavigableSet s) { - check(s.add(e));}}; - break; - case 1: f = new SetFrobber() {void frob(NavigableSet s) { - s.descendingSet().add(e);}}; - break; - case 2: f = new SetFrobber() {void frob(NavigableSet s) { - s.tailSet(e,true).headSet(e,true).add(e);}}; - break; - case 3: f = new SetFrobber() {void frob(NavigableSet s) { - s.descendingSet().tailSet(e,true).headSet(e,true).add(e);}}; - break; - default: throw new Error(); - } - final SetFrobber ff = f; + final SetFrobber[] randomAdders = { + new SetFrobber() {void frob(NavigableSet s) { + check(s.add(e));}}, + new SetFrobber() {void frob(NavigableSet s) { + s.descendingSet().add(e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.tailSet(e,true).headSet(e,true).add(e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.descendingSet().tailSet(e,true).headSet(e,true).add(e);}} + }; return new SetFrobber() {void frob(NavigableSet s) { if (maybe(2)) check(! s.contains(e)); - ff.frob(s); + randomAdders[rnd.nextInt(randomAdders.length)].frob(s); if (maybe(2)) check(! s.add(e)); if (maybe(2)) check(s.contains(e));}}; } @@ -605,89 +604,112 @@ public class LockStep {
static MapFrobber randomRemover(NavigableMap m) { final Integer k = usedKey(m); - switch (rnd.nextInt(7)) { - default: throw new Error(); - case 0: return new MapFrobber() {void frob(NavigableMap m) { - Map.Entry e = m.firstEntry(); - equal(m.pollFirstEntry(), e); - checkUnusedKey(m, e.getKey());}}; - case 1: return new MapFrobber() {void frob(NavigableMap m) { - Map.Entry e = m.lastEntry(); - equal(m.pollLastEntry(), e); - checkUnusedKey(m, e.getKey());}}; - case 2: return new MapFrobber() {void frob(NavigableMap m) { - check(m.remove(k) != null); - checkUnusedKey(m, k);}}; - case 3: return new MapFrobber() {void frob(NavigableMap m) { - m.subMap(k, true, k, true).clear(); - checkUnusedKey(m, k);}}; - case 4: return new MapFrobber() {void frob(NavigableMap m) { - m.descendingMap().subMap(k, true, k, true).clear(); - checkUnusedKey(m, k);}}; - case 5: return new MapFrobber() {void frob(NavigableMap m) { - final Iterator it = m.keySet().iterator(); - while (it.hasNext()) - if (it.next().equals(k)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, - new Fun(){void f(){ it.remove(); }}); - } - checkUnusedKey(m, k);}}; - case 6: return new MapFrobber() {void frob(NavigableMap m) { - final Iterator<Map.Entry> it = m.entrySet().iterator(); - while (it.hasNext()) - if (it.next().getKey().equals(k)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, remover(it)); - } - checkUnusedKey(m, k);}}; - } + final MapFrobber[] randomRemovers = { + new MapFrobber() {void frob(NavigableMap m) { + Map.Entry e = m.firstEntry(); + equal(m.pollFirstEntry(), e); + checkUnusedKey(m, e.getKey());}}, + new MapFrobber() {void frob(NavigableMap m) { + Map.Entry e = m.lastEntry(); + equal(m.pollLastEntry(), e); + checkUnusedKey(m, e.getKey());}}, + new MapFrobber() {void frob(NavigableMap m) { + check(m.remove(k) != null); + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.subMap(k, true, k, true).clear(); + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.descendingMap().subMap(k, true, k, true).clear(); + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + final Iterator it = m.keySet().iterator(); + while (it.hasNext()) + if (it.next().equals(k)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + final Iterator it = m.navigableKeySet().descendingIterator(); + while (it.hasNext()) + if (it.next().equals(k)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + final Iterator<Map.Entry> it = m.entrySet().iterator(); + while (it.hasNext()) + if (it.next().getKey().equals(k)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, remover(it)); + } + checkUnusedKey(m, k);}}, + }; + + return randomRemovers[rnd.nextInt(randomRemovers.length)]; }
static SetFrobber randomRemover(NavigableSet s) { final Integer e = usedElt(s); - switch (rnd.nextInt(7)) { - default: throw new Error(); - case 0: return new SetFrobber() {void frob(NavigableSet s) { - Object e = s.first(); - equal(s.pollFirst(), e); - checkUnusedElt(s, e);}}; - case 1: return new SetFrobber() {void frob(NavigableSet s) { - Object e = s.last(); - equal(s.pollLast(), e); - checkUnusedElt(s, e);}}; - case 2: return new SetFrobber() {void frob(NavigableSet s) { - check(s.remove(e)); - checkUnusedElt(s, e);}}; - case 3: return new SetFrobber() {void frob(NavigableSet s) { - s.subSet(e, true, e, true).clear(); - checkUnusedElt(s, e);}}; - case 4: return new SetFrobber() {void frob(NavigableSet s) { - s.descendingSet().subSet(e, true, e, true).clear(); - checkUnusedElt(s, e);}}; - case 5: return new SetFrobber() {void frob(NavigableSet s) { - final Iterator it = s.iterator(); - while (it.hasNext()) - if (it.next().equals(e)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, - new Fun(){void f(){ it.remove(); }}); - } - checkUnusedElt(s, e);}}; - case 6: return new SetFrobber() {void frob(NavigableSet s) { - final Iterator it = s.descendingSet().iterator(); - while (it.hasNext()) - if (it.next().equals(e)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, - new Fun(){void f(){ it.remove(); }}); - } - checkUnusedElt(s, e);}}; - } + + final SetFrobber[] randomRemovers = { + new SetFrobber() {void frob(NavigableSet s) { + Object e = s.first(); + equal(s.pollFirst(), e); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + Object e = s.last(); + equal(s.pollLast(), e); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + check(s.remove(e)); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.subSet(e, true, e, true).clear(); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.descendingSet().subSet(e, true, e, true).clear(); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + final Iterator it = s.iterator(); + while (it.hasNext()) + if (it.next().equals(e)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + final Iterator it = s.descendingSet().iterator(); + while (it.hasNext()) + if (it.next().equals(e)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + final Iterator it = s.descendingIterator(); + while (it.hasNext()) + if (it.next().equals(e)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedElt(s, e);}} + }; + + return randomRemovers[rnd.nextInt(randomRemovers.length)]; }
static void lockStep(NavigableMap m1,
Martin
On Sat, Apr 19, 2008 at 2:07 PM, charlie hunt <charlie.hunt@sun.com> wrote:
Alan Bateman wrote:
Martin Buchholz wrote:
:
2. Bug creation from Charlie (or some other person empowered to do
so)
I suggest making this bug P2-S2.
I will need the bug id and synopsis to create the proper mercurial comment.
I don't know if Charlie is online today, but as you seem to be ready to create the change-set, I've created java/classes_util bug:
6691185: (coll) TreeMap.navigableKeySet's descendingIterator method starts at first instead of last entry
with a link to this thread. The synopsis can be changed if you want something different.
-Alan.
Alan, thanks for filing the bug. One less item on my list of things to do. :-)
Fwiw, I've looked at Martin's proposed changes. From the familiarity I've gotten with TreeMap over the past week or two, the changes look good to me.
charlie ...
Folks, While we're at it, here's another Collections bug discovered recently by a Googler (Scott Blum). The value of this expression should be false: new IdentityHashMap().containsValue(null) Unfortunately, it's true. Looking at the code for containsValue, it's obvious what's wrong: /** * Tests whether the specified object reference is a value in this identity * hash map. * * @param value value whose presence in this map is to be tested * @return <tt>true</tt> if this map maps one or more keys to the * specified object reference * @see #containsKey(Object) */ public boolean containsValue(Object value) { Object[] tab = table; for (int i = 1; i < tab.length; i+= 2) if (tab[i] == value) return true; return false; } Empty entries are masquerading as entries mapping to null. The fix is easy: if (tab[i] == value) becomes: if (tab[i] == value && tab[i -1] != null) (Recall that the null key (but not value) is proxied by NULL_KEY.) Josh On Sun, Apr 20, 2008 at 12:07 AM, Joshua Bloch <jjb@google.com> wrote:
FWIW, I probably wrote the broken code. I wrote NavigableMap and retrofitted TreeMap. Doug wrote ConcurrentSkipListMap. Sorry 'bout that.
Josh
On Sat, Apr 19, 2008 at 5:56 PM, Martin Buchholz <martinrb@google.com> wrote:
Alan, thanks for filing the bug.
Charlie, thanks for the review. However, since you are not (yet?) an OpenJDK committer, I will still need an official review from Doug (or Alan?)
I noticed there was another test case, NavigableMap/LockStep.java, that "almost" tested the faulty code.
I include a change to that test case as well, below (as well as making the test case a little more maintainble).
diff --git a/test/java/util/NavigableMap/LockStep.java b/test/java/util/NavigableMap/LockStep.java --- a/test/java/util/NavigableMap/LockStep.java +++ b/test/java/util/NavigableMap/LockStep.java @@ -159,6 +159,7 @@ public class LockStep { Object[] a = new Object[1]; a[0] = Boolean.TRUE; equal(c.toArray(a), a); equal(a[0], null); + check(! c.iterator().hasNext()); }
static void testEmptySet(Set<?> c) { @@ -262,6 +263,16 @@ public class LockStep { } }
+ static void equalIterators(final Iterator<?> it1, + final Iterator<?> it2) { + while (it1.hasNext()) { + if (maybe(2)) + check(it2.hasNext()); + equal(it1.next(), it2.next()); + } + check(! it2.hasNext()); + } + static void equalNavigableSetsLeaf(final NavigableSet s1, final NavigableSet s2) { equal2(s1, s2); @@ -273,6 +284,8 @@ public class LockStep { equal(s1.first(), s2.first()); equal(s1.last(), s2.last()); } + equalIterators(s1.iterator(), s2.iterator()); + equalIterators(s1.descendingIterator(), s2.descendingIterator()); checkNavigableSet(s1); checkNavigableSet(s2); } @@ -493,30 +506,23 @@ public class LockStep {
static MapFrobber randomAdder(NavigableMap m) { final Integer k = unusedKey(m); - MapFrobber f; - switch (rnd.nextInt(4)) { - case 0: f = new MapFrobber() {void frob(NavigableMap m) { - equal(m.put(k, k+1), null); - equal(m.get(k), k+1); - if (maybe(4)) { - equal(m.put(k, k+1), k+1); - equal(m.get(k), k+1);}}}; - break; - case 1: f = new MapFrobber() {void frob(NavigableMap m) { - m.descendingMap().put(k, k+1); - equal(m.get(k), k+1);}}; - break; - case 2: f = new MapFrobber() {void frob(NavigableMap m) { - m.tailMap(k,true).headMap(k,true).put(k,k+1);}}; - break; - case 3: f = new MapFrobber() {void frob(NavigableMap m) { - m.tailMap(k,true).headMap(k,true).descendingMap().put(k,k+1);}}; - break; - default: throw new Error(); - } - final MapFrobber ff = f; + final MapFrobber[] randomAdders = { + new MapFrobber() {void frob(NavigableMap m) { + equal(m.put(k, k+1), null); + equal(m.get(k), k+1); + if (maybe(4)) { + equal(m.put(k, k+1), k+1); + equal(m.get(k), k+1);}}}, + new MapFrobber() {void frob(NavigableMap m) { + m.descendingMap().put(k, k+1); + equal(m.get(k), k+1);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.tailMap(k,true).headMap(k,true).put(k,k+1);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.tailMap(k,true).headMap(k,true).descendingMap().put(k,k+1);}} + }; return new MapFrobber() {void frob(NavigableMap m) { - ff.frob(m); + randomAdders[rnd.nextInt(randomAdders.length)].frob(m); if (maybe(2)) equal(m.get(k), k+1); if (maybe(4)) { equal(m.put(k, k+1), k+1); @@ -525,26 +531,19 @@ public class LockStep {
static SetFrobber randomAdder(NavigableSet s) { final Integer e = unusedElt(s); - SetFrobber f; - switch (rnd.nextInt(4)) { - case 0: f = new SetFrobber() {void frob(NavigableSet s) { - check(s.add(e));}}; - break; - case 1: f = new SetFrobber() {void frob(NavigableSet s) { - s.descendingSet().add(e);}}; - break; - case 2: f = new SetFrobber() {void frob(NavigableSet s) { - s.tailSet(e,true).headSet(e,true).add(e);}}; - break; - case 3: f = new SetFrobber() {void frob(NavigableSet s) { - s.descendingSet().tailSet(e,true).headSet(e,true).add(e);}}; - break; - default: throw new Error(); - } - final SetFrobber ff = f; + final SetFrobber[] randomAdders = { + new SetFrobber() {void frob(NavigableSet s) { + check(s.add(e));}}, + new SetFrobber() {void frob(NavigableSet s) { + s.descendingSet().add(e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.tailSet(e,true).headSet(e,true).add(e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.descendingSet().tailSet(e,true).headSet(e,true).add(e);}} + }; return new SetFrobber() {void frob(NavigableSet s) { if (maybe(2)) check(! s.contains(e)); - ff.frob(s); + randomAdders[rnd.nextInt(randomAdders.length)].frob(s); if (maybe(2)) check(! s.add(e)); if (maybe(2)) check(s.contains(e));}}; } @@ -605,89 +604,112 @@ public class LockStep {
static MapFrobber randomRemover(NavigableMap m) { final Integer k = usedKey(m); - switch (rnd.nextInt(7)) { - default: throw new Error(); - case 0: return new MapFrobber() {void frob(NavigableMap m) { - Map.Entry e = m.firstEntry(); - equal(m.pollFirstEntry(), e); - checkUnusedKey(m, e.getKey());}}; - case 1: return new MapFrobber() {void frob(NavigableMap m) { - Map.Entry e = m.lastEntry(); - equal(m.pollLastEntry(), e); - checkUnusedKey(m, e.getKey());}}; - case 2: return new MapFrobber() {void frob(NavigableMap m) { - check(m.remove(k) != null); - checkUnusedKey(m, k);}}; - case 3: return new MapFrobber() {void frob(NavigableMap m) { - m.subMap(k, true, k, true).clear(); - checkUnusedKey(m, k);}}; - case 4: return new MapFrobber() {void frob(NavigableMap m) { - m.descendingMap().subMap(k, true, k, true).clear(); - checkUnusedKey(m, k);}}; - case 5: return new MapFrobber() {void frob(NavigableMap m) { - final Iterator it = m.keySet().iterator(); - while (it.hasNext()) - if (it.next().equals(k)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, - new Fun(){void f(){ it.remove(); }}); - } - checkUnusedKey(m, k);}}; - case 6: return new MapFrobber() {void frob(NavigableMap m) { - final Iterator<Map.Entry> it = m.entrySet().iterator(); - while (it.hasNext()) - if (it.next().getKey().equals(k)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, remover(it)); - } - checkUnusedKey(m, k);}}; - } + final MapFrobber[] randomRemovers = { + new MapFrobber() {void frob(NavigableMap m) { + Map.Entry e = m.firstEntry(); + equal(m.pollFirstEntry(), e); + checkUnusedKey(m, e.getKey());}}, + new MapFrobber() {void frob(NavigableMap m) { + Map.Entry e = m.lastEntry(); + equal(m.pollLastEntry(), e); + checkUnusedKey(m, e.getKey());}}, + new MapFrobber() {void frob(NavigableMap m) { + check(m.remove(k) != null); + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.subMap(k, true, k, true).clear(); + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.descendingMap().subMap(k, true, k, true).clear(); + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + final Iterator it = m.keySet().iterator(); + while (it.hasNext()) + if (it.next().equals(k)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + final Iterator it = m.navigableKeySet().descendingIterator(); + while (it.hasNext()) + if (it.next().equals(k)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + final Iterator<Map.Entry> it = m.entrySet().iterator(); + while (it.hasNext()) + if (it.next().getKey().equals(k)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, remover(it)); + } + checkUnusedKey(m, k);}}, + }; + + return randomRemovers[rnd.nextInt(randomRemovers.length)]; }
static SetFrobber randomRemover(NavigableSet s) { final Integer e = usedElt(s); - switch (rnd.nextInt(7)) { - default: throw new Error(); - case 0: return new SetFrobber() {void frob(NavigableSet s) { - Object e = s.first(); - equal(s.pollFirst(), e); - checkUnusedElt(s, e);}}; - case 1: return new SetFrobber() {void frob(NavigableSet s) { - Object e = s.last(); - equal(s.pollLast(), e); - checkUnusedElt(s, e);}}; - case 2: return new SetFrobber() {void frob(NavigableSet s) { - check(s.remove(e)); - checkUnusedElt(s, e);}}; - case 3: return new SetFrobber() {void frob(NavigableSet s) { - s.subSet(e, true, e, true).clear(); - checkUnusedElt(s, e);}}; - case 4: return new SetFrobber() {void frob(NavigableSet s) { - s.descendingSet().subSet(e, true, e, true).clear(); - checkUnusedElt(s, e);}}; - case 5: return new SetFrobber() {void frob(NavigableSet s) { - final Iterator it = s.iterator(); - while (it.hasNext()) - if (it.next().equals(e)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, - new Fun(){void f(){ it.remove(); }}); - } - checkUnusedElt(s, e);}}; - case 6: return new SetFrobber() {void frob(NavigableSet s) { - final Iterator it = s.descendingSet().iterator(); - while (it.hasNext()) - if (it.next().equals(e)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, - new Fun(){void f(){ it.remove(); }}); - } - checkUnusedElt(s, e);}}; - } + + final SetFrobber[] randomRemovers = { + new SetFrobber() {void frob(NavigableSet s) { + Object e = s.first(); + equal(s.pollFirst(), e); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + Object e = s.last(); + equal(s.pollLast(), e); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + check(s.remove(e)); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.subSet(e, true, e, true).clear(); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.descendingSet().subSet(e, true, e, true).clear(); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + final Iterator it = s.iterator(); + while (it.hasNext()) + if (it.next().equals(e)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + final Iterator it = s.descendingSet().iterator(); + while (it.hasNext()) + if (it.next().equals(e)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + final Iterator it = s.descendingIterator(); + while (it.hasNext()) + if (it.next().equals(e)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedElt(s, e);}} + }; + + return randomRemovers[rnd.nextInt(randomRemovers.length)]; }
static void lockStep(NavigableMap m1,
Martin
On Sat, Apr 19, 2008 at 2:07 PM, charlie hunt <charlie.hunt@sun.com> wrote:
Alan Bateman wrote:
Martin Buchholz wrote:
:
2. Bug creation from Charlie (or some other person empowered to do
so)
I suggest making this bug P2-S2.
I will need the bug id and synopsis to create the proper mercurial comment.
I don't know if Charlie is online today, but as you seem to be ready to create the change-set, I've created java/classes_util bug:
6691185: (coll) TreeMap.navigableKeySet's descendingIterator method starts at first instead of last entry
with a link to this thread. The synopsis can be changed if you want something different.
-Alan.
Alan, thanks for filing the bug. One less item on my list of things to do. :-)
Fwiw, I've looked at Martin's proposed changes. From the familiarity I've gotten with TreeMap over the past week or two, the changes look good to me.
charlie ...
Joshua Bloch wrote:
Folks,
While we're at it, here's another Collections bug discovered recently by a Googler (Scott Blum). The value of this expression should be false:
new IdentityHashMap().containsValue(null)
Unfortunately, it's true. Looking at the code for containsValue, it's obvious what's wrong:
/** * Tests whether the specified object reference is a value in this identity * hash map. * * @param value value whose presence in this map is to be tested * @return <tt>true</tt> if this map maps one or more keys to the * specified object reference * @see #containsKey(Object) */ public boolean containsValue(Object value) { Object[] tab = table; for (int i = 1; i < tab.length; i+= 2) if (tab[i] == value) return true;
return false; }
Empty entries are masquerading as entries mapping to null. The fix is easy:
if (tab[i] == value)
becomes:
if (tab[i] == value && tab[i -1] != null)
(Recall that the null key (but not value) is proxied by NULL_KEY.)
Josh
I don't see this in the bug database so I've created the following so that it doesn't get lost: 6691215: (coll) IdentityHashMap.containsValue(null) returns true when null value not present -Alan.
Hi Martin, I (OpenJDK user chegar) approve the changes that you made to: src/share/classes/java/util/TreeMap.java test/java/util/Collection/MOAT.java test/java/util/NavigableMap/LockStep.java The only comment I have is that you may want to add the bug number, CR 6691185, to the @bug tag in the testcases. Do you still have integration access? I can take care of the JDK 6 integration. -Chris. Martin Buchholz wrote:
Alan, thanks for filing the bug.
Charlie, thanks for the review. However, since you are not (yet?) an OpenJDK committer, I will still need an official review from Doug (or Alan?)
I noticed there was another test case, NavigableMap/LockStep.java, that "almost" tested the faulty code.
I include a change to that test case as well, below (as well as making the test case a little more maintainble).
diff --git a/test/java/util/NavigableMap/LockStep.java b/test/java/util/NavigableMap/LockStep.java --- a/test/java/util/NavigableMap/LockStep.java +++ b/test/java/util/NavigableMap/LockStep.java @@ -159,6 +159,7 @@ public class LockStep { Object[] a = new Object[1]; a[0] = Boolean.TRUE; equal(c.toArray(a), a); equal(a[0], null); + check(! c.iterator().hasNext()); }
static void testEmptySet(Set<?> c) { @@ -262,6 +263,16 @@ public class LockStep { } }
+ static void equalIterators(final Iterator<?> it1, + final Iterator<?> it2) { + while (it1.hasNext()) { + if (maybe(2)) + check(it2.hasNext()); + equal(it1.next(), it2.next()); + } + check(! it2.hasNext()); + } + static void equalNavigableSetsLeaf(final NavigableSet s1, final NavigableSet s2) { equal2(s1, s2); @@ -273,6 +284,8 @@ public class LockStep { equal(s1.first(), s2.first()); equal(s1.last(), s2.last()); } + equalIterators(s1.iterator(), s2.iterator()); + equalIterators(s1.descendingIterator(), s2.descendingIterator()); checkNavigableSet(s1); checkNavigableSet(s2); } @@ -493,30 +506,23 @@ public class LockStep {
static MapFrobber randomAdder(NavigableMap m) { final Integer k = unusedKey(m); - MapFrobber f; - switch (rnd.nextInt(4)) { - case 0: f = new MapFrobber() {void frob(NavigableMap m) { - equal(m.put(k, k+1), null); - equal(m.get(k), k+1); - if (maybe(4)) { - equal(m.put(k, k+1), k+1); - equal(m.get(k), k+1);}}}; - break; - case 1: f = new MapFrobber() {void frob(NavigableMap m) { - m.descendingMap().put(k, k+1); - equal(m.get(k), k+1);}}; - break; - case 2: f = new MapFrobber() {void frob(NavigableMap m) { - m.tailMap(k,true).headMap(k,true).put(k,k+1);}}; - break; - case 3: f = new MapFrobber() {void frob(NavigableMap m) { - m.tailMap(k,true).headMap(k,true).descendingMap().put(k,k+1);}}; - break; - default: throw new Error(); - } - final MapFrobber ff = f; + final MapFrobber[] randomAdders = { + new MapFrobber() {void frob(NavigableMap m) { + equal(m.put(k, k+1), null); + equal(m.get(k), k+1); + if (maybe(4)) { + equal(m.put(k, k+1), k+1); + equal(m.get(k), k+1);}}}, + new MapFrobber() {void frob(NavigableMap m) { + m.descendingMap().put(k, k+1); + equal(m.get(k), k+1);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.tailMap(k,true).headMap(k,true).put(k,k+1);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.tailMap(k,true).headMap(k,true).descendingMap().put(k,k+1);}} + }; return new MapFrobber() {void frob(NavigableMap m) { - ff.frob(m); + randomAdders[rnd.nextInt(randomAdders.length)].frob(m); if (maybe(2)) equal(m.get(k), k+1); if (maybe(4)) { equal(m.put(k, k+1), k+1); @@ -525,26 +531,19 @@ public class LockStep {
static SetFrobber randomAdder(NavigableSet s) { final Integer e = unusedElt(s); - SetFrobber f; - switch (rnd.nextInt(4)) { - case 0: f = new SetFrobber() {void frob(NavigableSet s) { - check(s.add(e));}}; - break; - case 1: f = new SetFrobber() {void frob(NavigableSet s) { - s.descendingSet().add(e);}}; - break; - case 2: f = new SetFrobber() {void frob(NavigableSet s) { - s.tailSet(e,true).headSet(e,true).add(e);}}; - break; - case 3: f = new SetFrobber() {void frob(NavigableSet s) { - s.descendingSet().tailSet(e,true).headSet(e,true).add(e);}}; - break; - default: throw new Error(); - } - final SetFrobber ff = f; + final SetFrobber[] randomAdders = { + new SetFrobber() {void frob(NavigableSet s) { + check(s.add(e));}}, + new SetFrobber() {void frob(NavigableSet s) { + s.descendingSet().add(e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.tailSet(e,true).headSet(e,true).add(e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.descendingSet().tailSet(e,true).headSet(e,true).add(e);}} + }; return new SetFrobber() {void frob(NavigableSet s) { if (maybe(2)) check(! s.contains(e)); - ff.frob(s); + randomAdders[rnd.nextInt(randomAdders.length)].frob(s); if (maybe(2)) check(! s.add(e)); if (maybe(2)) check(s.contains(e));}}; } @@ -605,89 +604,112 @@ public class LockStep {
static MapFrobber randomRemover(NavigableMap m) { final Integer k = usedKey(m); - switch (rnd.nextInt(7)) { - default: throw new Error(); - case 0: return new MapFrobber() {void frob(NavigableMap m) { - Map.Entry e = m.firstEntry(); - equal(m.pollFirstEntry(), e); - checkUnusedKey(m, e.getKey());}}; - case 1: return new MapFrobber() {void frob(NavigableMap m) { - Map.Entry e = m.lastEntry(); - equal(m.pollLastEntry(), e); - checkUnusedKey(m, e.getKey());}}; - case 2: return new MapFrobber() {void frob(NavigableMap m) { - check(m.remove(k) != null); - checkUnusedKey(m, k);}}; - case 3: return new MapFrobber() {void frob(NavigableMap m) { - m.subMap(k, true, k, true).clear(); - checkUnusedKey(m, k);}}; - case 4: return new MapFrobber() {void frob(NavigableMap m) { - m.descendingMap().subMap(k, true, k, true).clear(); - checkUnusedKey(m, k);}}; - case 5: return new MapFrobber() {void frob(NavigableMap m) { - final Iterator it = m.keySet().iterator(); - while (it.hasNext()) - if (it.next().equals(k)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, - new Fun(){void f(){ it.remove(); }}); - } - checkUnusedKey(m, k);}}; - case 6: return new MapFrobber() {void frob(NavigableMap m) { - final Iterator<Map.Entry> it = m.entrySet().iterator(); - while (it.hasNext()) - if (it.next().getKey().equals(k)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, remover(it)); - } - checkUnusedKey(m, k);}}; - } + final MapFrobber[] randomRemovers = { + new MapFrobber() {void frob(NavigableMap m) { + Map.Entry e = m.firstEntry(); + equal(m.pollFirstEntry(), e); + checkUnusedKey(m, e.getKey());}}, + new MapFrobber() {void frob(NavigableMap m) { + Map.Entry e = m.lastEntry(); + equal(m.pollLastEntry(), e); + checkUnusedKey(m, e.getKey());}}, + new MapFrobber() {void frob(NavigableMap m) { + check(m.remove(k) != null); + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.subMap(k, true, k, true).clear(); + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.descendingMap().subMap(k, true, k, true).clear(); + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + final Iterator it = m.keySet().iterator(); + while (it.hasNext()) + if (it.next().equals(k)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + final Iterator it = m.navigableKeySet().descendingIterator(); + while (it.hasNext()) + if (it.next().equals(k)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + final Iterator<Map.Entry> it = m.entrySet().iterator(); + while (it.hasNext()) + if (it.next().getKey().equals(k)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, remover(it)); + } + checkUnusedKey(m, k);}}, + }; + + return randomRemovers[rnd.nextInt(randomRemovers.length)]; }
static SetFrobber randomRemover(NavigableSet s) { final Integer e = usedElt(s); - switch (rnd.nextInt(7)) { - default: throw new Error(); - case 0: return new SetFrobber() {void frob(NavigableSet s) { - Object e = s.first(); - equal(s.pollFirst(), e); - checkUnusedElt(s, e);}}; - case 1: return new SetFrobber() {void frob(NavigableSet s) { - Object e = s.last(); - equal(s.pollLast(), e); - checkUnusedElt(s, e);}}; - case 2: return new SetFrobber() {void frob(NavigableSet s) { - check(s.remove(e)); - checkUnusedElt(s, e);}}; - case 3: return new SetFrobber() {void frob(NavigableSet s) { - s.subSet(e, true, e, true).clear(); - checkUnusedElt(s, e);}}; - case 4: return new SetFrobber() {void frob(NavigableSet s) { - s.descendingSet().subSet(e, true, e, true).clear(); - checkUnusedElt(s, e);}}; - case 5: return new SetFrobber() {void frob(NavigableSet s) { - final Iterator it = s.iterator(); - while (it.hasNext()) - if (it.next().equals(e)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, - new Fun(){void f(){ it.remove(); }}); - } - checkUnusedElt(s, e);}}; - case 6: return new SetFrobber() {void frob(NavigableSet s) { - final Iterator it = s.descendingSet().iterator(); - while (it.hasNext()) - if (it.next().equals(e)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, - new Fun(){void f(){ it.remove(); }}); - } - checkUnusedElt(s, e);}}; - } + + final SetFrobber[] randomRemovers = { + new SetFrobber() {void frob(NavigableSet s) { + Object e = s.first(); + equal(s.pollFirst(), e); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + Object e = s.last(); + equal(s.pollLast(), e); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + check(s.remove(e)); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.subSet(e, true, e, true).clear(); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.descendingSet().subSet(e, true, e, true).clear(); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + final Iterator it = s.iterator(); + while (it.hasNext()) + if (it.next().equals(e)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + final Iterator it = s.descendingSet().iterator(); + while (it.hasNext()) + if (it.next().equals(e)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + final Iterator it = s.descendingIterator(); + while (it.hasNext()) + if (it.next().equals(e)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedElt(s, e);}} + }; + + return randomRemovers[rnd.nextInt(randomRemovers.length)]; }
static void lockStep(NavigableMap m1,
Martin
On Sat, Apr 19, 2008 at 2:07 PM, charlie hunt <charlie.hunt@sun.com> wrote:
Alan Bateman wrote:
Martin Buchholz wrote:
:
2. Bug creation from Charlie (or some other person empowered to do so) I suggest making this bug P2-S2.
I will need the bug id and synopsis to create the proper mercurial comment.
I don't know if Charlie is online today, but as you seem to be ready to create the change-set, I've created java/classes_util bug: 6691185: (coll) TreeMap.navigableKeySet's descendingIterator method starts at first instead of last entry with a link to this thread. The synopsis can be changed if you want something different. -Alan.
Alan, thanks for filing the bug. One less item on my list of things to do. :-)
Fwiw, I've looked at Martin's proposed changes. From the familiarity I've gotten with TreeMap over the past week or two, the changes look good to me.
charlie ...
On Sun, Apr 20, 2008 at 2:50 AM, Christopher Hegarty - Sun Microsystems Ireland <Christopher.Hegarty@sun.com> wrote:
Hi Martin,
I (OpenJDK user chegar) approve the changes that you made to:
src/share/classes/java/util/TreeMap.java test/java/util/Collection/MOAT.java test/java/util/NavigableMap/LockStep.java
Thanks, Chris.
The only comment I have is that you may want to add the bug number, CR 6691185, to the @bug tag in the testcases.
Quite right. Updated. Do you still have integration
access?
Yes, in theory. We'll see how it works in practice.
I can take care of the JDK 6 integration.
Thanks. Martin
participants (7)
-
Alan Bateman
-
charlie hunt
-
Christopher Hegarty - Sun Microsystems Ireland
-
Doug Lea
-
Joshua Bloch
-
kevin bourrillion
-
Martin Buchholz