xref: /6.0.3/couchstore/src/quicksort.c (revision a12b9ab1)
1 /* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 
3 /*
4  * qsort taken from FreeBSD, slightly modified to match glibc's
5  * argument ordering
6  */
7 
8 /*-
9  * Copyright (c) 1992, 1993
10  *    The Regents of the University of California.  All rights reserved.
11  *
12  * Redistribution and use in source and binary forms, with or without
13  * modification, are permitted provided that the following conditions
14  * are met:
15  * 1. Redistributions of source code must retain the above copyright
16  *    notice, this list of conditions and the following disclaimer.
17  * 2. Redistributions in binary form must reproduce the above copyright
18  *    notice, this list of conditions and the following disclaimer in the
19  *    documentation and/or other materials provided with the distribution.
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 /* $FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.13.2.1.8.1 2010/12/21 17:10:29 kensmith Exp $ */
38 
39 #include <stdlib.h>
40 #include "quicksort.h"
41 
42 typedef struct {
43     sort_cmp_t *func;
44     void       *ctx;
45 } qsort_wrapper;
46 
47 #if(defined __APPLE__ || defined _WIN32)
qsort_cmp_wrap(void * ctx,const void * a,const void * b)48 static int qsort_cmp_wrap(void *ctx, const void *a, const void *b)
49 {
50     qsort_wrapper *wrap = (qsort_wrapper *) ctx;
51     return (*wrap->func)(a, b, wrap->ctx);
52 }
53 
54 #elif(!defined HAVE_QSORT_R)
55 
56 static inline char    *med3(char *, char *, char *, sort_cmp_t *, void *);
57 static inline void     swapfunc(char *, char *, int, int);
58 
59 #define min(a, b)    (a) < (b) ? a : b
60 
61 /*
62  * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
63  */
64 #define swapcode(TYPE, parmi, parmj, n) {         \
65     long i = (n) / sizeof (TYPE);             \
66     TYPE *pi = (TYPE *) (parmi);         \
67     TYPE *pj = (TYPE *) (parmj);         \
68     do {                         \
69         TYPE    t = *pi;        \
70         *pi++ = *pj;                \
71         *pj++ = t;                \
72         } while (--i > 0);                \
73 }
74 
75 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
76     es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
77 
78 static inline void
swapfunc(a,b,n,swaptype)79 swapfunc(a, b, n, swaptype)
80     char *a, *b;
81     int n, swaptype;
82 {
83     if(swaptype <= 1)
84         swapcode(long, a, b, n)
85     else
86         swapcode(char, a, b, n)
87 }
88 
89 #define swap(a, b)                    \
90     if (swaptype == 0) {                \
91         long t = *(long *)(a);            \
92         *(long *)(a) = *(long *)(b);        \
93         *(long *)(b) = t;            \
94     } else                        \
95         swapfunc(a, b, es, swaptype)
96 
97 #define vecswap(a, b, n)     if ((n) > 0) swapfunc(a, b, n, swaptype)
98 
99 #define    CMP(t, x, y) (cmp((x), (y), (t)))
100 
med3(char * a,char * b,char * c,sort_cmp_t * cmp,void * thunk)101 static inline char *med3(char *a, char *b, char *c, sort_cmp_t *cmp, void *thunk)
102 {
103     return CMP(thunk, a, b) < 0 ?
104            (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a ))
105               :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
106 }
107 
qsort_fallback(void * a,size_t n,size_t es,sort_cmp_t * cmp,void * thunk)108 static void qsort_fallback(void *a, size_t n, size_t es, sort_cmp_t *cmp, void *thunk)
109 {
110     char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
111     size_t d, r;
112     int cmp_result;
113     int swaptype;
114 
115 loop:
116     SWAPINIT(a, es);
117     if (n < 7) {
118         for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
119             for (pl = pm;
120                  pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
121                  pl -= es)
122                 swap(pl, pl - es);
123         return;
124     }
125     pm = (char *)a + (n / 2) * es;
126     if (n > 7) {
127         pl = a;
128         pn = (char *)a + (n - 1) * es;
129         if (n > 40) {
130             d = (n / 8) * es;
131             pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
132             pm = med3(pm - d, pm, pm + d, cmp, thunk);
133             pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
134         }
135         pm = med3(pl, pm, pn, cmp, thunk);
136     }
137     swap(a, pm);
138     pa = pb = (char *)a + es;
139 
140     pc = pd = (char *)a + (n - 1) * es;
141     for (;;) {
142         while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) {
143             if (cmp_result == 0) {
144                 swap(pa, pb);
145                 pa += es;
146             }
147             pb += es;
148         }
149         while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) {
150             if (cmp_result == 0) {
151                 swap(pc, pd);
152                 pd -= es;
153             }
154             pc -= es;
155         }
156         if (pb > pc)
157             break;
158         swap(pb, pc);
159         pb += es;
160         pc -= es;
161     }
162 
163     pn = (char *)a + n * es;
164     r = min(pa - (char *)a, pb - pa);
165     vecswap(a, pb - r, r);
166     r = min(pd - pc, pn - pd - es);
167     vecswap(pb, pn - r, r);
168     if ((r = pb - pa) > es)
169         qsort_fallback(a, r / es, es, cmp, thunk);
170     if ((r = pd - pc) > es) {
171         /* Iterate rather than recurse to save stack space */
172         a = pn - r;
173         n = r / es;
174         goto loop;
175     }
176 /*        qsort(pn - r, r / es, es, cmp);*/
177 }
178 
179 #endif
180 
quicksort(void * a,size_t n,size_t es,sort_cmp_t * cmp,void * ctx)181 void quicksort(void *a, size_t n, size_t es, sort_cmp_t *cmp, void *ctx)
182 {
183 #if(defined __APPLE__ || _WIN32)
184     qsort_wrapper wrapper;
185     wrapper.func = cmp;
186     wrapper.ctx = ctx;
187 #endif
188 
189 #if(defined __APPLE__)
190     qsort_r(a, n, es, &wrapper, qsort_cmp_wrap);
191 #elif (defined _WIN32)
192     qsort_s(a, n, es, qsort_cmp_wrap, &wrapper);
193 #elif (defined __linux__ && HAVE_QSORT_R)
194     qsort_r(a, n, es, cmp, ctx);
195 #else
196     qsort_fallback(a, n, es, cmp, ctx);
197 #endif
198 }
199