Returning a struct by value gives the same wrong answer every time

Question

I'm trying to return a struct by value to find the position of a node in a tree. However using a wrapper to simplify the function call returns the incorrect value.

Relevant code:


typedef struct {
    uint16_t x;
    uint16_t y;
} coordinate_t;

coordinate_t node_pos_(uint16_t x, uint16_t y, node_t *node, node_t *find) {
    printf("%u, %u\n", x, y);

    if (node == find) {
        printf("found node at %u, %u\n", x, y);
        coordinate_t coords;
        coords.x = x;
        coords.y = y;
        return coords;
    }

    for (uint16_t i = 0; i < node->child_count; i++) {
        node_pos_(x + i, y + 1, node->children[i], find);
    }
}

coordinate_t node_pos(node_t *root, node_t *node) { 
    return node_pos_(0, 0, root, node);
}

int main() {
    coordinate_t coords = node_pos(root, child2);

    printf("coordinates of %s: %u, %u\n", child2->name, coords.x, coords.y);

    return 0;
}

The output:

0, 0
0, 1
0, 2
1, 2
1, 1
found node at 1, 1
coordinates of child2: 2, 0

In `node_pos_` you're not returning anything if `node == find` is not true. — Federico klez Culloca, Oct 31 '19 at 16:23
If `node != find` what do you return then? I think you need to rethink your implementation of the recursive function. — Some programmer dude, Oct 31 '19 at 16:24
You should be getting a warning from the compiler. Be sure to enable the warnings `-Wall` for gcc and clang `/W3` for microsoft. And then read and fix ***all*** of the warnings. — user3386109, Oct 31 '19 at 16:25
also note the portable method for printing `uint16_t` type is using `PRIu16`, so your code would be: `printf("%" PRIu16 ", %" PRIu16 "\n", x, y);`. See https://stackoverflow.com/questions/12120426/how-do-i-print-uint32-t-and-uint16-t-variables-value — yano, Oct 31 '19 at 16:42

Ian Abbott · Answer 1 · 2019-10-31T17:26:00.653

Currently, your node_pos_ function does not return a value in all execution paths, and has no way to indicate to the caller whether the node was found or not. Both of those are essential for a recursive algorithm that searches for a node in a tree.

In keeping with the spirit of returning a coordinate_t by value, I have reserved the coordinate pair (UINT16_MAX, UINT16_MAX) to represent the "not found" condition.

The modified function is below:

coordinate_t node_pos_(uint16_t x, uint16_t y, node_t *node, node_t *find) {
    coordinate_t coords;

    printf("%u, %u\n", x, y);

    if (node == find) {
        printf("found node at %u, %u\n", x, y);
        coords.x = x;
        coords.y = y;
        return coords;
    }

    // look for node in children
    for (uint16_t i = 0; i < node->child_count; i++) {
        coords = node_pos_(x + i, y + 1, node->children[i], find);
        if (!(coords.x == UINT16_MAX && coords.y == UINT16_MAX)) {
            // found
            return coords;
        }
    }

    // not found
    coords.x = UINT16_MAX;
    coords.y = UINT16_MAX;
    return coords;
}

As pointed out by @yano, the use of the %u printf format specifier to print a uint16_t value is not portable. A simple fix is to cast the values to unsigned int as below:

        printf("found node at %u, %u\n", (unsigned)x, (unsigned)y);

The "proper" way to fix it, avoiding the type cast, is to use the printf format specifier macros from #include <inttypes.h> as below:

        printf("found node at %" PRIu16 " , %" PRIu16 "\n", x, y);

This works the way I want but I modified the function to take int16_t arguments for x and y and return -1 on not found. Less expensive than checking two integers for equality. — Lurkki, Nov 01 '19 at 11:02

Returning a struct by value gives the same wrong answer every time

1 Answers1