Funkcja ll_push_front wywala segfaulta

Hej,
Próbuję zaimplementować listę łączoną w C i mam problem z błędem: Process finished with exit code 139 (interrupted by signal 11: SIGSEGV). Potrzebuję dodać na początek listy element i przepiąć po kolei jak leci wskaźniki następnych elementów. Podpowie mi ktoś jak to ogarnąć?
Pozdrawiam

Kodzik który sprawia problem:

void ll_push_front(struct ll_node *node, int data) {
    struct ll_node *current = (struct ll_node *) malloc(sizeof(struct node *));
    current->data = data;
    current->next = node;
    current->prev = NULL;
    node->next->prev = current;
//    while (node->next != NULL) {
//        node->next = node->prev->next;
//        node = node->next;
//    }
}

odpalasz debugger i krok po kroku.
Ale takie pytanie, co ty chcesz przepinać? W skrócie, nowy węzeł na górze dostaje prev na null a next na obecny który jest na górze. W obecnym tylko zmieniasz prev na nowy węzeł. Nie wiem co ty chcesz iterować? To własnie o to chodzi w takich węzłach żeby było je łatwo wstawiać.

No jak wstawię nowy węzeł na początek tam w to miejsce gdzie był node to muszę przepiąć resztę węzłów. Węzeł ma być wstawiony na początek listy, nie na koniec.

Dobrze tak jest?

void ll_push_front(struct ll_node *node, int data) {
    struct ll_node *current = (struct ll_node *) malloc(sizeof(struct node *));
    current->data = data;
    current->next = node;
    current->prev = NULL;
    node->prev = current;
}

struct ll_node *current = (struct ll_node *) malloc(sizeof(struct node *));

Alokujesz wielkość wskaźnika, powinno być struct ll_node *current = malloc(sizeof(struct node));

PS: rzutowanie jest niepotrzebne, o ile to nie C++, a jeśli to C++ to raczej nie powinieneś używać malloc poza edukacją.

PS2: a co jeśli node już ma jakieś elementy przed sobą?

pozwól że skorzystam z rysunku z https://www.geeksforgeeks.org/introduction-and-insertion-in-a-doubly-linked-list/

Dobra zrobiłem push_front i pop_front. Są dwie możliwości - zwrócić wskaźnik albo podać wskaźnik na wskaźnik. Dobrze to ogarnąłem? Co myślicie o tym?

void ll_push_back(struct ll_node **node, int data) {
    struct ll_node *tail = *node;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    struct ll_node *current = ll_new(data);
    current->next = NULL;
    current->prev = *node;
    tail->next = current;
}

void ll_push_front(struct ll_node **node, int data) {
    struct ll_node *head = ll_new(data);
    head->next = *node;
    head->prev = NULL;
    *node = head;
}

int ll_pop_back(struct ll_node **node) {
    struct ll_node *current = *node;
    while (current->next != NULL) {
        current = current->next;
    }
    int old_data = current->data;
    free(current);
    return old_data;
}

int ll_pop_front(struct ll_node **node) {
    int old_data = (*node)->data;
    *node = (*node)->next;
    free((*node)->prev);
    (*node)->prev = NULL;
    return old_data;
}

Ma ktoś pomysł jak ogarnąć w poniższym kodzie obslugę nulla w ll_get?

struct ll_node *ll_get_node_at(struct ll_node *node, int index) {
    if (!ll_check_index_bounds(node, index)) {
        fprintf(stderr, "ll_get_node_at: index %d is out of range", index);
        return NULL;
    }
    int n = 0;
    while (node->next != NULL) {
        if (n++ == index) {
            break;
        }
        node = node->next;
    }
    return node;
}

int ll_get(struct ll_node *node, int index) {
    struct ll_node *result = ll_get_node_at(node, index);
    if (!result) {
        // co tu dać...?
    }
    return result->data;
}

lester29 napisał(a):

Kodzik który sprawia problem:

void ll_push_front(struct ll_node *node, int data) {
    struct ll_node *current = (struct ll_node *) malloc(sizeof(struct node *));
    current->data = data;
    current->next = node;
    current->prev = NULL;
    node->next->prev = current;
//    while (node->next != NULL) {
//        node->next = node->prev->next;
//        node = node->next;
//    }
}

To ma by C czy C++?
Jeśli C to to cast-owanie jest zbędne (w C typ void* jest domyślnie konwetowany na dowolny inny wskaźnik).
Co nieby ma robić ta linijka?

node->next->prev = current;

I gdzie aktualizujesz głowę tej listy?

Żeby ostatni problem skonkretyzować potrzebny jest cały kod (jest kilka możliwości i dobrze by było by było konsystetnie z resztą).

Proszę oceńcie co mogę zmienić, co dodać. Od siebie na pewno chcę ogarnąć unit testy w cmocku żeby nauczyć się pisać kod zgodnie z TDD. Co do kodu to jest i ma być C, nie żaden C++.

main.c

#include <stdio.h>
#include "linked_list.h"

int main(void) {
    printf("** testing push_back, push_front, pop_back, pop_front operations **\n\n");
    struct ll_node *node = ll_new(2);
    if (!node) {
        fprintf(stderr, "failed to alocate memory for linked list");
        return 1;
    }
    ll_push_back(&node, 3);
    ll_push_back(&node, 4);
    ll_push_front(&node, 1);
    ll_print(node);
//    int result;
//    ll_pop_front(&node, &result);
//    printf("first call ll_pop_front: %d\n", result);
//    ll_pop_front(&node, &result);
//    printf("second call ll_pop_front: %d\n", result);
//    ll_pop_back(&node, &result);
//    printf("first call ll_pop_back: %d\n", result);
//    ll_pop_back(&node, &result);
//    printf("second call ll_pop_back: %d\n", result); <- tu wywala się program
    if (ll_is_empty(node)) {
        printf("list is empty");
    }
    ll_destroy(node);
    return 0;
}

linked_list.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H
#include <stdbool.h>

struct ll_node {
    int data;
    struct ll_node *prev;
    struct ll_node *next;
    struct ll_node *head;
    struct ll_node *tail;
};

struct ll_node *ll_new(int data);
int ll_destroy(struct ll_node *node);
int ll_push_back(struct ll_node **node, int data);
int ll_push_front(struct ll_node **node, int data);
int ll_pop_back(struct ll_node **node, int *data);
int ll_pop_front(struct ll_node **node, int *data);
int ll_delete_at(struct ll_node **node, int index, int *data);
bool ll_contains(struct ll_node *node, int data);
int ll_find(struct ll_node *node, int data);
int ll_size(struct ll_node *node);
bool ll_is_empty(struct ll_node *node);

bool ll_is_index_valid(struct ll_node *node, int index);
struct ll_node *ll_get_node_at(struct ll_node *node, int index);

int ll_get(struct ll_node *node, int index, int *data);
int ll_set(struct ll_node **node, int index, int data);

int ll_print(struct ll_node *node);

#endif //LINKED_LIST_H

linked_list.c

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

struct ll_node *ll_new(int data) {
    struct ll_node* node = malloc(sizeof(*node));
    if (!node) {
        return NULL;
    }
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

int ll_destroy(struct ll_node *node) {
    if (!node) {
        return -1;
    }
    while (node->next != NULL) {
        struct ll_node *current = node;
        node = node->next;
        free(current);
    }
    return 0;
}

int ll_push_back(struct ll_node **node, int data) {
    if (!node) {
        return -1;
    }
    struct ll_node *tail = *node;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    struct ll_node *current = ll_new(data);
    current->next = NULL;
    current->prev = *node;
    tail->next = current;
    return 0;
}

int ll_push_front(struct ll_node **node, int data) {
    if (!node) {
        return -1;
    }
    struct ll_node *head = ll_new(data);
    head->next = *node;
    head->prev = NULL;
    *node = head;
    return 0;
}

int ll_pop_back(struct ll_node **node, int *data) {
    if (!node) {
        return -1;
    }
    struct ll_node *current = *node;
    while (current->next != NULL) {
        current = current->next;
    }
    int old_data = current->data;
    free(current);
    if (data) {
        *data = old_data;
    }
    return 0;
}

int ll_pop_front(struct ll_node **node, int *data) {
    if (!node) {
        return -1;
    }
    int old_data = (*node)->data;
    *node = (*node)->next;
    if (*node) {
        free((*node)->prev);
    }
    (*node)->prev = NULL;
    if (data) {
        *data = old_data;
    }
    return 0;
}

int ll_delete_at(struct ll_node **node, int index, int *data) {
    struct ll_node *current = ll_get_node_at(*node, index);
    if (!current) {
        return -1;
    }
    if (data) {
        *data = current->data;
    }
    current->prev->next = current->next;
    current->next->prev = current->prev;
    free(current);
    return 0;
}

bool ll_contains(struct ll_node *node, int data) {
    while (node->next != NULL) {
        if (node->data != data) {
            return false;
        }
        node = node->next;
    }
    return true;
}

int ll_find(struct ll_node *node, int data) {
    if (!node) {
        return -1;
    }
    int idx = 0;
    while (node->next != NULL) {
        if (node->data == data) {
            return idx;
        }
        ++idx;
        node = node->next;
    }
    return -1;
}

int ll_size(struct ll_node *node) {
    if (!node) {
        return -1;
    }
    int size = 0;
    while (node != NULL) {
        ++size;
        node = node->next;
    }
    return size;
}

bool ll_is_empty(struct ll_node *node) {
    return ll_size(node) == 0;
}

bool ll_is_index_valid(struct ll_node *node, int idx) {
    return node && !(idx < 0 || idx >= ll_size(node));
}

struct ll_node *ll_get_node_at(struct ll_node *node, int index) {
    if (!ll_is_index_valid(node, index) || !node) {
        return NULL;
    }
    int n = 0;
    while (node->next != NULL) {
        if (n++ == index) {
            break;
        }
        node = node->next;
    }
    return node;
}

int ll_get(struct ll_node *node, int index, int *data) {
    struct ll_node *result = ll_get_node_at(node, index);
    if (!result) {
        return -1;
    }
    *data = result->data;
    return 0;
}

int ll_set(struct ll_node **node, int index, int data) {
    struct ll_node *current = ll_get_node_at(*node, index);
    if (!current) {
        return -1;
    }
    current->data = data;
    return 0;
}

int ll_print(struct ll_node *node) {
    if (!node) {
        return -1;
    }
    int i = 0;
    while (node != NULL) {
        printf("node %d: data=%d\n", i, node->data);
        node = node->next;
        ++i;
    }
    return 0;
}

Wywal wszystkie funkcje z indeksem, to nie tablica żeby działać na indeksach. Brakuje operacji insert_after/insert_before

Ja dzisiaj odpoczywam, więc tylko kilka luźnych rad.

bool wymaga stdbool do kompilacji o ile pamiętam.

Ten kod:

struct ll_node *ll_new(int data) {
    struct ll_node* node = malloc(sizeof(*node));
    if (!node) {
        return NULL;
    }
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

Jak nastawiasz strukturę to nastawiaj wszystko. Head i tail na NULL.

lepiej zrobić

    if ( node == NULL ) {

Bo jak czyta się kod to od razu wiesz, że autor oczekuje, ze node to ptr.
Taki duperel.

Na bogato.

struct ll_node {
    int data;
    struct ll_node *prev;
    struct ll_node *next;
    struct ll_node *head;
    struct ll_node *tail;
};

head i tail w każdym nodzie.

Teraz policz, robisz bazę danych Polaków - 32 miliony rekordów (dla samej listy, bez nazwisk, imion PESELi itp).
32 miliony * 4bajty (head) + 32 miliony * 4 bajty (tail) 128 000 000 bajtów = 125 000 kilobajtów = 122 megabajty.
W sumie tyle co nic.

ALE

Jak podzielisz exec'a na te 4 bajtowe kawałki i upchniesz, to masz 122 megowego execa w pamięci.
To już taki porządny wirusik się zmieści, chyba że ktoś inny tam coś upchnie.
No ale tu już masz pole do działania, i o to w programowaniu chodzi, żeby sobie pozostawiać jak największą swobodę ruchu.

(johnny_Be_good_ręką_nakreśla_znak_krzyża_na_czole_lester29)

Będzie z Ciebie użyteczny programista!