java/2579: gcj 3.0 branch libjava java/util/TreeMap fails in TreeIterator

[Tony Knaus]

>Number:         2579
>Category:       java
>Synopsis:       gcj 3.0 branch libjava java/util/TreeMap failes in TreeIterator
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Wed Apr 18 07:46:00 PDT 2001
>Closed-Date:
>Last-Modified:
>Originator:     awk@spinnakernet.com
>Release:        3.0 20010417 (prerelease)
>Organization:
>Environment:
System: Linux panic 2.2.12-20 #1 Mon Sep 27 10:40:35 EDT 1999 i686 unknown
Architecture: i686

	
host: i686-pc-linux-gnu
build: i686-pc-linux-gnu
target: i686-pc-linux-gnu
configured with: ../gcc/configure --prefix=/usr/local/gcc-3.0-alpha --enable-shared --enable-threads=posix --enable-version-specific-runtime-libs --enable-java-awt=xlib --enable-languages=c,c++,java
>Description:

The TreeMap implementation in libjava fails when creating an iterator. 
Following is the stack trace:

 ./treetest
java.lang.NullPointerException
   at 0x4016894c: _Jv_ThrowSignal (/usr/local/gcc-3.0-alpha/lib/libgcj.so.2)
   at 0x4016898d: _Jv_ThrowSignal (/usr/local/gcc-3.0-alpha/lib/libgcj.so.2)
   at 0x401ebe3b: _ZN4java4util25TreeMap__U24_TreeIterator11finit__U24_Ev (/usr/local/gcc-3.0-alpha/lib/libgcj.so.2)
   at 0x401ebe7b: _ZN4java4util25TreeMap__U24_TreeIteratorC1EPNS0_7TreeMapEi (/usr/local/gcc-3.0-alpha/lib/libgcj.so.2)
   at 0x401ec386: _ZN4java4util14TreeMap__U24_18iteratorEv (/usr/local/gcc-3.0-alpha/lib/libgcj.so.2)
   at 0x080498f6: _ZN8TreeTest4mainEP6JArrayIPN4java4lang6StringEE (/home/awk/treeTest/TreeTest.java:44)
   at 0x4017f71b: _ZN3gnu3gcj7runtime11FirstThread3runEv (/usr/local/gcc-3.0-alpha/lib/libgcj.so.2)
   at 0x4018a84b: _ZN4java4lang6Thread4run_EPNS0_6ObjectE (/usr/local/gcc-3.0-alpha/lib/libgcj.so.2)
   at 0x402a1985: _Z21_Jv_ThreadSetPriorityP12_Jv_Thread_ti (/usr/local/gcc-3.0-alpha/lib/libgcj.so.2)
   at 0x4043adb9: GC_start_routine (/usr/local/gcc-3.0-alpha/lib/libgcjgc.so.1)
   at 0x40454eca: pthread_detach (/lib/libpthread.so.0)
   at 0x4052739a: __clone (/lib/libc.so.6)

>From debugging it looks to be failing when initializing the variable "knownMod" in the
TreeIterator in java/util/TreeMap.java (shown below).

 /**
   * Iterate over HashMap's entries.
   * This implementation is parameterized to give a sequential view of
   * keys, values, or entries.
   */   
  class TreeIterator implements Iterator
  {
    static final int ENTRIES = 0,
                     KEYS = 1,
                     VALUES = 2;  
  
    // the type of this Iterator: KEYS, VALUES, or ENTRIES.
    int type;
    // the number of modifications to the backing Map that we know about.
    int knownMod = TreeMap.this.modCount;
    // The last Entry returned by a next() call.
    Node last;
    // The next entry that should be returned by next().
    Node next;
    // The last node visible to this iterator. This is used when iterating
    // on a SubMap.
    Node max;



>How-To-Repeat:

Compile and run the following example program:

//
//
//  Example for displaying iterator bug in 
//  gcj java/util/TreeMap.java
//
//
//

import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.Iterator;


class treeNode {
    private String token;

    public treeNode(String t) {
	token = new String(t);
    }

    public String toString() {
	return token;
    }
}

public class TreeTest {
    private static SortedMap tree;
    
    public static void main(String[] args) {

	tree = new TreeMap();

	try {
	    tree.put(new String("a"), new treeNode("a"));
	    tree.put(new String("b"), new treeNode("b"));	    
	    tree.put(new String("c"), new treeNode("c"));	    
	    tree.put(new String("d"), new treeNode("d"));	    
	    tree.put(new String("e"), new treeNode("e"));	    
	    tree.put(new String("f"), new treeNode("f"));	    
	    tree.put(new String("g"), new treeNode("g"));	    
	    tree.put(new String("h"), new treeNode("h"));

	    Iterator it = tree.entrySet().iterator();
	    while(it.hasNext()) {
		Map.Entry et = (Map.Entry) it.next();
		String key = (String) et.getKey();
		treeNode value = (treeNode) et.getValue();
		System.out.println(" key " + key +
				   " value " + value.toString());
	    }

	} catch (Exception e) {
	    e.printStackTrace();
	}
    }
}

>Fix:
 	As a work around I have found that moving the initialization
of "knownMod" in TreeIterator into TreeIterator's constructors
fixes the problem. I.E.

    // the number of modifications to the backing Map that we know about.
    int knownMod;
    // The last Entry returned by a next() call.
    Node last;
    // The next entry that should be returned by next().
    Node next;
    // The last node visible to this iterator. This is used when iterating
    // on a SubMap.
    Node max;

    /* Create Iterator with the supplied type: KEYS, VALUES, or ENTRIES */
    TreeIterator(int type)
    {
      this.knownMod = TreeMap.this.modCount;
      this.type = type;
      this.next = firstNode();
    }


etc......
>Release-Note:
>Audit-Trail:
>Unformatted: