Module Name: src
Committed By: riastradh
Date: Wed Jul 24 02:55:48 UTC 2013
Modified Files:
src/sys/external/bsd/drm2/include/linux [riastradh-drm2]: list_sort.h
src/sys/modules/drm2 [riastradh-drm2]: Makefile
Added Files:
src/sys/external/bsd/drm2/linux [riastradh-drm2]: linux_list_sort.c
Log Message:
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.
To generate a diff of this commit:
cvs rdiff -u -r1.1.2.1 -r1.1.2.2 \
src/sys/external/bsd/drm2/include/linux/list_sort.h
cvs rdiff -u -r0 -r1.1.2.1 src/sys/external/bsd/drm2/linux/linux_list_sort.c
cvs rdiff -u -r1.1.2.32 -r1.1.2.33 src/sys/modules/drm2/Makefile
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/sys/external/bsd/drm2/include/linux/list_sort.h
diff -u src/sys/external/bsd/drm2/include/linux/list_sort.h:1.1.2.1 src/sys/external/bsd/drm2/include/linux/list_sort.h:1.1.2.2
--- src/sys/external/bsd/drm2/include/linux/list_sort.h:1.1.2.1 Wed Jul 24 00:33:12 2013
+++ src/sys/external/bsd/drm2/include/linux/list_sort.h Wed Jul 24 02:55:48 2013
@@ -1,4 +1,4 @@
-/* $NetBSD: list_sort.h,v 1.1.2.1 2013/07/24 00:33:12 riastradh Exp $ */
+/* $NetBSD: list_sort.h,v 1.1.2.2 2013/07/24 02:55:48 riastradh Exp $ */
/*-
* Copyright (c) 2013 The NetBSD Foundation, Inc.
@@ -32,4 +32,9 @@
#ifndef _LINUX_LIST_SORT_H_
#define _LINUX_LIST_SORT_H_
+struct list_head;
+
+void list_sort(void *, struct list_head *,
+ int (*)(void *, struct list_head *, struct list_head *));
+
#endif /* _LINUX_LIST_SORT_H_ */
Index: src/sys/modules/drm2/Makefile
diff -u src/sys/modules/drm2/Makefile:1.1.2.32 src/sys/modules/drm2/Makefile:1.1.2.33
--- src/sys/modules/drm2/Makefile:1.1.2.32 Wed Jul 24 02:55:26 2013
+++ src/sys/modules/drm2/Makefile Wed Jul 24 02:55:48 2013
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.1.2.32 2013/07/24 02:55:26 riastradh Exp $
+# $NetBSD: Makefile,v 1.1.2.33 2013/07/24 02:55:48 riastradh Exp $
.include "../Makefile.inc"
.include "Makefile.inc"
@@ -49,5 +49,6 @@ SRCS+= drm_vm.c
SRCS+= drm_gem_vm.c
SRCS+= drm_module.c
SRCS+= linux_idr.c
+SRCS+= linux_list_sort.c
.include <bsd.kmodule.mk>
Added files:
Index: src/sys/external/bsd/drm2/linux/linux_list_sort.c
diff -u /dev/null src/sys/external/bsd/drm2/linux/linux_list_sort.c:1.1.2.1
--- /dev/null Wed Jul 24 02:55:48 2013
+++ src/sys/external/bsd/drm2/linux/linux_list_sort.c Wed Jul 24 02:55:48 2013
@@ -0,0 +1,189 @@
+/* $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;
+}
