lkml.org 
[lkml]   [2010]   [Jan]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    Subject[PATCH V3] sort: Introduce generic list_sort function
    On Tue, Jan 05, 2010 at 12:31:15PM +0100, Andi Kleen wrote:
    > 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?

    Bah, who uses modules? :P

    Fixed. Updated patch below.

    > Also it would seem cleaner to have it in a own file.

    That might make sense if we had a large number of generic sort
    functions and it was difficult to tell the code apart, but we've
    only got 2 right now....

    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>
    ---
    V3: Export list_sort()
    V2: fix a typo

    drivers/gpu/drm/drm_modes.c | 90 ++-------------------------------------
    fs/ubifs/gc.c | 95 -----------------------------------------
    include/linux/sort.h | 5 ++
    lib/sort.c | 98 +++++++++++++++++++++++++++++++++++++++++++
    4 files changed, 107 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..a9ce544 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,100 @@ 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;
    +}
    +
    +EXPORT_SYMBOL(list_sort);
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/
    \
     
     \ /
      Last update: 2010-01-05 13:23    [W:0.041 / U:32.544 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site