From 2c761270d5520dd84ab0b4e47c24d99ff8503c38 Mon Sep 17 00:00:00 2001 From: Dave Chinner Date: Tue, 12 Jan 2010 17:39:16 +1100 Subject: lib: 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 Acked-by: Dave Airlie Acked-by: Artem Bityutskiy Signed-off-by: Linus Torvalds --- drivers/gpu/drm/drm_modes.c | 90 ++------------------------------------------- 1 file changed, 4 insertions(+), 86 deletions(-) (limited to 'drivers') diff --git a/drivers/gpu/drm/drm_modes.c b/drivers/gpu/drm/drm_modes.c index 6d81a02463a3..76d63394c776 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 +#include #include "drmP.h" #include "drm.h" #include "drm_crtc.h" @@ -855,6 +851,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 * @@ -868,7 +865,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); @@ -885,85 +882,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 @@ -975,7 +893,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); -- cgit v1.2.3