From 07ec53769e4f91c2dd8909b73700c2f48cb2b173 Mon Sep 17 00:00:00 2001 From: zrj Date: Mon, 17 Aug 2015 15:49:08 +0300 Subject: [PATCH] drm/linux: Add list_sort() implementation Taken-from: NetBSD --- sys/dev/drm/include/linux/list_sort.h | 43 ++++++ sys/dev/drm/linux_list_sort.c | 190 ++++++++++++++++++++++++++ 2 files changed, 233 insertions(+) create mode 100644 sys/dev/drm/include/linux/list_sort.h create mode 100644 sys/dev/drm/linux_list_sort.c diff --git a/sys/dev/drm/include/linux/list_sort.h b/sys/dev/drm/include/linux/list_sort.h new file mode 100644 index 0000000000..7e40129b08 --- /dev/null +++ b/sys/dev/drm/include/linux/list_sort.h @@ -0,0 +1,43 @@ +/* $NetBSD: list_sort.h,v 1.2 2014/03/18 18:20:43 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. + */ + +#ifndef _LINUX_LIST_SORT_H_ +#define _LINUX_LIST_SORT_H_ + +struct list_head; + +/* XXX Make the nm output a little more greppable... */ +#define list_sort linux_list_sort + +void list_sort(void *, struct list_head *, + int (*)(void *, struct list_head *, struct list_head *)); + +#endif /* _LINUX_LIST_SORT_H_ */ diff --git a/sys/dev/drm/linux_list_sort.c b/sys/dev/drm/linux_list_sort.c new file mode 100644 index 0000000000..781023b5a0 --- /dev/null +++ b/sys/dev/drm/linux_list_sort.c @@ -0,0 +1,190 @@ +/* $NetBSD: linux_list_sort.c,v 1.2 2014/03/18 18:20:43 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 +//__KERNEL_RCSID(0, "$NetBSD: linux_list_sort.c,v 1.2 2014/03/18 18:20:43 riastradh Exp $"); + +#include + +#include + +#include +#include +#include + +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: accum[i] + * is sorted, and either is NULL or has length 2^i. + */ + struct list_head *accum[64]; + + /* Indices into accum. */ + 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 < ARRAY_SIZE(accum); logn++) + accum[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; accum[logn] != NULL; logn++) { + /* + * Merge, preferring previously accumulated + * elements to make the sort stable. + */ + sorted = list_sort_merge(accum[logn], sorted, compare, arg); + accum[logn] = NULL; + KKASSERT((logn + 1) < ARRAY_SIZE(accum)); + } + + /* Remember the highest index seen so far. */ + if (logn > max_logn) + max_logn = logn; + + /* + * logn = log_2(length(sorted)), and accum[logn] + * is now empty, so save the sorted sublist there. + */ + accum[logn] = sorted; + } + + /* + * Merge ~half of everything we have accumulated. + */ + sorted = NULL; + for (logn = 0; logn < max_logn; logn++) + sorted = list_sort_merge(accum[logn], sorted, compare, arg); + + /* + * Merge the last ~halves back into the list, and fix the back + * pointers. + */ + list_sort_merge_into(list, accum[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; +} -- 2.41.0