Add flist sorting

Imported from the kernel implementation.

Signed-off-by: Jens Axboe <jens.axboe@oracle.com>

diff --git a/Makefile b/Makefile
index 837f42119da8a1aafc4bac331b98385934322230..978f8b27149111e90f9feed978f87dae1ec96d2f 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -10,6 +10,7 @@ OBJS = gettime.o fio.o ioengines.o init.o stat.o log.o time.o filesetup.o \
        cgroup.o profile.o debug.o
 
 OBJS += lib/rand.o
+OBJS += lib/flist_sort.o
 
 OBJS += crc/crc7.o
 OBJS += crc/crc16.o

diff --git a/Makefile.FreeBSD b/Makefile.FreeBSD
index 3c59a994284c6c228ee96900f945b9233fb646ca..5882961a867949155641a3ebf642641fc9dbb061 100644 (file)
--- a/Makefile.FreeBSD
+++ b/Makefile.FreeBSD
@@ -9,6 +9,7 @@ OBJS = gettime.o fio.o ioengines.o init.o stat.o log.o time.o filesetup.o \
        rbtree.o smalloc.o filehash.o helpers.o profile.o debug.o
 
 OBJS += lib/rand.o
+OBJS += lib/flist_sort.o
 
 OBJS += crc/crc7.o
 OBJS += crc/crc16.o

diff --git a/Makefile.mac b/Makefile.mac
index fe84297fdea1c26a3b3352a173e72556ddd837e0..77e5f035082246c65c2c82ada3ff6840c70f58c0 100644 (file)
--- a/Makefile.mac
+++ b/Makefile.mac
@@ -9,6 +9,7 @@ OBJS = gettime.o fio.o ioengines.o init.o stat.o log.o time.o filesetup.o \
        rbtree.o smalloc.o filehash.o helpers.o profile.o debug.o
 
 OBJS += lib/rand.o
+OBJS += lib/flist_sort.o
 
 OBJS += crc/crc7.o
 OBJS += crc/crc16.o

diff --git a/Makefile.solaris b/Makefile.solaris
index 49a4ef92618c77f09796f38e989e5d97b0d4acb2..06020c261f396261d67db077fe36268f6ac87cfb 100644 (file)
--- a/Makefile.solaris
+++ b/Makefile.solaris
@@ -8,6 +8,7 @@ OBJS = gettime.o fio.o ioengines.o init.o stat.o log.o time.o filesetup.o \
        profile.o debug.o
 
 OBJS += lib/rand.o
+OBJS += lib/flist_sort.o
 
 OBJS += crc/crc7.o
 OBJS += crc/crc16.o

diff --git a/flist_sort.h b/flist_sort.h
new file mode 100644 (file)
index 0000000..686b7a5
--- /dev/null
+++ b/flist_sort.h
@@ -0,0 +1,9 @@
+#ifndef FIO_FLIST_SORT_H
+#define FIO_FLIST_SORT_H
+
+struct flist_head;
+
+void flist_sort(void *priv, struct flist_head *head,
+              int (*cmp)(void *priv, struct flist_head *a,
+                         struct flist_head *b));
+#endif

diff --git a/lib/flist_sort.c b/lib/flist_sort.c
new file mode 100644 (file)
index 0000000..6c7c4c0
--- /dev/null
+++ b/lib/flist_sort.c
@@ -0,0 +1,138 @@
+#include <string.h>
+#include <assert.h>
+
+#include "../flist.h"
+#include "../flist_sort.h"
+
+#ifndef ARRAY_SIZE
+#define        ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
+#endif
+
+#define MAX_LIST_LENGTH_BITS 65
+
+/*
+ * 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 flist_head *merge(void *priv,
+                               int (*cmp)(void *priv, struct flist_head *a,
+                                       struct flist_head *b),
+                               struct flist_head *a, struct flist_head *b)
+{
+       struct flist_head head, *tail = &head;
+
+       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 flist_head *a,
+                                       struct flist_head *b),
+                               struct flist_head *head,
+                               struct flist_head *a, struct flist_head *b)
+{
+       struct flist_head *tail = head;
+
+       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.
+                */
+               cmp(priv, tail, tail);
+
+               tail->next->prev = tail;
+               tail = tail->next;
+       } while (tail->next);
+
+       tail->next = head;
+       head->prev = tail;
+}
+
+/**
+ * flist_sort - sort a list
+ * @priv: private data, opaque to flist_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 flist_sort(void *priv, struct flist_head *head,
+               int (*cmp)(void *priv, struct flist_head *a,
+                       struct flist_head *b))
+{
+       struct flist_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
+                                               -- last slot is a sentinel */
+       int lev;  /* index into part[] */
+       int max_lev = 0;
+       struct flist_head *list;
+
+       if (flist_empty(head))
+               return;
+
+       memset(part, 0, sizeof(part));
+
+       head->prev->next = NULL;
+       list = head->next;
+
+       while (list) {
+               struct flist_head *cur = list;
+               list = list->next;
+               cur->next = NULL;
+
+               for (lev = 0; part[lev]; lev++) {
+                       cur = merge(priv, cmp, part[lev], cur);
+                       part[lev] = NULL;
+               }
+               if (lev > max_lev)
+                       assert(lev < ARRAY_SIZE(part) - 1);
+               part[lev] = cur;
+       }
+
+       for (lev = 0; lev < max_lev; lev++)
+               if (part[lev])
+                       list = merge(priv, cmp, part[lev], list);
+
+       merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
+}