00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #if defined(LIBC_SCCS) && !defined(lint)
00039 static char sccsid[] = "@(#)merge.c 8.2 (Berkeley) 2/14/94";
00040 #endif
00041
00042
00043
00044
00045
00046
00047
00048
00049 #define NATURAL
00050 #define THRESHOLD 16
00051
00052
00053
00054
00055
00056 #include "system.h"
00057
00058 #define ISIZE sizeof(int)
00059 #define PSIZE sizeof(unsigned char *)
00060 #define ICOPY_LIST(src, dst, last) \
00061 do \
00062 *(int*)dst = *(int*)src, src += ISIZE, dst += ISIZE; \
00063 while(src < last)
00064 #define ICOPY_ELT(src, dst, i) \
00065 do \
00066 *(int*) dst = *(int*) src, src += ISIZE, dst += ISIZE; \
00067 while (i -= ISIZE)
00068
00069 #define CCOPY_LIST(src, dst, last) \
00070 do \
00071 *dst++ = *src++; \
00072 while (src < last)
00073 #define CCOPY_ELT(src, dst, i) \
00074 do \
00075 *dst++ = *src++; \
00076 while (i -= 1)
00077
00078
00079
00080
00081
00082
00083
00084 #define EVAL(p) (unsigned char **) \
00085 ((unsigned char *)0 + \
00086 (((unsigned char *)p + PSIZE - 1 - (unsigned char *) 0) & ~(PSIZE - 1)))
00087
00088 #define swap(a, b) { \
00089 s = b; \
00090 i = size; \
00091 do { \
00092 tmp = *a; *a++ = *s; *s++ = tmp; \
00093 } while (--i); \
00094 a -= size; \
00095 }
00096 #define reverse(bot, top) { \
00097 s = top; \
00098 do { \
00099 i = size; \
00100 do { \
00101 tmp = *bot; *bot++ = *s; *s++ = tmp; \
00102 } while (--i); \
00103 s -= size2; \
00104 } while(bot < s); \
00105 }
00106
00107
00108
00109
00110
00111 static void
00112 insertionsort(unsigned char *a, size_t n, size_t size,
00113 int (*cmp) (const void *, const void *))
00114
00115 {
00116 u_char *ai, *s, *t, *u, tmp;
00117 int i;
00118
00119 for (ai = a+size; --n >= 1; ai += size)
00120 for (t = ai; t > a; t -= size) {
00121 u = t - size;
00122 if (cmp(u, t) <= 0)
00123 break;
00124 swap(u, t);
00125 }
00126 }
00127
00128
00129
00130
00131
00132
00133
00134 static void
00135 setup(unsigned char *list1, unsigned char *list2,
00136 size_t n, size_t size, int (*cmp) (const void *, const void *))
00137
00138 {
00139 int i, length, size2, tmp, sense;
00140 unsigned char *f1, *f2, *s, *l2, *last, *p2;
00141
00142 size2 = size*2;
00143 if (n <= 5) {
00144 insertionsort(list1, n, size, cmp);
00145 *EVAL(list2) = (unsigned char*) list2 + n*size;
00146 return;
00147 }
00148
00149
00150
00151
00152 i = 4 + (n & 1);
00153 insertionsort(list1 + (n - i) * size, i, size, cmp);
00154 last = list1 + size * (n - i);
00155 *EVAL(list2 + (last - list1)) = list2 + n * size;
00156
00157 #ifdef NATURAL
00158 p2 = list2;
00159 f1 = list1;
00160 sense = (cmp(f1, f1 + size) > 0);
00161 for (; f1 < last; sense = !sense) {
00162 length = 2;
00163
00164 for (f2 = f1 + size2; f2 < last; f2 += size2) {
00165 if ((cmp(f2, f2+ size) > 0) != sense)
00166 break;
00167 length += 2;
00168 }
00169 if (length < THRESHOLD) {
00170 do {
00171 p2 = *EVAL(p2) = f1 + size2 - list1 + list2;
00172 if (sense > 0)
00173 swap (f1, f1 + size);
00174 } while ((f1 += size2) < f2);
00175 } else {
00176 l2 = f2;
00177 for (f2 = f1 + size2; f2 < l2; f2 += size2) {
00178 if ((cmp(f2-size, f2) > 0) != sense) {
00179 p2 = *EVAL(p2) = f2 - list1 + list2;
00180 if (sense > 0)
00181 reverse(f1, f2-size);
00182 f1 = f2;
00183 }
00184 }
00185 if (sense > 0)
00186 reverse (f1, f2-size);
00187 f1 = f2;
00188 if (f2 < last || cmp(f2 - size, f2) > 0)
00189 p2 = *EVAL(p2) = f2 - list1 + list2;
00190 else
00191 p2 = *EVAL(p2) = list2 + n*size;
00192 }
00193 }
00194 #else
00195 for (f1 = list1, p2 = list2; f1 < last; f1 += size2) {
00196 p2 = *EVAL(p2) = p2 + size2;
00197 if (cmp (f1, f1 + size) > 0)
00198 swap(f1, f1 + size);
00199 }
00200 #endif
00201 }
00202
00203
00204
00205
00206 int
00207 mergesort(void *base, size_t nmemb, size_t size,
00208 int (*cmp) (const void *, const void *))
00209 {
00210 register int i, sense;
00211 int big, iflag;
00212 register unsigned char *f1, *f2, *t, *b, *q, *l1, *l2;
00213
00214 register unsigned char *tp2;
00215
00216 unsigned char *list2;
00217
00218 unsigned char *list1;
00219 unsigned char *p2, *p, *last, **p1;
00220
00221 if (size < PSIZE / 2) {
00222 errno = EINVAL;
00223 return (-1);
00224 }
00225
00226 if (nmemb == 0)
00227 return (0);
00228
00229
00230
00231
00232
00233 iflag = 0;
00234 if (!(size % ISIZE) && !(((char *)base - (char *)0) % ISIZE))
00235 iflag = 1;
00236
00237 if ((list2 = malloc(nmemb * size + PSIZE)) == NULL)
00238 return (-1);
00239
00240 list1 = base;
00241 setup(list1, list2, nmemb, size, cmp);
00242 last = list2 + nmemb * size;
00243 i = big = 0;
00244
00245 while (*EVAL(list2) != last) {
00246 l2 = list1;
00247 p1 = EVAL(list1);
00248 for (tp2 = p2 = list2; p2 != last; p1 = EVAL(l2)) {
00249 p2 = *EVAL(p2);
00250 f1 = l2;
00251 f2 = l1 = list1 + (p2 - list2);
00252 if (p2 != last)
00253 p2 = *EVAL(p2);
00254 l2 = list1 + (p2 - list2);
00255 while (f1 < l1 && f2 < l2) {
00256 if ((*cmp)(f1, f2) <= 0) {
00257 q = f2;
00258 b = f1, t = l1;
00259 sense = -1;
00260 } else {
00261 q = f1;
00262 b = f2, t = l2;
00263 sense = 0;
00264 }
00265 if (!big) {
00266 while ((b += size) < t && cmp(q, b) >sense)
00267 if (++i == 6) {
00268 big = 1;
00269 goto EXPONENTIAL;
00270 }
00271 } else {
00272
00273 EXPONENTIAL: for (i = size; ; i <<= 1)
00274 if ((p = (b + i)) >= t) {
00275 if ((p = t - size) > b &&
00276 (*cmp)(q, p) <= sense)
00277 t = p;
00278 else
00279 b = p;
00280 break;
00281 } else if ((*cmp)(q, p) <= sense) {
00282 t = p;
00283 if (i == size)
00284 big = 0;
00285 goto FASTCASE;
00286 } else
00287 b = p;
00288
00289 while (t > b+size) {
00290 i = (((t - b) / size) >> 1) * size;
00291 if ((*cmp)(q, p = b + i) <= sense)
00292 t = p;
00293 else
00294 b = p;
00295 }
00296 goto COPY;
00297 FASTCASE: while (i > size)
00298 if ((*cmp)(q,
00299 p = b + (i >>= 1)) <= sense)
00300 t = p;
00301 else
00302 b = p;
00303
00304
00305 COPY: b = t;
00306 }
00307 i = size;
00308 if (q == f1) {
00309 if (iflag) {
00310 ICOPY_LIST(f2, tp2, b);
00311 ICOPY_ELT(f1, tp2, i);
00312 } else {
00313 CCOPY_LIST(f2, tp2, b);
00314 CCOPY_ELT(f1, tp2, i);
00315 }
00316 } else {
00317 if (iflag) {
00318 ICOPY_LIST(f1, tp2, b);
00319 ICOPY_ELT(f2, tp2, i);
00320 } else {
00321 CCOPY_LIST(f1, tp2, b);
00322 CCOPY_ELT(f2, tp2, i);
00323 }
00324 }
00325 }
00326 if (f2 < l2) {
00327 if (iflag)
00328 ICOPY_LIST(f2, tp2, l2);
00329 else
00330 CCOPY_LIST(f2, tp2, l2);
00331 } else if (f1 < l1) {
00332 if (iflag)
00333 ICOPY_LIST(f1, tp2, l1);
00334 else
00335 CCOPY_LIST(f1, tp2, l1);
00336 }
00337 *p1 = l2;
00338 }
00339
00340 tp2 = list1;
00341 list1 = list2;
00342 list2 = tp2;
00343
00344 last = list2 + nmemb*size;
00345 }
00346
00347 if (base == list2) {
00348 memmove(list2, list1, nmemb*size);
00349 list2 = list1;
00350 }
00351
00352 free(list2);
00353
00354 return (0);
00355 }
00356