Annotation of prex-old/usr/lib/libc/stdlib/qsort.c, Revision 1.1
1.1 ! nbrk 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
! 9: * notice, this list of conditions and the following disclaimer.
! 10: * 2. Redistributions in binary form must reproduce the above copyright
! 11: * notice, this list of conditions and the following disclaimer in the
! 12: * documentation and/or other materials provided with the distribution.
! 13: * 3. Neither the name of the University nor the names of its contributors
! 14: * may be used to endorse or promote products derived from this software
! 15: * without specific prior written permission.
! 16: *
! 17: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
! 18: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
! 19: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
! 20: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
! 21: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
! 22: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
! 23: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
! 24: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
! 25: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
! 26: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
! 27: * SUCH DAMAGE.
! 28: */
! 29:
! 30: #include <sys/cdefs.h>
! 31: #include <sys/types.h>
! 32:
! 33: #include <assert.h>
! 34: #include <errno.h>
! 35: #include <stdlib.h>
! 36:
! 37: static __inline char *med3(char *, char *, char *,
! 38: int (*)(const void *, const void *));
! 39: static __inline void swapfunc(char *, char *, size_t, int);
! 40:
! 41: #define min(a, b) (a) < (b) ? a : b
! 42:
! 43: /*
! 44: * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
! 45: */
! 46: #define swapcode(TYPE, parmi, parmj, n) { \
! 47: size_t i = (n) / sizeof (TYPE); \
! 48: TYPE *pi = (TYPE *)(void *)(parmi); \
! 49: TYPE *pj = (TYPE *)(void *)(parmj); \
! 50: do { \
! 51: TYPE t = *pi; \
! 52: *pi++ = *pj; \
! 53: *pj++ = t; \
! 54: } while (--i > 0); \
! 55: }
! 56:
! 57: #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
! 58: es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
! 59:
! 60: static __inline void
! 61: swapfunc(a, b, n, swaptype)
! 62: char *a, *b;
! 63: size_t n;
! 64: int swaptype;
! 65: {
! 66: if (swaptype <= 1)
! 67: swapcode(long, a, b, n)
! 68: else
! 69: swapcode(char, a, b, n)
! 70: }
! 71:
! 72: #define swap(a, b) \
! 73: if (swaptype == 0) { \
! 74: long t = *(long *)(void *)(a); \
! 75: *(long *)(void *)(a) = *(long *)(void *)(b); \
! 76: *(long *)(void *)(b) = t; \
! 77: } else \
! 78: swapfunc(a, b, es, swaptype)
! 79:
! 80: #define vecswap(a, b, n) if ((n) > 0) swapfunc((a), (b), (size_t)(n), swaptype)
! 81:
! 82: static __inline char *
! 83: med3(a, b, c, cmp)
! 84: char *a, *b, *c;
! 85: int (*cmp)(const void *, const void *);
! 86: {
! 87: return cmp(a, b) < 0 ?
! 88: (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
! 89: :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
! 90: }
! 91:
! 92: void
! 93: qsort(a, n, es, cmp)
! 94: void *a;
! 95: size_t n, es;
! 96: int (*cmp)(const void *, const void *);
! 97: {
! 98: char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
! 99: int d, r, swaptype, swap_cnt;
! 100:
! 101: loop: SWAPINIT(a, es);
! 102: swap_cnt = 0;
! 103: if (n < 7) {
! 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: }
! 110: pm = (char *) a + (n / 2) * es;
! 111: if (n > 7) {
! 112: pl = (char *) a;
! 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);
! 123: pa = pb = (char *) a + es;
! 124:
! 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;
! 134: }
! 135: while (pb <= pc && (r = cmp(pc, a)) >= 0) {
! 136: if (r == 0) {
! 137: swap_cnt = 1;
! 138: swap(pc, pd);
! 139: pd -= es;
! 140: }
! 141: pc -= es;
! 142: }
! 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 = (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: pn = (char *) a + n * es;
! 158: r = min(pa - (char *) a, pb - pa);
! 159: vecswap(a, pb - r, r);
! 160: r = min(pd - pc, pn - pd - es);
! 161: vecswap(pb, pn - r, r);
! 162: if ((r = pb - pa) > es)
! 163: qsort(a, r / es, es, cmp);
! 164: if ((r = pd - pc) > es) {
! 165: /* Iterate rather than recurse to save stack space */
! 166: a = pn - r;
! 167: n = r / es;
! 168: goto loop;
! 169: }
! 170: /* qsort(pn - r, r / es, es, cmp);*/
! 171: }
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to qsort.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / prex-old / usr / lib / libc / stdlib