xref: /openbmc/u-boot/lib/qsort.c (revision e76cd5d4)
1 /*
2  * Code adapted from uClibc-0.9.30.3
3  *
4  * It is therefore covered by the GNU LESSER GENERAL PUBLIC LICENSE
5  * Version 2.1, February 1999
6  *
7  * Wolfgang Denk <wd@denx.de>
8  */
9 
10 /* This code is derived from a public domain shell sort routine by
11  * Ray Gardner and found in Bob Stout's snippets collection.  The
12  * original code is included below in an #if 0/#endif block.
13  *
14  * I modified it to avoid the possibility of overflow in the wgap
15  * calculation, as well as to reduce the generated code size with
16  * bcc and gcc. */
17 
18 #include <linux/types.h>
19 #include <common.h>
20 #include <exports.h>
21 
22 void qsort(void  *base,
23 	   size_t nel,
24 	   size_t width,
25 	   int (*comp)(const void *, const void *))
26 {
27 	size_t wgap, i, j, k;
28 	char tmp;
29 
30 	if ((nel > 1) && (width > 0)) {
31 		assert(nel <= ((size_t)(-1)) / width); /* check for overflow */
32 		wgap = 0;
33 		do {
34 			wgap = 3 * wgap + 1;
35 		} while (wgap < (nel-1)/3);
36 		/* From the above, we know that either wgap == 1 < nel or */
37 		/* ((wgap-1)/3 < (int) ((nel-1)/3) <= (nel-1)/3 ==> wgap <  nel. */
38 		wgap *= width;			/* So this can not overflow if wnel doesn't. */
39 		nel *= width;			/* Convert nel to 'wnel' */
40 		do {
41 			i = wgap;
42 			do {
43 				j = i;
44 				do {
45 					register char *a;
46 					register char *b;
47 
48 					j -= wgap;
49 					a = j + ((char *)base);
50 					b = a + wgap;
51 					if ((*comp)(a, b) <= 0) {
52 						break;
53 					}
54 					k = width;
55 					do {
56 						tmp = *a;
57 						*a++ = *b;
58 						*b++ = tmp;
59 					} while (--k);
60 				} while (j >= wgap);
61 				i += width;
62 			} while (i < nel);
63 			wgap = (wgap - width)/3;
64 		} while (wgap);
65 	}
66 }
67 
68 int strcmp_compar(const void *p1, const void *p2)
69 {
70 	return strcmp(*(const char **)p1, *(const char **)p2);
71 }
72