Re: [Xen-devel] [PATCH v2 17/45] Add list_sort() routine from Linux

[Jan Beulich]

>>> On 15.03.18 at 21:30,  wrote:
> This pulls in Linux' list_sort.c, which is a merge sort implementation
> for linked lists. Apart from adding a full featured license header and
> adjusting the #include file, nothing has been changed in this code.

Please mention the version of Linux this was taken from, to ease
later determination of applicability to our tree of changes they do.

Jan


___
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

[Xen-devel] [PATCH v2 17/45] Add list_sort() routine from Linux

[Andre Przywara]

This pulls in Linux' list_sort.c, which is a merge sort implementation
for linked lists. Apart from adding a full featured license header and
adjusting the #include file, nothing has been changed in this code.

Signed-off-by: Andre Przywara 
---
Changelog v1 ... v2:
- split out to just contain Linux code dump

 xen/common/list_sort.c  | 157 
 xen/include/xen/list_sort.h |  11 
 2 files changed, 168 insertions(+)
 create mode 100644 xen/common/list_sort.c
 create mode 100644 xen/include/xen/list_sort.h

diff --git a/xen/common/list_sort.c b/xen/common/list_sort.c
new file mode 100644
index 00..af2b2f6519
--- /dev/null
+++ b/xen/common/list_sort.c
@@ -0,0 +1,157 @@
+/*
+ * list_sort.c: merge sort implementation for linked lists
+ * Copied from the Linux kernel (lib/list_sort.c)
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU General Public License,
+ * version 2, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope 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, see .
+ */
+
+#include 
+#include 
+
+#define MAX_LIST_LENGTH_BITS 20
+
+/*
+ * Returns a list organized in an intermediate format suited
+ * to chaining of merge() calls: null-terminated, no reserved or
+ * sentinel head node, "prev" links not maintained.
+ */
+static struct list_head *merge(void *priv,
+   int (*cmp)(void *priv, struct list_head *a,
+   struct list_head *b),
+   struct list_head *a, struct list_head *b)
+{
+   struct list_head head, *tail = 
+
+   while (a && b) {
+   /* if equal, take 'a' -- important for sort stability */
+   if ((*cmp)(priv, a, b) <= 0) {
+   tail->next = a;
+   a = a->next;
+   } else {
+   tail->next = b;
+   b = b->next;
+   }
+   tail = tail->next;
+   }
+   tail->next = a?:b;
+   return head.next;
+}
+
+/*
+ * Combine final list merge with restoration of standard doubly-linked
+ * list structure.  This approach duplicates code from merge(), but
+ * runs faster than the tidier alternatives of either a separate final
+ * prev-link restoration pass, or maintaining the prev links
+ * throughout.
+ */
+static void merge_and_restore_back_links(void *priv,
+   int (*cmp)(void *priv, struct list_head *a,
+   struct list_head *b),
+   struct list_head *head,
+   struct list_head *a, struct list_head *b)
+{
+   struct list_head *tail = head;
+   u8 count = 0;
+
+   while (a && b) {
+   /* if equal, take 'a' -- important for sort stability */
+   if ((*cmp)(priv, a, b) <= 0) {
+   tail->next = a;
+   a->prev = tail;
+   a = a->next;
+   } else {
+   tail->next = b;
+   b->prev = tail;
+   b = b->next;
+   }
+   tail = tail->next;
+   }
+   tail->next = a ? : b;
+
+   do {
+   /*
+* In worst cases this loop may run many iterations.
+* Continue callbacks to the client even though no
+* element comparison is needed, so the client's cmp()
+* routine can invoke cond_resched() periodically.
+*/
+   if (unlikely(!(++count)))
+   (*cmp)(priv, tail->next, tail->next);
+
+   tail->next->prev = tail;
+   tail = tail->next;
+   } while (tail->next);
+
+   tail->next = head;
+   head->prev = tail;
+}
+
+/**
+ * list_sort - sort a list
+ * @priv: private data, opaque to list_sort(), passed to @cmp
+ * @head: the list to sort
+ * @cmp: the elements comparison function
+ *
+ * This function implements "merge sort", which has O(nlog(n))
+ * complexity.
+ *
+ * The comparison function @cmp must return a negative value if @a
+ * should sort before @b, and a positive value if @a should sort after
+ * @b. If @a and @b are equivalent, and their original relative
+ * ordering is to be preserved, @cmp must return 0.
+ */
+void list_sort(void *priv, struct list_head *head,
+   int (*cmp)(void *priv, struct list_head *a,
+   struct list_head *b))
+{
+   struct list_head