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