summaryrefslogtreecommitdiff
path: root/src/lib/libc/stdlib/qsort.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libc/stdlib/qsort.c')
-rw-r--r--src/lib/libc/stdlib/qsort.c34
1 files changed, 17 insertions, 17 deletions
diff --git a/src/lib/libc/stdlib/qsort.c b/src/lib/libc/stdlib/qsort.c
index c06bd54054..9b8bb5801b 100644
--- a/src/lib/libc/stdlib/qsort.c
+++ b/src/lib/libc/stdlib/qsort.c
@@ -32,15 +32,14 @@
32 */ 32 */
33 33
34#if defined(LIBC_SCCS) && !defined(lint) 34#if defined(LIBC_SCCS) && !defined(lint)
35/*static char sccsid[] = "from: @(#)qsort.c 8.1 (Berkeley) 6/4/93";*/ 35static char *rcsid = "$OpenBSD: qsort.c,v 1.7 2002/02/17 19:42:24 millert Exp $";
36static char *rcsid = "$Id: qsort.c,v 1.1.1.1 1995/10/18 08:42:18 deraadt Exp $";
37#endif /* LIBC_SCCS and not lint */ 36#endif /* LIBC_SCCS and not lint */
38 37
39#include <sys/types.h> 38#include <sys/types.h>
40#include <stdlib.h> 39#include <stdlib.h>
41 40
42static inline char *med3 __P((char *, char *, char *, int (*)())); 41static __inline char *med3(char *, char *, char *, int (*)());
43static inline void swapfunc __P((char *, char *, int, int)); 42static __inline void swapfunc(char *, char *, int, int);
44 43
45#define min(a, b) (a) < (b) ? a : b 44#define min(a, b) (a) < (b) ? a : b
46 45
@@ -61,12 +60,12 @@ static inline void swapfunc __P((char *, char *, int, int));
61#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ 60#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
62 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; 61 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
63 62
64static inline void 63static __inline void
65swapfunc(a, b, n, swaptype) 64swapfunc(a, b, n, swaptype)
66 char *a, *b; 65 char *a, *b;
67 int n, swaptype; 66 int n, swaptype;
68{ 67{
69 if(swaptype <= 1) 68 if (swaptype <= 1)
70 swapcode(long, a, b, n) 69 swapcode(long, a, b, n)
71 else 70 else
72 swapcode(char, a, b, n) 71 swapcode(char, a, b, n)
@@ -82,7 +81,7 @@ swapfunc(a, b, n, swaptype)
82 81
83#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) 82#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
84 83
85static inline char * 84static __inline char *
86med3(a, b, c, cmp) 85med3(a, b, c, cmp)
87 char *a, *b, *c; 86 char *a, *b, *c;
88 int (*cmp)(); 87 int (*cmp)();
@@ -93,27 +92,28 @@ med3(a, b, c, cmp)
93} 92}
94 93
95void 94void
96qsort(a, n, es, cmp) 95qsort(aa, n, es, cmp)
97 void *a; 96 void *aa;
98 size_t n, es; 97 size_t n, es;
99 int (*cmp)(); 98 int (*cmp)();
100{ 99{
101 char *pa, *pb, *pc, *pd, *pl, *pm, *pn; 100 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
102 int d, r, swaptype, swap_cnt; 101 int d, r, swaptype, swap_cnt;
102 register char *a = aa;
103 103
104loop: SWAPINIT(a, es); 104loop: SWAPINIT(a, es);
105 swap_cnt = 0; 105 swap_cnt = 0;
106 if (n < 7) { 106 if (n < 7) {
107 for (pm = a + es; pm < (char *) a + n * es; pm += es) 107 for (pm = (char *)a + es; pm < (char *) a + n * es; pm += es)
108 for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; 108 for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
109 pl -= es) 109 pl -= es)
110 swap(pl, pl - es); 110 swap(pl, pl - es);
111 return; 111 return;
112 } 112 }
113 pm = a + (n / 2) * es; 113 pm = (char *)a + (n / 2) * es;
114 if (n > 7) { 114 if (n > 7) {
115 pl = a; 115 pl = (char *)a;
116 pn = a + (n - 1) * es; 116 pn = (char *)a + (n - 1) * es;
117 if (n > 40) { 117 if (n > 40) {
118 d = (n / 8) * es; 118 d = (n / 8) * es;
119 pl = med3(pl, pl + d, pl + 2 * d, cmp); 119 pl = med3(pl, pl + d, pl + 2 * d, cmp);
@@ -123,9 +123,9 @@ loop: SWAPINIT(a, es);
123 pm = med3(pl, pm, pn, cmp); 123 pm = med3(pl, pm, pn, cmp);
124 } 124 }
125 swap(a, pm); 125 swap(a, pm);
126 pa = pb = a + es; 126 pa = pb = (char *)a + es;
127 127
128 pc = pd = a + (n - 1) * es; 128 pc = pd = (char *)a + (n - 1) * es;
129 for (;;) { 129 for (;;) {
130 while (pb <= pc && (r = cmp(pb, a)) <= 0) { 130 while (pb <= pc && (r = cmp(pb, a)) <= 0) {
131 if (r == 0) { 131 if (r == 0) {
@@ -151,14 +151,14 @@ loop: SWAPINIT(a, es);
151 pc -= es; 151 pc -= es;
152 } 152 }
153 if (swap_cnt == 0) { /* Switch to insertion sort */ 153 if (swap_cnt == 0) { /* Switch to insertion sort */
154 for (pm = a + es; pm < (char *) a + n * es; pm += es) 154 for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
155 for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; 155 for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
156 pl -= es) 156 pl -= es)
157 swap(pl, pl - es); 157 swap(pl, pl - es);
158 return; 158 return;
159 } 159 }
160 160
161 pn = a + n * es; 161 pn = (char *)a + n * es;
162 r = min(pa - (char *)a, pb - pa); 162 r = min(pa - (char *)a, pb - pa);
163 vecswap(a, pb - r, r); 163 vecswap(a, pb - r, r);
164 r = min(pd - pc, pn - pd - es); 164 r = min(pd - pc, pn - pd - es);