Add linux_list_sort.c implementing list_sort.

Algorithm is merge sort using binary counting in a temporary array of
64 elements on the stack, big enough for any list that'll fit into
memory in a 64-bit address space, but small enough to fit comfortably
on the stack.


(riastradh)

/*	$NetBSD: linux_list_sort.c,v 1.1.2.1 2013/07/24 02:55:48 riastradh Exp $	*/

/*-
 * Copyright (c) 2013 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by Taylor R. Campbell.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD: linux_list_sort.c,v 1.1.2.1 2013/07/24 02:55:48 riastradh Exp $");

#include <sys/systm.h>

#include <machine/limits.h>

#include <linux/list.h>
#include <linux/list_sort.h>

static struct list_head *
		list_sort_merge(struct list_head *, struct list_head *,
		    int (*)(void *, struct list_head *, struct list_head *),
		    void *);
static void	list_sort_merge_into(struct list_head *,
		    struct list_head *, struct list_head *,
		    int (*)(void *, struct list_head *, struct list_head *),
		    void *);

void
list_sort(void *arg, struct list_head *list,
    int (*compare)(void *, struct list_head *, struct list_head *))
{
	/*
	 * Array of sorted sublists, counting in binary: accumulator[i]
	 * is sorted, and either is NULL or has length 2^i.
	 */
	struct list_head *accumulator[64];

	/* Indices into accumulator.  */
	unsigned int logn, max_logn = 0;

	/* The sorted list we're currently working on.  */
	struct list_head *sorted;

	/* The remainder of the unsorted list.  */
	struct list_head *next;

	/* Make sure we can't possibly have more than 2^64-element lists.  */
	__CTASSERT((CHAR_BIT * sizeof(struct list_head *)) <= 64);

	for (logn = 0; logn < __arraycount(accumulator); logn++)
		accumulator[logn] = NULL;

	list_for_each_safe(sorted, next, list) {
		/* Pick off a single element, always sorted.  */
		sorted->next = NULL;

		/* Add one and propagate the carry.  */
		for (logn = 0; accumulator[logn] != NULL; logn++) {
			/*
			 * Merge, preferring previously accumulated
			 * elements to make the sort stable.
			 */
			sorted = list_sort_merge(accumulator[logn], sorted,
			    compare, arg);
			accumulator[logn] = NULL;
			KASSERT((logn + 1) < __arraycount(accumulator));
		}

		/* Remember the highest index seen so far.  */
		if (logn > max_logn)
			max_logn = logn;

		/*
		 * logn = log_2(length(sorted)), and accumulator[logn]
		 * is now empty, so save the sorted sublist there.
		 */
		accumulator[logn] = sorted;
	}

	/*
	 * Merge ~half of everything we have accumulated.
	 */
	sorted = NULL;
	for (logn = 0; logn < max_logn; logn++)
		sorted = list_sort_merge(accumulator[logn], sorted, compare,
		    arg);

	/*
	 * Merge the last ~halves back into the list, and fix the back
	 * pointers.
	 */
	list_sort_merge_into(list, accumulator[max_logn], sorted, compare,
	    arg);
}

/*
 * Merge the NULL-terminated lists starting at nodes `a' and `b',
 * breaking ties by choosing nodes in `a' first, and returning
 * whichever node has the least element.
 */
static struct list_head *
list_sort_merge(struct list_head *a, struct list_head *b,
    int (*compare)(void *, struct list_head *, struct list_head *), void *arg)
{
	struct list_head head, *tail = &head;

	/*
	 * Merge while elements in both remain.
	 */
	while ((a != NULL) && (b != NULL)) {
		struct list_head **const first = ((*compare)(arg, a, b) <= 0?
		    &a : &b);

		tail = tail->next = *first;
		*first = (*first)->next;
	}

	/*
	 * Attach whatever remains.
	 */
	tail->next = (a != NULL? a : b);
	return head.next;
}

/*
 * Merge the NULL-terminated lists starting at nodes `a' and `b' into
 * the (uninitialized) list head `list', breaking ties by choosing
 * nodes in `a' first, and setting the `prev' pointers as we go.
 */
static void
list_sort_merge_into(struct list_head *list,
    struct list_head *a, struct list_head *b,
    int (*compare)(void *, struct list_head *, struct list_head *), void *arg)
{
	struct list_head *prev = list;

	/*
	 * Merge while elements in both remain.
	 */
	while ((a != NULL) && (b != NULL)) {
		struct list_head **const first = ((*compare)(arg, a, b) <= 0?
		    &a : &b);

		(*first)->prev = prev;
		prev = prev->next = *first;
		*first = (*first)->next;
	}

	/*
	 * Attach whichever of a and b remains, and fix up the prev
	 * pointers all the way down the rest of the list.
	 */
	struct list_head *tail = (a == NULL? b : a);
	while (tail != NULL) {
		prev->next = tail;
		tail->prev = prev;
		prev = prev->next;
		tail = tail->next;
	}

	/*
	 * Finally, finish the cycle.
	 */
	prev->next = list;
	list->prev = prev;
}