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