/*

 * Soft:        Keepalived is a failover program for the LVS project

 *              <www.linuxvirtualserver.org>. It monitor & manipulate

 *              a loadbalanced server pool using multi-layer checks.

 *		In addition it provides a VRRPv2 & VRRPv3 stack.

 *

 * Author:      Alexandre Cassen, <acassen@corp.free.fr>

 *

 *              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.

 *

 *              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; either version

 *              2 of the License, or (at your option) any later version.

 *

 * Copyright (C) 2018 Alexandre Cassen, <acassen@corp.free.fr>

 */

#include "list_head.h"

#include "warnings.h"

void list_sort(struct list_head *head,

	       int (*cmp)(struct list_head *a, struct list_head *b))

{

	struct list_head *p, *q, *e, *list, *tail, *oldhead;

	unsigned insize, nmerges, psize, qsize, i;

	list = head->next;

	list_head_del(head);

	insize = 1;

	while (1) {

		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--;

				} else if (cmp(p, q) <= 0) {

					e = p;

					p = p->next;

					psize--;

				} 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;

}