Pointer Variables and Dynamic Allocation

Pointers: The Problem

Pointers - The Problem

Problem: Knowing the size of an object at compile time is not always possible

Example: Array or record containing Strings

Example: Array whose length is not known until runtime

Example: List that can grow (to unknown size) and shrink at runtime

Example: Array whose elements are members of a type hierarchy

Parent: Person. Children: Staff, Student. Array of Person

Problem: Making a copy of an object (eg value semantics) is not always efficient

Example: Update a field in a large record

Problem: Making a copy of an object (eg value semantics) is not always feasible

May not want more than one instance of a dictionary, a DB, or an table in the OS

Problem: Include a routine in an object

The Solution

Solution: Use pointers to reference objects

Why does this help:

Makes it possible for programmer dynamically allocate memory as needed

Pointers are fixed size, even if the items they point to are not

Terminology

We use these terms as roughly synonymous:

Pointer
Reference
Access

Other terms:

Access type: type whose value is an access of a value of another type

Dereference: follow a pointer to the object it points to

Object: anything in memory (not just as in OO)

Memory address: the location in memory at which an object is stored

Introduction: Box Example

Java References: Class Box

Let's start with something you already know: Java references

Example:

        class Box{ 
            int l;
            int w;
        }

        class Client{
            psvm(){
                Box p;          -- What's allocated for this local variable?
                p = new Box();  -- What's allocated here?

                p.l = 3;       -- How is p.l accessed
                p.w = 4;
                S.o.p(p.l + p.w);

                Box q = null;   -- What if no initialization?
                S.o.p(q.l);     -- What happens here?
            }
        }

Start with type Box

Shows a type for a Box with a length and a width:

        type Box is record
            len, wid: Integer;
        end record;

        -- What is allocated
        b1, b2, b3: Box
    begin
        b1.len := 11;
        b1.wid := 12;

        b2 := (len => 21, wid => 22); -- Aggregate assignment
        b3 := (21, 22);

Similar program: boxexample.adb (prettified)

Introduce Type BoxPtr - And Allocate New Boxes

Shows:

type BoxPointer is an access type - it points to a Box
we allocate boxes dynamically with new Box or new Box(1, 2)
Dynamic allocation creates the box and returns its address
.all dereferences (ie follows the pointer)

Example:

        type Box is record
            l, w: Integer;
        end record;

        -- A type for pointers to boxes
        type BoxPtr is access Box;

        -- What is allocated here?
        p1, p2, p3: BoxPtr;
    begin
        p1 := new Box;  -- Similar to Java, but what initial values?

        p2 := new Box'(l => 11, w => 12);  -- Allocate and initialize
        p2 := new Box'(21, 22);            -- ' is required

Access Fields: Dereference with .all (implicit allowed)

Example:

        type Box is record
            len, wid: Integer;
        end record;

        -- A type for pointers to boxes
        type BoxPtr is access Box;

        b1: Box;      --  Allocate only

        -- What is allocated here?
        p1: BoxPtr;
    begin
        p1 := new Box;

        b1.len := 11;
        b1.wid := 12;

        -- .all -  explicit  dereference of the pointer
        p1.all.len := 21;
        p1.all.wid := 22;

        -- implicit dereference of the pointer
        p1.len := 31;
        p1.wid := 32;

Dereference = follow the pointer to the object it points to
Sometimes, but not always, .all can be implicit

Refer to the Entire Box with .all

Can refer to the entire box with .all

Example:

        type Box is record
            len, wid: Integer;
        end record;

        -- A type for pointers to boxes
        type BoxPtr is access Box;

        b1: Box := (11, 12);  -- Allocate and initialize

        -- What is allocated here?
        p1, p2: BoxPtr;
    begin
        p1 := new Box'(21, 22);    -- Allocate and initialize
        p2 := new Box;

        p1.all := (31, 32);  -- Aggregate assignment

        p1.all := b1;

        b1 := (41, 42);
        b1 := p1.all;

        p2.all := p1.all;

Some Type Checking

Do some type checking:

        type Box is record
            len, wid: Integer;
        end record;

        -- A type for pointers to boxes
        type BoxPtr is access Box;

        b1: Box := (11, 12);  -- Allocate and initialize

        p1, p2: BoxPtr;
    begin
        p1 := new Box;  -- Allocate
        p2 := new Box;

        p1 := b1;         --  ??

        p1.all := b1;     --  ??

        p1.all := p2;     --  ??

Some Things Never Change ...

Another similarity with Java

        type Box is record
            len, wid: Integer := 0;
        end record;

        type BoxPtr is access Box;

        b1 := (1, 2);

        p1, p2: BoxPtr;
    begin
        p1.all.len := 11;    -- Okay?

        p1.all := p2.all;    -- Okay?

        p1.all := b1;        -- Okay?

        p1 := p2;            -- Okay?

Example with Integers

Pointers to Integer would be unusual

        type Box is record
            len, wid: Integer := 0;
        end record;

        type BoxPtr is access Box;
        type IntPtr is access Integer;

        bp: BoxPtr;
        ip: IntPtr;
        j:  Integer := 01;
    begin
        bp := new Box'(11, 12);

        ip := new Integer(21);

        ip.all := j;

        ip.all := 31;

        j := ip.all;

More Strong Typing

Now let's have two pointer types

        type Box is record
            len, wid: Integer := 0;
        end record;

        type Box3D is record
            len, wid, height: Integer := 0;
        end record;

        type BoxPtr is access Box;
        type Box3DPtr is access Box3D;

        bp: BoxPtr;
        bp3D: Box3DPtr;
    begin
        bp := new Box;
        bp3D := new Box3D;

        bp := bp3D?  -- Okay?

        bp := new Box3DPtr?  -- Okay?

        bp3D.all := (len => 11, wid => 22);  -- Okay?

Can .all can be Omitted?

Sometimes .all can be omitted

Example:

        type Box is record
            len, wid: Integer := 0;
        end record;

        -- A type for pointers to boxes
        type BoxPtr is access Box;

        p1: BoxPtr;
    begin
        p1 := new Box'(11, 22);

        p1.all.len := 33;
        p1.wid := 44;

        put(p1.len);
        put(p1.all.wid);

Shorthand notation: normally you can use automatic dereference

Sometimes .all is Required

.all is required when referring to the entire object

Look carefully at the two put routines and their calls:

        type Box is record
            len, wid: Integer := 0;
        end record;

        -- A type for pointers to boxes
        type BoxPtr is access Box;

        procedure put(b: Box) is begin
            put(b.len); 
            put(b.wid);
        end put;

        procedure put(b: BoxPtr) is begin
            put(b.len); 
            put(b.all.wid);
        end put;

        p1: BoxPtr;
    begin
        p1 := new Box'(11, 22);

        -- Is there a difference here?
        p1.all := (33, 44);
        p1     := (33, 44);

        put(p1);       -- What gets called?

        put(p1.all);   -- What gets called?

Type BoxPtr: Another Example

Here is another sample program

boxptrexample2.adb (prettified)

Illustrates:

Allocation with initial values: p := new Box'(3,4);
A pointer parameter
Strong typing
.all is optional: p.all.l := 55; p.w := 66;

Some Practice and Strong Typing

In the code below, consider the expressions in each statement

    p: BoxPtr := new Box'(1, 2);
    q: BoxPtr := new Box'(3, 4);
    b: Box;
begin
    p.all.x := q.all.x;
    p.x := q.x;
    p.all := q.all;
    p.all := b;
    p := q;

    -- Strong typing - these fail type checking
    p := q.all;
    p := b;

    p.all := 3;
    p.all := q;

One Type in Java vs Two in Ada

Java and the Object Referenced

Now consider some Java statements:

    Box p = new Box(1, 2);
    Box q = new Box(3, 4);

    // p.all.x := q.all.x;   // Let's do this in java?
    p.x = q.x;

    // p.all := q.all;       // Can we do this in java?

How do we implement something similar in Java?

Java Comparison: Two Types vs One

Example:

        class Box{ 
            int l, w;
        }

        class Client{
            psvm(){
                Box p = new Box();
            }
        }

Two types vs one:

Ada uses separate types for the pointer and the thing it points to

Informally, Java uses the same type for the pointer and the object it refers to

Java Terminology: Two Types vs One

Terminology:

Actually, Java does distinguish between the two:

Actually, Java says that p has type Box and the object has class Box
The object is said to belong to class Box

Sometimes we say the variable has a run-time type which refers to the class of the object that the variable points to
The First Edition of the Java Language Specification had a section entitled "Variables Have Types, Objects Have Classes"

Dynamic Structures and Linked Lists

Problem and Solution

Problem: we want structures whose size is dynamic

Solution:

Allocate and deallocate mememory as needed

Typically using a linked structure

Examples: linked lists, stacks, queues

Dynamic Stacks and Queues

Dynamic stacks and queues:

We can use linked structures to create lists, stacks, and queues

These structures can grow and shrink as needed

Types for Linked Structures - Version 1

What we want: Define a type for a node that ...

contains a field, typically called next, that ...

points to another (typically the next) node

What would a picture of the memory for this look like:

Possible solution (with a possible problem):

        type Node is record
            data: Integer;
            next: access Node;
        end record;

How would we access the list?

What would the type of the access value be?
What if we wanted a named type for the access?

Types for Linked Structures - Version 2

Let's try this named type for the access Node:

        type Node is record
            data: Integer;
            next: NodePointer;
        end record;

        type NodePointer is access Node;

        p: NodePointer;

Okay, but p and the field next should have the same named type

Let's try this:

        type NodePointer is access Node;

        type Node is record
            data: Integer;
            next: NodePointer;
        end record;

What is the problem?

Solution: Use an incomplete definition

        type Node;      -- An incomplete definition of the name Node 

        type NodePointer is access Node;

        type Node is record
            data: Integer;
            next: NodePointer;
        end record;

Problem (Circular definition) fixed

Making a List

Let's create a list with three nodes holding integers 1, 2, 3

First draw a picture

Now let's write code to PRINT the list

In what order do we add the nodes?

Now the code:

        p, q: Node
    begin
        p := new Node;
        p.all.data := 3;
        p.all.next := null;

        t := p;
        p := new Node'(2, t);
        p.all.data := 3;
        p.all.next := t;

        -- Can we create the second node in one statement
        -- Can we create the second node in one statement
        -- Can we create the third node in one statement

Let's write the code to print each element of the list

Dynamic Stacks and Queues

A Dynamic Stack

Our stack will add and remove nodes as we push and pop

Types for a Stack and a StackNode (ignoring privacy, for now)

        type StackNode;
        type Stack is access StackNode;

        type StackNode is record
            data: Integer;
            next: Stack;
        end record;

what is a Stack:

A Stack is a pointer to a StackNode

How would we code these routines:

            s: Stack;
        begin
            push(i, s);
            pop(s);
            put(top(s));

What modes are the parameters?

Stack specification (and prettified)

An Empty Stack

Notice that empty stack is different in Ada and Java

Ada:

            s: Stack;
        begin
            if isempty(s) then ...

What happens in Java?

        Stack s;
        if (s.isNull())

What does an empty stack look like

In Ada
In Java

A Dynamic Queue

Example using a dynamic queue

        myQ: Queue;
        enqueue(3, myQ);
        enqueue(4, myQ);
        while not isempty(myQ) loop
            f := front(myQ);
            dequeue(myQ);
        end loop;

Looks just like a regular queue

Dynamic queue implementation:

A Queue is a linked list of nodes (like a stack)

Needs pointers to both the front and back of the queue

The front and back pointers point to the first and last nodes in the list

Comparison with a dynamic stack:

A stack contains just one pointer (ie the top)
A variable of type Stack IS a pointer to a StackNode

A variable of type Queue IS NOT a pointer to a QueueNode

It is a pair of pointers

Code for Dynamic Stacks and Queues

Examples specifications and bodies:

Stack specification (and prettified)

Partial Stack implementation (and prettified)

Queue specification (and prettified)

Class Exercises for Linked Structures

Write the implementatio of a routine that will print all of the elements of a stack, from top to bottom.

Write the implementation of a = operation that would efficiently determine whether or not two stacks/queues are the same, using the underlying dynamic implementation, without using push and pop.

Write the implementation of a copy operation that would efficiently make a copy of an existing stack/queue using the underlying dynamic implementation, without using push and pop.

More Uses of Pointers

Pointers - The Problem - Revisited

Problem: Knowing the size of an object at compile time is not always possible

Example: Array or record containing Strings

Example: Array whose length is not known until runtime

Example: List that can grow (to unknown size) and shrink at runtime

Example: Array whose elements are members of a type hierarchy

Parent: Person. Children: Staff, Student. Array of Person

Problem: Making a copy of an object (eg value semantics) is not always efficient

Example: Update an array element in place (ie a field in a record)

Problem: Making a copy of an object (eg value semantics) is not always feasible

May not want more than one instance of a dictionary, a DB, or an table in the OS

Example Uses of Pointer

Updating an array element in place

Record containing pointer to array allocated at runtime

Include pointers to strings in a record

Accessing a Single Copy of a Value

Problem: sometimes it's not efficient to make a copy of a value

Solution: dynamically allocate the value and access it with pointers

Example: Employee problem and an Array of Employees

solution (and prettified)

Pointers to Arrays and Strings

Problem: Don't know how large to make an array

Example: An array as a field of a record
Example: A String as a field of a record

Solution: Make the field a pointer and dynamically allocate the array

Example 1: Array of Departments, each of which contains an Array of Employees

Sample data
solution (and prettified)

Example 2: Array of Departments, each containing an Array of Employees with pointers to Strings as names