Remove flist_sort(), it's no longer used

Signed-off-by: Jens Axboe <jaxboe@fusionio.com>

diff --git a/flist_sort.h b/flist_sort.h
deleted file mode 100644 (file)
index 686b7a5..0000000
--- a/flist_sort.h
+++ /dev/null
@@ -1,9 +0,0 @@
-#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
deleted file mode 100644 (file)
index 9a2da84..0000000
--- a/lib/flist_sort.c
+++ /dev/null
@@ -1,140 +0,0 @@
-#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);
-                       max_lev = lev;
-               }
-               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);
-}