HASH_FIND_INT garbage values

[Jake S]

I was solving a problem on Leetcode using uthash, and I encountered undefined behavior.

The pattern is just hashing all values, marking the value which is hashed twice, and marking the value missing from the hash.

• Struct definition:

struct entry {

    int id;

    UT_hash_handle hh;

};

Because the key -is- the hashed value, all that is necessary to keep track of is whether or not the hash exists.

• Code:

int* findErrorNums(int* nums, int numsSize, int* returnSize) {

    *returnSize = 2;

    int* ans = malloc(sizeof(int) * 2);

    struct entry *hash = NULL;

    // hash all values, find duplicate value: -- LOOP A --

    for (int i=0; i < numsSize; i++) {

        struct entry *e;

        int num = nums[i];

        HASH_FIND_INT(hash, &num, e);

        if (e) ans[0] = e->id;  // value already exists, mark it

        else {

            struct entry *new = malloc(sizeof(struct entry));

            new->id = nums[i];

            HASH_ADD_INT(hash, id, new);

        }

    }

    // search for non-existent value: -- LOOP B --

    for (int i=0; i < numsSize; i++) {

        struct entry *e;

        int num = nums[i];

        HASH_FIND_INT(hash, &num, e);

        if (!e) {

            ans[1] = nums[i];   // value does not exist, mark it

            break;

        }

    }

    // delete / free memory: -- LOOP C --

    struct entry *cur, *tmp;

    HASH_ITER(hh, hash, cur, tmp) {

        HASH_DEL(hash, cur);

        free(cur);

    }

    return ans;

}

• Result:
• Case 1:
• Input: [1, 2, 2, 4]
• Output: [2, -10994795586]
• Expected: [2, 3]
• Case 2:
• Input: [1, 1]
• Output: [1, -10994795586]
• Expected: [1, 2]
• Case 3:
• Input: [1, 2, 3, 4, 3, 6, 7]
• Output: [3, -10994795586]
• Expected: [3, 5]

• Analysis:

All cases set the second value to a garbage value. 

My lack of understanding is the reason for why a NULL pointer returned from HASH_FIND_INT prevents me from accessing an index of the original array, of which is never passed into any of the hash functions.

Why aren't I able to access the original array, if an unrelated pointer in my program, *e, happens to be set to NULL?

LOOP A correctly sets ans[0], and freeing memory takes place after ans[1] has already been set.

The issue has to lie in LOOP B.

• All of these alterations yield the same error:
• Directly calling FIND_INT with &nums[i] instead of using the variable num
• Setting ans[1] to num, instead of nums[i]
• Setting ans[1] to anything (such as an integer literal, 20), instead of nums[i]
• Declaring a variable, v, to mark the index of the missing value, and setting ans[1] to the nums array at that index (nums[v])
• Letting LOOP B run through instead of breaking early on NULL pointer
• Completely removing the deletion / freeing of memory (LOOP C)
• Adding an integer to the entry struct to store the hashed value, instead of using the id key

- - - - - - - - - - - - - - - - - - - - - - - - - -

I was expecting to be able to rubber duck debug this, but basically every function in the source code calls on something else, and it kind of requires a holistic understanding. The explanation for HASH_INT in the docs only refers to the returned pointer *s, of course. That isn't my issue (at least I don't believe it is.)

I greatly appreciate your consideration.

[Arthur O'Dwyer]

Hi Jake,

All your uthash usage looks reasonable to me. But I would suggest posting a complete program if possible, rather than just these two snippets. How is `main` calling your helper function?

And make sure to compile with -W -Wall (or with -W4 on MSVC), and at least look at all the warnings, even if you don't fix them (though you should!).

...However, after reproducing the behavior on Godbolt, OK, I see your (non-uthash-related) bug. I'll give you a hint:

          ans[1] = nums[i];   // value does not exist, mark it

If the value `nums[i]` doesn't exist in the supplied integer array `nums`, then... what value is at `nums[i]`? ;)

–Arthur

--
You received this message because you are subscribed to the Google Groups "uthash" group.
To unsubscribe from this group and stop receiving emails from it, send an email to uthash+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/uthash/xQkelPh_Pow6053qVTThbe0FJpYPAa9Vcx86RQOFQAXMAKMY1KkrCqWtB55SbFf6yiYDBWnf4avJKJyOlP1TAaOPdCMCsaxNbqkY26-UHmQ%3D%40proton.me.

[Jake S]

I meant to see this sooner, and Proton Mail is finicky / the replies do not appear in the inbox at all, my apologies.

It is amazing the difference stepping away from your code for 3 days can make, and I had a very good laugh.

Thank you very much for your help!