Switch to C++
[openmx:openmx.git] / src / merge.cpp
1 /*-
2  * Copyright (c) 1992, 1993
3  *      The Regents of the University of California.  All rights reserved.
4  *
5  * This code is derived from software contributed to Berkeley by
6  * Peter McIlroy.
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  * 4. Neither the name of the University nor the names of its contributors
17  *    may be used to endorse or promote products derived from this software
18  *    without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30  * SUCH DAMAGE.
31  */
32
33 #if defined(LIBC_SCCS) && !defined(lint)
34 static char sccsid[] = "@(#)merge.c     8.2 (Berkeley) 2/14/94";
35 #endif /* LIBC_SCCS and not lint */
36 //#include <sys/cdefs.h>
37 //__FBSDID("$FreeBSD: src/lib/libc/stdlib/merge.c,v 1.8.12.1 2010/02/10 00:26:20 kensmith Exp $");
38
39 /*
40  * Hybrid exponential search/linear search merge sort with hybrid
41  * natural/pairwise first pass.  Requires about .3% more comparisons
42  * for random data than LSMS with pairwise first pass alone.
43  * It works for objects as small as two bytes.
44  */
45
46 #define NATURAL
47 #define THRESHOLD 16    /* Best choice for natural merge cut-off. */
48
49 /* #define NATURAL to get hybrid natural merge.
50  * (The default is pairwise merging.)
51  */
52
53 #include <sys/types.h>
54
55 #include <errno.h>
56 #include <stdlib.h>
57 #include <string.h>
58 #include "merge.h"
59
60 static void setup(unsigned char *, unsigned char *, size_t, size_t, mergesort_cmp_t, void *);
61 static void insertionsort(unsigned char *, size_t, size_t, mergesort_cmp_t, void *);
62
63 #define ISIZE sizeof(int)
64 #define PSIZE sizeof(unsigned char *)
65 #define ICOPY_LIST(src, dst, last)                              \
66         do                                                      \
67         *(int*)dst = *(int*)src, src += ISIZE, dst += ISIZE;    \
68         while(src < last)
69 #define ICOPY_ELT(src, dst, i)                                  \
70         do                                                      \
71         *(int*) dst = *(int*) src, src += ISIZE, dst += ISIZE;  \
72         while (i -= ISIZE)
73
74 #define CCOPY_LIST(src, dst, last)              \
75         do                                      \
76                 *dst++ = *src++;                \
77         while (src < last)
78 #define CCOPY_ELT(src, dst, i)                  \
79         do                                      \
80                 *dst++ = *src++;                \
81         while (i -= 1)
82
83 /*
84  * Find the next possible pointer head.  (Trickery for forcing an array
85  * to do double duty as a linked list when objects do not align with word
86  * boundaries.
87  */
88 /* Assumption: PSIZE is a power of 2. */
89 #define EVAL(p) (unsigned char **)                                              \
90         ((unsigned char *)0 +                                                   \
91             (((unsigned char *)p + PSIZE - 1 - (unsigned char *) 0) & ~(PSIZE - 1)))
92
93 /*
94  * Arguments are as for qsort.
95  */
96 int
97 freebsd_mergesort(void *base, size_t nmemb, size_t size, mergesort_cmp_t cmp, void *userdata)
98 {
99         size_t i;
100         int sense;
101         int big, iflag;
102         unsigned char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2;
103         unsigned char *list2, *list1, *p2, *p, *last, **p1;
104
105         if (size < PSIZE / 2) {         /* Pointers must fit into 2 * size. */
106                 errno = EINVAL;
107                 return (-1);
108         }
109
110         if (nmemb == 0)
111                 return (0);
112
113         /*
114          * XXX
115          * Stupid subtraction for the Cray.
116          */
117         iflag = 0;
118         if (!(size % ISIZE) && !(((char *)base - (char *)0) % ISIZE))
119                 iflag = 1;
120
121         if ((list2 = (unsigned char*) malloc(nmemb * size + PSIZE)) == NULL)
122                 return (-1);
123
124         list1 = (unsigned char*) base;
125         setup(list1, list2, nmemb, size, cmp, userdata);
126         last = list2 + nmemb * size;
127         i = big = 0;
128         while (*EVAL(list2) != last) {
129             l2 = list1;
130             p1 = EVAL(list1);
131             for (tp2 = p2 = list2; p2 != last; p1 = EVAL(l2)) {
132                 p2 = *EVAL(p2);
133                 f1 = l2;
134                 f2 = l1 = list1 + (p2 - list2);
135                 if (p2 != last)
136                         p2 = *EVAL(p2);
137                 l2 = list1 + (p2 - list2);
138                 while (f1 < l1 && f2 < l2) {
139                         if ((*cmp)(f1, f2, userdata) <= 0) {
140                                 q = f2;
141                                 b = f1, t = l1;
142                                 sense = -1;
143                         } else {
144                                 q = f1;
145                                 b = f2, t = l2;
146                                 sense = 0;
147                         }
148                         if (!big) {     /* here i = 0 */
149                                 while ((b += size) < t && cmp(q, b, userdata) >sense)
150                                         if (++i == 6) {
151                                                 big = 1;
152                                                 goto EXPONENTIAL;
153                                         }
154                         } else {
155 EXPONENTIAL:                    for (i = size; ; i <<= 1)
156                                         if ((p = (b + i)) >= t) {
157                                                 if ((p = t - size) > b &&
158                                                     (*cmp)(q, p, userdata) <= sense)
159                                                         t = p;
160                                                 else
161                                                         b = p;
162                                                 break;
163                                         } else if ((*cmp)(q, p, userdata) <= sense) {
164                                                 t = p;
165                                                 if (i == size)
166                                                         big = 0;
167                                                 goto FASTCASE;
168                                         } else
169                                                 b = p;
170                                 while (t > b+size) {
171                                         i = (((t - b) / size) >> 1) * size;
172                                         if ((*cmp)(q, p = b + i, userdata) <= sense)
173                                                 t = p;
174                                         else
175                                                 b = p;
176                                 }
177                                 goto COPY;
178 FASTCASE:                       while (i > size)
179                                         if ((*cmp)(q,
180                                                    p = b + (i >>= 1), userdata) <= sense)
181                                                 t = p;
182                                         else
183                                                 b = p;
184 COPY:                           b = t;
185                         }
186                         i = size;
187                         if (q == f1) {
188                                 if (iflag) {
189                                         ICOPY_LIST(f2, tp2, b);
190                                         ICOPY_ELT(f1, tp2, i);
191                                 } else {
192                                         CCOPY_LIST(f2, tp2, b);
193                                         CCOPY_ELT(f1, tp2, i);
194                                 }
195                         } else {
196                                 if (iflag) {
197                                         ICOPY_LIST(f1, tp2, b);
198                                         ICOPY_ELT(f2, tp2, i);
199                                 } else {
200                                         CCOPY_LIST(f1, tp2, b);
201                                         CCOPY_ELT(f2, tp2, i);
202                                 }
203                         }
204                 }
205                 if (f2 < l2) {
206                         if (iflag)
207                                 ICOPY_LIST(f2, tp2, l2);
208                         else
209                                 CCOPY_LIST(f2, tp2, l2);
210                 } else if (f1 < l1) {
211                         if (iflag)
212                                 ICOPY_LIST(f1, tp2, l1);
213                         else
214                                 CCOPY_LIST(f1, tp2, l1);
215                 }
216                 *p1 = l2;
217             }
218             tp2 = list1;        /* swap list1, list2 */
219             list1 = list2;
220             list2 = tp2;
221             last = list2 + nmemb*size;
222         }
223         if (base == list2) {
224                 memmove(list2, list1, nmemb*size);
225                 list2 = list1;
226         }
227         free(list2);
228         return (0);
229 }
230
231 #define swap(a, b) {                                    \
232                 s = b;                                  \
233                 i = size;                               \
234                 do {                                    \
235                         tmp = *a; *a++ = *s; *s++ = tmp; \
236                 } while (--i);                          \
237                 a -= size;                              \
238         }
239 #define reverse(bot, top) {                             \
240         s = top;                                        \
241         do {                                            \
242                 i = size;                               \
243                 do {                                    \
244                         tmp = *bot; *bot++ = *s; *s++ = tmp; \
245                 } while (--i);                          \
246                 s -= size2;                             \
247         } while(bot < s);                               \
248 }
249
250 /*
251  * Optional hybrid natural/pairwise first pass.  Eats up list1 in runs of
252  * increasing order, list2 in a corresponding linked list.  Checks for runs
253  * when THRESHOLD/2 pairs compare with same sense.  (Only used when NATURAL
254  * is defined.  Otherwise simple pairwise merging is used.)
255  */
256 void
257 setup(unsigned char *list1, unsigned char *list2, size_t n, size_t size, mergesort_cmp_t cmp, void *userdata)
258 {
259         int i, length, size2, tmp, sense;
260         unsigned char *f1, *f2, *s, *l2, *last, *p2;
261
262         size2 = size*2;
263         if (n <= 5) {
264                 insertionsort(list1, n, size, cmp, userdata);
265                 *EVAL(list2) = (unsigned char*) list2 + n*size;
266                 return;
267         }
268         /*
269          * Avoid running pointers out of bounds; limit n to evens
270          * for simplicity.
271          */
272         i = 4 + (n & 1);
273         insertionsort(list1 + (n - i) * size, i, size, cmp, userdata);
274         last = list1 + size * (n - i);
275         *EVAL(list2 + (last - list1)) = list2 + n * size;
276
277 #ifdef NATURAL
278         p2 = list2;
279         f1 = list1;
280         sense = (cmp(f1, f1 + size, userdata) > 0);
281         for (; f1 < last; sense = !sense) {
282                 length = 2;
283                                         /* Find pairs with same sense. */
284                 for (f2 = f1 + size2; f2 < last; f2 += size2) {
285                         if ((cmp(f2, f2+ size, userdata) > 0) != sense)
286                                 break;
287                         length += 2;
288                 }
289                 if (length < THRESHOLD) {               /* Pairwise merge */
290                         do {
291                                 p2 = *EVAL(p2) = f1 + size2 - list1 + list2;
292                                 if (sense > 0)
293                                         swap (f1, f1 + size);
294                         } while ((f1 += size2) < f2);
295                 } else {                                /* Natural merge */
296                         l2 = f2;
297                         for (f2 = f1 + size2; f2 < l2; f2 += size2) {
298                                 if ((cmp(f2-size, f2, userdata) > 0) != sense) {
299                                         p2 = *EVAL(p2) = f2 - list1 + list2;
300                                         if (sense > 0)
301                                                 reverse(f1, f2-size);
302                                         f1 = f2;
303                                 }
304                         }
305                         if (sense > 0)
306                                 reverse (f1, f2-size);
307                         f1 = f2;
308                         if (f2 < last || cmp(f2 - size, f2, userdata) > 0)
309                                 p2 = *EVAL(p2) = f2 - list1 + list2;
310                         else
311                                 p2 = *EVAL(p2) = list2 + n*size;
312                 }
313         }
314 #else           /* pairwise merge only. */
315         for (f1 = list1, p2 = list2; f1 < last; f1 += size2) {
316                 p2 = *EVAL(p2) = p2 + size2;
317                 if (cmp (f1, f1 + size) > 0)
318                         swap(f1, f1 + size);
319         }
320 #endif /* NATURAL */
321 }
322
323 /*
324  * This is to avoid out-of-bounds addresses in sorting the
325  * last 4 elements.
326  */
327 static void
328 insertionsort(unsigned char *a, size_t n, size_t size, mergesort_cmp_t cmp, void *userdata)
329 {
330         unsigned char *ai, *s, *t, *u, tmp;
331         int i;
332
333         for (ai = a+size; --n >= 1; ai += size)
334                 for (t = ai; t > a; t -= size) {
335                         u = t - size;
336                         if (cmp(u, t, userdata) <= 0)
337                                 break;
338                         swap(u, t);
339                 }
340 }