Merge branch 'x86-rwsem-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git...

[mv-sheeva.git] / fs / ubifs / gc.c

diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index 618c2701d3a788ff821f35148d230090209b1eb6..e5a3d8e96bb706d1d03ab393cb9e84d5855f4e51 100644 (file)
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -54,6 +54,7 @@
  */
 
 #include <linux/pagemap.h>
+#include <linux/list_sort.h>
 #include "ubifs.h"
 
 /*
@@ -107,101 +108,6 @@ static int switch_gc_head(struct ubifs_info *c)
        return err;
 }
 
-/**
- * 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
- * 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.
- */
-static 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;
-}
-
 /**
  * data_nodes_cmp - compare 2 data nodes.
  * @priv: UBIFS file-system description object