| qsort.c (15312) | 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 --- 22 unchanged lines hidden (view full) --- 31 * SUCH DAMAGE. 32 */ 33 34#if defined(LIBC_SCCS) && !defined(lint) 35#if 0 36static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93"; 37#endif 38static const char rcsid[] = | 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 --- 22 unchanged lines hidden (view full) --- 31 * SUCH DAMAGE. 32 */ 33 34#if defined(LIBC_SCCS) && !defined(lint) 35#if 0 36static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93"; 37#endif 38static const char rcsid[] = |
| 39 "$Id: qsort.c,v 1.3 1995/12/26 13:24:58 bde Exp $"; | 39 "$Id: qsort.c,v 1.4 1996/04/19 18:40:20 bde Exp $"; |
| 40#endif /* LIBC_SCCS and not lint */ 41 42#include <stdlib.h> 43 44typedef int cmp_t __P((const void *, const void *)); 45static inline char *med3 __P((char *, char *, char *, cmp_t *)); 46static inline void swapfunc __P((char *, char *, int, int)); 47 --- 54 unchanged lines hidden (view full) --- 102 cmp_t *cmp; 103{ 104 char *pa, *pb, *pc, *pd, *pl, *pm, *pn; 105 int d, r, swaptype, swap_cnt; 106 107loop: SWAPINIT(a, es); 108 swap_cnt = 0; 109 if (n < 7) { | 40#endif /* LIBC_SCCS and not lint */ 41 42#include <stdlib.h> 43 44typedef int cmp_t __P((const void *, const void *)); 45static inline char *med3 __P((char *, char *, char *, cmp_t *)); 46static inline void swapfunc __P((char *, char *, int, int)); 47 --- 54 unchanged lines hidden (view full) --- 102 cmp_t *cmp; 103{ 104 char *pa, *pb, *pc, *pd, *pl, *pm, *pn; 105 int d, r, swaptype, swap_cnt; 106 107loop: SWAPINIT(a, es); 108 swap_cnt = 0; 109 if (n < 7) { |
| 110 for (pm = a + es; pm < (char *) a + n * es; pm += es) 111 for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; | 110 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) 111 for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; |
| 112 pl -= es) 113 swap(pl, pl - es); 114 return; 115 } | 112 pl -= es) 113 swap(pl, pl - es); 114 return; 115 } |
| 116 pm = a + (n / 2) * es; | 116 pm = (char *)a + (n / 2) * es; |
| 117 if (n > 7) { 118 pl = a; | 117 if (n > 7) { 118 pl = a; |
| 119 pn = a + (n - 1) * es; | 119 pn = (char *)a + (n - 1) * es; |
| 120 if (n > 40) { 121 d = (n / 8) * es; 122 pl = med3(pl, pl + d, pl + 2 * d, cmp); 123 pm = med3(pm - d, pm, pm + d, cmp); 124 pn = med3(pn - 2 * d, pn - d, pn, cmp); 125 } 126 pm = med3(pl, pm, pn, cmp); 127 } 128 swap(a, pm); | 120 if (n > 40) { 121 d = (n / 8) * es; 122 pl = med3(pl, pl + d, pl + 2 * d, cmp); 123 pm = med3(pm - d, pm, pm + d, cmp); 124 pn = med3(pn - 2 * d, pn - d, pn, cmp); 125 } 126 pm = med3(pl, pm, pn, cmp); 127 } 128 swap(a, pm); |
| 129 pa = pb = a + es; | 129 pa = pb = (char *)a + es; |
| 130 | 130 |
| 131 pc = pd = a + (n - 1) * es; | 131 pc = pd = (char *)a + (n - 1) * es; |
| 132 for (;;) { 133 while (pb <= pc && (r = cmp(pb, a)) <= 0) { 134 if (r == 0) { 135 swap_cnt = 1; 136 swap(pa, pb); 137 pa += es; 138 } 139 pb += es; --- 9 unchanged lines hidden (view full) --- 149 if (pb > pc) 150 break; 151 swap(pb, pc); 152 swap_cnt = 1; 153 pb += es; 154 pc -= es; 155 } 156 if (swap_cnt == 0) { /* Switch to insertion sort */ | 132 for (;;) { 133 while (pb <= pc && (r = cmp(pb, a)) <= 0) { 134 if (r == 0) { 135 swap_cnt = 1; 136 swap(pa, pb); 137 pa += es; 138 } 139 pb += es; --- 9 unchanged lines hidden (view full) --- 149 if (pb > pc) 150 break; 151 swap(pb, pc); 152 swap_cnt = 1; 153 pb += es; 154 pc -= es; 155 } 156 if (swap_cnt == 0) { /* Switch to insertion sort */ |
| 157 for (pm = a + es; pm < (char *) a + n * es; pm += es) 158 for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; | 157 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) 158 for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; |
| 159 pl -= es) 160 swap(pl, pl - es); 161 return; 162 } 163 | 159 pl -= es) 160 swap(pl, pl - es); 161 return; 162 } 163 |
| 164 pn = a + n * es; | 164 pn = (char *)a + n * es; |
| 165 r = min(pa - (char *)a, pb - pa); 166 vecswap(a, pb - r, r); 167 r = min(pd - pc, pn - pd - es); 168 vecswap(pb, pn - r, r); 169 if ((r = pb - pa) > es) 170 qsort(a, r / es, es, cmp); 171 if ((r = pd - pc) > es) { 172 /* Iterate rather than recurse to save stack space */ 173 a = pn - r; 174 n = r / es; 175 goto loop; 176 } 177/* qsort(pn - r, r / es, es, cmp);*/ 178} | 165 r = min(pa - (char *)a, pb - pa); 166 vecswap(a, pb - r, r); 167 r = min(pd - pc, pn - pd - es); 168 vecswap(pb, pn - r, r); 169 if ((r = pb - pa) > es) 170 qsort(a, r / es, es, cmp); 171 if ((r = pd - pc) > es) { 172 /* Iterate rather than recurse to save stack space */ 173 a = pn - r; 174 n = r / es; 175 goto loop; 176 } 177/* qsort(pn - r, r / es, es, cmp);*/ 178} |