About Lab 04, COMP2521

hardrain

About Post

Create on: 2019-10-27 19:45:58 UTC

Update on: 2019-10-27 19:45:58 UTC

Words: 640

For the task 1 in lab 04, COMP2521, the difficult point is that you cannot count comparisons like how you count rotates because:

  1. The "dummy" functions (cmp(), less() and eq()) (in fact, it is called "macro" in C) is implemented for comparing, there's no way to add other statement inside them.
  2. Although real functions are created, we still have no access to within point from the input of these functions, thus, we have no way to access the parent Tree (as well as ncompares counter inside it).

In sight of these facts, we have to find every single call of these three macros.

There are basically 2 ways for these 3 macros to be called:

First: Being called normally, the return was taken.

e.g. code in Tree.c at line (May be different as Tree.c is modified by every single student.)

int diff = cmp (key (it), key (t->value));

This case is pretty easy, just add these line under it.

t->within->ncompares += 1;

Second: The return of the macro forms the condition of if() statement

This can be more complex except when there is multiple if()...N*<else if()>...else{} and the macro appears in the condition of the else if() statement.

e.g. Line (around) 241-251 in Tree.c:

    if (t->left == NULL) {
        t->left = newNode (it);
    } else if (less (v, key (t->left->value))) {
        t->left->left = insertSplay (t->left->left, it);
        t = rotateR (t);
    } else {
        t->left->right = insertSplay (t->left->right, it);
        t->left = rotateL (t->left);
    }

    t = rotateR (t);

The question is: is less() called if t->left == NULL? Or the other cases like this?


We can find it out by writing and playing with the following simple code:

#include <stdio.h>

int less_5 (int i) {
    printf("compared!\n");
    if (i < 5)
        return 1;
    else 
        return 0;
}

int main (void) {
    int a;
    scanf("%d", &a);
    if (a == 0) 
        printf("CASE 1\n"); 
    else if (a == 1)
        printf("CASE 2\n");
    else if (less_5(a)) 
        printf("CASE 3\n");
    else
        printf("CASE 4\n");
    return 0;
}

It is obvious that if the function int less_5 (int i); is called, compared! (and newline/LF/'\n') will be printed to stdout.

So, the result is:

leo@arch-vm-03: ~/cs2521/04 $ gcc -no-pie -o demo demo.c
leo@arch-vm-03: ~/cs2521/04 $ ./demo
0
CASE 1
leo@arch-vm-03: ~/cs2521/04 $ ./demo
1
CASE 2
leo@arch-vm-03: ~/cs2521/04 $ ./demo
2
compared!
CASE 3
leo@arch-vm-03: ~/cs2521/04 $ ./demo
4
compared!
CASE 3
leo@arch-vm-03: ~/cs2521/04 $ ./demo
100
compared!
CASE 4

Then you got the answer for the question. (Which is NO.)


We can now implement the counter with the second case like this:

    if (t->left == NULL) {
            t->left = newNode (it);
    } else if (less (v, key (t->left->value))/*LESS1*/) {
        t->left->left = insertSplay (t->left->left, it);
        t = rotateR (t);
        //LESS1
        t->within->ncompares += 1;
    } else {
        t->left->right = insertSplay (t->left->right, it);
        t->left = rotateL (t->left);
        //LESS1
        t->within->ncompares += 1;
    }

    t = rotateR (t);

The principle is:

  1. only increase the counter after the if() / else if () statements containing the macros.
  2. Create comments at where the macros are called and your code adding 1 to the ncompares, this avoids you from messing up the code when playing with nested if-else if-else statements.

Appendix

One possible final version of Tree.c can be found at here.

The demo.c mentioned in this article can also be found at here


Comments:

There is no comment yet...

Comment as visitor:

We'll never share your email with anyone else.