StackOverflowException when serializing binary tree

Question

I'm attempting to implement a binary tree for an Android app, and I want to be able to serialize it to a file on the device. Unfortunately, I'm getting stackoverflow errors when trying to serialize it.

Code:

class BTree<V extends Model> implements Serializable {
/**
 * 
 */
private static final long serialVersionUID = 4944483811730762415L;

private V value;
private BTree<V> left;
private BTree<V> right;

public BTree(V value) {
    this.value = value;
}

public BTree(V value, BTree<V> left, BTree<V> right) {
    this.value = value;
    this.left = left;
    this.right = right;
}

private int getValue() {
    return this.value.hashCode();
}

public void insert(BTree<V> node) {     
    if (this.getValue() >= node.getValue()) {
        if (this.left == null) {
            this.left = node;
        } else {
            this.left.insert(node);
        }
    } else {
        if (this.right == null) {
            this.right = node;
        } else {
            this.right.insert(node);
        }
    }
}

public boolean containsKey(Object key) {
    return this.find(key) != null;
}

public V find(Object key) {
    if (key.hashCode() == this.getValue()) {
        return this.value;
    } else if (key.hashCode() > this.getValue() && this.left != null) {
        return this.left.find(key);
    } else if (key.hashCode() < this.getValue() && this.right != null) {
        return this.right.find(key);
    } else {
        return null;
    }
}

public ArrayList<V> getAllValues() {
    ArrayList<V> values = new ArrayList<V>();
    if (this.left != null) {
        values.addAll(this.left.getAllValues());
    }
    if (this.right != null) {
        values.addAll(this.right.getAllValues());
    }

    return values;
}
}

And I'm trying to serialize in this block of text in a separate class:

try {           
        FileOutputStream fos = this.context.openFileOutput(FILE_NAME, Context.MODE_PRIVATE);
        ObjectOutputStream oos = new ObjectOutputStream(fos);
        oos.writeObject(this.tree);
        oos.close();

        //this.lastModified = getLastModified(FILE_NAME);
    } catch (FileNotFoundException e) {
        //File will get created, so this doesn't matter
    } catch (IOException e) {
        Log.d("BTreeModel Serialization Error", "Error serialization model.");
        Log.e("Serialization error details", e.toString());
    }

What I have noticed is that if I serialize to a file that does not currently exist, the it serializes fine. The second time I run the same program it causes the StackOverflowException when serializing to disk again.

Here is the output of logcat:

09-07 05:29:42.011: ERROR/AndroidRuntime(916): FATAL EXCEPTION: main
09-07 05:29:42.011: ERROR/AndroidRuntime(916): java.lang.StackOverflowError
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at         java.util.IdentityHashMap.getModuloHash(IdentityHashMap.java:435)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.util.IdentityHashMap.findIndex(IdentityHashMap.java:419)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at     java.util.IdentityHashMap.get(IdentityHashMap.java:371)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.dumpCycle(ObjectOutputStream.java:471)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObjectInternal(ObjectOutputStream.java:1739)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1689)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1653)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeFieldValues(ObjectOutputStream.java:1143)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.defaultWriteObject(ObjectOutputStream.java:413)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeHierarchy(ObjectOutputStream.java:1241)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeHierarchy(ObjectOutputStream.java:1205)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeNewObject(ObjectOutputStream.java:1575)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObjectInternal(ObjectOutputStream.java:1847)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1689)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1653)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeFieldValues(ObjectOutputStream.java:1143)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.defaultWriteObject(ObjectOutputStream.java:413)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeHierarchy(ObjectOutputStream.java:1241)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeNewObject(ObjectOutputStream.java:1575)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObjectInternal(ObjectOutputStream.java:1847)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1689)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1653)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeFieldValues(ObjectOutputStream.java:1143)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.defaultWriteObject(ObjectOutputStream.java:413)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeHierarchy(ObjectOutputStream.java:1241)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeNewObject(ObjectOutputStream.java:1575)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObjectInternal(ObjectOutputStream.java:1847)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1689)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1653)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeFieldValues(ObjectOutputStream.java:1143)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.defaultWriteObject(ObjectOutputStream.java:413)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeHierarchy(ObjectOutputStream.java:1241)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeNewObject(ObjectOutputStream.java:1575)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObjectInternal(ObjectOutputStream.java:1847)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1689)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1653)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeFieldValues(ObjectOutputStream.java:1143)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.defaultWriteObject(ObjectOutputStream.java:413)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeHierarchy(ObjectOutputStream.java:1241)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeNewObject(ObjectOutputStream.java:1575)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObjectInternal(ObjectOutputStream.java:1847)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1689)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1653)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeFieldValues(ObjectOutputStream.java:1143)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.defaultWriteObject(ObjectOutputStream.java:413)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeHierarchy(ObjectOutputStream.java:1241)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeNewObject(ObjectOutputStream.java:1575)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObjectInternal(ObjectOutputStream.java:1847)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1689)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1653)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeFieldValues(ObjectOutputStream.java:1143)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.defaultWriteObject(ObjectOutputStream.java:413)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeHierarchy(ObjectOutputStream.j

From the Activity that adds the nodes:

public void onCreate(Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);
    setContentView(R.layout.main);

    //TextView averageHashMapTime = (TextView)findViewById(R.id.averageHashCollectionTime);
    //averageHashMapTime.setText("Just a moment");
    //TextView averageBtreeTime = (TextView)findViewById(R.id.averageBTreeCollectionTime);
    //averageBtreeTime.setText("working");

    HashMapModelCollection<Integer, Content> hashCollection = new HashMapModelCollection<Integer, Content>(this);
    long totalTicks = 0;
    final int totalIterations = 16;

    BTreeModelCollection<Integer, Content> btreeCollection = new BTreeModelCollection<Integer, Content>(this);
    totalTicks = 0;
    for(int i = 0; i < totalIterations; i++) {
        Content test = new Content();
        test.setText(String.valueOf(i));
        Random r = new Random();
        int key = r.nextInt();
        Date start = new Date();
        btreeCollection.put(key, test);
        Date end = new Date();

        totalTicks += end.getTime() - start.getTime();
    }

    Log.d("Finished", "btree length: " + String.valueOf(totalTicks / totalIterations));
    Toast.makeText(this, "btree length: " + String.valueOf(totalTicks / totalIterations), Toast.LENGTH_LONG).show();
    //averageBtreeTime.setText(String.valueOf(totalTicks / totalIterations));

}

The class that directly handles the BTree objects:

public class BTreeModelCollection<K extends Serializable, V extends Model> implements IModelCollection<K, V>,
    Serializable {


/**
 * 
 */
private static final long serialVersionUID = -3969909157515987705L;

private static final String FILE_NAME = "testCollection-5";

private BTree<V> tree;
private Context context;

public BTreeModelCollection(Context context) {
    this.context = context;
}

@Override
public void clear() {
    // TODO Auto-generated method stub

}

@Override
public boolean containsKey(Object key) {
    return tree.containsKey(key);
}

@Override
public boolean containsValue(Object value) {
    // TODO Auto-generated method stub
    return false;
}

@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
    // TODO Auto-generated method stub
    return null;
}

@Override
public V get(Object key) {
    return getTree().find(key);
}

@Override
public boolean isEmpty() {
    // TODO Auto-generated method stub
    return false;
}

@Override
public Set<K> keySet() {
    // TODO Auto-generated method stub
    return null;
}

@Override
public void put(K key, V value) {
    value.setKey(key);
    getTree();
    if (this.tree != null) {
        this.tree.insert(new BTree<V>(value));
    } else {
        this.tree = new BTree<V>(value);
    }
    serialize();
}

@Override
public V remove(Object key) {
    // TODO Auto-generated method stub
    return null;
}

@Override
public int size() {
    // TODO Auto-generated method stub
    return 0;
}

@Override
public Collection<V> values() {
    return getTree().getAllValues();
}

@Override
public void putAll(Map<? extends K, ? extends V> map) {
    // TODO Auto-generated method stub

}

private BTree<V> getTree() {
    if (this.tree == null) {
        loadTree();
    }

    return tree;
}

@SuppressWarnings("unchecked")
private void loadTree() {
    try {
        FileInputStream fis = context.openFileInput(FILE_NAME);
        ObjectInputStream ois = new ObjectInputStream(fis);
        this.tree = (BTree<V>)ois.readObject();
        ois.close();
    } catch (FileNotFoundException e) {
        this.tree = null;
    } catch (StreamCorruptedException e) {
        e.printStackTrace();
    } catch (IOException e) {
        this.tree = null;
    } catch (ClassNotFoundException e) {
        e.printStackTrace();
    } 
}

private void serialize() {
    if (this.tree == null) {
        Log.w("Serialization problem", "No collection to serialize to disk");
        return;
    }

    try {           
        FileOutputStream fos = this.context.openFileOutput(FILE_NAME, Context.MODE_PRIVATE);
        ObjectOutputStream oos = new ObjectOutputStream(fos);
        oos.writeObject(this.tree);
        oos.close();

        //this.lastModified = getLastModified(FILE_NAME);
    } catch (FileNotFoundException e) {
        //File will get created, so this doesn't matter
    } catch (IOException e) {
        Log.d("BTreeModel Serialization Error", "Error serialization model.");
        Log.e("Serialization error details", e.toString());
    } 
}

}

And the Model class:

public abstract class Model implements Serializable {

/**
 * 
 */
private static final long serialVersionUID = -5724152403115334006L;

private Serializable key;

void setKey(Serializable key) {
    this.key = key;
}

Serializable getKey() {
    return this.key;
}
}

After reading the title, I thought this had something to do with the site. :P — Paul Manta, Sep 07 '11 at 05:34
@Corey Can you include the code that set up the tree? Looks like the circular reference could be possible by inserting the same node using the insert() method/constructor — momo, Sep 07 '11 at 06:03
@mom - I have added every line of code I can find that is being called. — Corey Sunwold, Sep 07 '11 at 06:13
Please check if your program is failing for any number of nodes or its working for smaller number of nodes and failing for large number of nodes. In the former case there is surely some circular reference which is eating up the stack memory. — Santosh, Sep 07 '11 at 06:30
@Santosh - It does seem to work for under 16 nodes. I hadn't thought about circular references though, I'll investigate further. — Corey Sunwold, Sep 07 '11 at 06:54
If circular memory is not an issue then also check by increasing the stack memory as well. Check this questions which I feel is similar to your scenario http://stackoverflow.com/questions/2127217/java-stack-overflow-error-how-to-increase-the-stack-size-in-eclipse — Santosh, Sep 07 '11 at 06:58
@Corey is BTreeModelCollection.put() is the only way you insert new node in the app? If that's so, then circular reference might occur for the value. Doesn't look like that would occur in your test though since you are creating new Content() everytime. Is that a test code or the actual code in the app? — momo, Sep 07 '11 at 07:03
@momo - That is the only way I insert a new node. Currently I'm only using this test program, I don't have a "real" program yet. I think I may have just solved it. I'll post my answer in a second. Still not sure why it fixes it though. Hopefully someone can take a look at my answer and give an explanation as to why. — Corey Sunwold, Sep 07 '11 at 07:08
@momo Looks like I was wrong. Still not working. I don't see any circular references and upping the stack size doesn't feel like the best fix. — Corey Sunwold, Sep 08 '11 at 01:17
@Corey Let's work on this one again. Let me start trying to replicate this bug then we should be able to close this out. If it is not a circular reference and we don't want to increase the stack size, we probably need to provide custom serialization so it doesn't back off the to the default field recursion when writing to file — momo, Sep 08 '11 at 01:33
@momo I agree. Custom serialization is probably the way to go. I'm currently trying to restructure it to maintain the tree in an array. — Corey Sunwold, Sep 08 '11 at 02:33
@Corey I put up an answer to give you a suggestion. My approach is to serialize it as String in the JSON data format. There are other formats/forms you could take, but personally I like to work with JSON structure as I could mimic the tree structure + it's easy to code and understand. You could choose whichever format that you are most familiar with. Regardless of format/form that you choose, a similar approach with custom serialization should hopefully solve your problem. — momo, Sep 08 '11 at 03:36

score 0 · Answer 1 · answered Sep 07 '11 at 07:32

0

This usually happens when the recursion does not have a correct exit condition.

answered Sep 07 '11 at 07:32

pierrotlefou

39,805
37
135
175

1

...or the tree is too deep, aka linked list. serializing linked list can do just the same – bestsss Sep 13 '11 at 04:26

momo · Answer 2 · 2011-09-08T03:47:01.713

I've gotten to replicate your bug. It seems that Android doesn't handle deep recursion very well as I tried the same program on the Desktop and it works fine with the size that I am trying.

Per the discussion in the comment, I did alternative serialization that doesn't involve recursion to the Object level. There is definitely more than one way to do this, but I choose to serialize the structure as String in JSON data format and write it to the output stream. Note that I have not tested it thoroughly. The intention of this answer is to provide an approach that you perhaps could take as well.

Now assuming my value is int, I thought up the JSON structure should look like:

 { 
       root : {
           "value" : 8
           "left": {
                   "value" : 3
                   "left" : {
                       "value" : 1
                   }
               },
           "right" : {
               "value" : 10
               "right" : {
                   "value": 14
               }
           }
       }
   }

Now following that structure I have the methods to build the tree in BTree class:


    private JSONObject buildJSONObject(BTree  root) throws JSONException {
        JSONObject baseJSON = new JSONObject();
        JSONObject rootElement = new JSONObject();
        rootElement.put("value", root.getValue());
        baseJSON.put("root", rootElement);
        buildJSONObject(root, rootElement);
        return baseJSON;
    }

    private void buildJSONObject(BTree currentNode, JSONObject jsonElement) throws JSONException {
        jsonElement.put("value", currentNode.getValue());

        if(currentNode.left != null) {
            JSONObject leftJSON = new JSONObject();
            jsonElement.put("left", leftJSON);
            leftJSON.put("value", currentNode.left.getValue());
            buildJSONObject(currentNode.left, leftJSON);
        } 

        if (currentNode.right != null ){
            JSONObject rightJSON = new JSONObject();
            jsonElement.put("right", rightJSON);
            rightJSON.put("value", currentNode.right.getValue());
            buildJSONObject(currentNode.right, rightJSON);
        }
    }

Conversely to read it back:


private void readJSONObject(String json) throws JSONException, IllegalAccessException, InstantiationException {
        JSONObject baseJSON = new JSONObject(json);
        JSONObject rootElement = baseJSON.getJSONObject("root");
        readJSONObject(this, rootElement);
    }

    private void readJSONObject(BTree btree, JSONObject jsonElement) throws JSONException, IllegalAccessException, InstantiationException {
        int nodeValue = jsonElement.getInt("value");
        btree.value.setKey(nodeValue);

        if(jsonElement.has("left")) {
            JSONObject leftJSON = jsonElement.getJSONObject("left");
            Model m = this.value.getClass().newInstance();
            this.left = new BTree((V) m); 
            readJSONObject(this.left, leftJSON);
        } 

        if (jsonElement.has("right")){
            JSONObject rightJSON = jsonElement.getJSONObject("right");
            V m = (V)this.value.getClass().newInstance();
            this.right = new BTree(m); 
            readJSONObject(this.right, rightJSON);
        }
    }

And finally, I apply my custom serialization:


 private void writeObject(ObjectOutputStream oos)
    throws IOException {
        try {
            oos.defaultWriteObject();
            JSONObject root = buildJSONObject(this);
            oos.writeObject(root.toString());
            oos.writeObject(this.value);
        } catch(Exception e) {
            // handle exception
            throw new RuntimeException(e);
        }
    }

    // assumes "static java.util.Date aDate;" declared
    private void readObject(ObjectInputStream ois)
    throws ClassNotFoundException, IOException {
        ois.defaultReadObject();
        String jsonString = (String)ois.readObject();
        this.value = (V)ois.readObject();

        try {
            readJSONObject(jsonString);
        } catch (Exception e) {
            // handle exception
            throw new RuntimeException(e);
        }
    }

Unfortunately this also does not work. It gives a stackoverflow error at the same point. Good try though. I was holding out hope for Json serialization working. I did get it to work with an array based BTree I'll post here soon. — Corey Sunwold, Sep 13 '11 at 03:34

score 0 · Accepted Answer · answered Sep 13 '11 at 04:22

Here is the code for the revised class that solves the StackOverflowException problem. It does have one critical drawback: For unbalanced trees, it is incredibly inefficient as it has to resize the internal array over and over.

class BTree<V extends Model> implements Serializable {  
/**
 * 
 */
private static final long serialVersionUID = -7602392759811243945L;

private static final int MINIMUM_CAPACITY = 15;

private Model[] values;
private int depth = 3;

public void insert(V newValue) {    
    int index = 0;
    while(true) {           
        ensureSpotExists(index);

        Model value = values[index];
        if (value == null) {                
            values[index] = newValue;
            return;
        } else if (newValue.getKey().hashCode() < value.getKey().hashCode()) {
            index = (2 * index) + 1;
        } else if (newValue.getKey().hashCode() > value.getKey().hashCode()) {
            index = (2 * index) + 2;
        } else {
            values[index] = newValue;
            return;
        }
    }
}

protected void ensureSpotExists(int index) {
    if (this.values == null) {
        this.values = new Model[MINIMUM_CAPACITY];
    } else if (this.values.length < index + 1) {
        Model[] temp = this.values;
        this.values = new Model[getSize(++depth)];
        for(int i = 0; i < temp.length; i++) {
            this.values[i] = temp[i];
        }
    }
}

protected static int getSize(int depth) {
    int size = 0;
    for(int i = 0; i <= depth; i++) {
        size += Math.pow(2, i);
    }

    return size;
}

public boolean containsKey(Object key) {
    return this.find(key) != null;
}

public V find(Object key) {
    return null;
}

void replace(Object key, V value) {
    return;
}

public List<Model> getAllValues() {
    return Arrays.asList(this.values);
}  
}

StackOverflowException when serializing binary tree

3 Answers3