Skip to main content
Code Review

Return to Answer

Added info about calloc and about a bug
Source Link
user1118321
user1118321
  • 11.8k
  • 1
  • 19
  • 46

Edit: Also, instead of calling malloc() and then manually setting each field to 0, you can use calloc(sizeof(Node), 1); to both allocate and clear the memory.

Use Types

Also, you were starting with an empty node with an uninitialized string, and ending with an empty node with an uninitialized string. I fixed the first by setting the value field of last before allocating a new node. I fixed the second by only allocating the next node if we have some characters remaining in the string.

Edit: I also realized that both of our implementations have another bug in them. If the file (or input string) is empty, we end up with a list containing an empty node, whereas we probably should not have a list at all. You could fix that by not allocating a node until you know you have a string. So root would start out as NULL and could end up as NULL if there are no lines in the input. I'll leave that as an exercise for the reader. :-)

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

typedef struct Node {
    void* value;
    struct Node* next;
} Node;

int main() {
    char *input_string = "Line 1\nLine 2\nLine 3";
    long remaining = (long)strlen(input_string);
    long chunk_size;
    char *next_line = input_string;
    char *string_copy;
    Node *root = malloccalloc(sizeof(Node), 1);
    Node *last = root;
    Node *lines = NULL;
    
    while (remaining > 0) {
        char* next_new_line = strpbrk(next_line, "\n");
        /* If the string doesn't end with "\n", we need the rest of the string */
        if (next_new_line == NULL) {
            chunk_size = remaining;
        }
        else {
            chunk_size = next_new_line - next_line;
        }
        
        /* This allocates and copies the string */
        string_copy = strndup(next_line, chunk_size);
        
        last->value = (void *) string_copy;
        
        /* + 1 bc the '\n' is ignored */
        remaining -= chunk_size + 1;
        next_line += chunk_size + 1;
        
        /* If there's more, then allocate another node for the next go round */
        if (remaining > 0) {
            last->next = malloccalloc(sizeof(Node), 1);
            last->next->value = NULL;
            last->next->next = NULL;
            last = last->next;
        }
    }
    
    lines = root;
    
    /* do something with lines */
}

Use Types

Also, you were starting with an empty node with an uninitialized string, and ending with an empty node with an uninitialized string. I fixed the first by setting the value field of last before allocating a new node. I fixed the second by only allocating the next node if we have some characters remaining in the string.

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

typedef struct Node {
    void* value;
    struct Node* next;
} Node;

int main() {
    char *input_string = "Line 1\nLine 2\nLine 3";
    long remaining = (long)strlen(input_string);
    long chunk_size;
    char *next_line = input_string;
    char *string_copy;
    Node *root = malloc(sizeof(Node));
    Node *last = root;
    Node *lines = NULL;
    
    while (remaining > 0) {
        char* next_new_line = strpbrk(next_line, "\n");
        /* If the string doesn't end with "\n", we need the rest of the string */
        if (next_new_line == NULL) {
            chunk_size = remaining;
        }
        else {
            chunk_size = next_new_line - next_line;
        }
        
        /* This allocates and copies the string */
        string_copy = strndup(next_line, chunk_size);
        
        last->value = (void *) string_copy;
        
        /* + 1 bc the '\n' is ignored */
        remaining -= chunk_size + 1;
        next_line += chunk_size + 1;
        
        /* If there's more, then allocate another node for the next go round */
        if (remaining > 0) {
            last->next = malloc(sizeof(Node));
            last->next->value = NULL;
            last->next->next = NULL;
            last = last->next;
        }
    }
    
    lines = root;
    
    /* do something with lines */
}

Edit: Also, instead of calling malloc() and then manually setting each field to 0, you can use calloc(sizeof(Node), 1); to both allocate and clear the memory.

Use Types

Also, you were starting with an empty node with an uninitialized string, and ending with an empty node with an uninitialized string. I fixed the first by setting the value field of last before allocating a new node. I fixed the second by only allocating the next node if we have some characters remaining in the string.

Edit: I also realized that both of our implementations have another bug in them. If the file (or input string) is empty, we end up with a list containing an empty node, whereas we probably should not have a list at all. You could fix that by not allocating a node until you know you have a string. So root would start out as NULL and could end up as NULL if there are no lines in the input. I'll leave that as an exercise for the reader. :-)

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

typedef struct Node {
    void* value;
    struct Node* next;
} Node;

int main() {
    char *input_string = "Line 1\nLine 2\nLine 3";
    long remaining = (long)strlen(input_string);
    long chunk_size;
    char *next_line = input_string;
    char *string_copy;
    Node *root = calloc(sizeof(Node), 1);
    Node *last = root;
    Node *lines = NULL;
    
    while (remaining > 0) {
        char* next_new_line = strpbrk(next_line, "\n");
        /* If the string doesn't end with "\n", we need the rest of the string */
        if (next_new_line == NULL) {
            chunk_size = remaining;
        }
        else {
            chunk_size = next_new_line - next_line;
        }
        
        /* This allocates and copies the string */
        string_copy = strndup(next_line, chunk_size);
        
        last->value = (void *) string_copy;
        
        /* + 1 bc the '\n' is ignored */
        remaining -= chunk_size + 1;
        next_line += chunk_size + 1;
        
        /* If there's more, then allocate another node for the next go round */
        if (remaining > 0) {
            last->next = calloc(sizeof(Node), 1);
            last = last->next;
        }
    }
    
    lines = root;
    
    /* do something with lines */
}
Source Link
user1118321
user1118321
  • 11.8k
  • 1
  • 19
  • 46

While I agree with most of what's been said in the comments, I do think that writing your own linked list is a worthwhile exercise. (Though so is learning about reallocating arrays.) So I'll go with that premise - that it's worth your time to write a linked list. And I think you've done a pretty good job to start with! Here are some suggestions.

Don't Reinvent The Wheel

You've written your own functions for count_to_next() and string_copy(). There are functions in the standard C library that do these same things, so you don't need to write your own. Instead, you could use strpbrk() and strdup() or memcpy(). strdup() actually allocates the memory for you, if you want to go that route.

Use Types

You should create type definitions for your structures to make it easier to read and save some typing. I'd do this:

typedef struct Node {
    void* value;
    struct Node* next;
} Node;

Then, whenever you declare one, you can simply write:

Node *root;

instead of:

struct Node *root;

Avoid Magic Numbers

Instead of just putting the number 20 into your code, you should either have a named constant telling you what the value 20 represents (something like const int TEST_STR_LENGTH = 20;, or get the value from the string so you can change the string without having to update the value in the code. Like this:

int remaining = strlen(raw);

Name Your Variables Appropriately

The variable names raw, pointer, and buffer aren't very informative. I recommend naming them something like input_string, next_line, and string_copy or something along those lines.

Bugs

I think the last line is incorrect. I think it should be:

lines = root;

Otherwise you're starting with the second line.

Also, you were starting with an empty node with an uninitialized string, and ending with an empty node with an uninitialized string. I fixed the first by setting the value field of last before allocating a new node. I fixed the second by only allocating the next node if we have some characters remaining in the string.

So putting it all together, your function might look something like this:

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

typedef struct Node {
    void* value;
    struct Node* next;
} Node;

int main() {
    char *input_string = "Line 1\nLine 2\nLine 3";
    long remaining = (long)strlen(input_string);
    long chunk_size;
    char *next_line = input_string;
    char *string_copy;
    Node *root = malloc(sizeof(Node));
    Node *last = root;
    Node *lines = NULL;
    
    while (remaining > 0) {
        char* next_new_line = strpbrk(next_line, "\n");
        /* If the string doesn't end with "\n", we need the rest of the string */
        if (next_new_line == NULL) {
            chunk_size = remaining;
        }
        else {
            chunk_size = next_new_line - next_line;
        }
        
        /* This allocates and copies the string */
        string_copy = strndup(next_line, chunk_size);
        
        last->value = (void *) string_copy;
        
        /* + 1 bc the '\n' is ignored */
        remaining -= chunk_size + 1;
        next_line += chunk_size + 1;
        
        /* If there's more, then allocate another node for the next go round */
        if (remaining > 0) {
            last->next = malloc(sizeof(Node));
            last->next->value = NULL;
            last->next->next = NULL;
            last = last->next;
        }
    }
    
    lines = root;
    
    /* do something with lines */
}

Oh, and don't forget to free() all those strings and Nodes after you've used them!