openblt

a hobby OS from the late 90s
git clone http://frotz.net/git/openblt.git
Log | Files | Refs | LICENSE

qsort.c (5016B)


      1 /* $Id: //depot/blt/lib/libc/qsort.c#1 $ */
      2 /* $OpenBSD: qsort.c,v 1.5 1997/06/20 11:19:38 deraadt Exp $ */
      3 
      4 /*
      5  * Copyright (c) 1992, 1993
      6  *	The Regents of the University of California.  All rights reserved.
      7  *
      8  * Redistribution and use in source and binary forms, with or without
      9  * modification, are permitted provided that the following conditions
     10  * are met:
     11  * 1. Redistributions of source code must retain the above copyright
     12  *    notice, this list of conditions and the following disclaimer.
     13  * 2. Redistributions in binary form must reproduce the above copyright
     14  *    notice, this list of conditions and the following disclaimer in the
     15  *    documentation and/or other materials provided with the distribution.
     16  * 3. All advertising materials mentioning features or use of this software
     17  *    must display the following acknowledgement:
     18  *	This product includes software developed by the University of
     19  *	California, Berkeley and its contributors.
     20  * 4. Neither the name of the University nor the names of its contributors
     21  *    may be used to endorse or promote products derived from this software
     22  *    without specific prior written permission.
     23  *
     24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     34  * SUCH DAMAGE.
     35  */
     36 
     37 #include <sys/types.h>
     38 #include <stdlib.h>
     39 
     40 static __inline char	*med3 (char *, char *, char *, int (*)());
     41 static __inline void	 swapfunc (char *, char *, int, int);
     42 
     43 #define min(a, b)	(a) < (b) ? a : b
     44 
     45 /*
     46  * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
     47  */
     48 #define swapcode(TYPE, parmi, parmj, n) { 		\
     49 	long i = (n) / sizeof (TYPE); 			\
     50 	register TYPE *pi = (TYPE *) (parmi); 		\
     51 	register TYPE *pj = (TYPE *) (parmj); 		\
     52 	do { 						\
     53 		register TYPE	t = *pi;		\
     54 		*pi++ = *pj;				\
     55 		*pj++ = t;				\
     56         } while (--i > 0);				\
     57 }
     58 
     59 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
     60 	es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
     61 
     62 static __inline void
     63 swapfunc(a, b, n, swaptype)
     64 	char *a, *b;
     65 	int n, swaptype;
     66 {
     67 	if (swaptype <= 1) 
     68 		swapcode(long, a, b, n)
     69 	else
     70 		swapcode(char, a, b, n)
     71 }
     72 
     73 #define swap(a, b)					\
     74 	if (swaptype == 0) {				\
     75 		long t = *(long *)(a);			\
     76 		*(long *)(a) = *(long *)(b);		\
     77 		*(long *)(b) = t;			\
     78 	} else						\
     79 		swapfunc(a, b, es, swaptype)
     80 
     81 #define vecswap(a, b, n) 	if ((n) > 0) swapfunc(a, b, n, swaptype)
     82 
     83 static __inline char *
     84 med3(a, b, c, cmp)
     85 	char *a, *b, *c;
     86 	int (*cmp)();
     87 {
     88 	return cmp(a, b) < 0 ?
     89 	       (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
     90               :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
     91 }
     92 
     93 void
     94 qsort(aa, n, es, cmp)
     95 	void *aa;
     96 	size_t n, es;
     97 	int (*cmp)();
     98 {
     99 	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
    100 	int d, r, swaptype, swap_cnt;
    101 	register char *a = aa;
    102 
    103 loop:	SWAPINIT(a, es);
    104 	swap_cnt = 0;
    105 	if (n < 7) {
    106 		for (pm = (char *)a + es; pm < (char *) a + n * es; pm += es)
    107 			for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
    108 			     pl -= es)
    109 				swap(pl, pl - es);
    110 		return;
    111 	}
    112 	pm = (char *)a + (n / 2) * es;
    113 	if (n > 7) {
    114 		pl = (char *)a;
    115 		pn = (char *)a + (n - 1) * es;
    116 		if (n > 40) {
    117 			d = (n / 8) * es;
    118 			pl = med3(pl, pl + d, pl + 2 * d, cmp);
    119 			pm = med3(pm - d, pm, pm + d, cmp);
    120 			pn = med3(pn - 2 * d, pn - d, pn, cmp);
    121 		}
    122 		pm = med3(pl, pm, pn, cmp);
    123 	}
    124 	swap(a, pm);
    125 	pa = pb = (char *)a + es;
    126 
    127 	pc = pd = (char *)a + (n - 1) * es;
    128 	for (;;) {
    129 		while (pb <= pc && (r = cmp(pb, a)) <= 0) {
    130 			if (r == 0) {
    131 				swap_cnt = 1;
    132 				swap(pa, pb);
    133 				pa += es;
    134 			}
    135 			pb += es;
    136 		}
    137 		while (pb <= pc && (r = cmp(pc, a)) >= 0) {
    138 			if (r == 0) {
    139 				swap_cnt = 1;
    140 				swap(pc, pd);
    141 				pd -= es;
    142 			}
    143 			pc -= es;
    144 		}
    145 		if (pb > pc)
    146 			break;
    147 		swap(pb, pc);
    148 		swap_cnt = 1;
    149 		pb += es;
    150 		pc -= es;
    151 	}
    152 	if (swap_cnt == 0) {  /* Switch to insertion sort */
    153 		for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
    154 			for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; 
    155 			     pl -= es)
    156 				swap(pl, pl - es);
    157 		return;
    158 	}
    159 
    160 	pn = (char *)a + n * es;
    161 	r = min(pa - (char *)a, pb - pa);
    162 	vecswap(a, pb - r, r);
    163 	r = min(pd - pc, pn - pd - es);
    164 	vecswap(pb, pn - r, r);
    165 	if ((r = pb - pa) > es)
    166 		qsort(a, r / es, es, cmp);
    167 	if ((r = pd - pc) > es) { 
    168 		/* Iterate rather than recurse to save stack space */
    169 		a = pn - r;
    170 		n = r / es;
    171 		goto loop;
    172 	}
    173 /*		qsort(pn - r, r / es, es, cmp);*/
    174 }