dlsort.c (v2)

#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* Double linked list implementation */

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

#define LIST_HEAD(name) \
    struct list_head name = { &(name), &(name) }

static void list_del(struct list_head *entry)
{
    struct list_head *prev = entry->prev;
    struct list_head *next = entry->next;

    next->prev = prev;
    prev->next = next;
}

static void list_add(struct list_head *new, struct list_head *head)
{
    struct list_head *prev = head->prev;
    struct list_head *next = head;

        next->prev = new;
        new->next = next;
        new->prev = prev;
        prev->next = new;
}

static int list_empty(const struct list_head *head)
{
        return head->next == head;
}

static void list_splice(const struct list_head *list, struct list_head *prev, struct list_head *next)
{
    struct list_head *first = list->next;
    struct list_head *last = list->prev;

    first->prev = prev;
    prev->next = first;

    last->next = next;
    next->prev = last;
}

/* The member type of list_head MUST be first in a structure */
#define list_entry(ptr, type, member)       ((type *)(ptr))

#define list_first_entry(ptr, type, member) list_entry((ptr)->next, type, member)

#define list_next_entry(pos, member)        list_entry((pos)->member.next, typeof(*(pos)), member)

#define list_for_each_entry_safe(pos, n, head, member)          \
    for (pos = list_first_entry(head, typeof(*pos), member),    \
           n = list_next_entry(pos, member);            \
         &pos->member != (head);                    \
         pos = n, n = list_next_entry(n, member))

/*************************************/

struct bus {
    struct list_head node;  /* MUST be first member */
    int route;
};

static void dump(struct list_head *bs)
{
    unsigned int i = 0;
    struct bus *b, *_b;

    list_for_each_entry_safe(b, _b, bs, node) {
        printf("Bus[%u]: %d\n", i++, b->route);
    }
    printf("\n");
}

static void bsfree(struct list_head *bs)
{
    struct bus *b, *_b;

    list_for_each_entry_safe(b, _b, bs, node) {
        list_del(&b->node);
        free(b);
    }
}

static int prepare(struct list_head *bs)
{
    unsigned int num;
    unsigned int i;
    struct bus *b;

    srand(time(NULL));

    num = rand() % 16;

    for (i = 0; i < num; i++) {
        b = malloc(sizeof(*b));
        if (!b)
            err(1, NULL);

        b->route = rand() % 512;
        list_add(&b->node, bs);
    }

    return 0;
}

/* Quicksort implementation for double-linked list */
static void dlsort(struct list_head *bs)
{
    struct bus *b, *_b, *first;
    LIST_HEAD(less);
    LIST_HEAD(more);
    int pivot;

    first = list_first_entry(bs, struct bus, node);
    pivot = first->route;

    list_del(&first->node);
    list_for_each_entry_safe(b, _b, bs, node) {
        list_del(&b->node);
        if (b->route >= pivot)
            list_add(&b->node, &more);
        else
            list_add(&b->node, &less);
    }
    list_add(&first->node, &less);

    if (!list_empty(&less)) {
        if (less.next != less.prev)
            dlsort(&less);
        list_splice(&less, bs->prev, bs);
    }

    if (!list_empty(&more)) {
        if (more.next != more.prev)
            dlsort(&more);
        list_splice(&more, bs->prev, bs);
    }
}

static void bssort(struct list_head *bs)
{
    if (list_empty(bs))
        return;

    dlsort(bs);
}

int main(int argc, char *argv[])
{
    LIST_HEAD(bussit);
    int ret;

    ret = prepare(&bussit);
    if (ret)
        return ret;

    dump(&bussit);
    bssort(&bussit);
    dump(&bussit);

    bsfree(&bussit);
    return 0;
}