4
\$\begingroup\$

Recently, I wrote a C header file that defines a new type called HashMap that allows for the storage of key/value pairs.

I am just learning about the wonders of void pointers and as I use them, I get lots and lots of warnings about making pointers without a cast. The header file itself does not yield any warnings, but when I use the header file, I get lots.

Here is the header file (I am leaving out all the guards and other preprocessor commands):

typedef struct {
    int size;
    void **k;
    void **v;
} HashMap;

void hashmap_init(HashMap *hm, int size) {
    hm->k = malloc(size);
    hm->v = malloc(size);
    hm->size = size;
}

void hashmap_push(HashMap *hm, void *k, void *v, int index) {
    hm->[index] = k;
    hm->[index] = v;
}

void *hashmap_get(HashMap *hm, void *k) {
    int i;
    for(i = 0; i < hm->size; i++)
        if(hm->k[i] == k)
            return hm->v[i];
}

And the file in which I am testing the header:

int main(void) {
    HashMap hm; // a new HashMap
    hashmap_init(&hm, 10); // Initialize the HashMap with 10 spots for memory

    hashmap_push(&hm, 3, 7, 0); // In the first index, put 3 as the key and 7 as it's value

    int v = (int)hashmap_get(&hm, 3); // Get the key dubbed 3 from the hashmap

    printf("%d\n", v); // => 7
    return 0;
}

I was thinking: In Java, when using a HashMap, you initialize it with 2 different values. Would it be better if I did that here? (this is just a second thought - you don't have to answer this too)

\$\endgroup\$
7
\$\begingroup\$

You have a bug

This doesn't compile for me:

hm->[index] = k;
hm->[index] = v;

I think you meant this:

hm->k[index] = k;
hm->v[index] = v;

Understanding the warnings and responding to them

Recently, I wrote a C header file that defines a new type called HashMap that allows for the storage of key/value pairs.

As comments pointed out, this is not a hash map. It's a map. This wiki page explains what is a hash map.

I am just learning about the wonders of void pointers and as I use them, I get lots and lots of warnings about making pointers without a cast.

Pay attention to the warnings. Any unhandled warnings are bugs waiting to happen.

Since you mentioned you're new with pointers, I'm getting the feeling that maybe you're just not comfortable reading warnings yet. They are not that hard to read though, and you don't really have a choice: you must read and understand them so you could eliminate them.

Here's an example:

t.c: In function 'main':
t.c:31:5: warning: passing argument 2 of 'hashmap_push' makes pointer from integer without a cast [enabled by default]
     hashmap_push(&hm, 3, 7, 0);
     ^

As a reminder, here's the method signature:

void hashmap_push(HashMap *hm, void *k, void *v, int index);

The method takes as 2nd parameter a void*, but you're passing it the int value 3. Well, that just doesn't work: you're passing the wrong type. To make it work, the compiler casts this integer to void*, and warns you about it. Is this really what you wanted? No. Casting an int variable to void* can't be good.

The next warning is related to the first:

t.c:15:6: note: expected 'void *' but argument is of type 'int'
 void hashmap_push(HashMap *hm, void *k, void *v, int index) {
      ^

The first warning was about calling hashmap_push with the wrong parameter types, this one is about the hashmap_push receiving the wrong parameter types.

Next warnings:

t.c:31:5: warning: passing argument 3 of 'hashmap_push' makes pointer from integer without a cast [enabled by default]
     hashmap_push(&hm, 3, 7, 0);
     ^
t.c:15:6: note: expected 'void *' but argument is of type 'int'
 void hashmap_push(HashMap *hm, void *k, void *v, int index) {
      ^

I hope you guessed, this warning is about the same line, but this time argument 3, which is the int value 7. Same problem: casting an int to void*.

t.c:33:5: warning: passing argument 2 of 'hashmap_get' makes pointer from integer without a cast [enabled by default]
     int v = (int)hashmap_get(&hm, 3);
     ^
t.c:20:7: note: expected 'void *' but argument is of type 'int'
 void *hashmap_get(HashMap *hm, void *k) {
       ^

Based on the explanations earlier, can you tell what this is trying to tell you?

The 2nd argument of the call to hashmap_get is invalid, as the number 3 is of type int instead of void*. The warning after that is about the receiving side: the hashmap_get is expecting a void* but it's receiving an int.

Finally, this one:

t.c:33:13: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
     int v = (int)hashmap_get(&hm, 3);
             ^

Can you tell what the warning is trying to tell you?

The hashmap_get method returns a void*, but you're casting it to int. This is not valid.

In short, all these warnings were trying to tell you that you're calling methods with the wrong types. It's a fairly lucky accident that this code works at all and produces the expected output. Without clearing up these warnings by calling the methods with the appropriate types, you cannot trust this code.

The header file itself does not yield any warnings, but when I use the header file, I get lots.

When the header file compiles without warnings, but the source file using that header produces warnings, that practically means the source file is misusing the header. The header is like a contract: it specifies what you can do. Your source file twisted that contract. You got a result that sort of magically seemed to work, but it's in violation of the contract, and it wasn't really supposed to work.

Using the map without warnings

This (by no means good) code eliminates the warnings and works:

int main(map) {
    HashMap hm;
    hashmap_init(&hm, 10);

    int key = 3;
    int value = 7;
    hashmap_push(&hm, &key, &value, 0);

    int v = * (int*) hashmap_get(&hm, &key);

    int key2 = 3;
    float value2 = 5.3;
    hashmap_push(&hm, &key2, &value2, 0);

    float v2 = * (float*) hashmap_get(&hm, &key2);

    printf("%d\n", v);
    printf("%f\n", v2);

    return 0;
}

This code passes the methods the types they expect, and doesn't make invalid casts, namely:

  • &key is a int*, which is a subtype of void*, therefore valid
  • Same for &value
  • Casting the 1st call to hashmap_get to int* is valid, because it corresponds to the type of &value that was passed in earlier for &key
  • Casting the 2nd call to hashmap_get to float* is valid, because it corresponds to the type of &value2 that was passed in earlier for &key2

I used different value types for the sake of a demonstration, but keep in mind that ideally (and in 99% of practical cases) all values of a map should be of the same type. Among other things, one reason for that is given some key k whose value you don't know, you cannot know in advance the correct type of the value. In this specific example, I knew in advance that the value of key2 is value2.

Finally, what do you think the program outputs?

7 5.300000

Well, this is a bit unexpected from a map. Normally I would expect from a map that if I set the value of key 3 to x, and then again set the value of key 3 to y, the second call would update the existing entry and overwrite it with y. This map works this way because of this code in hashmap_get:

    if (hm->k[i] == k)
        return hm->v[i];

That is, you are comparing the pointers of keys, rather than their values. In a more common map implementation, two distinct key objects both having the value 3 would be treated as the same key. To make this code work that way, it will take a substantial rewrite, and rethinking of the types.

Other coding style issues

I suggest to use braces with all single-line statements, for example instead of:

for (i = 0; i < hm->size; i++)
    if (hm->k[i] == k)
        return hm->v[i];

Write like this:

for (i = 0; i < hm->size; i++) {
    if (hm->k[i] == k) {
        return hm->v[i];
    }
}

It's a bit longer, but it can save you from some simple but common mistakes.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you for taking the time to write all of that. I also appreciate the hidden boxes along with the questions tied to them to get me thinking about it myself. \$\endgroup\$ – SirPython Dec 14 '14 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.