I use the following code snippet to add an element to the back of my doubly circular linked list.

typedef struct node
{
    int nb;
    struct node *prev;
    struct node *next;
} st_node;

void add_back(st_node *origin, st_node *node)
{
    st_node *tmp;

    if (!origin || !node)
        exit(1);
    tmp = origin;
    while (tmp->next != origin)
        tmp = tmp->next;
    tmp->next = node;
    node->prev = tmp;
    node->next = origin;
    origin->prev = node;
}

Then I print my list with the folling function :

void    printer(st_node *origin)
{
    st_node *node;

    node = origin;
    while (node->next != origin)
    {
        printf("%d\n", node->nb);
        node = node->next;
    }
    printf("%d\n", node->nb);
}

I got the origin value with printf and then random values in a loop. I don't know what to do and I realized origin->prev = node; was causing the problem inside the add_back function but I don't know why.

Here's the main:

int main(int ac, char **av)
{
    st_node     *stack;
    int         i;

    if (ac <= 2)
        return (1);
    stack = create_element(atoi(av[1]));
    i = 2;
    while (i < ac)
        add_back(stack, create_element(atoi(av[i  ])));
    printf("Stack:\n");
    printer(stack);
}

st_node *create_element(int nb)
{
    st_node *element;
    element = malloc(sizeof(st_node *));
    element->nb = nb;
    element->next = element;
    element->prev = element;
    return (element);
}

CodePudding user response：

Your create_element() function is wrong. It does not allocate enough memory for each node. This ...

    st_node *element;
    element = malloc(sizeof(st_node *));

... should be ...

    st_node *element;
    element = malloc(sizeof(st_node));

... or, better ...

    st_node *element;
    element = malloc(sizeof(*element));

With that correction, and adding a closing brace to main(), your program works for me.

CodePudding user response：

Several bugs:

1. malloc in create_element is wrong
2. In add_back, the order of the link setting is wrong
3. In add_back, no need to loop to find the tail node. It is origin->prev
4. The printer function will segfault on an empty list because it is dereferencing node before checking whether it is non-null
5. The first if in main is too strict: It does not allow: ./myprogram 1 (i.e. a list with one element)

Here is the refactored/working code. It is annotated with the bugs/fixes:

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

typedef struct node {
    int nb;
    struct node *prev;
    struct node *next;
} st_node;

st_node *
create_element(int nb)
{
    st_node *element;

// NOTE/BUG: does _not_ allocate enough space (causing UB/undefined behavior)
#if 0
    element = malloc(sizeof(st_node *));
#else
    element = malloc(sizeof(*element));
#endif
    element->nb = nb;
    element->next = element;
    element->prev = element;
    return (element);
}

void
add_back(st_node *origin, st_node *node)
{
    st_node *tmp;

    if (!origin || !node)
        exit(1);

// NOTE/BUG: no need to traverse -- origin->prev is the back
#if 0
    tmp = origin;
    while (tmp->next != origin)
        tmp = tmp->next;
#else
    tmp = origin->prev;
#endif

// NOTE/BUG: order and set is incorrect -- causes self loop
#if 0
    tmp->next = node;
    node->prev = tmp;
    node->next = origin;
#else
    node->prev = tmp;
    node->next = tmp->next;
    tmp->next = node;
#endif
    origin->prev = node;
}

void
printer(st_node *origin)
{
    st_node *node;

// NOTE/BUG: this will segfault on an empty list
#if 1
    node = origin;
    while (node->next != origin) {
        printf("%d\n", node->nb);
        node = node->next;
    }
    printf("%d\n", node->nb);
#else
    node = origin;
    if (node != NULL) {
        while (1) {
            printf("%d\n", node->nb);
            node = node->next;
            if (node == origin)
                break;
        }
    }
#endif
}

int
main(int ac, char **av)
{
    st_node *stack;
    int i;

// NOTE/BUG: does _not_ allow for list of only one element
#if 0
    if (ac <= 2) {
#else
    if (ac < 2) {
#endif
        printf("main: too short\n");
        return (1);
    }
    stack = create_element(atoi(av[1]));

// NOTE/BUG: for loop is cleaner
#if 0
    i = 2;
    while (i < ac)
        add_back(stack, create_element(atoi(av[i  ])));
#else
    for (i = 2;  i < ac;    i)
        add_back(stack, create_element(atoi(av[i])));
#endif

    printf("Stack:\n");
    printer(stack);
}

In the above, I used cpp conditionals to denote old/broken vs. new/fixed code:

#if 0
// old code
#else
// new code
#endif

The above code fixed most of the bugs, but the program could not create an empty list.

Here's some more cleanup/refactoring to make the program more general. In particular, I generalized add_back to allow adding a node to an empty list. In the original code, it treated this as a fatal exit condition.

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

typedef struct node {
    int nb;
    struct node *prev;
    struct node *next;
} st_node;

st_node *
create_element(int nb)
{
    st_node *element;

    element = malloc(sizeof(*element));
    element->nb = nb;
    element->next = element;
    element->prev = element;
    return (element);
}

st_node *
add_back(st_node *origin, st_node *node)
{
    st_node *tmp;

    if (node == NULL)
        exit(1);

    do {
        // add to empty list
        if (origin == NULL) {
            origin = node;
            break;
        }

        tmp = origin->prev;

        node->prev = tmp;
        node->next = tmp->next;
        tmp->next = node;
        origin->prev = node;
    } while (0);

    return origin;
}

void
printer(st_node *origin)
{
    st_node *node;

    node = origin;
    if (node != NULL) {
        while (1) {
            printf("%d\n", node->nb);
            node = node->next;
            if (node == origin)
                break;
        }
    }
}

int
main(int ac, char **av)
{
    st_node *stack = NULL;
    int i;

    for (i = 1;  i < ac;    i)
        stack = add_back(stack, create_element(atoi(av[i])));

    printf("Stack:\n");
    printer(stack);
}