2.6.6-xfs-qsort-lkml.patch

   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
  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
  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