Linked List Insertion Sort Benchmark

/* A benchmark of three different implementations of selection sort on a linked list
 * 1: singly-linked (reverse loop)
 * 2: singly-linked (recursive)
 * 3: doubly-linked (normal loop)
 * A stack overflow can be simulated with valgrind: valgrind --main-stacksize=1000 ./a.out
 */

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

#define CMP_T(name, expr) \
    int name(int a, int b){return (expr);}

typedef int (*cmp_t)(int,int);

struct list {
    struct list *next;
    struct list *prev;
    // used to allow for both single-linked and double-linked implementations (for benchmarking purposes)
    // every use of prev is marked with a comment saying "use of list.prev"
    int data;
};

struct list *
list_new(int data)
{
    struct list *list = malloc(sizeof *list);

    list->data = data;
    list->next = NULL;
    list->prev = NULL; // use of list.prev
    return list;
}

struct list *
list_addl(struct list *list, struct list *node)
{
    node->next = list;
    list->prev = node; // use of list.prev
    return node;
}

struct list *
list_get_prev(struct list *list, struct list *node)
{
    if(list == node)
        return NULL;

    while(list->next != node)
        list = list->next;

    return list;
}

void
list_swap_next(struct list *node)
{
    struct list *next = node->next;

    if(next == NULL)
        return;

    node->data ^= next->data;
    next->data ^= node->data;
    node->data ^= next->data;
}

struct list *
list_random(int size)
{
    struct list *list = list_new(rand() % (size * 10));
    struct list *new;

    for(int i = 0; i < size - 1; ++i){
        new = list_new(rand() % (size * 10));
        list = list_addl(list, new);
    }

    return list;
}

struct list *
list_end(struct list *list)
{
    while(list->next != NULL)
        list = list->next;

    return list;
}

void
list_print(struct list *list)
{
    while(list != NULL){
        printf("%i -> ", list->data);
        list = list->next;
    }

    printf("(null)\n");
}

void
list_free(struct list *list)
{
    struct list *next;

    while(list != NULL){
        next = list->next;
        free(list);
        list = next;
    }
}

void
list_ins_sort_inner(struct list *sublist, cmp_t cmp)
{
    while(sublist->next != NULL && cmp(sublist->next->data, sublist->data) == -1){
        list_swap_next(sublist);
        sublist = sublist->next;
    }
}

// use of list.prev
void
list_ins_sort_double_inner(struct list *sublist, cmp_t cmp)
{
    while(sublist->prev != NULL && cmp(sublist->prev->data, sublist->data) == 1){
        list_swap_next(sublist->prev);
        sublist = sublist->prev;
    }
}

// implementation of ins_sort with singly-linked list
void
list_ins_sort(struct list *list, cmp_t cmp)
{
    for(struct list *selnode = list_end(list); selnode != NULL; selnode = list_get_prev(list, selnode))
        list_ins_sort_inner(selnode, cmp);
}

// implementation of ins_sort with singly-linked list. Recursive-optimized edition.
void
list_ins_sort_recursive(struct list *list, cmp_t cmp)
{
    if(list->next != NULL)
        list_ins_sort_recursive(list->next, cmp);

    list_ins_sort_inner(list, cmp);
}

// implementation of ins_sort with doubly-linked list.
void
list_ins_sort_double(struct list *list, cmp_t cmp)
{
    for(struct list *selnode = list; selnode != NULL; selnode = selnode->next)
        list_ins_sort_double_inner(selnode, cmp);
}

CMP_T(num_cmp, (a < b) ? (-1) : (a > b ? 1 : 0))

int
main(void)
{
    struct list *list;
    int list_size = 20000;

    srand(time(NULL));
    list = list_random(list_size);
    list_print(list);

    // Un-comment the function being benchmarked
    //list_ins_sort(list, num_cmp); // avg 1.8s
    //list_ins_sort_recursive(list, num_cmp); // avg 1.2s (note: stack overflow risk)
    //list_ins_sort_double(list, num_cmp); // avg 1.3s

    list_print(list);
    list_free(list);

    return 0;
}