Tuesday, May 5, 2009

back to the roots – linked list in C

I just had great fun to remember how to code linked list in C. I did it jest for propose of exercise. Next time I’ll try to do quick sort for linked list and will examine glibc if I have enough time for this exercise. Good lack and enjoy great game of coding ;)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

/**
 * Example of linked list in C
 * GUID of this code sniped: 75c6b760-1fa9-4b94-8f8d-53e5e4d6a20c
 * Author: Darius Kucinskas (c) 2008-2009
 * Email: d[dot]kucinskas[eta]gmail[dot]com
 * Blog: http://blog-of-darius.blogspot.com/
 * License: GPL
 */

typedef struct llnode LLNODE;

struct llnode
{
    void* data;
    LLNODE* next;
    LLNODE* prev;
};

int myprintstr(void* str)
{
    printf("'%s'\n", (char*)str);
    return 0;
}

int myfindstr(void *listdata, void *searchdata)
{
    return strcmp((char*)listdata, (char*)searchdata);
}

LLNODE* my_list_alloc0()
{
    LLNODE* n = malloc(sizeof(LLNODE));
    if (n == NULL)
    {
        return NULL;
    }

    memset(n, 0, sizeof(LLNODE));
    return n;
}

LLNODE* my_list_append(LLNODE* tail, void* data)
{
    LLNODE* n = my_list_alloc0();
    if (n == NULL)
    {
        printf("bad malloc my_list_append\n");
        return NULL;
    }

    n->data = data;

    if (tail != NULL)
    {
        assert(tail-<next == NULL);
        tail->next = n;
        n->prev = tail;
    }

    return n;
}

LLNODE* my_list_prepend(LLNODE* head, void* data)
{
    LLNODE* n = my_list_alloc0();
    if (n == NULL)
    {
        printf("bad malloc my_list_prepend\n");
        return NULL;
    }

    n->data = data;

    if (head != NULL)
    {
        assert(head->prev == NULL);
        n->next = head;
        head->prev = n;
    }

    return n;
}

int my_list_foreach(LLNODE* head, int(*func)(void*))
{
    LLNODE* p = head;
    while(p != NULL)
    {
        if (func(p->data) != 0)
        {
            return -1;
        }

        p = p->next;
    }
    return 0;
}

LLNODE* my_list_find(LLNODE* head, int (*func)(void*, void*), void* data)
{
    LLNODE* p = head;
    while(p != NULL)
    {
        if (func(p->data, data) == 0)
        {
            return p;
        }

        p = p->next;
    }

    return NULL;
}

void my_list_swap(LLNODE* p1, LLNODE* p2)
{
    void* p = p2->data;
    p2->data = p1->data;
    p1->data = p;
}

int my_list_sort_bubble(LLNODE** head, int(*func)(void*, void*))
{
    int sort_again = 1;

    while(sort_again == 1)
    {
        LLNODE* p = *head;
        sort_again = 0;

        while((p != NULL) && (p->next != NULL))
        {
            LLNODE* p2 = p->next;

            if (strcmp(p->data, p2->data) > 0)
            {
                my_list_swap(p, p2);
                sort_again = 1;
            }

            p = p->next;
        }
    }

    return 0;
}

void my_list_free1(LLNODE* node)
{
    assert(node != NULL);
    if (node == NULL)
    {
        return;
    }

    if (node->data != NULL)
    {
        free(node->data);
    }

    free(node);
}

void my_list_free(LLNODE* head)
{
    assert(head != NULL);
    if (head == NULL)
    {
        return;
    }

    LLNODE* p = head;
    while(p != NULL)
    {
        LLNODE* node = p;
        p = p->next;

        my_list_free1(node);
    }
}

unsigned long my_list_length(LLNODE* head)
{
    assert(head->prev == NULL);

    LLNODE* p = head;
    unsigned long count = 0;

    while(p != NULL)
    {
        count++;
        p = p->next;
    }

    return count;
}

long my_list_index(LLNODE *head, int (*func)(void*, void*), void* data)
{
    LLNODE* p = head;
    long index = 0;

    while(p != NULL)
    {
        if (func(p->data, data) == 0)
        {
            return index;
        }

        index++;
        p = p->next;
    }

    return -1;
}

LLNODE* my_list_concat(LLNODE* head1, LLNODE* head2)
{
    if ((head1 == NULL) || (head2 == NULL))
    {
        return NULL;
    }

    LLNODE* p = head1;
    while(p->next != NULL)
    {
        p = p->next;
    }

    p->next = head2;
    head2->prev = p;

    return head1;
}

int main(int argc, char** argv)
{
    LLNODE* head, *head2 = NULL;
    LLNODE* tail = NULL;

    tail = my_list_append(NULL, "first");
    if (tail == NULL)
    {
        printf("Failed to create new list");
        return 0;
    }
    head = tail;// save head of list

    // test of prepend
    head = my_list_prepend(head, "xxx");

    tail = my_list_append(tail, "second");
    tail = my_list_append(tail, "fird");
    tail = my_list_append(tail, "aac");
    tail = my_list_append(tail, "aaa");
    tail = my_list_append(tail, "test_very_long_string_jest_in_case!!!");
    tail = my_list_append(tail, "aab");
    tail = my_list_append(tail, "aba");
    tail = my_list_append(tail, "abb");

    printf("--- list: ---\n");
    my_list_foreach(head, myprintstr);
    printf("--- end of list ---\n");

    printf(" length of list: %ld \n", my_list_length(head));

    // sort
    my_list_sort_bubble(&head, myfindstr);
    printf("--- list after sort: ---\n");
    my_list_foreach(head, myprintstr);
    printf("--- end of list ---\n");

    // find test
    LLNODE* f1 = my_list_find(head, myfindstr, (void*)"test");
    if (f1 == NULL)
        printf("test not found\n");
    else
        printf("found '%s'\n", (char*)f1->data);

    // fins test
    LLNODE* f2 = my_list_find(head, myfindstr, (void*)"second");
    if (f2 == NULL)
        printf("test not found\n");
    else
        printf("found '%s'\n", (char*)f2->data);

    printf("Find index of 'xxx': %ld\n", my_list_index(head, myfindstr, (void*)"xxx"));
    printf("Find index of 'aba': %ld\n", my_list_index(head, myfindstr, (void*)"aba"));
    printf("Find index of 'test': %ld\n", my_list_index(head, myfindstr, (void*)"test"));

    // test concat
    tail = my_list_append(NULL, "ccc");
    if (tail == NULL)
    {
        printf("Failed to create new list");
        return 0;
    }
    head2 = tail;// save head of list
    tail = my_list_append(tail, "cbc");
    tail = my_list_append(tail, "cbb");
    tail = my_list_append(tail, "ddd");
    tail = my_list_append(tail, "ddc");
    tail = my_list_append(tail, "dcd");
    tail = my_list_append(tail, "dcc");
    tail = my_list_append(tail, "eee");
    tail = my_list_append(tail, "eed");

    head = my_list_concat(head, head2);
    printf("--- list after concat: ---\n");
    my_list_foreach(head, myprintstr);
    printf("--- end of list ---\n");

    // sort
    my_list_sort_bubble(&head, myfindstr);
    printf("--- list after sort: ---\n");
    my_list_foreach(head, myprintstr);
    printf("--- end of list ---\n");

    my_list_free(head);

    return 0;
}