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