What are the memory requirements for the Pop and Push algorithms in C?

[evinda]

Hello! (Smile)

I am looking at the algorithms [m]Pop[/m] and [m]Push[/m] of a stack:

void Push(info x, pointer S)
       pointer P; /* temporary pointer */
       P=NewCell(NODE); /* malloc() */
       P->data=x;
       P->next = S;
       S=P; /* This wouldn't give the right result in C*/

Why doesn't [m]S=P[/m] work in C?

info Pop(pointer S)
      info x;
      if (IsEmptyStack(S)) then error;
      else
           x=Top(S);
           S=S->next;
      return x;

How can we find how much memory the algorithm [m]Pop[/m] needs? (Thinking)

 

[I like Serena]

Hey! (Smile)

void Push(info x, pointer S)
       ...
       S=P; /* This wouldn't give the right result in C*/

Why doesn't [m]S=P[/m] work in C?

That is because S is passed by value instead of by reference.
Changing S won't change the original pointer that was passed to the function. (Nerd)

To make it work in C, we would need:

void Push(info x, pointer *pS)
       ...
       *pS=P; /* This will give the right result in C*/

This means the pS is a pointer to a pointer, giving us the opportunity to change the original pointer. (Wasntme)

Alternatively, we can do in C++:

void Push(info x, pointer& S)
       ...
       S=P; /* This will give the right result in C++ "if" we use a reference */

The symbol & means that S is passed by reference.

info Pop(pointer S)
      info x;
      if (IsEmptyStack(S)) then error;
      else
           x=Top(S);
           S=S->next;
      return x;

How can we find how much memory the algorithm [m]Pop[/m] needs? (Thinking)

Counting the memory may depend on the course you are following.
If we try to account for everything (and many courses don't), we have:

• The required memory to pass the parameter S (1 unit).
• The required memory for the local variable x (sizeof info).
• The required memory for a stack frame and the return address (in practice 2 units, but this may depend on your course that may choose to neglect this).
• The maximum of the required memory for IsEmptyStack(S) and Top(S).

(Wasntme)

 

[evinda]

Hey! (Smile)
That is because S is passed by value instead of by reference.
Changing S won't change the original pointer that was passed to the function. (Nerd)

To make it work in C, we would need:

void Push(info x, pointer *pS)
       ...
       *pS=P; /* This will give the right result in C*/

A ok.. (Nod)

This means the pS is a pointer to a pointer, giving us the opportunity to change the original pointer. (Wasntme)

Could you explain me why pS is a pointer to a pointer?

Alternatively, we can do in C++:

void Push(info x, pointer& S)
       ...
       S=P; /* This will give the right result in C++ "if" we use a reference */

The symbol & means that S is passed by reference.

Aha.. interesting! (Nerd)

Counting the memory may depend on the course you are following.
If we try to account for everything (and many courses don't), we have:

• The required memory to pass the parameter S (1 unit).
• The required memory for the local variable x (sizeof info).
• The required memory for a stack frame and the return address (in practice 2 units, but this may depend on your course that may choose to neglect this).
• The maximum of the required memory for IsEmptyStack(S) and Top(S).

(Wasntme)

Could you explain me what a stack frame is? (Thinking)

According to my notes, the memory is: inputs & (n+1) pointers (if the stack has n elements).. (Talking)

 

[I like Serena]

Could you explain me why pS is a pointer to a pointer?

Suppose we have the following code.

struct Node {
  int value;
};

Node node;
Node *pNode = &node;
Node *ppNode = &pNode;

Then [m]node[/m] is a global object, [m]pNode[/m] is a pointer to that node, and [m]ppNode[/m] is a pointer to a pointer to that node.

Could you explain me what a stack frame is? (Thinking)

The stack is some space in the memory of the computer where all parameters to functions, and all local variables go.
It's called a stack, because we "push" a function call on top of the stack together with all its parameters and local variables.
And when the function call is done, they all get "popped" again from the top.

When the function call is made, the computer needs to keep track where those parameters and local variables actually are, and also to which address he should return when the function call is done. To do that, a marker is also pushed onto the stack, together with the return address.
These make up the so called stack frame. (Nerd)

According to my notes, the memory is: inputs & (n+1) pointers (if the stack has n elements).. (Talking)

That sound like the total memory or something of a RAM machine.
A RAM machine keeps track of $n$ registers, and additionally it will get inputs that it will read.
If those are limited, we need to figure out how many of those a function will need, before we know if that function can be executed by the RAM machine. (Wasntme)

 

[evinda]

Suppose we have the following code.

struct Node {
  int value;
};

Node node;
Node *pNode = &node;
Node *ppNode = &pNode;

Then [m]node[/m] is a global object, [m]pNode[/m] is a pointer to that node, and [m]ppNode[/m] is a pointer to a pointer to that node.

void Push(info x, pointer S)
       pointer P; /* temporary pointer */
       P=NewCell(NODE); /* malloc() */
       P->data=x;
       P->next = S;
       S=P;

I thought that when the function is like that in C, S is not a pointer, but only if the parameter would be *S.
So, why is *S a pointer to a pointer? (Worried)

The stack is some space in the memory of the computer where all parameters to functions, and all local variables go.
It's called a stack, because we "push" a function call on top of the stack together with all its parameters and local variables.
And when the function call is done, they all get "popped" again from the top.

When the function call is made, the computer needs to keep track where those parameters and local variables actually are, and also to which address he should return when the function call is done. To do that, a marker is also pushed onto the stack, together with the return address.
These make up the so called stack frame. (Nerd)

I haven't understood it... (Sweating) Could you explain it further to me?

That sound like the total memory or something of a RAM machine.
A RAM machine keeps track of $n$ registers, and additionally it will get inputs that it will read.
If those are limited, we need to figure out how many of those a function will need, before we know if that function can be executed by the RAM machine. (Wasntme)

So, what do we have to count, in order to find the needed memory? (Worried)

 

[I like Serena]

I thought that when the function is like that in C, S is not a pointer, but only if the parameter would be *S.
So, why is *S a pointer to a pointer? (Worried)

There has to be a typedef:

typedef Node *pointer;

It means that when we refer to [m]pointer S[/m] it is actually [m]Node *S[/m].
And [m]pointer *pS[/m] is actually [m]Node **pS[/m].

I haven't understood it... (Sweating) Could you explain it further to me?

What is it that you do not understand?

To be fair, this is a concept that may requires a bit more than only a couple of lines to explain. (Tauri)

So, what do we have to count, in order to find the needed memory? (Worried)

What do you think we have to count? (Wondering)

 

[evinda]

There has to be a typedef:

typedef Node *pointer;

It means that when we refer to [m]pointer S[/m] it is actually [m]Node *S[/m].
And [m]pointer *pS[/m] is actually [m]Node **pS[/m].

So, you mean that in C, it should be like that?

void Push(info x, pointer *S)
       pointer *P; /* temporary pointer */
       P=NewCell(NODE); /* malloc() */
       P->data=x;
       P->next = S;
       **S=P;

Or have I understood it wrong?

What do you think we have to count? (Wondering)

How can we figure out how many registers and inputs the function needs in our case? (Thinking)

 

[I like Serena]

So, you mean that in C, it should be like that?

void Push(info x, pointer *S)
       pointer *P; /* temporary pointer */
       P=NewCell(NODE); /* malloc() */
       P->data=x;
       P->next = S;
       **S=P;

Or have I understood it wrong?

Does it compile? (Wondering)

How can we figure out how many registers and inputs the function needs in our case? (Thinking)

How many registers do you count that would be needed, counting the things we can? (Wondering)

 

[evinda]

Does it compile? (Wondering)

I don't think so... (Sweating)

How many registers do you count that would be needed, counting the things we can? (Wondering)

How can we count how many registers are needed? (Worried)

 

[I like Serena]

I don't think so... (Sweating)

Then what's going wrong? (Wondering)

How can we count how many registers are needed? (Worried)

We need 1 register to keep the value of the parameter S.
It's not clear how many registers we need for x. That depends on how much information the type [m]info[/m] holds, but can say for now that it is sizeof(info).
Then we call 2 functions that would again take the parameter S.
Those 2 functions probably don't need anything else, so that is 1 more register.
If we ignore the stack frame and return address, that makes for a total of:
$$1 + \text{sizeof}(info) + 1 = \text{sizeof}(info) + 2$$
(Mmm)

 

[evinda]

Then what's going wrong? (Wondering)

We need 1 register to keep the value of the parameter S.
It's not clear how many registers we need for x. That depends on how much information the type [m]info[/m] holds, but can say for now that it is sizeof(info).
Then we call 2 functions that would again take the parameter S.
Those 2 functions probably don't need anything else, so that is 1 more register.
If we ignore the stack frame and return address, that makes for a total of:
$$1 + \text{sizeof}(info) + 1 = \text{sizeof}(info) + 2$$
(Mmm)

We use three times the value of the parameter S, right? (Thinking)

So, shouldn't it be $\text{sizeof}(info) + 3$?

Or have I understood it wrong? (Worried)

 

[I like Serena]

We use three times the value of the parameter S, right? (Thinking)

So, shouldn't it be $\text{sizeof}(info) + 3$?

Or have I understood it wrong? (Worried)

The first time we're getting S as an input parameter, which takes up 1 register.
The second time, we use S to call IsStackEmpty(S), which takes up another register (although this could be optimized away).
After that we don't need this 2nd register anymore and we can reuse it.
Then, the third time, in the call to Top(S), we can reuse the 2nd register to pass S as a parameter. (Nerd)

Actually, Top(S) would keep x as a local variable before returning it, which would take another $\text{sizeof}(info)$, although that can be optimized away as well. (Thinking)

But to keep things clean we would get: $2\text{ sizeof}(info) + 2$ (excluding stack frame and return address). (Mmm)