| qsort.c (17880) | qsort.c (17971) |
|---|---|
| 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 --- 16 unchanged lines hidden (view full) --- 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 * | 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 --- 16 unchanged lines hidden (view full) --- 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 * |
| 33 * $Id$ | 33 * $Id: qsort.c,v 1.4 1996/08/28 20:32:19 bde Exp $ |
| 34 */ 35 36#include <stdlib.h> 37 38typedef int cmp_t __P((const void *, const void *)); 39static inline char *med3 __P((char *, char *, char *, cmp_t *)); 40static inline void swapfunc __P((char *, char *, int, int)); 41 --- 54 unchanged lines hidden (view full) --- 96 cmp_t *cmp; 97{ 98 char *pa, *pb, *pc, *pd, *pl, *pm, *pn; 99 int d, r, swaptype, swap_cnt; 100 101loop: SWAPINIT(a, es); 102 swap_cnt = 0; 103 if (n < 7) { | 34 */ 35 36#include <stdlib.h> 37 38typedef int cmp_t __P((const void *, const void *)); 39static inline char *med3 __P((char *, char *, char *, cmp_t *)); 40static inline void swapfunc __P((char *, char *, int, int)); 41 --- 54 unchanged lines hidden (view full) --- 96 cmp_t *cmp; 97{ 98 char *pa, *pb, *pc, *pd, *pl, *pm, *pn; 99 int d, r, swaptype, swap_cnt; 100 101loop: SWAPINIT(a, es); 102 swap_cnt = 0; 103 if (n < 7) { |
| 104 for (pm = a + es; pm < (char *) a + n * es; pm += es) 105 for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; | 104 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) 105 for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; |
| 106 pl -= es) 107 swap(pl, pl - es); 108 return; 109 } | 106 pl -= es) 107 swap(pl, pl - es); 108 return; 109 } |
| 110 pm = a + (n / 2) * es; | 110 pm = (char *)a + (n / 2) * es; |
| 111 if (n > 7) { 112 pl = a; | 111 if (n > 7) { 112 pl = a; |
| 113 pn = a + (n - 1) * es; | 113 pn = (char *)a + (n - 1) * es; |
| 114 if (n > 40) { 115 d = (n / 8) * es; 116 pl = med3(pl, pl + d, pl + 2 * d, cmp); 117 pm = med3(pm - d, pm, pm + d, cmp); 118 pn = med3(pn - 2 * d, pn - d, pn, cmp); 119 } 120 pm = med3(pl, pm, pn, cmp); 121 } 122 swap(a, pm); | 114 if (n > 40) { 115 d = (n / 8) * es; 116 pl = med3(pl, pl + d, pl + 2 * d, cmp); 117 pm = med3(pm - d, pm, pm + d, cmp); 118 pn = med3(pn - 2 * d, pn - d, pn, cmp); 119 } 120 pm = med3(pl, pm, pn, cmp); 121 } 122 swap(a, pm); |
| 123 pa = pb = a + es; | 123 pa = pb = (char *)a + es; |
| 124 | 124 |
| 125 pc = pd = a + (n - 1) * es; | 125 pc = pd = (char *)a + (n - 1) * es; |
| 126 for (;;) { 127 while (pb <= pc && (r = cmp(pb, a)) <= 0) { 128 if (r == 0) { 129 swap_cnt = 1; 130 swap(pa, pb); 131 pa += es; 132 } 133 pb += es; --- 9 unchanged lines hidden (view full) --- 143 if (pb > pc) 144 break; 145 swap(pb, pc); 146 swap_cnt = 1; 147 pb += es; 148 pc -= es; 149 } 150 if (swap_cnt == 0) { /* Switch to insertion sort */ | 126 for (;;) { 127 while (pb <= pc && (r = cmp(pb, a)) <= 0) { 128 if (r == 0) { 129 swap_cnt = 1; 130 swap(pa, pb); 131 pa += es; 132 } 133 pb += es; --- 9 unchanged lines hidden (view full) --- 143 if (pb > pc) 144 break; 145 swap(pb, pc); 146 swap_cnt = 1; 147 pb += es; 148 pc -= es; 149 } 150 if (swap_cnt == 0) { /* Switch to insertion sort */ |
| 151 for (pm = a + es; pm < (char *) a + n * es; pm += es) 152 for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; | 151 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) 152 for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; |
| 153 pl -= es) 154 swap(pl, pl - es); 155 return; 156 } 157 | 153 pl -= es) 154 swap(pl, pl - es); 155 return; 156 } 157 |
| 158 pn = a + n * es; | 158 pn = (char *)a + n * es; |
| 159 r = min(pa - (char *)a, pb - pa); 160 vecswap(a, pb - r, r); 161 r = min(pd - pc, pn - pd - es); 162 vecswap(pb, pn - r, r); 163 if ((r = pb - pa) > es) 164 qsort(a, r / es, es, cmp); 165 if ((r = pd - pc) > es) { 166 /* Iterate rather than recurse to save stack space */ 167 a = pn - r; 168 n = r / es; 169 goto loop; 170 } 171/* qsort(pn - r, r / es, es, cmp);*/ 172} | 159 r = min(pa - (char *)a, pb - pa); 160 vecswap(a, pb - r, r); 161 r = min(pd - pc, pn - pd - es); 162 vecswap(pb, pn - r, r); 163 if ((r = pb - pa) > es) 164 qsort(a, r / es, es, cmp); 165 if ((r = pd - pc) > es) { 166 /* Iterate rather than recurse to save stack space */ 167 a = pn - r; 168 n = r / es; 169 goto loop; 170 } 171/* qsort(pn - r, r / es, es, cmp);*/ 172} |