Simple word counter

Question

I've decided to do this by writing a simple word counter. The app gets all the params and outputs all the unique words, each one with a counter:

"Hello world Hello" would return "Hello: 2", "world: 1"

(not taking in consideration the actual output structure)

This program is the Python equivalent of:

import sys
from collections import defaultdict

def main():
    results = defaultdict(int)
    for word in sys.argv[1:]:
        results[word] += 1
    print results

Writing it in C is a bit different. I feel like I'm getting something utterly wrong with pointers, arrays of pointers and all that stuff.

#include <stdio.h>
#include <stdlib.h>

// This is what a key-value pair: <int, string>
typedef struct {
    int counter;
    unsigned char* word;
} hashmap;

// Checks if inside the array of results, hashmap->word is equals to word paramter
hashmap* get_word_from_results(hashmap* results[], int count, const char* word) {
    int i;
    hashmap* result;
    for (i = 0; i < count; i++) {
        result = results[i];
        if (result->word == (unsigned char *)word)
            return result;
    }
    return NULL;
}

int main(int argc, const char *argv[])
{
    hashmap* results;
    int results_counter = 0;

    int i;
    const char* word;
    for (i = 1; i < argc; i++) {
        word = argv[i];
        hashmap* result = get_word_from_results(&results, results_counter, word);
        // If result is NULL, means word is not inserted yet, let's create a new hashmap and insert it inside the array
        if (result == NULL) {
            hashmap h;
            h.counter = 1;
            h.word = (unsigned char *)word;

            results = realloc(NULL, (results_counter + 1) * sizeof(hashmap) );
            // NOTE: potential memory leak? would h be deallocated?
            results[results_counter] = h;
            results_counter++;
            printf("NEW\n");
        } else {
            // The word already exists in the hashmap array, let's increase it by 1
            result->counter++;
            printf("INCREMENTED\n");
        }
    }   
    return 0;
}

1. Can anyone give me some advice?
2. What am I doing wrong here?
3. Are my pointers okay? I also think I've spotted a memory leak (see comments).
4. Would anyone like to submit their version?

Answer 1

Well, firstly, your hashmap isn't a hash map. If that's what you want, it'd be better to go and implement one first. Remember, just because C doesn't have direct support for OO, doesn't mean you can't write real containers, or use real abstractions.

Try implementing the hash map in isolation first, then you can test the implementation, and then write your app on top.

Alternatively, if you want to focus on the app logic first,and then drill down into the implementation, either find an existing hashmap you can use, or switch to C++ and just use std::unordered_map<std::string, int>

---

OK, and a review of the actual code:

• you're switching between char * and unsigned char * for no reason. Stick with char * for text strings

• you're using realloc wrongly; you need to pass the current value of results as the first argument if you want to grow the existing array (and have the existing values copied over)

  • eg. results = realloc(NULL, n) just discards (and leaks) the old array and allocates a new, bigger one

  • but results = realloc(results, n) moves the existing contents to a new, bigger block

    • unless the re-allocation fails, in which case you've leaked the old block. This may be an unrecoverable error anyway, but Loki Astari's comment shows the correct approach:

      hashmap *tmp = realloc(results, n);
      if (tmp)
        results = tmp; // reallocation succeeded
      else {
        // handle failure somehow?
      }
      

• the hashmap* results[] argument to get_word_from_results is the wrong type. You're passing hashmap*, and that's what it should take. The fact you're using it as an array doesn't mean you have to throw in random []

• you can't compare string values using if (result->word == word), that just checks whether they have the same address. It's exactly equivalent to if id(result.word) == id(word) in Python. Use strcmp to compare the contents of the string (or, go with C++ and use std::string references, which you can compare with ==)

---

For example, the public interface in hashmap.h might look like:

#ifndef HASHMAP_H
#define HASHMAP_H
/* nobody needs to see the contents except the implementation */
struct hashmap;

struct hashmap* create_hashmap();

void *lookup_hashmap(struct hashmap*, const char *key);
/* return NULL if not found? */

int insert_hashmap(struct hashmap*, const char *key, void *value);
/* return zero on success, -1 on collision? */
#endif

and the implementation file hashmap.c

#include "hashmap.h"

struct bucket
{
    const char *key;
    void *value;
};

struct hashmap
{
    int used; /* to calculate load factor */
    int n_buckets;
    struct bucket *buckets;
}

struct hashmap* create_hashmap() { /* allocate and initialize */ }

void *lookup_hashmap(struct hashmap *map, const char *key)
{
    /* hash key, find bucket, return value */
}

int insert_hashmap(struct hashmap *map, const char *key, void *value)
{
    /* hash key, find bucket, return -1 if it's in use?
       otherwise store value and return 0
       factor out bucket lookup from insert_ and lookup_?
       ...
    */
}

---

For reference, here's a simple C++11 implementation, which is (hopefully) much closer to Python than you can get in C:

#include <string>
#include <unordered_map>
#include <iostream>

int main(int argc, char *argv[]) {
    // std::unordered_map is similar to dict
    std::unordered_map<std::string, int> results;
    for (int i=1; i<argc; ++i) {
        std::string word = argv[i];
        results[word] += 1;
    }
    // the main complexity is that C++ library types don't have a
    // built-in way to print themselves
    std::cout << "results = {";
    for (auto i:results) {
        std::cout << i.first << ':' << i.second << ' ';
    }
    std::cout << "}\n";
}

Answer 2

I am new to programming so there is chance to be completely wrong, but isn't this line a problem?

if (result->word == (unsigned char *)word)

I think that you should compare strings using strcmp()

Answer 3

1) As Faery says, you should be using strcmp() to compare strings. What you're doing is comparing the address of the string, which is always going to be different (in your program), even if it's the same word.

2) You have got a bit confused with your pointers! Should results hold an array of hashmaps or pointers to hashmaps. I'd guess that you meant the former - in which case, the function prototype should be either:

hashmap* get_word_from_results(hashmap* results, int count, const char* word)

or

hashmap* get_word_from_results(hashmap results[], int count, const char* word)

and various lines should be:

result = &results[i];

and in main:

hashmap* result = get_word_from_results(results, results_counter, word);

3) Keep using char* rather than unsigned char*.

4) When you realloc with NULL as the first parameter, you're throwing away what you originally had. You need to initialise results = NULL; and then use results as that first parameter.

5) As an aside - don't reallocate every time through the loop. In this case, you know the maximum number of words possible, so allocate that before the start of the loop.

6) Your assignment of h is OK. You're performing a shallow copy rather than anything involving memory allocations.

7) Don't forget to free your results (preferably after printing them out)!!

Answer 4

Never trust a hand written hashing algorithm.
People have an advanced feeling of superiority if they do and they always botch it up resulting in a pretty shitty hash. Writing a good hash is actually quite hard; something you should leave to the experts or specifically study up on. DO NOT write your own and expect a good result.

The most common hash you see people write is

// DO NOT USE THIS.
// Its bad for ENGLISH worse for URLS
val = <SEED>;
for(int loop = 0;loop < len;++loop)
{    val = val * <MULT> + str[loop];
}

No matter what you choose for SEED/MULT this always pretty bad. English means the input values are nor evenly distributed and overflow of the val is usually the next thing that happens meaning you are really only generating the hash with the last 4-8 characters of the string.

C++ gives you the power of C but the express-ability of python.

#include <unordered_map>
#include <vector>
#include <iterator>
#include <iostream>
#include <sstream>

int main(int argc, char* argv[])
{
    std::vector<std::string>                 args(argv+1, argv+argc);
    std::unordered_map<std::string, int>     result;

    for(auto loop = args.begin(); loop != args.end(); ++loop)
    {   
        ++result[word];
    }   
    for(auto loop = result.begin();loop != result.end();++loop)
    {   
        std::cout << loop->first << ": " << loop->second << "\n";
    }   
}

Answer 5

Declarations must be located at the start of the scope ({}). For example, hashmap* result in the loop is not at the start of the loop body.

As two other answers have stated, use strcmp() to compare strings. For example (strcmp(x,y) == 0) is true if x and y are equal. You'll have to add #include <string.h>.

if(result == NULL) is easy to get wrong because C will sap you of your will. Always make sure the lhs of a condition expression is not a l-value. For example, if(NULL == x) or if(x + 0 == y).

Just don't use realloc(). It is six functions in one. Just do the following...

{
    hashmap* temp;
    temp = (pair_p) malloc((results_counter + 1) * sizeof(hashmap));
    memmove(temp, results, (results_counter + 1) * sizeof(hashmap));
    free(results);
    results = temp;
}

Comments in C are /* */ not //.

Get rid of unsigned qualifier for the strings, as another person said.

Rename hashmap to pair. For instance,

typedef struct {
    int counter;
    char * word;
} pair, * pair_p;

Replacing pair_p for hashmap* ...

pair_p get_word_from_results(pair_p results[], int count, char* word)

Notice that the first parameter is the wrong type. It reads as results is an array of pointers of type pair. But it should read as results is a pointer of type pair. (Yes, I know it is a sequence but trust me on this.) Removing the square brackets will fix it.

As to your memory leak comment. It is wrong. h would not be leaked because it is stored on the stack and not on the heap. But results would leak from the prior line. Grr!