[FIXED] How is this function that creates a linked list for any environment string supposed to work?

Issue

The code is the following:

typedef struct Node
{
    char *str;
    struct Node *next;

} Node;

Node *_getdir(char *path, char **pathCopy)
{
    char *token = NULL;
    Node *head;
    Node *pathNode;


if (path == NULL)
    return (NULL);

*pathCopy = strdup(path); 

head = NULL;
pathNode = malloc(sizeof(Node));
if (pathNode == NULL)
    return (NULL);

token = strtok(*pathCopy,  ":");
pathNode->str = token;
pathNode->next = head;
head = pathNode;
while (token != NULL)
{
    token = strtok(NULL, ":");
    if (token == NULL) 
        break;
    pathNode = malloc(sizeof(Node));
    if (pathNode == NULL)
        return (NULL);
    pathNode->str = token;
    pathNode->next = head;
    head = pathNode;
}
return (head);

}
path = "/sbin:/usr/sbin:/bin:/usr/bin:/usr/local/bin"
char *pathCopy = NULL;
pathDirs = _getdir(path, pathCopy);

My confusion starts at pathNode = malloc(sizeof(Node)) and finishes at return (head);

First, I don't understand why this function is allocating the size of a type variable called "Node", storing that information in a variable called pathNode, and just right after that there's an if statement to execute in case pathNode is a NULL value, I mean, how could that be possible if the "Node" type variable is fixed (at least initially)?

Second, I understand that the strtok function is used to divide a string by using a delimiter, which in this case is :. I also know that the arrow operator -> is used to access elements in Structures.

But then, the next lines of code are pathNode->str = token; and pathNode->next = head; which are like, some kind of variable declaration reversed, making the syntax look just weird to me, and these variables str and next were not declared as the case with pointers, isn't that necessary?

And finally, there's the while loop, which I guess it's going to be executed until it finds the \0 element at the end of the pathCopy string. However, there's again the use of pathNode = malloc(sizeof(Node)); , pathNode->str = token; and pathNode->next = head;, throwing me back to the previous confusion...

Solution

Your question seems to be about single-linked list. This function inserts nodes in to single-linked list.

It allocates pathNode, assigns it as head.

strtok breaks the strings in to tokens, the first token is for head.

If the next token is successful, it allocates another node, that node becomes the new head. pathNode->next = head indicates that the next element is head. It then assigns head = pathNode, and continues in the loop.

"pathNode is a NULL value, I mean, how could that be possible if the "Node" type variable is fixed (at least initially)"

pathNode can be NULL if there is not enough memory and malloc fails.

"However, there's again the use of pathNode = malloc(sizeof(Node));"

There is a malloc at the beginning for head and malloc inside the loop for the following nodes.

Also, there a couple of problems. The function uses pathCopy to duplicate the source string. This is the right approach because strtok will modify its source. But pathCopy should be freed at the end. It is of little use to return it to the caller.

Overall this function is more complicated than it needs to be. Here is a simpler example:

Node* create_node(const char* str)
{
    Node* node = malloc(sizeof(Node)); if (!node) return NULL;
    node->str = strdup(str);
    node->next = NULL;
    return node;
}

Node* mygetdir(const char* source)
{
    if (!source) return NULL;
    char *path = strdup(source);
    if (!path) return NULL;

    Node* head = NULL;
    char* token = strtok(path, ":");
    while (token)
    {
        Node* save = head;
        head = create_node(token); if (!head) return NULL;
        head->next = save;
        token = strtok(NULL, ":");
    }

    free(path);
    return head;
}

You can print it as follows. You have to free the linked list at the end.

int main(void)
{
    Node* head = mygetdir("/sbin1:/usr/sbin2:/bin3:/usr/bin4:/usr/local/bin5");
    Node* node = head;
    while (node)
    {
        printf("ID = %s\n", node->str);
        node = node->next;
    }

    node = head;
    while (node)
    {
        Node* next = node->next;

        // ******* EDIT
        // don't call `free(node->str)` if using your own version
        // because in your own version node->str is just a pointer to `pathCopy`
        free(node->str);

        free(node);
        node = next;
    }

    return 0;
}

Answered By - Barmak Shemirani

Answer Checked By - Senaida (PHPFixing Volunteer)