#include <sys/queue.h>

#if !DUMP
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#endif

#include "queueutil.h"

struct int_item {
	int x;
	SLIST_ENTRY (int_item) next;
};
SLIST_HEAD (int_list, int_item);

#if 1
#define int_cmp(a, b) ((a)->x - (b)->x)
SLIST_SORT_GENERATE (int_list, int_item, next, int_cmp)
#else
void int_list_LISTSORT(struct int_list * _head) {
	struct int_item *_a, *_b, *_prev, *_start, *_tmp;
	int _i, _k, _n, _na, _nb;
	if (((_head)->slh_first == (void *) 0))
		return;
	_n = 0;
	for (_k = 1; _n != 1; _k *= 2) {
		_start = ((_head)->slh_first);
		do {
			(_head)->slh_first = (void *) 0;
		} while (0);
		_prev = (void *) 0;
		for (_n = 0; _start != (void *) 0; ++_n) {
			_tmp = _a = _start;
			_na = 0;
			for (_i = 0; _i < _k; ++_i) {
				if (_tmp == (void *) 0)
					break;
				_tmp = ((_tmp)->next.sle_next);
			} _b = _tmp;
			_na = _i;
			_tmp = _b;
			_nb = 0;
			for (_i = 0; _i < _k; ++_i) {
				if (_tmp == (void *) 0)
					break;
				_tmp = ((_tmp)->next.sle_next);
			} _start = _tmp;
			_nb = _i;
			while (_na != 0 || _nb != 0) {
				if (_na != 0 && (_nb == 0 || ((_a)->x - (_b)->x) < 0)) {
					_tmp = ((_a)->next.sle_next);
					do {
						if ((_prev) == (void *) 0)
							do {
								((_a))->next.sle_next = ((_head))->slh_first;
								((_head))->slh_first = ((_a));
							} while (0);
						else
							do {
								((_a))->next.sle_next = ((_prev))->next.sle_next;
								((_prev))->next.sle_next = ((_a));
							} while (0);
					} while (0);
					_prev = _a;
					_a = _tmp;
					--_na;
				} else {
					_tmp = ((_b)->next.sle_next);
					do {
						if ((_prev) == (void *) 0)
							do {
								((_b))->next.sle_next = ((_head))->slh_first;
								((_head))->slh_first = ((_b));
							} while (0);
						else
							do {
								((_b))->next.sle_next = ((_prev))->next.sle_next;
								((_prev))->next.sle_next = ((_b));
							} while (0);
					} while (0);
					_prev = _b;
					_b = _tmp;
					--_nb;
				}
			}
		}
		SLIST_FOREACH (_tmp, _head, next)
			printf("%d ", _tmp->x);
		printf("\n");
	}
}
#endif

static void *
xmalloc(size_t n)
{
	void *p;

	p = malloc(n);
	if (p == NULL)
		err(1, "malloc");
	return p;
}

int
main(void)
{
	struct int_list list;
	struct int_item *it;
	int i;

	srand(time(NULL));

	SLIST_INIT(&list);
	for (i = 0; i < 10; ++i) {
		it = xmalloc(sizeof *it);
		it->x = rand() % 10;
		SLIST_INSERT_HEAD(&list, it, next);
	}

	SLIST_FOREACH (it, &list, next)
		printf("%d ", it->x);
	printf("\n");

	SLIST_SORT(int_list, &list);

	SLIST_FOREACH (it, &list, next)
		printf("%d ", it->x);
	printf("\n");

	return 0;
}