C program i curenje memorije

[NovaNada]

Pokušao sam da napravim program koji čita sa standardnog ulaza jedan red (tj. do znaka '\n'), i svaku rec ubacuje u ulančanu listu. Problem je što mi valgrind prijavljuje da imam više alokacija nego dealokacija memorije. Da li neko vidi gde je problem?

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

#define ALLOCCHECK(x) if ((x) == NULL) exit(-2)

typedef struct node {
    char* word;
    struct node* next;
} Node;


void delete_list(Node* list)
{
    Node* old;
    while(list) {
        old = list;
        list = list->next;
        free(old->word);
        free(old);
    }
}

Node* add_to_list(Node* line, char* word)
{
    Node* current;
    Node* new_node =(Node*) malloc(sizeof(Node)); 
    new_node->next = NULL;
    new_node->word = (char*) malloc(strlen(word)+1); 
    strcpy(new_node->word, word);

    if (!line) {
        line = new_node;
    } else {
        for(current=line; current->next; current = current->next);
        current->next = new_node;
    }
    return line;
}

Node* read_line(void)
{
    Node* line = NULL;
    char c, *word = NULL;
    unsigned i;

    while (1) {
        c = getchar();
        i = 1;
        while (c != ' ' && c != '\n') {
            word = (char*) realloc(word, i*sizeof(char)); 
            ALLOCCHECK(word);
            *(word+i-1) = c;
            i++;
            c = getchar();
        }
        word = (char*) realloc(word, i*sizeof(char));
        ALLOCCHECK(word);
        *(word+i-1) = '\0';

        line = add_to_list(line, word);

        free(word);
        word = NULL;
        if ( c == '\n')
            break;
    }

    return line;
}

void print_list(Node* list)
{
    Node* current = list;
    while (current) {
        printf("%s\n", current->word);
        current = current->next;
    }
}

int main(void)
{
    Node* line = NULL;

    line = read_line();

    print_list(line);

    free(line);
    line = NULL;

    return 0;
}

[voodoo_]

Nemam pojma, ali imam par saveta za optimizaciju:

1. Formiranje stringa tako što čitaš znak po znak i svaki put radiš realokaciju bafera je nepotrebno drndanje memorijskog alokatora operativnog sistema i teoretski može izazvati veliku fragmentaciju memorije procesa (ne u ovom slučaju pošto je trivijalan program, ali u nekom visoko threadovanom programu koji ovo radi jako brzo, može i te kako). Realloc nije predviđen za takve namene.
Prosto učitaj string sa gets() koji kopira string sa ulaza dok ne pritisneš \n, dobićeš pointer na učitani string, eventualno možeš nad njim da proveriš da li sadrži razmake i da na lokaciji razmaka staviš NULL karakter da bi ga terminisao. Pošto gets() vraća adresu, prosto je prekopiraj u node->word.

2. Preradi program tako da element liste ne sadrži pointer na bafer, nego da je bafer u samom elementu, to jest:

typedef struct node {
char word[MAX_SIZE];
struct node* next;
} Node;

i izbaci alokacije worda pa vidi je l se valgrind i dalje žali. String koji učitaš sa gets možeš prosto da iskopiraš u word.

[NovaNada]

Ovako radi potpuno korektno, ali u postavci zadatka moram da čuvam dinamički alociranu memoriju u listi. Probaću da iskoristim ovaj način učitavanja sa fgets(), i nekako da dinamički alociram prostor za svaku reč.

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

#define LENGHT 81

#define ALLOCCHECK(x) if ((x) == NULL) exit(-2)

typedef struct node {
    char word[LENGHT];
    struct node* next;
} Node;


void delete_list(Node* list)
{
    Node* old;
    while(list) {
        old = list;
        list = list->next;
        free(old);
    }
}

Node* add_to_list(Node* line, char* word)
{
    Node* current;
    Node* new_node =(Node*) malloc(sizeof(Node)); 
    new_node->next = NULL; 
    strcpy(new_node->word, word);

    if (!line) {
        line = new_node;
    } else {
        for(current=line; current->next; current = current->next);
        current->next = new_node;
    }
    return line;
}

Node* read_line(void)
{
    Node* line = NULL;
    char input[LENGHT+1], word[LENGHT], *c;
    unsigned i;

    if (fgets(input, LENGHT-1, stdin) == NULL)
        exit(-2);

    c = input;
    while (1) {
        i = 0;
        while (*c != ' ' && *c != '\n') {
            word[i++] = *c;
            c++;
        }
        word[i] = '\0';
        line = add_to_list(line, word);
        if (*c != '\n') {
            c++;
        } else {
            break;
        }
    }

    return line;
}

void print_list(Node* list)
{
    Node* current = list;
    while (current) {
        printf("%s\n", current->word);
        current = current->next;
    }
}

int main(void)
{
    Node* line = NULL;

    line = read_line();

    print_list(line);

    free(line);
    line = NULL;

    return 0;
}

EDIT: Uspeo sam, Valgrind više ne kuka. Hvala Voodoo!

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

#define LENGHT 81

#define ALLOCCHECK(x) if ((x) == NULL) exit(-2)

typedef struct node {
    char *word;
    struct node* next;
} Node;


void delete_list(Node* list)
{
    Node* old;
    while(list) {
        old = list;
        list = list->next;
        free(list->word);
        free(old);
    }
}

Node* add_to_list(Node* line, char* word)
{
    Node* current;
    Node* new_node =(Node*) malloc(sizeof(Node)); 
    new_node->next = NULL; 
    new_node->word = malloc(strlen(word)+1);
    ALLOCCHECK(new_node->word);
    strcpy(new_node->word, word);

    if (!line) {
        line = new_node;
    } else {
        for(current=line; current->next; current = current->next);
        current->next = new_node;
    }
    return line;
}

Node* read_line(void)
{
    Node* line = NULL;
    char input[LENGHT+1], word[LENGHT], *c;
    unsigned i;

    if (fgets(input, LENGHT-1, stdin) == NULL)
        exit(-2);

    c = input;
    while (1) {
        i = 0;
        while (*c != ' ' && *c != '\n') {
            word[i++] = *c;
            c++;
        }
        word[i] = '\0';
        line = add_to_list(line, word);
        if (*c != '\n') {
            c++;
        } else {
            break;
        }
    }

    return line;
}

void print_list(Node* list)
{
    Node* current = list;
    while (current) {
        printf("%s\n", current->word);
        current = current->next;
    }
}

int main(void)
{
    Node* line = NULL;

    line = read_line();

    print_list(line);

    free(line);
    line = NULL;

    return 0;
}

[voodoo_]

Alternativno, ako baš nećeš da budeš ograničen maksimalnom mogućom dužinom stringa, možeš da pokušaš sa prvobitnom implementacijom koristeći realloc(), ali da ne pozivaš realokaciju nakon svakog učitanog znaka već da alociraš word na neku fiksnu dužinu (npr. LENGTH), i tek ako probije tu dužinu tokom učitavanja, onda uradiš realloc na 'i' * LENGTH (gde je 'i' inicijalno jedan i povećava se pred svaku novu realokaciju). U tipičnoj upotrebi programa, realloc nikad neće ni biti pozvan, a formalno si podržao stringove beskonačne dužine (teoretski).

Sličan princip koristi implementacija vektora (niza) u standardnoj biblioteci C++, gde imaš fleksibilan niz proizvoljne dužine, a ispod haube se radi realokacija po potrebi i u velikim koracima (da bi se izbegla fragmentacija memorije).

[NovaNada]

Uradiću i na taj način.
Sada sam implementirao sličan program, samo što reči stavlja u dinamički niz, tj. matricu. Valgrind kaže da je sve dobro, ali meni se ne sviđa rešenje jer nikada nisam video da iko koristi char***. Da li može drugačije da se uradi?

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

#define LENGHT 81

#define ALLOCCHECK(x) if ((x) == NULL) exit(-2)

char** add_to_matrix(char** m, char *word, int *n);

void read_line(char*** m, int *n)
{
    char input[LENGHT+1], word[LENGHT], *c;
    unsigned i;

    if (fgets(input, LENGHT-1, stdin) == NULL)
        exit(-2);

    c = input;
    while (1) {
        i = 0;
        while (*c != ' ' && *c != '\n') {
            word[i++] = *c;
            c++;
        }
        word[i] = '\0';

        *m = add_to_matrix(*m, word, n);

        if (*c != '\n') {
            c++;
        } else {
            break;
        }
    }
}

char** add_to_matrix(char** m, char *word, int *n)
{
    if (m != NULL) {
        m = realloc(m, (*n+1)*sizeof(char*));
        ALLOCCHECK(m);
        *(m + *n) = malloc(sizeof(word)+1);
        strcpy(*(m + *n), word);
        (*n)++;

    } else {
        m = malloc(sizeof(char*));
        ALLOCCHECK(m);
        *m = malloc(sizeof(word)+1);
        ALLOCCHECK(*m);
        strcpy(*m, word);
        (*n)++;
    }

    return m;

}

int main(void)
{
    int n = 0; /*broj elemenata u matrici*/
    char** m = NULL; /*matrica*/

    read_line(&m, &n);

    for (int i = 0; i<n; i++) {
        printf("%s\n", *(m+i));
        free(*(m+i));
    }
    
    free(m);

    return 0;
}