Sollen wir gemeinsam eine nette Double-linked- oder vielleicht sogar Skip List in C schreiben?

[Swordfish]

Topic ist programm. Nachdem wir hier in letzter Zeit ziemlich ... Fragen darüber hatten ... zeigen wie es geht?

[Swordfish]

Oder doch einen Artikel über alle möglichen Arten von Pointers?

[DocShoe]

Warum in C? Wir sind hier doch in einem C++ Forum.
Write in C

[Wutz]

@Swordfish
Nein. Das würde suggerieren, LL wären zu irgendwas nütze.

[DocShoe]

@Wutz
Naja, sie sind schon zu was nütze. Für die meisten Fälle reicht ein Vektor, es gibt Fälle, wo DLL besser abschneiden.

[Swordfish]

@DocShoe Weil Assembler noch weniger Spaß macht.

[Ein ehemaliger Benutzer]

Kann man machen. Würde mich auch so interessieren wie man das in der Praxis sauber macht. Ich hab was, komplett makrotisiert damits mit eigenen Typen läuft + Pointer auf ein Destructor-Callback wenn man so will. Aber das hab ich grad nicht zur Hand.

[5cript]

Ich hol schonmal das Popcorn.

[Swordfish]

@5cript bring' was mit.

@eigenartig sagte in Sollen wir gemeinsam eine nette Double-linked- oder vielleicht sogar Skip List in C schreiben?:

komplett makrotisiert damits mit eigenen Typen läuft

void *data; // done.

[Ein ehemaliger Benutzer]

@Swordfish sagte in Sollen wir gemeinsam eine nette Double-linked- oder vielleicht sogar Skip List in C schreiben?:

@5cript bring' was mit.

Wie wärs wenn du einfach selbst ein Artikel schreibst, damit wir den hier lesen, und damit der dann hier einfach eingepflegt werden kann, damit du glücklich bist, die Fresse hältst und immer was zum Zurückschauen hast.

[Swordfish]

@eigenartig sagte in Sollen wir gemeinsam eine nette Double-linked- oder vielleicht sogar Skip List in C schreiben?:

die Fresse hältst

ok.

[Ein ehemaliger Benutzer]

@Swordfish Ich bin dafür dass du selbst was bringst.

[Swordfish]

Vorschlag für eine Node und eine List:

#include <stddef.h>

typedef struct node_tag node_t;

struct node_tag {
    void    *data;
    node_t  *next;
    node_t  *prev;
};

typedef struct list_tag {
    node_t  *head;
    node_t  *tail;
    size_t   length;
} list_t;

Einwände? Vorschläge?

^{//edit: Boah ey, Tabsize hier ist immer noch 8}

// edit2: Sollen wir uns auch die payload size merken?

[Quiche Lorraine]

@Swordfish
Bitte haue mich nicht, ich hatte gerade Lust die Liste zu implementieren.

Wenn du diese mal ausprobieren möchtest, dann kopiere den folgenden Code in LinkedList.h und inkludiere diese in einem C Projekt. Die Funktion LinkedList_Test_Function() ist eine Art Testreihe für die Liste und überprüft diverse Eigenschaften.

#pragma once

#include <malloc.h>
#include <assert.h>
#include <stdbool.h>


// ******************** Defines ********************


#define LINKED_LIST_VERSION         1


// ******************** Typedefs ********************


typedef int LinkedList_NodeValueType;


/**
 * @brief Definition der Callback Funktion für LinkedList_ForEach()
 */
typedef void (*ForEachFunctionCallback)(LinkedList_NodeValueType);


/**
 * @brief Knoten der Liste
 */
typedef struct LinkedList_Node
{
    struct LinkedList_Node* mPrev;
    struct LinkedList_Node* mSucc;
    LinkedList_NodeValueType mValue;
} LinkedList_Node;


/**
 * @brief Definition der doppelt verkettete Liste
 */
typedef struct
{
    LinkedList_Node* mAnchor;
} LinkedList;


// ******************** Funktionen ********************


/**
 * @brief Initíalisiert die Liste
 */
void LinkedList_Create(LinkedList* const List)
{
    List->mAnchor = NULL;
}


/**
 * @brief Bestimmt die Anzahl der in der Liste gespeicherten Elemente.
 */
size_t LinkedList_Size(LinkedList const* const List)
{    
    LinkedList_Node const* Node = List->mAnchor;
    size_t Count = 0;

    while (Node != NULL)
    {
        Count++;
        Node = Node->mSucc;
    }
    return Count;
}


/**
 * @brief Fügt ein Element an das Ende der Liste an.
 */
void LinkedList_PushBack(LinkedList* const List, LinkedList_NodeValueType Value)
{
    if (List->mAnchor == NULL)
    {
        List->mAnchor = malloc(sizeof(LinkedList_Node));
        List->mAnchor->mPrev = NULL;
        List->mAnchor->mSucc = NULL;
        List->mAnchor->mValue = Value;
    }
    else
    {
        LinkedList_Node* Node = List->mAnchor;

        while(Node->mSucc != NULL)
            Node = Node->mSucc;
        Node->mSucc = malloc(sizeof(LinkedList_Node));
        Node->mSucc->mPrev = Node;
        Node->mSucc->mSucc = NULL;
        Node->mSucc->mValue = Value;
    }
}


/**
 * @brief Fügt ein Element der Liste an.
 */
bool LinkedList_Add(LinkedList* const List, size_t Index, LinkedList_NodeValueType Value)
{
    size_t i = 0;
    LinkedList_Node* Node = List->mAnchor;

    while (i != Index)
    {
        if (Node == NULL)
            return false;
       Node = Node->mSucc;
       i++;
    }
    if (Node != NULL)
    {
        LinkedList_Node* PrevNode = Node->mPrev;
        LinkedList_Node* NewNode = malloc(sizeof(LinkedList_Node));

        NewNode->mValue = Value;
        NewNode->mSucc = Node;
        NewNode->mPrev = PrevNode;
        if (PrevNode == NULL)
            List->mAnchor = NewNode;
        else
            PrevNode->mSucc = NewNode;
        Node->mPrev = NewNode;
        return true;
    }
    else if (Index == 0)
    {
        LinkedList_Node* SuccNode = List->mAnchor;

        List->mAnchor = malloc(sizeof(LinkedList_Node));
        List->mAnchor->mSucc = SuccNode;
        List->mAnchor->mPrev = NULL;
        List->mAnchor->mValue = Value;
        return true;
    }
    else if (i == Index)
    {
        Node = List->mAnchor;

        if (Node == NULL)
            return false;
        while (Node->mSucc != NULL)
            Node = Node->mSucc;
        Node->mSucc = malloc(sizeof(LinkedList_Node));
        Node->mSucc->mSucc = NULL;
        Node->mSucc->mPrev = Node;
        Node->mSucc->mValue = Value;
        return true;
    }
    return false;
}


/**
 * @brief Löscht das i-te Element der Liste
 */
bool LinkedList_Remove(LinkedList* const List, size_t Index)
{
    size_t i = 0;
    LinkedList_Node* Node = List->mAnchor;

    while (i != Index)
    {
        if (Node == NULL)
            return false;
       Node = Node->mSucc;
       i++;
    }
    if (Node != NULL)
    {
        LinkedList_Node* SuccNode = Node->mSucc;
        LinkedList_Node* PrevNode = Node->mPrev;

        free(Node);
        if (SuccNode != NULL)
            SuccNode->mPrev = PrevNode;
        if (PrevNode != NULL)
            PrevNode->mSucc = SuccNode;
        else
            List->mAnchor = SuccNode;
        return true;
    }
    return false;
}


/**
 * @brief Löscht die komplette Liste
 */
void LinkedList_Release(LinkedList* const List)
{
    LinkedList_Node* Node = List->mAnchor;

    while (Node != NULL)
    {
        LinkedList_Node* SuccNode = Node->mSucc;
        free(Node);
        Node = SuccNode;
    }
    List->mAnchor = NULL;
}

/**
 * @brief Bestimmt das i-te Element der Liste
 */
bool LinkedList_At(LinkedList const* const List, size_t Index, LinkedList_NodeValueType* Value)
{
    LinkedList_Node const * Node = List->mAnchor;
    size_t i = 0;

    while (i != Index)
    {
        Node = Node->mSucc;
        if (Node == NULL)
            return false;
        i++;
    }
    if (Value != NULL)
        *Value = Node->mValue;
    return true;
}


// Vorschlag für weitere Funktionen


// void LinkedList_Transform(LinkedList const* const List, LinkedList_NodeValueType Value)
// void LinkedList_ForEach(LinkedList const* const List, ForEachFunctionCallback Callback)
// void LinkedList_ForEachReverse(LinkedList const* const List, ForEachFunctionCallback Callback)
// void LinkedList_FindIf(LinkedList const* const List, LinkedList_NodeValueType Value)


// Die folgenden Funktionen dienen rein zur Überprüfung/Debugging der Liste.


/**
 * @brief Testfunktion: Überprüft den Inhalt der Liste. Wird nur für LinkedList_Test_Function() benötigt.
 */
void LinkedList_Test_ListContains(LinkedList const* const List, LinkedList_NodeValueType const* const Content, size_t Size)
{
    LinkedList_NodeValueType Value;

    assert(LinkedList_Size(List) == Size);
    for (size_t i = 0; i < Size; i++)
    {
        assert(LinkedList_At(List, i, &Value));
        assert(Value == Content[i]);
    }
    if (List->mAnchor == NULL)
        return;
    // Der Vorgänger des ersten Elements muss immer NULL sein
    assert(List->mAnchor->mPrev == NULL);
    // Nun prüfen wir die mPrev, mSucc Beziehungen
    LinkedList_Node const* Node = List->mAnchor;

    while (Node != NULL)
    {
        if (Node->mSucc != NULL)
            assert(Node->mSucc->mPrev == Node);
        if (Node->mPrev != NULL)
            assert(Node->mPrev->mSucc == Node);     // doppelt gemoppelt hält halt besser
        Node = Node->mSucc;
    }
}


/**
 * @brief Testfunktion: Stellt diverse Eigenschaften der Implementierung sicher
 */
void LinkedList_Test_Function()
{
    LinkedList L;

    LinkedList_Create(&L);
    assert(L.mAnchor == NULL);
    assert(LinkedList_Size(&L) == 0);

    // Hänge ans Ende der Liste 10 und prüfe Inhalt
    static const LinkedList_NodeValueType R1[] = { 10 };

    LinkedList_PushBack(&L, 10);
    LinkedList_Test_ListContains(&L, R1, 1);
    // Hänge ans Ende der Liste 20 und prüfe Inhalt
    static const LinkedList_NodeValueType R2[] = { 10, 20 };

    LinkedList_PushBack(&L, 20);
    LinkedList_Test_ListContains(&L, R2, 2);
    // Hänge ans Ende der Liste 30 und prüfe Inhalt
    static const LinkedList_NodeValueType R3[] = { 10, 20, 30 };

    LinkedList_PushBack(&L, 30);
    LinkedList_Test_ListContains(&L, R3, 3);
    // Füge 10 an der ersten Stelle ein und prüfe Inhalt
    static const LinkedList_NodeValueType R4[] = {10, 40, 20, 30};

    assert(LinkedList_Add(&L, 1, 40));
    LinkedList_Test_ListContains(&L, R4, 4);
    // Füge 50 an der ersten Stelle ein und prüfe Inhalt
    static const LinkedList_NodeValueType R5[] = {50, 10, 40, 20, 30};

    assert(LinkedList_Add(&L, 0, 50));
    LinkedList_Test_ListContains(&L, R5, 5);
    // Lösche Element 3 und prüfe Inhalt
    static const LinkedList_NodeValueType R6[] = {50, 10, 40, 30};

    assert(LinkedList_Remove(&L, 3));
    LinkedList_Test_ListContains(&L, R6, 4);
    // Lösche Element 0 und prüfe Inhalt
    static const LinkedList_NodeValueType R7[] = {10, 40, 30};

    assert(LinkedList_Remove(&L, 0));
    LinkedList_Test_ListContains(&L, R7, 3);
    // Füge Element 60 ans Ende hinzu und prüfe Inhalt
    static const LinkedList_NodeValueType R8[] = {10, 40, 30, 60};

    assert(LinkedList_Add(&L, 3, 60));
    LinkedList_Test_ListContains(&L, R8, 4);
    // Lösche letztes Element und prüfe Inhalt
    static const LinkedList_NodeValueType R9[] = {10, 40, 30};

    assert(LinkedList_Remove(&L, 3));
    LinkedList_Test_ListContains(&L, R9, 3);

    // Am Ende die Liste löschen
    LinkedList_Release(&L);
}

[Caligulaminus]

@Swordfish sagte in [Sollen wir gemeinsam eine nette Double-linked- oder vielleicht sogar

^{//edit: Boah ey, Tabsize hier ist immer noch 8}

Ich benutze das Stylus-Browser-Plugin und damit

code{
    tab-size: 4 !important;
}

Funktioniert wunderbar.

[hustbaer]

@Swordfish sagte in Sollen wir gemeinsam eine nette Double-linked- oder vielleicht sogar Skip List in C schreiben?:

Vorschlag für eine Node und eine List:

#include <stddef.h>

typedef struct node_tag node_t;

struct node_tag {
    void    *data;
    node_t  *next;
    node_t  *prev;
};

typedef struct list_tag {
    node_t  *head;
    node_t  *tail;
    size_t   length;
} list_t;

Einwände? Vorschläge?

Ich würde empfehlen die Liste als Ring-Liste zu implementieren. Damit spart man sich einiges an Code. Ein Nachteil ist dass dabei "next" beim letzten Element nicht NULL ist (genau so wie "prev" beim ersten). Die einfachere Implementierung wiegt das mMn. aber auf.

Weiters finde ich es in C fragwürdig einen "data" Zeiger in der Liste zu haben. Normalerweise verwendet man da intrusive Lists, macht also

struct MyData {
     MyListNode node;
     // ...
};

und bastelt sich dann Makros mit denen man von der Node zur äusseren Struct kommt (falls die Node nicht das erste Element ist).

Als Beispiel kann man sich an der Implementierung im WDK orientieren, die haben das recht nett gemacht: https://docs.microsoft.com/en-us/windows-hardware/drivers/kernel/singly-and-doubly-linked-lists

[*john 0]

Und wie sieht es aus?

[Swordfish]

@john-0 Nachdem hustbaer dieses vollständige Beispiel aus dem WDK gepostet hat habe ich das nicht weiterverfolgt.

[*john 0]

Den Thread habe ich irgend wie übersehen.

Da ich keine Motivation hatte, den x-ten Aufguss in C zu machen. Das ganze einmal in Fortran. Das auskommentierte ist untested.

module doubly_linked_list
    use iso_fortran_env
    implicit none
    private
    public :: node, list, node_create

    type :: node
        class(*), allocatable, public :: value
        class (node), pointer, private :: prevptr => null(), nextptr => null()
    contains
        procedure, pass, non_overridable :: next => node_next
        procedure, pass, non_overridable :: prev => node_prev

        final :: node_destruct
    end type node

    type :: list
        class (node), pointer, private :: headptr => null(), tailptr => null()
    contains
        procedure, pass, non_overridable :: add_tail => list_add_tail
        procedure, pass, non_overridable :: add_head => list_add_head
        procedure, pass, non_overridable :: delete => list_delete
        !procedure, pass, non_overridable :: add_before_node => list_add_before_node
        !procedure, pass, non_overridable :: add_after_node => list_add_after_node
        procedure, pass, non_overridable :: head => list_head
        procedure, pass, non_overridable :: tail => list_tail

        final :: list_destruct
    end type list
contains
    function node_create (data) result (new_node)
        class (node), pointer :: new_node
        class (*), intent(in) :: data
        integer :: error

        new_node => null()

        allocate (new_node, STAT=error)
        if (0 /= error) then
            write (error_unit,*) 'cannot allocate'
            stop
        end if

        allocate (new_node%value, STAT=error, SOURCE=data)
        if (0 /= error) then
            write (error_unit,*) 'cannot allocate'
            stop
        end if
    end function node_create

    function node_next (this) result (next_node)
        class (node), pointer :: next_node
        class (node) :: this
        
        next_node => this%nextptr
    end function node_next

    function node_prev (this) result (prev_node)
        class (node), pointer :: prev_node
        class (node) :: this

        prev_node => this%prevptr
    end function node_prev

    subroutine node_destruct (this)
        type (node) :: this

        this%nextptr => null()
        this%prevptr => null()
        deallocate(this%value)
    end subroutine node_destruct

    subroutine list_add_tail (this, node_pointer)
        class (list) :: this
        class (node), pointer, intent(in) :: node_pointer

        if (.NOT.associated(this%tailptr)) then
            this%tailptr => node_pointer
            this%headptr => node_pointer
        else
            node_pointer%prevptr => this%tailptr
            node_pointer%nextptr => null()
            this%tailptr => node_pointer
        end if
    end subroutine list_add_tail

    subroutine list_add_head (this, node_pointer)
        class (list) :: this
        class (node), pointer, intent (in) :: node_pointer

        if (.NOT.associated(this%headptr)) then
            this%headptr => node_pointer
            this%tailptr => node_pointer
        else
            node_pointer%nextptr => this%headptr
            node_pointer%prevptr => null()
            this%headptr => node_pointer
        end if
    end subroutine list_add_head

    subroutine list_delete (this)
        class (list) :: this

        type (node), pointer :: p1 => null(), p2 => null()

        p1 => this%headptr
        if (associated(p1)) then
            do

                p2 => p1%nextptr
                p1%nextptr => null()
                p1%prevptr => null()
                deallocate (p1)

                if (.NOT.associated(p2)) then
                    exit
                end if

                p1 => p2
            end do

            this%headptr => null()
            this%tailptr => null()
        end if
    end subroutine list_delete

    subroutine list_destruct (this)
        type (list) :: this

        call this%delete
    end subroutine list_destruct

!    subroutine list_add_before_node (this, position, object)
!        class (list) :: this
!        class (node), pointer, intent(in) :: position, object

!        object%prevptr => position%prevptr
!        object%nextptr => position

!        if (.NOT.associated(position%prevptr)) then
!            this%headptr => object
!        end if

!        position%prevptr => object
!    end subroutine list_add_before_node

!    subroutine list_add_after_node (this, position, object)
!        class (list) :: this
!        class (node), pointer, intent(in) :: position, object

!        object%nextptr => position%nextptr
!        object%prevptr => position

!       if (.NOT.associated(position%nextptr)) then
!            this%tailptr => object
!        end if

!        position%nextptr => object
!    end subroutine list_add_after_node

    function list_head (this) result (node_ptr)
        class (list) :: this
        class (node), pointer :: node_ptr

        node_ptr => this%headptr
    end function list_head

    function list_tail (this) result (node_ptr)
        class (list) :: this
        class (node), pointer :: node_ptr

        node_ptr => this%tailptr
    end function list_tail
end module doubly_linked_list

Und ein kurzes Testprogramm was die Nuutzung des Moduls verdeutlicht bzw. es rudimentär testet.

program doubly_linked_list_test
    implicit none

    type :: my_data
        integer :: number
        integer :: serial
    end type my_data

    type :: my_data2
        integer:: code
    end type my_data2

    call main
contains
    subroutine main
        use doubly_linked_list
        use iso_fortran_env
        implicit none

        type (my_data) :: data1, data2
        type (my_data2) :: data3
        type (list) :: my_list
        type (node), pointer :: a_node

        data1%number = 1
        data1%serial = 1

        data2%number = 1
        data2%serial = 2

        data3%code = -5
    
        a_node => node_create (data1)

        call my_list%add_head (a_node)

        a_node => null()
        a_node => node_create (data2)

        call my_list%add_head (a_node)
        a_node => null()
        
        a_node => node_create (data3)
        call my_list%add_head (a_node)

        a_node => my_list%head ()

        a_node => null()
        data1%serial = 3
        a_node => node_create (data1)

        call my_list%add_tail (a_node)
    end subroutine main
end program doubly_linked_list_test