CSC403: More Storage

(Click here for one slide per page)

Storage

• Local variable (including method parameters): stored with record for each method call. (In reality, determined by compiler. The compiler freely introduces and removes local variables. They may be stored in register or not stored at all.)
• Object variable (field): stored with object.
• Class variable (static field): stored with class.

Sharing

• Local variable: separate for each method call, even on the same object.
• Object variable (field): shared by method calls on the same object.
• Class variable (static field): shared by all objects.

Initialization

• Local variable: initialized when method called.
• Object variable (field): initialized when object is first created.
• Class variable (static field): initialized when class is loaded (before any object created).

See XFields.java

Here is the state just before the main function ends:

    public int size () {
        return size (root, 0);
    }
    private static int size (Node x, int sz) {
        if (x == null) return sz;
        sz = sz + 1;
        size (x.left, sz);
        size (x.right, sz);
        return sz;
    }

Recall this broken version of size

Mistake here is to think of sz as shared among the function calls.

Here is a trace of an execution.

    public int size () {
        return size (root);
    }
    private static int sz = 0;
    private static int size (Node x) {
        if (x == null) return sz;
        sz = sz + 1;
        size (x.left);
        size (x.right);
        return sz;
    }

Is this correct?

    public int size () {
        return size (root);
    }
    private static int sz = 0;
    private static int size (Node x) {
        if (x == null) return sz;
        sz = sz + 1;
        size (x.left);
        size (x.right);
        return sz;
    }

Is this correct?

Only if you call size exactly once, no matter which instance you call it on. If size() is called more than one time (regardless of the instance of the containing class) it gives the wrong answer.

Here is a trace of an execution.

    public int size () {
        return size (root);
    }
    private int sz = 0;
    private int size (Node x) {
        if (x == null) return sz;
        sz = sz + 1;
        size (x.left);
        size (x.right);
        return sz;
    }

A variation without static. Still wrong: if you call size() more than once on any particular object instance, the value returned will be wrong for that instance!

Here is a trace of an execution.

    public int size () {
        sz = 0;
        return size (root);
    }
    private static int sz;
    private static int size (Node x) {
        if (x == null) return sz;
        sz = sz + 1;
        size (x.left);
        size (x.right);
        return sz;
    }

Is this correct?

    public int size () {
        sz = 0;
        return size (root);
    }
    private static int sz;
    private static int size (Node x) {
        if (x == null) return sz;
        sz = sz + 1;
        size (x.left);
        size (x.right);
        return sz;
    }

Is this correct?

Only if your code is single threaded. If two threads call size() on any instance of the containing class the same time, the sz field could become a mess.