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


Log in to reply