.
CPSC 213 – 2018 Winter Term 2
Exam Review: Function pointers and switch statements
1 [12 marks] Static and Dynamic Procedure Calls.
1a ProcedurecallsinCarenormallystatic.MethodinvocationsinJavaarenormallydynamic.Carefullyexplain
the reason why Java uses dynamic method invocation and what benefit this provides to Java programs.
1b CarefullyexplainanimportantdisadvantageofdynamicinvocationinJavaorotherlanguages.
1c DemonstratetheuseoffunctionpointersinCbywritingaprocedurecalledcomputethat:
1. has three arguments: a non-empty array of integers, the size of the array, and a function pointer;
2. computes either the array min or max depending only on the value of the function pointer argument; 3. contains a for loop, no if statements, and one procedure call (per loop).
Give the C code for compute, the two procedures that it uses (i.e., that are passed to it as the value of the function-pointer argument), and two calls to compute, one that computes min and the other that computes max (be sure to indicate which is which).
Polymorphism requires the use of dynamic method invocation. Java, like other object-oriented programming languages, provide polymorphism as a way to allow code to be parameterized by the procedures it calls, not just the data it operates on. For example, the statement ¡°a.foo()¡± calls the version of foo that is implemented by a¡¯s actual type, which is determined dynamically.
Its slower, because the procedure call requires an additional memory access, to read the target address of the dynamic jump from memory (e.g., from the jump table).
int compute (int* a, int n, int (*f)(int,int)) { int s = a[0];
for (int i=1; i
}
int min (int a, int b) { return a
}
*b = *a;
int fn4 (int* a, int* b){
if (*a > *b)
return *a;
return *b; }
3
.
3 [1 marks] Complete the C procedure named apply that returns the sum of an operation repeatedly performed on
the elements of two arrays for which a certain condition is met. Fill in the blanks!
int fn1(int a, int b) { return a+b; }
int fn2(int a, int b) { return a-b; }
int fn3(int a, int b) { return a*b; }
int fn4(int a, int b) { return a/b; }
int fn5(int a, int b) { return a>b; }
int fn6(int a, int b) { return (a-b) == 0; }
int fn7(int a, int b) { return (a-b) <= 0; }
int fn8(int a, int b) { return (a%b) == 0; }
int fn9(int a, int b) { return (a/b) == 0; }
int fn0(int a, int b) { return (a&b) == 0; }
int apply(int(*fn)(int,int),int(*cond)(int,int),int *a, int *b, int size) {
int result = 0;
for (int i = 0; i < size; i++) {
if (cond(a[i], b[i])
_________________________________________________________
}
result += fn(a[i], b[i]);
_____________________________________________________
return result;
}
3a Usingapplyandthesuppliedproceduresabove,finishtheprocedurecallsothatresultissettothesumof differences between values of the value-pairs in the array where the value in a[i] is greater than b[i].
For example:
a: {8, 2, 6, 1, 3}
b: {3, 5, 1, 4, 2}
difference: 5 -3 5 -4 1
a bigger? Y N Y N Y
result: 5 + 5 + 1 = 11
fn2, fn5
int result = apply(________________,________________, a, b, size);
3b Usingapplyandthesuppliedproceduresabove,finishtheprocedurecallsothatresultissettothesumof products between values of the value-pairs in the array where the value in a[i] is equal to b[i].
For example:
a: {8, 2, 6, 1, 3}
b: {5, 2, 7, 1, 3}
equal?: N Y N Y Y
product: 40 4 42 1 9
result: 4+1+9=14
fn3, fn6
int result = apply(________________,________________, a, b, size);
3c Usingapplyandthesuppliedproceduresabove,finishtheprocedurecallsothatresultissettothenumber of value-pairs in the array where the value in a[i] is a multiple of b[i].For example:
a: {8, 8, 6, 1, 6}
b: {8, 2, 7, 4, 3}
multiple?: Y Y N N Y
result: 3 (number of Ys)
fn8, fn8
int result = apply(________________,________________, a, b, size);
4
.
4 [6 marks] There are two ways to implement switch statements in machine code. For purposes of this question,
lets call them A and B.
4a DescribeA,verybriefly.
A sequence of IF statements.
4b DescribeB,verybriefly. A jump table.
4c StatepreciselyonesituationwhereAwouldbepreferredoverBandwhy.
4d StatepreciselyonesituationwhereBwouldbepreferredoverAandwhy.
IF statements are preferred if there are very few case labels or when the case label values are sparsely populated (i.e., there is a large gap between the smallest and largest label value. Because, in the first case there overhead of using the jumptable is higher than the cost of a few IF statements and in the second case the jump table would be too large, leading to a poor space-time tradeoff.
Jumptables are preferred when there are many cases and the labels are densely arranged, because in this case the execution cost of the switch statement is independent of the value of the index variable, which is not the case for the IF approach. The problem with IF is that if there are many case labels, it may be required to compare against each of them to find the label that matches the index variable. With the jump table, this comparison is unnecessary; the index simply selects the matching case block¡¯s code address using the variable¡¯s index into the jumptable.
5
.
5 [1 marks] Translate the following assembly code into two different C implementations. One implementation should use a switch statement, the other should use a jump table.
There is space on the next page for you to write your solutions.
You do not need to write comments, but it may award you part marks if you are unable to correctly write the corre- sponding C code.
.pos 0x100
foo: ld
ld $-2, r1
add r0, r1
bgt r1, L0
br L4
L0: ld $-6, r1
add r0, r1
bgt r1, L4
ld $-3, r1
add r1, r0
ld $jt, r1
j *(r1, r0, 4)
L6: halt
.pos 0x140
L1: ld
L2: ld
br L5
L3: ld
br L5
L4: ld
br L5
L5: ld
st r1, 0x0(r0)
.pos 0x800
jt: .long L1
.long L2
.long L4
.long L3
.pos 0x1000
i: .long 0x4
j: .long 0x0
$i, r0
ld 0x0(r0), r0
$0, r1 br L5
$1, r1
$2, r1
$3, r1
$j, r0 j L6
6
5a Solutionusingswitchstatements:
//assume i and j have been declared and initialized above
switch(i) {
case 3: j=0; break;
case 4: j=1; break;
case 6: j=2; break;
default: j=3; break;
}
5b Solutionusingajumptable:
//assume i and j have been declared and initialized above
static const void* jt[] = {&&L0, &&L1, &&DEFAULT, &&L2};
if (i < 3 ll i > 6)
goto DEFAULT;
goto *jt [i – 3];
L0: j=0; goto CONT;
L1: j=1; goto CONT;
L2: j=2; goto CONT;
DEFAULT: j=3; goto CONT;
CONT: //end of question
7