aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDave Chinner <david@fromorbit.com>2010-01-12 01:39:16 -0500
committerLinus Torvalds <torvalds@linux-foundation.org>2010-01-13 00:02:00 -0500
commit2c761270d5520dd84ab0b4e47c24d99ff8503c38 (patch)
treec23a51fdcc96641661b632d3b3c2c46ad7e53a91
parentdbf004d7883b3adb058c0c1a5635bc4ec27651c0 (diff)
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 <david@fromorbit.com> Acked-by: Dave Airlie <airlied@redhat.com> Acked-by: Artem Bityutskiy <dedekind@infradead.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat
-rw-r--r--drivers/gpu/drm/drm_modes.c90
-rw-r--r--fs/ubifs/gc.c96
-rw-r--r--include/linux/list_sort.h11
-rw-r--r--lib/Makefile2
-rw-r--r--lib/list_sort.c102
5 files changed, 119 insertions, 182 deletions
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 @@
1/* 1/*
2 * The list_sort function is (presumably) licensed under the GPL (see the
3 * top level "COPYING" file for details).
4 *
5 * The remainder of this file is:
6 *
7 * Copyright © 1997-2003 by The XFree86 Project, Inc. 2 * Copyright © 1997-2003 by The XFree86 Project, Inc.
8 * Copyright © 2007 Dave Airlie 3 * Copyright © 2007 Dave Airlie
9 * Copyright © 2007-2008 Intel Corporation 4 * Copyright © 2007-2008 Intel Corporation
@@ -36,6 +31,7 @@
36 */ 31 */
37 32
38#include <linux/list.h> 33#include <linux/list.h>
34#include <linux/list_sort.h>
39#include "drmP.h" 35#include "drmP.h"
40#include "drm.h" 36#include "drm.h"
41#include "drm_crtc.h" 37#include "drm_crtc.h"
@@ -855,6 +851,7 @@ EXPORT_SYMBOL(drm_mode_prune_invalid);
855 851
856/** 852/**
857 * drm_mode_compare - compare modes for favorability 853 * drm_mode_compare - compare modes for favorability
854 * @priv: unused
858 * @lh_a: list_head for first mode 855 * @lh_a: list_head for first mode
859 * @lh_b: list_head for second mode 856 * @lh_b: list_head for second mode
860 * 857 *
@@ -868,7 +865,7 @@ EXPORT_SYMBOL(drm_mode_prune_invalid);
868 * Negative if @lh_a is better than @lh_b, zero if they're equivalent, or 865 * Negative if @lh_a is better than @lh_b, zero if they're equivalent, or
869 * positive if @lh_b is better than @lh_a. 866 * positive if @lh_b is better than @lh_a.
870 */ 867 */
871static int drm_mode_compare(struct list_head *lh_a, struct list_head *lh_b) 868static int drm_mode_compare(void *priv, struct list_head *lh_a, struct list_head *lh_b)
872{ 869{
873 struct drm_display_mode *a = list_entry(lh_a, struct drm_display_mode, head); 870 struct drm_display_mode *a = list_entry(lh_a, struct drm_display_mode, head);
874 struct drm_display_mode *b = list_entry(lh_b, struct drm_display_mode, head); 871 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)
885 return diff; 882 return diff;
886} 883}
887 884
888/* FIXME: what we don't have a list sort function? */
889/* list sort from Mark J Roberts (mjr@znex.org) */
890void list_sort(struct list_head *head,
891 int (*cmp)(struct list_head *a, struct list_head *b))
892{
893 struct list_head *p, *q, *e, *list, *tail, *oldhead;
894 int insize, nmerges, psize, qsize, i;
895
896 list = head->next;
897 list_del(head);
898 insize = 1;
899 for (;;) {
900 p = oldhead = list;
901 list = tail = NULL;
902 nmerges = 0;
903
904 while (p) {
905 nmerges++;
906 q = p;
907 psize = 0;
908 for (i = 0; i < insize; i++) {
909 psize++;
910 q = q->next == oldhead ? NULL : q->next;
911 if (!q)
912 break;
913 }
914
915 qsize = insize;
916 while (psize > 0 || (qsize > 0 && q)) {
917 if (!psize) {
918 e = q;
919 q = q->next;
920 qsize--;
921 if (q == oldhead)
922 q = NULL;
923 } else if (!qsize || !q) {
924 e = p;
925 p = p->next;
926 psize--;
927 if (p == oldhead)
928 p = NULL;
929 } else if (cmp(p, q) <= 0) {
930 e = p;
931 p = p->next;
932 psize--;
933 if (p == oldhead)
934 p = NULL;
935 } else {
936 e = q;
937 q = q->next;
938 qsize--;
939 if (q == oldhead)
940 q = NULL;
941 }
942 if (tail)
943 tail->next = e;
944 else
945 list = e;
946 e->prev = tail;
947 tail = e;
948 }
949 p = q;
950 }
951
952 tail->next = list;
953 list->prev = tail;
954
955 if (nmerges <= 1)
956 break;
957
958 insize *= 2;
959 }
960
961 head->next = list;
962 head->prev = list->prev;
963 list->prev->next = head;
964 list->prev = head;
965}
966
967/** 885/**
968 * drm_mode_sort - sort mode list 886 * drm_mode_sort - sort mode list
969 * @mode_list: list to sort 887 * @mode_list: list to sort
@@ -975,7 +893,7 @@ void list_sort(struct list_head *head,
975 */ 893 */
976void drm_mode_sort(struct list_head *mode_list) 894void drm_mode_sort(struct list_head *mode_list)
977{ 895{
978 list_sort(mode_list, drm_mode_compare); 896 list_sort(NULL, mode_list, drm_mode_compare);
979} 897}
980EXPORT_SYMBOL(drm_mode_sort); 898EXPORT_SYMBOL(drm_mode_sort);
981 899
diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index 618c2701d3a7..e5a3d8e96bb7 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -54,6 +54,7 @@
54 */ 54 */
55 55
56#include <linux/pagemap.h> 56#include <linux/pagemap.h>
57#include <linux/list_sort.h>
57#include "ubifs.h" 58#include "ubifs.h"
58 59
59/* 60/*
@@ -108,101 +109,6 @@ static int switch_gc_head(struct ubifs_info *c)
108} 109}
109 110
110/** 111/**
111 * list_sort - sort a list.
112 * @priv: private data, passed to @cmp
113 * @head: the list to sort
114 * @cmp: the elements comparison function
115 *
116 * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
117 * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
118 * in ascending order.
119 *
120 * The comparison function @cmp is supposed to return a negative value if @a is
121 * than @b, and a positive value if @a is greater than @b. If @a and @b are
122 * equivalent, then it does not matter what this function returns.
123 */
124static void list_sort(void *priv, struct list_head *head,
125 int (*cmp)(void *priv, struct list_head *a,
126 struct list_head *b))
127{
128 struct list_head *p, *q, *e, *list, *tail, *oldhead;
129 int insize, nmerges, psize, qsize, i;
130
131 if (list_empty(head))
132 return;
133
134 list = head->next;
135 list_del(head);
136 insize = 1;
137 for (;;) {
138 p = oldhead = list;
139 list = tail = NULL;
140 nmerges = 0;
141
142 while (p) {
143 nmerges++;
144 q = p;
145 psize = 0;
146 for (i = 0; i < insize; i++) {
147 psize++;
148 q = q->next == oldhead ? NULL : q->next;
149 if (!q)
150 break;
151 }
152
153 qsize = insize;
154 while (psize > 0 || (qsize > 0 && q)) {
155 if (!psize) {
156 e = q;
157 q = q->next;
158 qsize--;
159 if (q == oldhead)
160 q = NULL;
161 } else if (!qsize || !q) {
162 e = p;
163 p = p->next;
164 psize--;
165 if (p == oldhead)
166 p = NULL;
167 } else if (cmp(priv, p, q) <= 0) {
168 e = p;
169 p = p->next;
170 psize--;
171 if (p == oldhead)
172 p = NULL;
173 } else {
174 e = q;
175 q = q->next;
176 qsize--;
177 if (q == oldhead)
178 q = NULL;
179 }
180 if (tail)
181 tail->next = e;
182 else
183 list = e;
184 e->prev = tail;
185 tail = e;
186 }
187 p = q;
188 }
189
190 tail->next = list;
191 list->prev = tail;
192
193 if (nmerges <= 1)
194 break;
195
196 insize *= 2;
197 }
198
199 head->next = list;
200 head->prev = list->prev;
201 list->prev->next = head;
202 list->prev = head;
203}
204
205/**
206 * data_nodes_cmp - compare 2 data nodes. 112 * data_nodes_cmp - compare 2 data nodes.
207 * @priv: UBIFS file-system description object 113 * @priv: UBIFS file-system description object
208 * @a: first data node 114 * @a: first data node
diff --git a/include/linux/list_sort.h b/include/linux/list_sort.h
new file mode 100644
index 000000000000..1a2df2efb771
--- /dev/null
+++ b/include/linux/list_sort.h
@@ -0,0 +1,11 @@
1#ifndef _LINUX_LIST_SORT_H
2#define _LINUX_LIST_SORT_H
3
4#include <linux/types.h>
5
6struct list_head;
7
8void list_sort(void *priv, struct list_head *head,
9 int (*cmp)(void *priv, struct list_head *a,
10 struct list_head *b));
11#endif
diff --git a/lib/Makefile b/lib/Makefile
index 911b25aed1e7..3b0b4a696db9 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -21,7 +21,7 @@ lib-y += kobject.o kref.o klist.o
21 21
22obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \ 22obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
23 bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \ 23 bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
24 string_helpers.o gcd.o 24 string_helpers.o gcd.o list_sort.o
25 25
26ifeq ($(CONFIG_DEBUG_KOBJECT),y) 26ifeq ($(CONFIG_DEBUG_KOBJECT),y)
27CFLAGS_kobject.o += -DDEBUG 27CFLAGS_kobject.o += -DDEBUG
diff --git a/lib/list_sort.c b/lib/list_sort.c
new file mode 100644
index 000000000000..19d11e0bb958
--- /dev/null
+++ b/lib/list_sort.c
@@ -0,0 +1,102 @@
1#include <linux/kernel.h>
2#include <linux/module.h>
3#include <linux/list_sort.h>
4#include <linux/slab.h>
5#include <linux/list.h>
6
7/**
8 * list_sort - sort a list.
9 * @priv: private data, passed to @cmp
10 * @head: the list to sort
11 * @cmp: the elements comparison function
12 *
13 * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
14 * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
15 * in ascending order.
16 *
17 * The comparison function @cmp is supposed to return a negative value if @a is
18 * less than @b, and a positive value if @a is greater than @b. If @a and @b
19 * are equivalent, then it does not matter what this function returns.
20 */
21void list_sort(void *priv, struct list_head *head,
22 int (*cmp)(void *priv, struct list_head *a,
23 struct list_head *b))
24{
25 struct list_head *p, *q, *e, *list, *tail, *oldhead;
26 int insize, nmerges, psize, qsize, i;
27
28 if (list_empty(head))
29 return;
30
31 list = head->next;
32 list_del(head);
33 insize = 1;
34 for (;;) {
35 p = oldhead = list;
36 list = tail = NULL;
37 nmerges = 0;
38
39 while (p) {
40 nmerges++;
41 q = p;
42 psize = 0;
43 for (i = 0; i < insize; i++) {
44 psize++;
45 q = q->next == oldhead ? NULL : q->next;
46 if (!q)
47 break;
48 }
49
50 qsize = insize;
51 while (psize > 0 || (qsize > 0 && q)) {
52 if (!psize) {
53 e = q;
54 q = q->next;
55 qsize--;
56 if (q == oldhead)
57 q = NULL;
58 } else if (!qsize || !q) {
59 e = p;
60 p = p->next;
61 psize--;
62 if (p == oldhead)
63 p = NULL;
64 } else if (cmp(priv, p, q) <= 0) {
65 e = p;
66 p = p->next;
67 psize--;
68 if (p == oldhead)
69 p = NULL;
70 } else {
71 e = q;
72 q = q->next;
73 qsize--;
74 if (q == oldhead)
75 q = NULL;
76 }
77 if (tail)
78 tail->next = e;
79 else
80 list = e;
81 e->prev = tail;
82 tail = e;
83 }
84 p = q;
85 }
86
87 tail->next = list;
88 list->prev = tail;
89
90 if (nmerges <= 1)
91 break;
92
93 insize *= 2;
94 }
95
96 head->next = list;
97 head->prev = list->prev;
98 list->prev->next = head;
99 list->prev = head;
100}
101
102EXPORT_SYMBOL(list_sort);
generated by cgit v1.2.2 (git 2.25.0) at 2024-10-06 14:30:08 -0400