Fixing Memory Leaks in Chapter 6.5 Example in the K&R book (Self-Referential Structures)

Question

I am using visual leak detector in visual studio and It detects some leaks when i run the program. Basically there are two leaks in the program one is detected on the malloc'd structure *p and the other is detected in its members (p->word). I read all about your discussions about freeing memory in a malloc'd structure. The problem is I can't seem to find a place where i can free the memory especially when this is a recursive structure.

Here is the code

#include <stdio.h>
#include <ctype.h>
#include <string.h>

#include <stdlib.h>
#include <vld.h>

#define MAXWORD 100

struct tnode { /*the tree node */
    char *word; /* points to itself */
    int count; /* number of occurences */
    struct tnode *left; /* left child */
    struct tnode *right; /* right child */
};


struct tnode *addtree (struct tnode *, char *);
struct tnode *talloc(void);
void treeprint (struct tnode *);
char *strdupli (char *s);
int getword (char *, int);
void strcopy (char *, const char *);

int main(void)
{
    struct tnode *root;
    char word[MAXWORD];

    root = NULL;
    while(getword(word, MAXWORD) != EOF)
        if( isalpha (word[0]))
            root = addtree(root, word);
        treeprint(root);
        return 0;
}



int getword(char *word, int lim)
{
    int c, getch(void);
    void ungetch(int);
    char *w = word;

    while(isspace(c = getch()))
        ;
    if(c != EOF)
        *w++ = c;
    if(!isalpha(c)) {
        *w = '\0';
        return c;
    }
    for( ; --lim > 0; w++)
        if(!isalnum(*w = getch())) {
            ungetch(*w);
            break;
        }
    *w = '\0';
    return word[0];

}

struct tnode *addtree (struct tnode *p, char *w)
{
    int cond;

    if (p == NULL) { /* a new word has arrived*/
        p = talloc(); /* make a new node */
        p->word = strdupli(w);
        p->count = 1;
        p->left = p->right = NULL;
    } else if ((cond=strcmp(w, p->word))==0)
        p->count++;
    else if (cond < 0)
    {
        p->left = addtree (p->left, w);
    } else
    {
        p->right = addtree(p->right, w);
    }
    return p;
}

void treeprint (struct tnode *p)
{
    if(p != NULL) {
        treeprint(p->left);
        printf("%4d %s\n", p->count, p->word);
        treeprint(p->right);
    }
}


/* talloc: make a tnode */
struct tnode *talloc(void)
{
    return (struct tnode *) malloc(sizeof(struct tnode));
}

char *strdupli (char *s) /* make a duplicate of s */
{
    char *p;
    p = (char *) malloc (strlen(s) + 1);
    if (p != NULL)
        strcopy(p, s);
    return p;
}

void strcopy (char *s, const char *t)
{
        while ((*s++ = *t++) != '\0')
        ;
}

#define BUFSIZE 100
char buf[BUFSIZE]; /* buffer for ungetch */
int bufp = 0; /* next free position in buf */
int getch(void) /* get a (possibly pushed-back) character */
{
    return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c) /* push character back on input */
{
    if (bufp >= BUFSIZE)
        printf("ungetch: too many characters\n");
    else
        buf[bufp++] = c;
}

And you need to look at *addtree function

score 3 · Accepted Answer · answered Jul 04 '13 at 06:10

To fix that, create a recursive function who looks like your print function to free you tree.

An example :

void free_tree (struct tnode *p)
{
    if(p != NULL) {
        free_tree(p->left);
        free_tree(p->right);
        free( p->word );
        free( p );
    }
}

You can put it in the main after treeprint :

int main(void)
{
    ...
    treeprint(root);
    free_tree( root );
    // ^^^^^^^^^^^^^^^
    return 0;
}

score 2 · Answer 2 · edited May 23 '17 at 12:11

In situations like this, you write a recursive function to free the tree when you're done with it. In keeping with the style of this code:

void tfree(struct tnode *p) 
{ 
    if (p != NULL) {
        tfree(p->left);
        tfree(p->right);
        free(p->word);
        free(p);
    }     
}

Note that malloced memory that's still accessible at the end of the program isn't really a leak, since the operating system will clean it up. Some interesting discussion here, in particular this answer.

OF course, it's good style to free memory once you're done with it, but I would be more concerned with memory that is allocated but now unreachable.

Fixing Memory Leaks in Chapter 6.5 Example in the K&R book (Self-Referential Structures)

2 Answers2