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