]>
git.ipfire.org Git - people/ms/u-boot.git/blob - fs/yaffs2/yaffs_qsort.c
2 * Copyright (c) 1992, 1993
3 * The Regents of the University of California. All rights reserved.
5 * SPDX-License-Identifier: BSD-3-Clause
9 /* #include <linux/string.h> */
12 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
14 #define swapcode(TYPE, parmi, parmj, n) do { \
15 long i = (n) / sizeof(TYPE); \
16 register TYPE *pi = (TYPE *) (parmi); \
17 register TYPE *pj = (TYPE *) (parmj); \
19 register TYPE t = *pi; \
25 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
26 es % sizeof(long) ? 2 : es == sizeof(long) ? 0 : 1;
29 swapfunc(char *a
, char *b
, int n
, int swaptype
)
32 swapcode(long, a
, b
, n
);
34 swapcode(char, a
, b
, n
);
37 #define yswap(a, b) do { \
38 if (swaptype == 0) { \
39 long t = *(long *)(a); \
40 *(long *)(a) = *(long *)(b); \
43 swapfunc(a, b, es, swaptype); \
46 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
49 med3(char *a
, char *b
, char *c
, int (*cmp
)(const void *, const void *))
51 return cmp(a
, b
) < 0 ?
52 (cmp(b
, c
) < 0 ? b
: (cmp(a
, c
) < 0 ? c
: a
))
53 : (cmp(b
, c
) > 0 ? b
: (cmp(a
, c
) < 0 ? a
: c
));
57 #define min(a, b) (((a) < (b)) ? (a) : (b))
61 yaffs_qsort(void *aa
, size_t n
, size_t es
,
62 int (*cmp
)(const void *, const void *))
64 char *pa
, *pb
, *pc
, *pd
, *pl
, *pm
, *pn
;
65 int d
, r
, swaptype
, swap_cnt
;
66 register char *a
= aa
;
68 loop
: SWAPINIT(a
, es
);
71 for (pm
= (char *)a
+ es
; pm
< (char *) a
+ n
* es
; pm
+= es
)
72 for (pl
= pm
; pl
> (char *) a
&& cmp(pl
- es
, pl
) > 0;
77 pm
= (char *)a
+ (n
/ 2) * es
;
80 pn
= (char *)a
+ (n
- 1) * es
;
83 pl
= med3(pl
, pl
+ d
, pl
+ 2 * d
, cmp
);
84 pm
= med3(pm
- d
, pm
, pm
+ d
, cmp
);
85 pn
= med3(pn
- 2 * d
, pn
- d
, pn
, cmp
);
87 pm
= med3(pl
, pm
, pn
, cmp
);
90 pa
= pb
= (char *)a
+ es
;
92 pc
= pd
= (char *)a
+ (n
- 1) * es
;
94 while (pb
<= pc
&& (r
= cmp(pb
, a
)) <= 0) {
102 while (pb
<= pc
&& (r
= cmp(pc
, a
)) >= 0) {
117 if (swap_cnt
== 0) { /* Switch to insertion sort */
118 for (pm
= (char *) a
+ es
; pm
< (char *) a
+ n
* es
; pm
+= es
)
119 for (pl
= pm
; pl
> (char *) a
&& cmp(pl
- es
, pl
) > 0;
125 pn
= (char *)a
+ n
* es
;
126 r
= min(pa
- (char *)a
, pb
- pa
);
127 vecswap(a
, pb
- r
, r
);
128 r
= min((long)(pd
- pc
), (long)(pn
- pd
- es
));
129 vecswap(pb
, pn
- r
, r
);
132 yaffs_qsort(a
, r
/ es
, es
, cmp
);
135 /* Iterate rather than recurse to save stack space */
140 /* yaffs_qsort(pn - r, r / es, es, cmp);*/