* [PATCH] sort: Introduce generic list_sort function
@ 2010-01-04 23:54 Dave Chinner
2010-01-05 0:48 ` Dave Airlie
` (2 more replies)
0 siblings, 3 replies; 6+ messages in thread
From: Dave Chinner @ 2010-01-04 23:54 UTC (permalink / raw)
To: xfs; +Cc: linux-kernel, Dave Airlie, Artem Bityutskiy, Adrian Hunter
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 9209 bytes --]
There are two copies of list_sort() in the tree already, one in the DRM code,
another in ubifs. Now XFS needs this as well. Create a generic list_sort()
function from the ubifs version and convert existing users to it so we
don't end up with yet another copy in the tree.
CC: Dave Airlie <airlied@redhat.com>
CC: Artem Bityutskiy <dedekind@infradead.org>
CC: Adrian Hunter <adrian.hunter@nokia.com>
Signed-off-by: Dave Chinner <david@fromorbit.com>
---
drivers/gpu/drm/drm_modes.c | 90 ++--------------------------------------
fs/ubifs/gc.c | 95 ------------------------------------------
include/linux/sort.h | 5 ++
lib/sort.c | 97 +++++++++++++++++++++++++++++++++++++++++++
4 files changed, 106 insertions(+), 181 deletions(-)
diff --git a/drivers/gpu/drm/drm_modes.c b/drivers/gpu/drm/drm_modes.c
index 51f6772..3846ed4 100644
--- a/drivers/gpu/drm/drm_modes.c
+++ b/drivers/gpu/drm/drm_modes.c
@@ -1,9 +1,4 @@
/*
- * The list_sort function is (presumably) licensed under the GPL (see the
- * top level "COPYING" file for details).
- *
- * The remainder of this file is:
- *
* Copyright © 1997-2003 by The XFree86 Project, Inc.
* Copyright © 2007 Dave Airlie
* Copyright © 2007-2008 Intel Corporation
@@ -36,6 +31,7 @@
*/
#include <linux/list.h>
+#include <linux/sort.h>
#include "drmP.h"
#include "drm.h"
#include "drm_crtc.h"
@@ -829,6 +825,7 @@ EXPORT_SYMBOL(drm_mode_prune_invalid);
/**
* drm_mode_compare - compare modes for favorability
+ * @priv: unused
* @lh_a: list_head for first mode
* @lh_b: list_head for second mode
*
@@ -842,7 +839,7 @@ EXPORT_SYMBOL(drm_mode_prune_invalid);
* Negative if @lh_a is better than @lh_b, zero if they're equivalent, or
* positive if @lh_b is better than @lh_a.
*/
-static int drm_mode_compare(struct list_head *lh_a, struct list_head *lh_b)
+static int drm_mode_compare(void *priv, struct list_head *lh_a, struct list_head *lh_b)
{
struct drm_display_mode *a = list_entry(lh_a, struct drm_display_mode, head);
struct drm_display_mode *b = list_entry(lh_b, struct drm_display_mode, head);
@@ -859,85 +856,6 @@ static int drm_mode_compare(struct list_head *lh_a, struct list_head *lh_b)
return diff;
}
-/* FIXME: what we don't have a list sort function? */
-/* list sort from Mark J Roberts (mjr@znex.org) */
-void list_sort(struct list_head *head,
- int (*cmp)(struct list_head *a, struct list_head *b))
-{
- struct list_head *p, *q, *e, *list, *tail, *oldhead;
- int insize, nmerges, psize, qsize, i;
-
- 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(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;
-}
-
/**
* drm_mode_sort - sort mode list
* @mode_list: list to sort
@@ -949,7 +867,7 @@ void list_sort(struct list_head *head,
*/
void drm_mode_sort(struct list_head *mode_list)
{
- list_sort(mode_list, drm_mode_compare);
+ list_sort(NULL, mode_list, drm_mode_compare);
}
EXPORT_SYMBOL(drm_mode_sort);
diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index 618c270..4976e07 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -108,101 +108,6 @@ static int switch_gc_head(struct ubifs_info *c)
}
/**
- * 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
* @a: first data node
diff --git a/include/linux/sort.h b/include/linux/sort.h
index d534da2..99a2ed5 100644
--- a/include/linux/sort.h
+++ b/include/linux/sort.h
@@ -3,8 +3,13 @@
#include <linux/types.h>
+struct list_head;
+
void sort(void *base, size_t num, size_t size,
int (*cmp)(const void *, const void *),
void (*swap)(void *, void *, int));
+void list_sort(void *priv, struct list_head *head,
+ int (*cmp)(void *priv, struct list_head *a,
+ struct list_head *b));
#endif
diff --git a/lib/sort.c b/lib/sort.c
index 926d004..1772c45 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -8,6 +8,7 @@
#include <linux/module.h>
#include <linux/sort.h>
#include <linux/slab.h>
+#include <linux/list.h>
static void u32_swap(void *a, void *b, int size)
{
@@ -121,3 +122,99 @@ static int sort_test(void)
module_init(sort_test);
#endif
+
+/**
+ * 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.
+ */
+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;
+}
+
--
1.6.5
^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH] sort: Introduce generic list_sort function
2010-01-04 23:54 [PATCH] sort: Introduce generic list_sort function Dave Chinner
@ 2010-01-05 0:48 ` Dave Airlie
2010-01-05 6:23 ` Artem Bityutskiy
2010-01-05 6:26 ` Artem Bityutskiy
2 siblings, 0 replies; 6+ messages in thread
From: Dave Airlie @ 2010-01-05 0:48 UTC (permalink / raw)
To: Dave Chinner; +Cc: xfs, linux-kernel, Artem Bityutskiy, Adrian Hunter
On Tue, 2010-01-05 at 10:54 +1100, Dave Chinner wrote:
> There are two copies of list_sort() in the tree already, one in the DRM code,
> another in ubifs. Now XFS needs this as well. Create a generic list_sort()
> function from the ubifs version and convert existing users to it so we
> don't end up with yet another copy in the tree.
Acked-by: Dave Airlie <airlied@redhat.com>
Meant to do this myself when we imported modesetting, but never got
around to it,
Thanks,
Dave.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] sort: Introduce generic list_sort function
2010-01-04 23:54 [PATCH] sort: Introduce generic list_sort function Dave Chinner
2010-01-05 0:48 ` Dave Airlie
@ 2010-01-05 6:23 ` Artem Bityutskiy
2010-01-05 6:26 ` Artem Bityutskiy
2 siblings, 0 replies; 6+ messages in thread
From: Artem Bityutskiy @ 2010-01-05 6:23 UTC (permalink / raw)
To: Dave Chinner; +Cc: xfs, linux-kernel, Dave Airlie, Adrian Hunter
On Tue, 2010-01-05 at 10:54 +1100, Dave Chinner wrote:
> There are two copies of list_sort() in the tree already, one in the DRM code,
> another in ubifs. Now XFS needs this as well. Create a generic list_sort()
> function from the ubifs version and convert existing users to it so we
> don't end up with yet another copy in the tree.
>
> CC: Dave Airlie <airlied@redhat.com>
> CC: Artem Bityutskiy <dedekind@infradead.org>
> CC: Adrian Hunter <adrian.hunter@nokia.com>
>
> Signed-off-by: Dave Chinner <david@fromorbit.com>
Acked-by: Artem Bityutskiy <dedekind@infradead.org>
Thanks, this has been in my TODO list for long time as well :-)
--
Best Regards,
Artem Bityutskiy (Артём Битюцкий)
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] sort: Introduce generic list_sort function
2010-01-04 23:54 [PATCH] sort: Introduce generic list_sort function Dave Chinner
2010-01-05 0:48 ` Dave Airlie
2010-01-05 6:23 ` Artem Bityutskiy
@ 2010-01-05 6:26 ` Artem Bityutskiy
2010-01-05 9:34 ` Dave Chinner
2 siblings, 1 reply; 6+ messages in thread
From: Artem Bityutskiy @ 2010-01-05 6:26 UTC (permalink / raw)
To: Dave Chinner; +Cc: xfs, linux-kernel, Dave Airlie, Adrian Hunter
On Tue, 2010-01-05 at 10:54 +1100, Dave Chinner wrote:
> There are two copies of list_sort() in the tree already, one in the DRM code,
> another in ubifs. Now XFS needs this as well. Create a generic list_sort()
> function from the ubifs version and convert existing users to it so we
> don't end up with yet another copy in the tree.
>
> CC: Dave Airlie <airlied@redhat.com>
> CC: Artem Bityutskiy <dedekind@infradead.org>
> CC: Adrian Hunter <adrian.hunter@nokia.com>
>
> Signed-off-by: Dave Chinner <david@fromorbit.com>
> ---
> drivers/gpu/drm/drm_modes.c | 90 ++--------------------------------------
> fs/ubifs/gc.c | 95 ------------------------------------------
> include/linux/sort.h | 5 ++
> lib/sort.c | 97 +++++++++++++++++++++++++++++++++++++++++++
> 4 files changed, 106 insertions(+), 181 deletions(-)
>
> diff --git a/drivers/gpu/drm/drm_modes.c b/drivers/gpu/drm/drm_modes.c
> index 51f6772..3846ed4 100644
> --- a/drivers/gpu/drm/drm_modes.c
> +++ b/drivers/gpu/drm/drm_modes.c
> @@ -1,9 +1,4 @@
> /*
> - * The list_sort function is (presumably) licensed under the GPL (see the
> - * top level "COPYING" file for details).
> - *
> - * The remainder of this file is:
> - *
> * Copyright © 1997-2003 by The XFree86 Project, Inc.
> * Copyright © 2007 Dave Airlie
> * Copyright © 2007-2008 Intel Corporation
> @@ -36,6 +31,7 @@
> */
>
> #include <linux/list.h>
> +#include <linux/sort.h>
> #include "drmP.h"
> #include "drm.h"
> #include "drm_crtc.h"
> @@ -829,6 +825,7 @@ EXPORT_SYMBOL(drm_mode_prune_invalid);
>
> /**
> * drm_mode_compare - compare modes for favorability
> + * @priv: unused
> * @lh_a: list_head for first mode
> * @lh_b: list_head for second mode
> *
> @@ -842,7 +839,7 @@ EXPORT_SYMBOL(drm_mode_prune_invalid);
> * Negative if @lh_a is better than @lh_b, zero if they're equivalent, or
> * positive if @lh_b is better than @lh_a.
> */
> -static int drm_mode_compare(struct list_head *lh_a, struct list_head *lh_b)
> +static int drm_mode_compare(void *priv, struct list_head *lh_a, struct list_head *lh_b)
> {
> struct drm_display_mode *a = list_entry(lh_a, struct drm_display_mode, head);
> struct drm_display_mode *b = list_entry(lh_b, struct drm_display_mode, head);
> @@ -859,85 +856,6 @@ static int drm_mode_compare(struct list_head *lh_a, struct list_head *lh_b)
> return diff;
> }
>
> -/* FIXME: what we don't have a list sort function? */
> -/* list sort from Mark J Roberts (mjr@znex.org) */
> -void list_sort(struct list_head *head,
> - int (*cmp)(struct list_head *a, struct list_head *b))
> -{
> - struct list_head *p, *q, *e, *list, *tail, *oldhead;
> - int insize, nmerges, psize, qsize, i;
> -
> - 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(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;
> -}
> -
> /**
> * drm_mode_sort - sort mode list
> * @mode_list: list to sort
> @@ -949,7 +867,7 @@ void list_sort(struct list_head *head,
> */
> void drm_mode_sort(struct list_head *mode_list)
> {
> - list_sort(mode_list, drm_mode_compare);
> + list_sort(NULL, mode_list, drm_mode_compare);
> }
> EXPORT_SYMBOL(drm_mode_sort);
>
> diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
> index 618c270..4976e07 100644
> --- a/fs/ubifs/gc.c
> +++ b/fs/ubifs/gc.c
> @@ -108,101 +108,6 @@ static int switch_gc_head(struct ubifs_info *c)
> }
>
> /**
> - * 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
> * @a: first data node
> diff --git a/include/linux/sort.h b/include/linux/sort.h
> index d534da2..99a2ed5 100644
> --- a/include/linux/sort.h
> +++ b/include/linux/sort.h
> @@ -3,8 +3,13 @@
>
> #include <linux/types.h>
>
> +struct list_head;
> +
> void sort(void *base, size_t num, size_t size,
> int (*cmp)(const void *, const void *),
> void (*swap)(void *, void *, int));
>
> +void list_sort(void *priv, struct list_head *head,
> + int (*cmp)(void *priv, struct list_head *a,
> + struct list_head *b));
> #endif
> diff --git a/lib/sort.c b/lib/sort.c
> index 926d004..1772c45 100644
> --- a/lib/sort.c
> +++ b/lib/sort.c
> @@ -8,6 +8,7 @@
> #include <linux/module.h>
> #include <linux/sort.h>
> #include <linux/slab.h>
> +#include <linux/list.h>
>
> static void u32_swap(void *a, void *b, int size)
> {
> @@ -121,3 +122,99 @@ static int sort_test(void)
>
> module_init(sort_test);
> #endif
> +
> +/**
> + * 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
While you are on it, could you also please fix the typo: "if @a is less
than @b".
> + * equivalent, then it does not matter what this function returns.
> + */
--
Best Regards,
Artem Bityutskiy (Артём Битюцкий)
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] sort: Introduce generic list_sort function
2010-01-05 6:26 ` Artem Bityutskiy
@ 2010-01-05 9:34 ` Dave Chinner
0 siblings, 0 replies; 6+ messages in thread
From: Dave Chinner @ 2010-01-05 9:34 UTC (permalink / raw)
To: Artem Bityutskiy; +Cc: xfs, linux-kernel, Dave Airlie, Adrian Hunter
On Tue, Jan 05, 2010 at 08:26:11AM +0200, Artem Bityutskiy wrote:
> > + * 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
>
> While you are on it, could you also please fix the typo: "if @a is less
> than @b".
Fixed. New patch below.
Cheers,
Dave.
--
Dave Chinner
david@fromorbit.com
sort: Introduce generic list_sort function
There are two copies of list_sort() in the tree already, one in the DRM code,
another in ubifs. Now XFS needs this as well. Create a generic list_sort()
function from the ubifs version and convert existing users to it so we
don't end up with yet another copy in the tree.
Signed-off-by: Dave Chinner <david@fromorbit.com>
Acked-by: Dave Airlie <airlied@redhat.com>
Acked-by: Artem Bityutskiy <dedekind@infradead.org>
---
drivers/gpu/drm/drm_modes.c | 90 ++--------------------------------------
fs/ubifs/gc.c | 95 ------------------------------------------
include/linux/sort.h | 5 ++
lib/sort.c | 97 +++++++++++++++++++++++++++++++++++++++++++
4 files changed, 106 insertions(+), 181 deletions(-)
diff --git a/drivers/gpu/drm/drm_modes.c b/drivers/gpu/drm/drm_modes.c
index 51f6772..3846ed4 100644
--- a/drivers/gpu/drm/drm_modes.c
+++ b/drivers/gpu/drm/drm_modes.c
@@ -1,9 +1,4 @@
/*
- * The list_sort function is (presumably) licensed under the GPL (see the
- * top level "COPYING" file for details).
- *
- * The remainder of this file is:
- *
* Copyright © 1997-2003 by The XFree86 Project, Inc.
* Copyright © 2007 Dave Airlie
* Copyright © 2007-2008 Intel Corporation
@@ -36,6 +31,7 @@
*/
#include <linux/list.h>
+#include <linux/sort.h>
#include "drmP.h"
#include "drm.h"
#include "drm_crtc.h"
@@ -829,6 +825,7 @@ EXPORT_SYMBOL(drm_mode_prune_invalid);
/**
* drm_mode_compare - compare modes for favorability
+ * @priv: unused
* @lh_a: list_head for first mode
* @lh_b: list_head for second mode
*
@@ -842,7 +839,7 @@ EXPORT_SYMBOL(drm_mode_prune_invalid);
* Negative if @lh_a is better than @lh_b, zero if they're equivalent, or
* positive if @lh_b is better than @lh_a.
*/
-static int drm_mode_compare(struct list_head *lh_a, struct list_head *lh_b)
+static int drm_mode_compare(void *priv, struct list_head *lh_a, struct list_head *lh_b)
{
struct drm_display_mode *a = list_entry(lh_a, struct drm_display_mode, head);
struct drm_display_mode *b = list_entry(lh_b, struct drm_display_mode, head);
@@ -859,85 +856,6 @@ static int drm_mode_compare(struct list_head *lh_a, struct list_head *lh_b)
return diff;
}
-/* FIXME: what we don't have a list sort function? */
-/* list sort from Mark J Roberts (mjr@znex.org) */
-void list_sort(struct list_head *head,
- int (*cmp)(struct list_head *a, struct list_head *b))
-{
- struct list_head *p, *q, *e, *list, *tail, *oldhead;
- int insize, nmerges, psize, qsize, i;
-
- 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(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;
-}
-
/**
* drm_mode_sort - sort mode list
* @mode_list: list to sort
@@ -949,7 +867,7 @@ void list_sort(struct list_head *head,
*/
void drm_mode_sort(struct list_head *mode_list)
{
- list_sort(mode_list, drm_mode_compare);
+ list_sort(NULL, mode_list, drm_mode_compare);
}
EXPORT_SYMBOL(drm_mode_sort);
diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index 618c270..4976e07 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -108,101 +108,6 @@ static int switch_gc_head(struct ubifs_info *c)
}
/**
- * 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
* @a: first data node
diff --git a/include/linux/sort.h b/include/linux/sort.h
index d534da2..99a2ed5 100644
--- a/include/linux/sort.h
+++ b/include/linux/sort.h
@@ -3,8 +3,13 @@
#include <linux/types.h>
+struct list_head;
+
void sort(void *base, size_t num, size_t size,
int (*cmp)(const void *, const void *),
void (*swap)(void *, void *, int));
+void list_sort(void *priv, struct list_head *head,
+ int (*cmp)(void *priv, struct list_head *a,
+ struct list_head *b));
#endif
diff --git a/lib/sort.c b/lib/sort.c
index 926d004..5bab8ff 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -8,6 +8,7 @@
#include <linux/module.h>
#include <linux/sort.h>
#include <linux/slab.h>
+#include <linux/list.h>
static void u32_swap(void *a, void *b, int size)
{
@@ -121,3 +122,99 @@ static int sort_test(void)
module_init(sort_test);
#endif
+
+/**
+ * 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;
+}
+
^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH] sort: Introduce generic list_sort function
[not found] <1262649295-28427-1-git-send-email-david__25057.2445955642$1262651404$gmane$org@fromorbit.com>
@ 2010-01-05 11:31 ` Andi Kleen
0 siblings, 0 replies; 6+ messages in thread
From: Andi Kleen @ 2010-01-05 11:31 UTC (permalink / raw)
To: Dave Chinner
Cc: xfs, Artem Bityutskiy, Dave Airlie, linux-kernel, Adrian Hunter
Dave Chinner <david@fromorbit.com> writes:
> +
> +/**
> + * 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.
> + */
> +void list_sort(void *priv, struct list_head *head,
> + int (*cmp)(void *priv, struct list_head *a,
> + struct list_head *b))
No EXPORT_SYMBOL?
Also it would seem cleaner to have it in a own file.
-Andi
--
ak@linux.intel.com -- Speaking for myself only.
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2010-01-05 11:31 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2010-01-04 23:54 [PATCH] sort: Introduce generic list_sort function Dave Chinner
2010-01-05 0:48 ` Dave Airlie
2010-01-05 6:23 ` Artem Bityutskiy
2010-01-05 6:26 ` Artem Bityutskiy
2010-01-05 9:34 ` Dave Chinner
[not found] <1262649295-28427-1-git-send-email-david__25057.2445955642$1262651404$gmane$org@fromorbit.com>
2010-01-05 11:31 ` Andi Kleen
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox