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