[COLLECTIONS-447] TreeListIterator can return incorrect results after remove() is called

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: Nightly Builds
• Fix Version/s: 3.2.2, 4.0-alpha1, 4.0
• Component/s: Collection
• Labels: patch test

Environment

Windows 7, jdk1.5.0_22

• Assignee: Unassigned
• Reporter: Jeffrey Barnes
• Created: 03/Mar/13 03:24
• Updated: 09/Nov/15 20:53
• Resolved: 04/Mar/13 20:20

Description

TreeList.TreeListIterator can get in a bad state when remove() is called, causing it to subsequently return incorrect results. This is because TreeListIterator caches an AVLNode reference in its field next, and this node reference may become stale when remove() is called (it may contain a reference to a node that no longer exists in the tree).

I will attach two patches: testcase.patch will contain a test case illustrating the bug, and fix.patch will contain a fix. (To fix the bug, I simply clear the cached next value in TreeListIterator.remove.)

This was originally reported in a comment to COLLECTIONS-433; I am creating a separate issue for this at Thomas Neidhart's suggestion.

Issue Links

• is depended upon by: COLLECTIONS-433 TreeList.addAll() complexity