lib: Introduce generic list_sort function

[firefly-linux-kernel-4.4.55.git] / lib / list_sort.c

diff --git a/lib/list_sort.c b/lib/list_sort.c
new file mode 100644 (file)
index 0000000..19d11e0
--- /dev/null
+++ b/lib/list_sort.c
@@ -0,0 +1,102 @@
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/list_sort.h>
+#include <linux/slab.h>
+#include <linux/list.h>
+
+/**
+ * list_sort - sort a list.
+ * @priv: private data, passed to @cmp
+ * @head: the list to sort
+ * @cmp: the elements comparison function
+ *
+ * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
+ * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
+ * in ascending order.
+ *
+ * The comparison function @cmp is supposed to return a negative value if @a is
+ * less than @b, and a positive value if @a is greater than @b. If @a and @b
+ * are equivalent, then it does not matter what this function returns.
+ */
+void list_sort(void *priv, struct list_head *head,
+              int (*cmp)(void *priv, struct list_head *a,
+                         struct list_head *b))
+{
+       struct list_head *p, *q, *e, *list, *tail, *oldhead;
+       int insize, nmerges, psize, qsize, i;
+
+       if (list_empty(head))
+               return;
+
+       list = head->next;
+       list_del(head);
+       insize = 1;
+       for (;;) {
+               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--;
+                                       if (p == oldhead)
+                                               p = NULL;
+                               } else if (cmp(priv, p, q) <= 0) {
+                                       e = p;
+                                       p = p->next;
+                                       psize--;
+                                       if (p == oldhead)
+                                               p = NULL;
+                               } 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;
+}
+
+EXPORT_SYMBOL(list_sort);