Merge tag 'ti-v2020.07-rc3' of https://gitlab.denx.de/u-boot/custodians/u-boot-ti
[platform/kernel/u-boot.git] / lib / qsort.c
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 <log.h>
19 #include <linux/types.h>
20 #include <common.h>
21 #include <exports.h>
22 #include <sort.h>
23
24 void qsort(void  *base,
25            size_t nel,
26            size_t width,
27            int (*comp)(const void *, const void *))
28 {
29         size_t wgap, i, j, k;
30         char tmp;
31
32         if ((nel > 1) && (width > 0)) {
33                 assert(nel <= ((size_t)(-1)) / width); /* check for overflow */
34                 wgap = 0;
35                 do {
36                         wgap = 3 * wgap + 1;
37                 } while (wgap < (nel-1)/3);
38                 /* From the above, we know that either wgap == 1 < nel or */
39                 /* ((wgap-1)/3 < (int) ((nel-1)/3) <= (nel-1)/3 ==> wgap <  nel. */
40                 wgap *= width;                  /* So this can not overflow if wnel doesn't. */
41                 nel *= width;                   /* Convert nel to 'wnel' */
42                 do {
43                         i = wgap;
44                         do {
45                                 j = i;
46                                 do {
47                                         register char *a;
48                                         register char *b;
49
50                                         j -= wgap;
51                                         a = j + ((char *)base);
52                                         b = a + wgap;
53                                         if ((*comp)(a, b) <= 0) {
54                                                 break;
55                                         }
56                                         k = width;
57                                         do {
58                                                 tmp = *a;
59                                                 *a++ = *b;
60                                                 *b++ = tmp;
61                                         } while (--k);
62                                 } while (j >= wgap);
63                                 i += width;
64                         } while (i < nel);
65                         wgap = (wgap - width)/3;
66                 } while (wgap);
67         }
68 }
69
70 int strcmp_compar(const void *p1, const void *p2)
71 {
72         return strcmp(*(const char **)p1, *(const char **)p2);
73 }