/* -*- Mode: C ; c-basic-offset: 2 -*- */
/*****************************************************************************
*
*   list_sort() adapted from linux kernel.
*
*   This program is free software; you can redistribute it and/or modify
*   it under the terms of the GNU General Public License as published by
*   the Free Software Foundation; version 2 of the License
*
*   This program is distributed in the hope that it will be useful,
*   but WITHOUT ANY WARRANTY; without even the implied warranty of
*   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*   GNU General Public License for more details.
*
*   You should have received a copy of the GNU General Public License
*   along with this program; if not, write to the Free Software
*   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
*****************************************************************************/

#include <assert.h>

#include "list.h"

/* list sort from Mark J Roberts (mjr@znex.org) */
void
__list_sort (
	struct list_head *head,
	int member_offset,
	int (*cmp)(void * a, void * b))
{
	struct list_head *p, *q, *e, *list, *tail, *oldhead;
	int insize, nmerges, psize, qsize, i;

	list = head->next;
	list_del (head);
	insize = 1;
	for (;; ) {
		p = oldhead = list;
		list = tail = NULL;
		nmerges = 0;

		while (p) {
			nmerges++;
			q = p;
			psize = 0;
			for (i = 0; i < insize; i++) {
				psize++;
				q = q->next == oldhead ? NULL : q->next;
				if (!q) {
					break;
				}
			}

			qsize = insize;
			while (psize > 0 || (qsize > 0 && q)) {
				if (!psize) {
					e = q;
					q = q->next;
					qsize--;
					if (q == oldhead) {
						q = NULL;
					}
				} else if (!qsize || !q) {
					e = p;
					p = p->next;
					psize--;
					if (p == oldhead) {
						p = NULL;
					}
				} else if (cmp ((void*)p - member_offset, (void*)q - member_offset) <= 0) {
					e = p;
					p = p->next;
					psize--;
					if (p == oldhead) {
						p = NULL;
					}
				} else {
					e = q;
					q = q->next;
					qsize--;
					if (q == oldhead) {
						q = NULL;
					}
				}
				if (tail) {
					tail->next = e;
				} else {
					list = e;
				}
				e->prev = tail;
				tail = e;
			}
			p = q;
		}

		tail->next = list;
		list->prev = tail;

		if (nmerges <= 1) {
			break;
		}

		insize *= 2;
	}

	head->next = list;
	head->prev = list->prev;
	list->prev->next = head;
	list->prev = head;
}

struct test_list_el {
	int value;
	struct list_head test_list_node;
};

int test_list_sort_comparator (struct test_list_el * e1, struct test_list_el * e2)
{
	return e1->value - e2->value;
}

void test_list_sort (void)
{
	struct list_head test_list;
	struct test_list_el *el, *next;
	struct test_list_el te1 = { .value = 1 };
	struct test_list_el te2 = { .value = 2 };
	struct test_list_el te3 = { .value = 3 };
	struct test_list_el te4 = { .value = 4 };
	struct test_list_el te5 = { .value = 5 };
	struct test_list_el te6 = { .value = 6 };
	struct test_list_el te7 = { .value = 7 };

	const int expected[] = { 1, 2, 3, 4, 5, 6, 7 };
	int i;

	INIT_LIST_HEAD (&test_list);
	list_add_tail (&te2.test_list_node, &test_list);
	list_add_tail (&te6.test_list_node, &test_list);
	list_add_tail (&te4.test_list_node, &test_list);
	list_add_tail (&te5.test_list_node, &test_list);
	list_add_tail (&te7.test_list_node, &test_list);
	list_add_tail (&te1.test_list_node, &test_list);
	list_add_tail (&te3.test_list_node, &test_list);

	list_sort (&test_list, struct test_list_el, test_list_node, test_list_sort_comparator);

	i = 0;
	list_for_each_entry_safe (el, next, &test_list, test_list_node) {
		assert (el->value == expected[i]);
		i++;
	}
}