Algorithms

Table Lookup

A small table can map codes to values without a chain of repeated conditions.

table row Each row stores one code and the value associated with it.
lookup The loop searches rows until the requested code matches.

Table Lookup

code
table_lookup.c
Replay: real traced execution (multi-file project)
#include <stdio.h>

struct Rate {
    char code;
    int value;
};

int main(void) {
    char code = 'B';
    struct Rate rates[3] = {{'A', 10}, {'B', 20}, {'C', 30}};
    int result = 0;

    for (int i = 0; i < 3; i++) {
        if (rates[i].code == code) {
            result = rates[i].value;
            break;
        }
    }

    printf("value=%d\n", result);
    return 0;
}

#include <stdio.h>

struct Rate {
    char code;
    int value;
};

int main(void) {
    char code = 'A';
    struct Rate rates[3] = {{'A', 10}, {'B', 20}, {'C', 30}};
    int result = 0;

    for (int i = 0; i < 3; i++) {
        if (rates[i].code == code) {
            result = rates[i].value;
            break;
        }
    }

    printf("value=%d\n", result);
    return 0;
}

#include <stdio.h>

struct Rate {
    char code;
    int value;
};

int main(void) {
    char code = 'C';
    struct Rate rates[3] = {{'A', 10}, {'B', 20}, {'C', 30}};
    int result = 0;

    for (int i = 0; i < 3; i++) {
        if (rates[i].code == code) {
            result = rates[i].value;
            break;
        }
    }

    printf("value=%d\n", result);
    return 0;
}

  1. code ← B, rates ← ⟨addr A⟩, result ← 0

    8int main(void) {9    char code→ B = 'B'; //@code='A', 'C'10    struct Rate rates→ ⟨addr A⟩[3] = {{'A', 10}, {'B', 20}, {'C', 30}};11    int result→ 0 = 0;

  2. for (int i = 0; i < 3; i++)

    pass 1 of 2
    13for (int i0 = 0; i < 3; i++) {14    if (rates[i].code == code) {

  3. for (int i = 0; i < 3; i++)

    pass 2 of 2
    13for (int i1 = 0; i < 3; i++) {14    if (rates[i].code == code) {

  4. result ← 20

    13for (int i = 0; i < 3; i++) {14    if (rates[i].codeB == codeB) {15        result→ 20 = rates[i].value20;16        break;17    }

  5. printf("value=%d ", result);

    20    printf("value=%d\n", result20);21    return 0;22}
    outputvalue=20

  1. code ← A, rates ← ⟨addr A⟩, result ← 0

    8int main(void) {9    char code→ A = 'A';10    struct Rate rates→ ⟨addr A⟩[3] = {{'A', 10}, {'B', 20}, {'C', 30}};11    int result→ 0 = 0;

  2. for (int i = 0; i < 3; i++)

    13for (int i0 = 0; i < 3; i++) {14    if (rates[i].code == code) {

  3. result ← 10

    13for (int i = 0; i < 3; i++) {14    if (rates[i].codeA == codeA) {15        result→ 10 = rates[i].value10;16        break;17    }

  4. printf("value=%d ", result);

    20    printf("value=%d\n", result10);21    return 0;22}
    outputvalue=10

  1. code ← C, rates ← ⟨addr A⟩, result ← 0

    8int main(void) {9    char code→ C = 'C';10    struct Rate rates→ ⟨addr A⟩[3] = {{'A', 10}, {'B', 20}, {'C', 30}};11    int result→ 0 = 0;

  2. for (int i = 0; i < 3; i++)

    pass 1 of 3
    13for (int i0 = 0; i < 3; i++) {14    if (rates[i].code == code) {
    All 3 passes — pass 1 is the card above
    passirates[i].codecoderates[i].valueresult
    10————
    21————
    32CC300 → 30

  3. result ← 30

    13for (int i = 0; i < 3; i++) {14    if (rates[i].codeC == codeC) {15        result→ 30 = rates[i].value30;16        break;17    }

  4. printf("value=%d ", result);

    20    printf("value=%d\n", result30);21    return 0;22}
    outputvalue=30