views:

214

answers:

6

I am developing C89 on Visual Studio 2010 Ultimate Beta (Win 7). I don't think I'm using malloc() correctly. I am new to C, so please excuse the beginner question.

The goal of my program is to count the occurrence of words in **argv using a tree.

hist.c

#include "tree.h"
#include <stdlib.h>

int main(int argc, char *argv[]) {
    unsigned int i;
    struct tree *tree;
    tree = new_tree();

    for (i = 1; i < argc; i++) {
        tree_add(tree, argv[i]);
    }

    tree_dump(tree);
    tree_free(tree);

    return 0;
}

tree_add.c:

#include "tree.h"
#include <stdlib.h>
#include <string.h>

struct tree *tree_add(struct tree *tree, char *value) {
    if (tree == NULL) {
        tree = new_tree();
        tree->value = value;
        tree->count = 0;
    }
    else if (tree->value == NULL) {
        tree->value = value;
    }
    else if (tree->value == value) {
        tree->count++;
    }
    else if (strcmp(value, tree->value) < 0) {
        tree_add(tree->left, value);
    }
    else if (strcmp(value, tree->value) > 0) {
        tree_add(tree->right, value);
    }
}

struct tree *new_tree() {
    struct tree * tree;
    tree = malloc(sizeof *tree);
    tree->left = NULL;
    tree->right = NULL;
    tree->value = NULL;
    tree->count = 0;
    return tree;
}

The error I get is:

0xC0000005: Access violation reading location 0x00000000.

I looked online, and it appears that this error is caused by trying to access improperly allocated memory. So what am I doing wrong?

UPDATED code to reflect comments. Now I have a new problem. This condition is not working properly when value == "x" and tree->value == "x"

else if (tree->value == value) {

In the debugger, I see that tree->value is 0x00553373 "x" char *, whereas value is 0x00553375 "x" char *. The hex value is different in the last digit. What is wrong here? Am I checking for string equality incorrectly?

+1  A: 

strcmp expects two strings and cannot handle null. Note that char *c="\0" is not the same as char *c = 0. The first is a pointer to a char array with a single null element, the second is a null pointer.

disown
+2  A: 
if (tree == NULL) {
    tree->value = value;
    tree->count = 0;
}

there is a problem here, if tree is NULL you can't use it, you must allocate it first

Additionally, you should store the return value of strcmp instead of doing it twice

f4
+1  A: 

You have an improper check in tree_add, here:

if (tree == NULL) { 
    tree->value = value; 
    tree->count = 0; 
} 

Since tree is not-NULL in the original call, you will not write to tree->value and it will stay NULL. When you then call strcmp, you get the access violation while trying to read from tree->value.

You never actually allocate tree->left and tree->right - you need to allocate these with malloc before using.

Michael
+2  A: 

Some problems :

tree = malloc(sizeof tree);

I think you mean sizeof *tree here, you're only allocating space for a pointer in your code, not for the entire struct.

if (tree == NULL) {
    tree->value = value;
    tree->count = 0;
}

If tree is NULL then tree->value is not ok.

Per Ekman
Heaths answer is more complete.
Per Ekman
+3  A: 

How is this part supposed to work?

    if (tree == NULL) {
        tree->value = value;
        tree->count = 0;
    }

I ask because what it will do is always attempt to dereference NULL if possible. The code amounts to:

    if (tree == NULL) {
        (NULL)->value = value;
        (NULL)->count = 0;
    }

So that is going to receive the AV when it attempts to reach the value element of the struct.

I think what you are missing is that you need to call malloc() for each node in your tree. You can't call it once at the beginning as you have done here, that only allocates enough memory for one node.

You probably meant something like:

    if (tree->left == NULL) {
        tree->left = malloc(sizeof struct tree);
        tree = tree->left;
    }
    /* ... */

Then your tree_free() function must recursively traverse the tree in depth-first order, calling free() on the most leafward elements first, finishing at the root by ultimately freeing the first block you allocated.

Heath Hunnicutt
A: 

In addition to the other comments, 'tree_add' needs to return tree and the 'tree_add' calls needs to save that result. (Although the recursive calls shouldn't save them as tree, but as the left/right pointers).

mpez0