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



  • 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.



  • Ich hol schonmal das Popcorn.



  • @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.
    


  • @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 Ich bin dafür dass du selbst was bringst.



  • 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?



  • @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);
    }
    
    


  • @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.



  • @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



  • Und wie sieht es aus?



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



  • 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
    

Anmelden zum Antworten