TreeMap.navigableKeySet().descendingIterator() sequence ?
Joshua Bloch
jjb at google.com
Sun Apr 20 07:26:51 UTC 2008
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 at 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 at 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 at 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 ...
> > >
> > >
> > >
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20080420/7de85d1a/attachment.html>
More information about the core-libs-dev
mailing list