qsort.c (333fc21e3cd79bca0c94d7722c5a56cb5ad078d1) qsort.c (eca67d510483ad9565b7b816e16fc72ebe3b2864)
1/*-
2 * Copyright (c) 1992, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright

--- 25 unchanged lines hidden (view full) ---

34#if defined(LIBC_SCCS) && !defined(lint)
35static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93";
36#endif /* LIBC_SCCS and not lint */
37#include <sys/cdefs.h>
38__FBSDID("$FreeBSD$");
39
40#include <stdlib.h>
41
1/*-
2 * Copyright (c) 1992, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright

--- 25 unchanged lines hidden (view full) ---

34#if defined(LIBC_SCCS) && !defined(lint)
35static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93";
36#endif /* LIBC_SCCS and not lint */
37#include <sys/cdefs.h>
38__FBSDID("$FreeBSD$");
39
40#include <stdlib.h>
41
42#ifdef I_AM_QSORT_R
43typedef int cmp_t(void *, const void *, const void *);
44#else
42typedef int cmp_t(const void *, const void *);
45typedef int cmp_t(const void *, const void *);
43static inline char *med3(char *, char *, char *, cmp_t *);
46#endif
47static inline char *med3(char *, char *, char *, cmp_t *, void *);
44static inline void swapfunc(char *, char *, int, int);
45
46#define min(a, b) (a) < (b) ? a : b
47
48/*
49 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
50 */
51#define swapcode(TYPE, parmi, parmj, n) { \

--- 26 unchanged lines hidden (view full) ---

78 long t = *(long *)(a); \
79 *(long *)(a) = *(long *)(b); \
80 *(long *)(b) = t; \
81 } else \
82 swapfunc(a, b, es, swaptype)
83
84#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
85
48static inline void swapfunc(char *, char *, int, int);
49
50#define min(a, b) (a) < (b) ? a : b
51
52/*
53 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
54 */
55#define swapcode(TYPE, parmi, parmj, n) { \

--- 26 unchanged lines hidden (view full) ---

82 long t = *(long *)(a); \
83 *(long *)(a) = *(long *)(b); \
84 *(long *)(b) = t; \
85 } else \
86 swapfunc(a, b, es, swaptype)
87
88#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
89
90#ifdef I_AM_QSORT_R
91#define CMP(t, x, y) (cmp((t), (x), (y)))
92#else
93#define CMP(t, x, y) (cmp((x), (y)))
94#endif
95
86static inline char *
96static inline char *
87med3(a, b, c, cmp)
88 char *a, *b, *c;
89 cmp_t *cmp;
97med3(char *a, char *b, char *c, cmp_t *cmp, void *thunk
98#ifndef I_AM_QSORT_R
99__unused
100#endif
101)
90{
102{
91 return cmp(a, b) < 0 ?
92 (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
93 :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
103 return CMP(thunk, a, b) < 0 ?
104 (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a ))
105 :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
94}
95
106}
107
108#ifdef I_AM_QSORT_R
96void
109void
97qsort(a, n, es, cmp)
98 void *a;
99 size_t n, es;
100 cmp_t *cmp;
110qsort_r(void *a, size_t n, size_t es, void *thunk, cmp_t *cmp)
111#else
112#define thunk NULL
113void
114qsort(void *a, size_t n, size_t es, cmp_t *cmp)
115#endif
101{
102 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
103 int d, r, swaptype, swap_cnt;
104
105loop: SWAPINIT(a, es);
106 swap_cnt = 0;
107 if (n < 7) {
108 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
116{
117 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
118 int d, r, swaptype, swap_cnt;
119
120loop: SWAPINIT(a, es);
121 swap_cnt = 0;
122 if (n < 7) {
123 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
109 for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
124 for (pl = pm;
125 pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
110 pl -= es)
111 swap(pl, pl - es);
112 return;
113 }
114 pm = (char *)a + (n / 2) * es;
115 if (n > 7) {
116 pl = a;
117 pn = (char *)a + (n - 1) * es;
118 if (n > 40) {
119 d = (n / 8) * es;
126 pl -= es)
127 swap(pl, pl - es);
128 return;
129 }
130 pm = (char *)a + (n / 2) * es;
131 if (n > 7) {
132 pl = a;
133 pn = (char *)a + (n - 1) * es;
134 if (n > 40) {
135 d = (n / 8) * es;
120 pl = med3(pl, pl + d, pl + 2 * d, cmp);
121 pm = med3(pm - d, pm, pm + d, cmp);
122 pn = med3(pn - 2 * d, pn - d, pn, cmp);
136 pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
137 pm = med3(pm - d, pm, pm + d, cmp, thunk);
138 pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
123 }
139 }
124 pm = med3(pl, pm, pn, cmp);
140 pm = med3(pl, pm, pn, cmp, thunk);
125 }
126 swap(a, pm);
127 pa = pb = (char *)a + es;
128
129 pc = pd = (char *)a + (n - 1) * es;
130 for (;;) {
141 }
142 swap(a, pm);
143 pa = pb = (char *)a + es;
144
145 pc = pd = (char *)a + (n - 1) * es;
146 for (;;) {
131 while (pb <= pc && (r = cmp(pb, a)) <= 0) {
147 while (pb <= pc && (r = CMP(thunk, pb, a)) <= 0) {
132 if (r == 0) {
133 swap_cnt = 1;
134 swap(pa, pb);
135 pa += es;
136 }
137 pb += es;
138 }
148 if (r == 0) {
149 swap_cnt = 1;
150 swap(pa, pb);
151 pa += es;
152 }
153 pb += es;
154 }
139 while (pb <= pc && (r = cmp(pc, a)) >= 0) {
155 while (pb <= pc && (r = CMP(thunk, pc, a)) >= 0) {
140 if (r == 0) {
141 swap_cnt = 1;
142 swap(pc, pd);
143 pd -= es;
144 }
145 pc -= es;
146 }
147 if (pb > pc)
148 break;
149 swap(pb, pc);
150 swap_cnt = 1;
151 pb += es;
152 pc -= es;
153 }
154 if (swap_cnt == 0) { /* Switch to insertion sort */
155 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
156 if (r == 0) {
157 swap_cnt = 1;
158 swap(pc, pd);
159 pd -= es;
160 }
161 pc -= es;
162 }
163 if (pb > pc)
164 break;
165 swap(pb, pc);
166 swap_cnt = 1;
167 pb += es;
168 pc -= es;
169 }
170 if (swap_cnt == 0) { /* Switch to insertion sort */
171 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
156 for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
172 for (pl = pm;
173 pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
157 pl -= es)
158 swap(pl, pl - es);
159 return;
160 }
161
162 pn = (char *)a + n * es;
163 r = min(pa - (char *)a, pb - pa);
164 vecswap(a, pb - r, r);
165 r = min(pd - pc, pn - pd - es);
166 vecswap(pb, pn - r, r);
167 if ((r = pb - pa) > es)
174 pl -= es)
175 swap(pl, pl - es);
176 return;
177 }
178
179 pn = (char *)a + n * es;
180 r = min(pa - (char *)a, pb - pa);
181 vecswap(a, pb - r, r);
182 r = min(pd - pc, pn - pd - es);
183 vecswap(pb, pn - r, r);
184 if ((r = pb - pa) > es)
185#ifdef I_AM_QSORT_R
186 qsort_r(a, r / es, es, thunk, cmp);
187#else
168 qsort(a, r / es, es, cmp);
188 qsort(a, r / es, es, cmp);
189#endif
169 if ((r = pd - pc) > es) {
170 /* Iterate rather than recurse to save stack space */
171 a = pn - r;
172 n = r / es;
173 goto loop;
174 }
175/* qsort(pn - r, r / es, es, cmp);*/
176}
190 if ((r = pd - pc) > es) {
191 /* Iterate rather than recurse to save stack space */
192 a = pn - r;
193 n = r / es;
194 goto loop;
195 }
196/* qsort(pn - r, r / es, es, cmp);*/
197}