Implementacji listy łączonej i testów

Hej wam, napisałem wreszcie działającą listę łączoną, program działa, wyniki są sprawdzone w mainie. Mam w planach ogarnąć cmocka do unit testów. Co sądzicie o tym, żeby sprawdzać w funkcjach pop_front i pop_back czy lista jest pusta? Jaką wartość powinna w tym przypadku otrzymać zmienna data?

Kodzik:

main.c

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

int main(void) {
    printf("initializing list");
    struct linked_list *list = ll_new();
    ll_push_back(&list, 2);
    ll_push_back(&list, 3);
    printf("data after ll_push_bash:\n");
    ll_print(list);

    int data;
    ll_pop_back(&list, &data);
    ll_pop_back(&list, &data);
    printf("data after 2x ll_pop_back: data=%d\n", data);
    ll_print(list);

    ll_push_front(&list, 3);
    ll_push_front(&list, 4);
    printf("data after ll_push_front:\n");
    ll_print(list);

    ll_pop_front(&list, &data);
    ll_pop_front(&list, &data);
    ll_print(list);
    printf("data after 2x ll_pop_front: %d\n", data);

    printf("inserting data into list:\n");
    ll_push_front(&list, 1);
    ll_push_front(&list, 2);
    ll_push_back(&list, 3);
    ll_print(list);
    if (ll_contains(list, 3) > -1) {
        printf("list contains element 3\n");
    }
    int idx = ll_find(list, 1);
    if (idx > -1) {
        printf("list contains element 1 at position %d\n", idx);
    }
    ll_destroy(list);
    return 0;
}

linked_list.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <stdlib.h>

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

struct linked_list {
    struct ll_node *head;
    struct ll_node *tail;
    size_t size;
};

struct linked_list *ll_new(void);
int ll_destroy(struct linked_list *list);

int ll_push_back(struct linked_list **list, int data);
int ll_pop_back(struct linked_list **list, int *data);
int ll_push_front(struct linked_list **list, int data);
int ll_pop_front(struct linked_list **list, int *data);

int ll_find(struct linked_list *list, int data);
int ll_contains(struct linked_list *list, int data);

int ll_print(struct linked_list *list);

#endif //LINKED_LIST_H

linked_list.c

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

struct linked_list *ll_new(void) {
    struct linked_list *list = malloc(sizeof(struct linked_list));
    if (list == NULL) {
        return NULL;
    }
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
    return list;
}

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

int ll_push_back(struct linked_list **list, int data) {
    if (list == NULL || *list == NULL) {
        return -1;
    }
    struct ll_node *node = malloc(sizeof(struct ll_node));
    if (node == NULL) {
        return -1;
    }
    node->prev = (*list)->tail;
    node->next = NULL;
    node->data = data;
    if ((*list)->size == 0) {
        (*list)->head = node;
        (*list)->tail = node;
    } else {
        (*list)->tail->next = node;
        (*list)->tail = (*list)->tail->next;
    }
    ++((*list)->size);
    return 0;
}

int ll_pop_back(struct linked_list **list, int *data) {
    if (list == NULL || *list == NULL) {
        return -1;
    }
    if (data != NULL) {
        *data = (*list)->tail->data;
    }
    if ((*list)->size > 1) {
        struct ll_node *prev = (*list)->tail->prev;
        free((*list)->tail);
        (*list)->tail = prev;
        (*list)->tail->next = NULL;
    } else {
        free((*list)->tail);
        (*list)->tail = NULL;
        (*list)->head = NULL;
    }
    --((*list)->size);
    return 0;
}

int ll_push_front(struct linked_list **list, int data) {
    if (list == NULL || *list == NULL) {
        return -1;
    }
    struct ll_node *node = malloc(sizeof(struct ll_node));
    node->data = data;
    node->prev = NULL;
    if ((*list)->size == 0) {
        node->next = NULL;
        (*list)->tail = node;
    } else {
        node->next = (*list)->head;
    }
    (*list)->head = node;
    ++((*list)->size);
    return 0;
}

int ll_pop_front(struct linked_list **list, int *data) {
    if (list == NULL || *list == NULL) {
        return -1;
    }
    if (data != NULL) {
        *data = (*list)->head->data;
    }
    if ((*list)->size > 1) {
        struct ll_node *next = (*list)->head->next;
        (*list)->head = next;
        free((*list)->head->prev);
        (*list)->head->prev = NULL;
    } else {
        free((*list)->head);
        (*list)->head = NULL;
        (*list)->tail = NULL;
    }
    --((*list)->size);
    return 0;
}

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

int ll_contains(struct linked_list *list, int data) {
    return ll_find(list, data) >= 0;
}

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

Jeżeli Twój węzeł zawiera głowę i ogon a więc nie modyfikujesz wskaźnika przekazanego do funkcji tylko elementy otrzymane w skutek dereferencji to nie potrzebujesz używać "referencji" do wskaźnika, tak więc wygląda na to, że wszędzie gdzie używasz struct linked_list **list jako argumentu powinno wystarczyć struct linked_list *list. Za to w ll_destroy(struct linked_list *list) powinieneś przekazać "referencję" do wskaźnika.

Zeruj wskaźniki gdy zwolniasz "pokazywaną" przez nie pamięć. Co się stanie jeśli zawołasz Twoje obecne ll_destroy dwa razy pod rząd na tej samej liście?.
Zmniejsz i zeruj rozmiar gdy redukujesz bądź usuwasz listę.

Twój size to tak na prawdę count.

Teraz lepiej?

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

struct linked_list *ll_new(void) {
    struct linked_list *list = malloc(sizeof(struct linked_list));
    if (list == NULL) {
        return NULL;
    }
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
    return list;
}

int ll_destroy(struct linked_list **list) {
    if (list == NULL || *list == NULL) {
        return -1;
    }
    if ((*list)->head != NULL) {
        struct ll_node *node = (*list)->head;
        while (node->next != NULL) {
            node = node->next;
            free(node->prev);
            node->prev = NULL;
        }
        free(node);
    }
    free(*list);
    return 0;
}

int ll_push_back(struct linked_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    struct ll_node *node = malloc(sizeof(struct ll_node));
    if (node == NULL) {
        return -1;
    }
    node->prev = list->tail;
    node->next = NULL;
    node->data = data;
    if (list->size == 0) {
        list->head = node;
        list->tail = node;
    } else {
        list->tail->next = node;
        list->tail = list->tail->next;
    }
    ++(list->size);
    return 0;
}

int ll_pop_back(struct linked_list *list, int *data) {
    if (list == NULL) {
        return -1;
    }
    if (data != NULL) {
        *data = list->tail->data;
    }
    if (list->size > 1) {
        struct ll_node *prev = list->tail->prev;
        free(list->tail);
        list->tail = prev;
        list->tail->next = NULL;
    } else {
        free(list->tail);
        list->tail = NULL;
        list->head = NULL;
    }
    --(list->size);
    return 0;
}

int ll_push_front(struct linked_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    struct ll_node *node = malloc(sizeof(struct ll_node));
    node->data = data;
    node->prev = NULL;
    if (list->size == 0) {
        node->next = NULL;
        list->tail = node;
    } else {
        node->next = list->head;
    }
    list->head = node;
    ++(list->size);
    return 0;
}

int ll_pop_front(struct linked_list *list, int *data) {
    if (list == NULL) {
        return -1;
    }
    if (data != NULL) {
        *data = list->head->data;
    }
    if (list->size > 1) {
        struct ll_node *next = list->head->next;
        list->head = next;
        free(list->head->prev);
        list->head->prev = NULL;
    } else {
        free(list->head);
        list->head = NULL;
        list->tail = NULL;
    }
    --(list->size);
    return 0;
}

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

int ll_contains(struct linked_list *list, int data) {
    return ll_find(list, data) >= 0;
}

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

Wg mnie brakuje insert_after/insert_before. To kluczowe api dla listy, inaczej masz deque.

Jakie argumenty miałyby mieć insert_after/insert_before? Nie bardzo rozumiem co miałyby przyjmować, ll_node czy pierwszego znalezionego inta przed/po którym miałyby wstawiać wartość?

Dodałem takie coś:

int ll_is_index_valid(struct linked_list *list, int index) {
    return index >= 0 && index < list->count ? 0 : -1;
}

int ll_get(struct linked_list *list, int index, int *data) {
    if (list == NULL || ll_is_index_valid(list, index) < 0) {
        return -1;
    }
    int result;
    if (index <= list->count / 2 - 1) {
        struct ll_node *node = list->head;
        for (int i = 0; i <= index && node != NULL; ++i) {
            result = node->data;
            node = node->next;
        }
    } else {
        struct ll_node *node = list->tail;
        for (int i = 0; i < list->count - index && node != NULL; ++i) {
            result = node->data;
            node = node->prev;
        }
    }
    *data = result;
    return 0;
}

int ll_set(struct linked_list *list, int index, int data) {
    if (list == NULL || ll_is_index_valid(list, index) < 0) {
        return -1;
    }
    if (index <= list->count / 2 - 1) {
        struct ll_node *node = list->head;
        for (int i = 0; i <= index && node->next != NULL; ++i) {
            node = node->next;
        }
        node->prev->data = data;
    } else {
        struct ll_node *node = list->tail;
        for (int i = 0; i < list->count - index - 1 && node->prev != NULL; ++i) {
            node = node->prev;
        }
        node->data = data;
    }
    return 0;
}

Linked listy się nie indeksuje, api opartego o indeksy w ogóle nie powinno w niej być - jest kosztowne i jest zaprzeczeniem idei używania listy.

Insert before/after powinny przyjmować wskaźnik na node przed/za którym ma zostać dodany nowy element oraz wartość tego elementu. Nic więcej.

Możesz też dodać funkcję swap, która zamieni dwa elementy w liście miejscami, tutaj musisz uważać na przypadki krańcowe (lub zamienić wartości, ale to pierwsze w ramach ćwiczen warto zrobić)

kq napisał(a):

Insert before/after powinny przyjmować wskaźnik na node przed/za którym ma zostać dodany nowy element oraz wartość tego elementu. Nic więcej.

Takie coś masz na myśli?

int ll_insert_before(struct ll_node *node, int data);
int ll_insert_after(struct ll_node *node, int data);

Tak, dokładnie, chociaż nie wiem co ma oznaczać ten zwracany int

Zwracany int ma sygnalizować czy operacja się powiodła

Tak.... może to sygnalizować ewentualny błąd , nie lepiej bool? Właśnie się zastanawiam ile rzeczy można zwrócić w 4 bajtach. Ale jestem absolutnie w stanie zaakceptować Twój wybór.

Podejście mocno z 1975. Zwracałbym bool albo odpowiedniego enuma. Ale int też będzie ok, tylko tutaj z reguły jest odwrotna metodyka i zwracasz kod błędu (0 jeśli operacja się powiodła).

Nie dodawaj mocków do tych testów - nie są Ci do niczego potrzebne, a tylko zaciemnisz test.

Riddle napisał(a):

Nie dodawaj mocków do tych testów - nie są Ci do niczego potrzebne, a tylko zaciemnisz test.

Czyli w ogóle nie robić testów jednostkowych? Jak polecasz przetestować kod?

kq napisał(a):

Podejście mocno z 1975. Zwracałbym bool albo odpowiedniego enuma. Ale int też będzie ok, tylko tutaj z reguły jest odwrotna metodyka i zwracasz kod błędu (0 jeśli operacja się powiodła).

Zwracam inta bo funkcje ze standardowej biblioteki zwracają inty. Czy używanie boola będzie ok jeśli w swoim kodzie będę się trzymał booli? Co z funkcjami ze standardowej biblioteki?

@lester29: standardowe biblioteki... niedawno był ktoś tutaj kto chciał pisać własny język, trochę spore wyzwanie, ale zapytam, widzisz różnicę między narzędziem które sam zrobisz a które dostajesz w markecie? Nie pytasz co z funkcjami których sam nie napiszesz?

johnny_Be_good napisał(a):

@lester29: standardowe biblioteki... niedawno był ktoś tutaj kto chciał pisać własny język, trochę spore wyzwanie, ale zapytam, widzisz różnicę między narzędziem które sam zrobisz a które dostajesz w markecie? Nie pytasz co z funkcjami których sam nie napiszesz?

Co masz na myśli? Lepiej samodzielnie ogarnąć narzędzia do testów niż korzystać z gotowych rozwiązań?

Biblioteka standardowa C ma już ok 50 lat. W tym czasie wiele się zmieniło, zarówno w języku jak i w ogólnym podejściu do pisania programów i tworzenia API. Wg mnie bool lub enum będzie lepszym rozwiązaniem, chociaż int nie jest tragicznym, ponieważ jest zgodny istniejącym już gdzieś kanonem.

lester29 napisał(a):

Riddle napisał(a):

Nie dodawaj mocków do tych testów - nie są Ci do niczego potrzebne, a tylko zaciemnisz test.

Czyli w ogóle nie robić testów jednostkowych? Jak polecasz przetestować kod?

Nie kieruj się takimi określeniami jak jednostkowy/integracyjny. Te określenia już dawno straciły swoje ścisłe znaczenie.

Napisz testy które po prostu korzystają z listy którą napisałeś.

Riddle napisał(a):

Napisz testy które po prostu korzystają z listy którą napisałeś.

Mam użyć zewnętrznej libki jak CMocka czy zrobić własną libkę od podstaw?

lester29 napisał(a):

Riddle napisał(a):

Napisz testy które po prostu korzystają z listy którą napisałeś.

Mam użyć zewnętrznej libki jak CMocka czy zrobić własną libkę od podstaw?

Ale po co chcesz używać czegoś takiego? Nie potrzebujesz mocków do przetestowania swojej listy. Wystarczy Ci runner testów, np CppUnitTestFramework.

Jeśli dodasz mocki z użyciem CMock to po pierwsze niepotrzebnie skomplikujesz testy, a po drugie osłabisz ich zdolność do wykrywania bugów i odporność na refaktor kodu.

Riddle napisał(a):

lester29 napisał(a):

Riddle napisał(a):

Napisz testy które po prostu korzystają z listy którą napisałeś.

Mam użyć zewnętrznej libki jak CMocka czy zrobić własną libkę od podstaw?

Ale po co chcesz używać czegoś takiego? Nie potrzebujesz mocków do przetestowania swojej listy. Wystarczy Ci runner testów, np CppUnitTestFramework.

Jeśli dodasz mocki z użyciem CMock to po pierwsze niepotrzebnie skomplikujesz testy, a po drugie osłabisz ich zdolność do wykrywania bugów i odporność na refaktor kodu.

To jakie narzędzia polecisz do testów? Używam linuxa, nie windowsa z visual studio

https://nemequ.github.io/munit/
Takie coś będzie ok?

lester29 napisał(a):

https://nemequ.github.io/munit/
Takie coś będzie ok?

Tak, wydaje się spoko.

Ma ktoś pomysł jak uogólnić listę na dane dowolnego typu? Czy zmiana typu data z inta na void* będzie dobrym pomysłem?

1. Jak chcesz testować listę, to testuj listę, a nie jej mocka. Mock zapewne działa poprawnie, to lista może być popsuta…
2. W C niestety trudno o lepsze rozwiązanie niż void * w takich sytuacjach… Inne podejścia byłyby karkołomne. Byłby sens je rozważać, gdybyś chciał jednak ograniczyć zakres typów, które lista może przechowywać; ale jak faktycznie chcesz ogólną listę (a raczej chcesz), to byłoby to raczej bezcelowe.