1 /****************************************************************
2 Copyright (C) 1997 Lucent Technologies
3 All Rights Reserved
4
5 Permission to use, copy, modify, and distribute this software and
6 its documentation for any purpose and without fee is hereby
7 granted, provided that the above copyright notice appear in all
8 copies and that both that the copyright notice and this
9 permission notice and warranty disclaimer appear in supporting
10 documentation, and that the name of Lucent or any of its entities
11 not be used in advertising or publicity pertaining to
12 distribution of the software without specific, written prior
13 permission.
14
15 LUCENT DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
16 INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
17 IN NO EVENT SHALL LUCENT OR ANY OF ITS ENTITIES BE LIABLE FOR ANY
18 SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
19 WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER
20 IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
21 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
22 THIS SOFTWARE.
23 ****************************************************************/
24
25 /* qsortv -- qsort with an extra argument v (of type void*) that is
26 passed to the comparison function, to facilitate complicated
27 comparisons in environments with multiple threads.
28 Derived (by dmg) from code by Jon Bentley and Doug McIlroy, with
29 modifications to avoid comparing an element to itself.
30 See "Engineering a Sort Function" by Jon L. Bentley and M. Douglas
31 McIlroy, Software--Practice and Experience 23 (11), Nov. 1993,
32 pp. 1249-1265.
33 */
34
35 #ifdef KR_headers
36 typedef int cmpfunc();
37 typedef unsigned int size_t;
38 #else
39 typedef int cmpfunc(const void *, const void*, void*);
40 #include "stddef.h"
41 #ifdef __cplusplus
42 extern "C" void qsortv(void*, size_t, size_t, cmpfunc*, void*);
43 #endif
44 #endif
45
46 #define SWAPINIT(a, es) swaptype = \
47 ((char*)a-(char*)0 | es) % sizeof(long) ? 2 : es > sizeof(long) ? 1 : 0;
48 #define swapcode(TYPE, parmi, parmj, n) { \
49 register TYPE *pi = (TYPE *) (parmi); \
50 register TYPE *pj = (TYPE *) (parmj); \
51 do { \
52 register TYPE t = *pi; \
53 *pi++ = *pj; \
54 *pj++ = t; \
55 } while ((n -= sizeof(TYPE)) > 0); \
56 }
57
58 static void
59 #ifdef KR_headers
swapfunc(a,b,n,swaptype)60 swapfunc(a, b, n, swaptype) char *a, *b; size_t n; int swaptype;
61 #else
62 swapfunc(char *a, char *b, size_t n, int swaptype)
63 #endif
64 { if (swaptype <= 1) swapcode(long, a, b, n)
65 else swapcode(char, a, b, n)
66 }
67 #define swap(a, b) \
68 if (swaptype == 0) { \
69 t = *(long*)(a); \
70 *(long*)(a) = *(long*)(b); \
71 *(long*)(b) = t; \
72 } else \
73 swapfunc(a, b, es, swaptype)
74
75 #define vecswap(a, b, n) if (n > 0) swapfunc(a, b, n, swaptype)
76
77 #define min(x, y) ((x)<=(y) ? (x) : (y))
78
79 static char *
80 #ifdef KR_headers
med3(a,b,c,cmp,v)81 med3(a, b, c, cmp, v) char *a, *b, *c; cmpfunc *cmp; char *v;
82 #else
83 med3(char *a, char *b, char *c, cmpfunc *cmp, void *v)
84 #endif
85 { return (*cmp)(a,b,v) < 0 ?
86 ((*cmp)(b,c,v) < 0 ? b : (*cmp)(a,c,v) < 0 ? c : a)
87 : ((*cmp)(b,c,v) > 0 ? b : (*cmp)(a,c,v) > 0 ? c : a);
88 }
89
90 void
91 #ifdef KR_headers
qsortv(a,n,es,cmp,v)92 qsortv(a, n, es, cmp, v) char *a; size_t n; size_t es; cmpfunc *cmp; char *v;
93 #else
94 #define a ((char*)a0)
95 qsortv(void *a0, size_t n, size_t es, cmpfunc *cmp, void *v)
96 #endif
97 {
98 char *ae, *pa, *pb, *pc, *pd, *pl, *pm, *pn;
99 int r, swaptype;
100 size_t s;
101 long t;
102
103 SWAPINIT(a, es);
104 if (n < 7) { /* Insertion sort on smallest arrays */
105 for (pm = a + es, ae = a + n*es; pm < ae; pm += es)
106 for (pl = pm; pl > a && (*cmp)(pl-es, pl, v) > 0; pl -= es)
107 swap(pl, pl-es);
108 return;
109 }
110 pm = a + (n/2)*es; /* Small arrays, middle element */
111 if (n > 7) {
112 pl = a;
113 pn = a + (n-1)*es;
114 if (n > 40) { /* Big arrays, pseudomedian of 9 */
115 s = (n/8)*es;
116 pl = med3(pl, pl+s, pl+2*s, cmp, v);
117 pm = med3(pm-s, pm, pm+s, cmp, v);
118 pn = med3(pn-2*s, pn-s, pn, cmp, v);
119 }
120 pm = med3(pl, pm, pn, cmp, v); /* Mid-size, med of 3 */
121 }
122 pa = pb = a;
123 pc = pd = a + (n-1)*es;
124 for (;;) {
125 for ( ; pb <= pc; pb += es) {
126 if (pb != pm)
127 if ((r = (*cmp)(pb, pm, v)) > 0) break;
128 else if (r < 0) continue;
129 swap(pa, pb); pm = pa; pa += es;
130 }
131 for ( ; pb <= pc; pc -= es) {
132 if (pc != pm)
133 if ((r = (*cmp)(pc, pm, v)) < 0) break;
134 else if (r > 0) continue;
135 swap(pc, pd); pm = pd; pd -= es;
136 }
137 if (pb > pc) break;
138 swap(pb, pc);
139 pb += es;
140 pc -= es;
141 }
142 pn = a + n*es;
143 s = min(pa-a, pb-pa ); vecswap(a, pb-s, s);
144 s = min(pd-pc, pn-pd-es); vecswap(pb, pn-s, s);
145 if ((s = pb-pa) > es) qsortv(a, s/es, es, cmp, v);
146 if ((s = pd-pc) > es) qsortv(pn-s, s/es, es, cmp, v);
147 }
148