C trie memory leak in add function

Question

I've been trying to get my code to work. It compiles but when I run it I get a segfault and gdb and valgrind pointed to this line in particular and my problem is that I don't really know how to fix it:

    if (!pCrawl->cvec[index]) {

which is in addword(). Essentially I'm supposed to implement functions in the head file for a trie data structure: makedictionary, add, search, and delete.

Here's the school supplied header file:

#define VECSIZE ('z'-'a' + 1)

typedef char *word;
enum __bool__ { FALSE, TRUE };
typedef enum __bool__ bool;

typedef struct __tnode__  *Dict, TNode;

struct __tnode__ {
  Dict cvec[VECSIZE];          
  bool eow;                   
};

void newdict(Dict *dp);
void addword (const Dict r, const word w);
bool checkword (const Dict r, const word w);
void delword (const Dict r, const word w);

void barf(char *s);           

Also not that since I can't change the header file, and bool is a typedef I can't use stdbool.h. And this is my C code which I'm writing up:

#define CHAR_TO_INDEX(c) ((int)c - (int)'a')

void newdict (Dict *dp) {
    *dp = NULL;
    dp = (Dict *)malloc(sizeof(Dict));
    if (dp) {
        int i;
        (*dp)->eow = FALSE;
        for (i = 0; i < VECSIZE; i++) {
            (*dp)->cvec[i] = NULL;
        }
    }
}

void addword (const Dict r, const word w) {
    int level;
    int length = strlen(w);
    int index;

    Dict pCrawl = r;
    printf("line 1\n");
    for (level = 0; level < length; level++) {
        index = CHAR_TO_INDEX(w[level]);
        if (!pCrawl->cvec[index]) {
            newdict(&(pCrawl->cvec[index]));
        }
        pCrawl = pCrawl->cvec[index];
    }
    pCrawl->eow = TRUE;
}

bool checkword (const Dict r, const word w) {
    int level;
    int length = strlen(w);
    int index;

    Dict pCrawl = r;

    for (level = 0; level < length; level++) {
        index = CHAR_TO_INDEX(w[level]);
        if (!pCrawl->cvec[index]) {
            return FALSE;
        }
        pCrawl = pCrawl->cvec[index];       
    }
    if (pCrawl != NULL && pCrawl->eow) {
        return TRUE;
    } else {
        return FALSE;
    }
}

I'm a bit new to C so any tips would be greatly appreciated. Thanks in advance.

Answer 1

I'm guessing that the confusion is in understanding

typedef struct _tnode__ *Dict, TNode;

This means that

Dict lookup;

is the same as

TNode* lookup;

So when you are creating the dictionary

void newdict(Dict* dp)

Is the same as

void newdict(TNode** dp)

So when allocating, allocating sizeof(Dict) is the same as sizeof(TNode*) i.e. sizeof a pointer. What is really required is a TNode. Note - in C there is no need to cast mallocs. It is only required for C++.

*dp = malloc (sizeof(TNode));

Try that and see if it fixes your problem.