]>
Commit | Line | Data |
---|---|---|
cb791f4e | 1 | This is a rehash of a patch from Andreas Gruenbacher <agruen@suse.de> |
2 | to have XFS use a kernel-provided qsort function (ie. not it's own). | |
3 | It requires (but does not conflict with) the previous patch I posted | |
4 | adding qsort to the kernel library functions. | |
5 | ||
6 | ||
7 | --cw | |
8 | ||
9 | ||
10 | Kconfig | 1 | |
11 | xfs/linux/xfs_linux.h | 1 | |
12 | xfs/support/qsort.c | 155 -------------------------------------------------- | |
13 | xfs/support/qsort.h | 41 ------------- | |
14 | 4 files changed, 1 insertion(+), 197 deletions(-) | |
15 | ||
16 | ||
17 | ||
18 | diff -Nru a/fs/Kconfig b/fs/Kconfig | |
19 | --- a/fs/Kconfig Sun May 9 20:27:31 2004 | |
20 | +++ b/fs/Kconfig Sun May 9 20:27:31 2004 | |
21 | @@ -293,6 +293,7 @@ | |
22 | ||
23 | config XFS_FS | |
24 | tristate "XFS filesystem support" | |
25 | + select QSORT | |
26 | help | |
27 | XFS is a high performance journaling filesystem which originated | |
28 | on the SGI IRIX platform. It is completely multi-threaded, can | |
c9d1c54c AM |
29 | diff -Nru a/fs/xfs/linux-2.6/xfs_linux.h b/fs/xfs/linux-2.6/xfs_linux.h |
30 | --- a/fs/xfs/linux-2.6/xfs_linux.h Sun May 9 20:27:31 2004 | |
31 | +++ b/fs/xfs/linux-2.6/xfs_linux.h Sun May 9 20:27:31 2004 | |
cb791f4e | 32 | @@ -64,7 +64,6 @@ |
33 | #include <sema.h> | |
34 | #include <time.h> | |
35 | ||
36 | -#include <support/qsort.h> | |
37 | #include <support/ktrace.h> | |
38 | #include <support/debug.h> | |
39 | #include <support/move.h> | |
40 | diff -Nru a/fs/xfs/support/qsort.c b/fs/xfs/support/qsort.c | |
41 | --- a/fs/xfs/support/qsort.c Sun May 9 20:27:31 2004 | |
42 | +++ b/fs/xfs/support/qsort.c Sun May 9 20:27:31 2004 | |
43 | @@ -1,155 +0,0 @@ | |
44 | -/* | |
45 | - * Copyright (c) 1992, 1993 | |
46 | - * The Regents of the University of California. All rights reserved. | |
47 | - * | |
48 | - * Redistribution and use in source and binary forms, with or without | |
49 | - * modification, are permitted provided that the following conditions | |
50 | - * are met: | |
51 | - * 1. Redistributions of source code must retain the above copyright | |
52 | - * notice, this list of conditions and the following disclaimer. | |
53 | - * 2. Redistributions in binary form must reproduce the above copyright | |
54 | - * notice, this list of conditions and the following disclaimer in the | |
55 | - * documentation and/or other materials provided with the distribution. | |
56 | - * 3. Neither the name of the University nor the names of its contributors | |
57 | - * may be used to endorse or promote products derived from this software | |
58 | - * without specific prior written permission. | |
59 | - * | |
60 | - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | |
61 | - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
62 | - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
63 | - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
64 | - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
65 | - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
66 | - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
67 | - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
68 | - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
69 | - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
70 | - * SUCH DAMAGE. | |
71 | - */ | |
72 | - | |
73 | -#include <linux/kernel.h> | |
74 | -#include <linux/string.h> | |
75 | - | |
76 | -/* | |
77 | - * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". | |
78 | - */ | |
79 | -#define swapcode(TYPE, parmi, parmj, n) { \ | |
80 | - long i = (n) / sizeof (TYPE); \ | |
81 | - register TYPE *pi = (TYPE *) (parmi); \ | |
82 | - register TYPE *pj = (TYPE *) (parmj); \ | |
83 | - do { \ | |
84 | - register TYPE t = *pi; \ | |
85 | - *pi++ = *pj; \ | |
86 | - *pj++ = t; \ | |
87 | - } while (--i > 0); \ | |
88 | -} | |
89 | - | |
90 | -#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ | |
91 | - es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; | |
92 | - | |
93 | -static __inline void | |
94 | -swapfunc(char *a, char *b, int n, int swaptype) | |
95 | -{ | |
96 | - if (swaptype <= 1) | |
97 | - swapcode(long, a, b, n) | |
98 | - else | |
99 | - swapcode(char, a, b, n) | |
100 | -} | |
101 | - | |
102 | -#define swap(a, b) \ | |
103 | - if (swaptype == 0) { \ | |
104 | - long t = *(long *)(a); \ | |
105 | - *(long *)(a) = *(long *)(b); \ | |
106 | - *(long *)(b) = t; \ | |
107 | - } else \ | |
108 | - swapfunc(a, b, es, swaptype) | |
109 | - | |
110 | -#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) | |
111 | - | |
112 | -static __inline char * | |
113 | -med3(char *a, char *b, char *c, int (*cmp)(const void *, const void *)) | |
114 | -{ | |
115 | - return cmp(a, b) < 0 ? | |
116 | - (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a )) | |
117 | - :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c )); | |
118 | -} | |
119 | - | |
120 | -void | |
121 | -qsort(void *aa, size_t n, size_t es, int (*cmp)(const void *, const void *)) | |
122 | -{ | |
123 | - char *pa, *pb, *pc, *pd, *pl, *pm, *pn; | |
124 | - int d, r, swaptype, swap_cnt; | |
125 | - register char *a = aa; | |
126 | - | |
127 | -loop: SWAPINIT(a, es); | |
128 | - swap_cnt = 0; | |
129 | - if (n < 7) { | |
130 | - for (pm = (char *)a + es; pm < (char *) a + n * es; pm += es) | |
131 | - for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; | |
132 | - pl -= es) | |
133 | - swap(pl, pl - es); | |
134 | - return; | |
135 | - } | |
136 | - pm = (char *)a + (n / 2) * es; | |
137 | - if (n > 7) { | |
138 | - pl = (char *)a; | |
139 | - pn = (char *)a + (n - 1) * es; | |
140 | - if (n > 40) { | |
141 | - d = (n / 8) * es; | |
142 | - pl = med3(pl, pl + d, pl + 2 * d, cmp); | |
143 | - pm = med3(pm - d, pm, pm + d, cmp); | |
144 | - pn = med3(pn - 2 * d, pn - d, pn, cmp); | |
145 | - } | |
146 | - pm = med3(pl, pm, pn, cmp); | |
147 | - } | |
148 | - swap(a, pm); | |
149 | - pa = pb = (char *)a + es; | |
150 | - | |
151 | - pc = pd = (char *)a + (n - 1) * es; | |
152 | - for (;;) { | |
153 | - while (pb <= pc && (r = cmp(pb, a)) <= 0) { | |
154 | - if (r == 0) { | |
155 | - swap_cnt = 1; | |
156 | - swap(pa, pb); | |
157 | - pa += es; | |
158 | - } | |
159 | - pb += es; | |
160 | - } | |
161 | - while (pb <= pc && (r = cmp(pc, a)) >= 0) { | |
162 | - if (r == 0) { | |
163 | - swap_cnt = 1; | |
164 | - swap(pc, pd); | |
165 | - pd -= es; | |
166 | - } | |
167 | - pc -= es; | |
168 | - } | |
169 | - if (pb > pc) | |
170 | - break; | |
171 | - swap(pb, pc); | |
172 | - swap_cnt = 1; | |
173 | - pb += es; | |
174 | - pc -= es; | |
175 | - } | |
176 | - if (swap_cnt == 0) { /* Switch to insertion sort */ | |
177 | - for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) | |
178 | - for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; | |
179 | - pl -= es) | |
180 | - swap(pl, pl - es); | |
181 | - return; | |
182 | - } | |
183 | - | |
184 | - pn = (char *)a + n * es; | |
185 | - r = min(pa - (char *)a, pb - pa); | |
186 | - vecswap(a, pb - r, r); | |
187 | - r = min((long)(pd - pc), (long)(pn - pd - es)); | |
188 | - vecswap(pb, pn - r, r); | |
189 | - if ((r = pb - pa) > es) | |
190 | - qsort(a, r / es, es, cmp); | |
191 | - if ((r = pd - pc) > es) { | |
192 | - /* Iterate rather than recurse to save stack space */ | |
193 | - a = pn - r; | |
194 | - n = r / es; | |
195 | - goto loop; | |
196 | - } | |
197 | -/* qsort(pn - r, r / es, es, cmp);*/ | |
198 | -} | |
199 | diff -Nru a/fs/xfs/support/qsort.h b/fs/xfs/support/qsort.h | |
200 | --- a/fs/xfs/support/qsort.h Sun May 9 20:27:31 2004 | |
201 | +++ b/fs/xfs/support/qsort.h Sun May 9 20:27:31 2004 | |
202 | @@ -1,41 +0,0 @@ | |
203 | -/* | |
204 | - * Copyright (c) 2000-2002 Silicon Graphics, Inc. All Rights Reserved. | |
205 | - * | |
206 | - * This program is free software; you can redistribute it and/or modify it | |
207 | - * under the terms of version 2 of the GNU General Public License as | |
208 | - * published by the Free Software Foundation. | |
209 | - * | |
210 | - * This program is distributed in the hope that it would be useful, but | |
211 | - * WITHOUT ANY WARRANTY; without even the implied warranty of | |
212 | - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. | |
213 | - * | |
214 | - * Further, this software is distributed without any warranty that it is | |
215 | - * free of the rightful claim of any third person regarding infringement | |
216 | - * or the like. Any license provided herein, whether implied or | |
217 | - * otherwise, applies only to this software file. Patent licenses, if | |
218 | - * any, provided herein do not apply to combinations of this program with | |
219 | - * other software, or any other product whatsoever. | |
220 | - * | |
221 | - * You should have received a copy of the GNU General Public License along | |
222 | - * with this program; if not, write the Free Software Foundation, Inc., 59 | |
223 | - * Temple Place - Suite 330, Boston MA 02111-1307, USA. | |
224 | - * | |
225 | - * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy, | |
226 | - * Mountain View, CA 94043, or: | |
227 | - * | |
228 | - * http://www.sgi.com | |
229 | - * | |
230 | - * For further information regarding this notice, see: | |
231 | - * | |
232 | - * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/ | |
233 | - */ | |
234 | - | |
235 | -#ifndef QSORT_H | |
236 | -#define QSORT_H | |
237 | - | |
238 | -extern void qsort (void *const pbase, | |
239 | - size_t total_elems, | |
240 | - size_t size, | |
241 | - int (*cmp)(const void *, const void *)); | |
242 | - | |
243 | -#endif | |
244 | - | |
245 |