Calling a function makes UThash to fail

Question

I am using the hash-table implementation UThash.

I am inserting elements using the primitive:

    HASH_ADD(hh,hash_table,key,keylen,elem);

And retrieving elements with the primitive:

    HASH_FIND(hh,hash_table,key,keylen,elem);

For some reason I don't know, the behaviour of hash find is being modified when I call a function. That is to say, uthash does not find an element that is present in the table.

I suspect memory has been compromised in some way.

The function that triggers this failure does not need to execute any code to make UThash fail:

    //Note: ct = custom_type
    int func1(ct1 *ptr1, ct2 *ptr2, ct3 *ptr3,char **buffer,size_t *size)
    {
       HASH_FIND(...) //does not work

       /**
        * code
        */
        return 0;
    }

    int func2(ct1 *ptr1,ct2 *ptr2,ct3 *ptr3)
    {
        char *buffer;
        size_t buf_size;

       /**
        * code
        */

        HASH_FIND(...) // works!
        if(func1(ptr1,ptr2,ptr3,&buffer,&buf_size)){
            //code
        }/*error*/

        return 0;
    }

    int func3(ct1 *ptr1,ct2 *ptr2,ct3 *ptr3)
    {
        char *buffer;
        size_t buf_size;

        HASH_FIND(...) // works!
        if(func1(ptr1,ptr2,ptr3,&buffer,&buf_size)){
            //code
        }/*error*/

        /**
         * code
         */

        return 0;
    }

So in both func2() and func3() the same behaviour happens. hash_find() starts to fail after I call func1().

All the rest of the code is executed perfectly and correctly.

My obvious question is what could cause such type of failure?

Thank you for reading and be free to ask any additional info.

Answer 1

This can be caused by adding several items with the same key into hash. If you use uthash, you need to make sure that you don't have duplicated keys in your structure, or to provide a wrapper function which will substitute an old item with the new one. Otherwise, the behaviour of the structure is unpredictable and can cause the failure you described.

From uthash user guide:

If there’s any chance that duplicate keys could be generated by your program, you must explicitly check the uniqueness before adding the key to the hash. If the key is already in the hash, you can simply modify the existing structure in the hash rather than adding the item. It is an error to add two items with the same key to the hash table.

Answer 2

That is because you are hashing the pointer not the data.

Use HASH_ADD_KEYPTR.

Answer 3

I had similar problems, when my key had type unsigned char, after replacing it with int HASH_FIND_INT started to work properly. Further investiation showed that bother signed char and unsigned char are not appropriate, whereas short int and unsigned short int seem to work fine as well.

Probably 8 bits are not enough for hash function calculation algorithm to operate properly. Notice, that original code with unsigned char operation was intermittent, code worked in some builds, did not work in others (with changes unrelated to uthash).

Conclusion: use key of type signed int for proper operation of HASH_FIND_INT, or use short int or unsigned short at your own risk.

Answer 4

Maybe, it's not the case, but I have encountered similar problem when I used some struct as a key for HASH_FIND. Beware of struct padding when you use sizeof() to determine key length. If you don't initialize a key properly this padding may be the reason why uthash does not find when you lookup.

Answer 5

I have also encountered this problem because of struct padding, as mentioned by @yerden. On gcc it is easy, but slow, to define the struct with the packed attribute, as

struct __attribute__((__packed__)) a_struct {
    char a, b;
    unsigned int i;
};

This problem is mentioned in the uthash manual for structure keys, and the solution is to zero out the struct before adding it to the hash, as demonstrated there.

Another solution is to learn about structure packing and reorganize your struct so padding is not (or less of) an issue. A quick overview of structure packing is given in another helpful stack overflow question.