38 #if defined(LIBC_SCCS) && !defined(lint)
39 static char sccsid[] =
"@(#)merge.c 8.2 (Berkeley) 2/14/94";
64 #define ISIZE sizeof(int)
65 #define PSIZE sizeof(unsigned char *)
66 #define ICOPY_LIST(src, dst, last) \
68 *(int*)dst = *(int*)src, src += ISIZE, dst += ISIZE; \
70 #define ICOPY_ELT(src, dst, i) \
72 *(int*) dst = *(int*) src, src += ISIZE, dst += ISIZE; \
75 #define CCOPY_LIST(src, dst, last) \
79 #define CCOPY_ELT(src, dst, i) \
90 #define EVAL(p) (unsigned char **) \
91 ((unsigned char *)0 + \
92 (((unsigned char *)p + PSIZE - 1 - (unsigned char *) 0) & ~(PSIZE - 1)))
94 #define swap(a, b) { \
98 tmp = *a; *a++ = *s; *s++ = tmp; \
102 #define reverse(bot, top) { \
107 tmp = *bot; *bot++ = *s; *s++ = tmp; \
119 int (*cmp) (
const void *,
const void *))
122 u_char *ai, *
s, *
t, *
u, tmp;
125 for (ai = a+size; --n >= 1; ai +=
size)
126 for (t = ai; t > a; t -=
size) {
141 setup(
unsigned char *list1,
unsigned char *list2,
142 size_t n,
size_t size,
int (*cmp) (
const void *,
const void *))
145 int i, length, size2, sense;
146 unsigned char *f1, *f2, *
s, *l2, *last, *p2, tmp;
151 *
EVAL(list2) = (
unsigned char*) list2 + n*size;
158 i = (
int)(4 + (n & 1));
160 last = list1 + size * (n -
i);
161 *
EVAL(list2 + (last - list1)) = list2 + n *
size;
166 sense = (cmp(f1, f1 + size) > 0);
167 for (; f1 < last; sense = !sense) {
170 for (f2 = f1 + size2; f2 < last; f2 += size2) {
171 if ((cmp(f2, f2+ size) > 0) != sense)
177 p2 = *
EVAL(p2) = f1 + size2 - list1 + list2;
179 swap (f1, f1 + size);
180 }
while ((f1 += size2) < f2);
183 for (f2 = f1 + size2; f2 < l2; f2 += size2) {
184 if ((cmp(f2-size, f2) > 0) != sense) {
185 p2 = *
EVAL(p2) = f2 - list1 + list2;
194 if (f2 < last || cmp(f2 - size, f2) > 0)
195 p2 = *
EVAL(p2) = f2 - list1 + list2;
201 for (f1 = list1, p2 = list2; f1 < last; f1 += size2) {
202 p2 = *
EVAL(p2) = p2 + size2;
203 if (cmp (f1, f1 + size) > 0)
214 int (*cmp) (
const void *,
const void *))
216 register int i, sense;
218 register unsigned char *f1, *f2, *
t, *
b, *
q, *l1, *l2;
220 register unsigned char *tp2;
222 unsigned char *list2;
224 unsigned char *list1;
225 unsigned char *p2, *
p, *last, **p1;
227 if (size <
PSIZE / 2) {
240 if (!(size %
ISIZE) && !(((
char *)base - (
char *)0) % ISIZE))
243 if ((list2 = (
unsigned char *) malloc(nmemb * size +
PSIZE)) ==
NULL)
246 list1 = (
unsigned char *) base;
247 setup(list1, list2, nmemb, size, cmp);
248 last = list2 + nmemb *
size;
250 while (*
EVAL(list2) != last) {
253 for (tp2 = p2 = list2; p2 != last; p1 =
EVAL(l2)) {
256 f2 = l1 = list1 + (p2 - list2);
259 l2 = list1 + (p2 - list2);
260 while (f1 < l1 && f2 < l2) {
261 if ((*cmp)(f1, f2) <= 0) {
271 while ((b += size) < t && cmp(q, b) >sense)
278 EXPONENTIAL:
for (i = (
int)
size; ; i <<= 1)
279 if ((p = (b + i)) >=
t) {
280 if ((p = t - size) > b &&
281 (*cmp)(
q,
p) <= sense)
286 }
else if ((*cmp)(
q,
p) <= sense) {
296 if ((*cmp)(
q, p = b +
i) <= sense)
302 FASTCASE:
while (i > (
int)
size)
304 p = b + (i >>= 1)) <= sense)
336 }
else if (f1 < l1) {
349 last = list2 + nmemb*
size;
352 memmove(list2, list1, nmemb*size);
#define reverse(bot, top)
static void insertionsort(unsigned char *a, size_t n, size_t size, int(*cmp)(const void *, const void *))
#define ICOPY_ELT(src, dst, i)
static void setup(unsigned char *list1, unsigned char *list2, size_t n, size_t size, int(*cmp)(const void *, const void *))
#define CCOPY_LIST(src, dst, last)
int rpm_mergesort(void *base, size_t nmemb, size_t size, int(*cmp)(const void *, const void *))
Mergesort, same arguments as qsort(2).
#define ICOPY_LIST(src, dst, last)
int
Save source and expand field into target.
Access RPM indices using Berkeley DB interface(s).
#define CCOPY_ELT(src, dst, i)