1 /*
2  * Copyright © 2005-2020 Rich Felker
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining
5  * a copy of this software and associated documentation files (the
6  * "Software"), to deal in the Software without restriction, including
7  * without limitation the rights to use, copy, modify, merge, publish,
8  * distribute, sublicense, and/or sell copies of the Software, and to
9  * permit persons to whom the Software is furnished to do so, subject to
10  * the following conditions:
11  *
12  * The above copyright notice and this permission notice shall be
13  * included in all copies or substantial portions of the Software.
14  *
15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
18  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
19  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
20  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
21  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22  */
23 #define _GNU_SOURCE
24 #include <stdlib.h>
25 #include <stdint.h>
26 #include <stdio.h>
27 #include <string.h>
28 
scmp(const void * a,const void * b)29 static int scmp(const void *a, const void *b)
30 {
31 	return strcmp(*(char **)a, *(char **)b);
32 }
33 
icmp(const void * a,const void * b)34 static int icmp(const void *a, const void *b)
35 {
36         long d = *(long*)a - *(long*)b;
37 	return (d > 0) ? 1 : (d < 0) ? -1 : 0;
38 }
39 
40 struct three {
41     unsigned char b[3];
42 };
43 
44 #define i3(x)                                                    \
45         { (unsigned char) (((int32_t)(x)) >> 16), (unsigned char) ((x) >> 8), \
46                         (unsigned char) ((x) >> 0) }
47 
tcmp(const void * av,const void * bv)48 static int tcmp(const void *av, const void *bv)
49 {
50     const struct three *a = av, *b = bv;
51     int c;
52     int i;
53 
54     for (i = 0; i < 3; i++) {
55         c = (int) a->b[i] - (int) b->b[i];
56         if (c)
57             return c;
58     }
59     return 0;
60 }
61 
62 #define FAIL(m) do {                                            \
63         printf(__FILE__ ":%d: %s failed\n", __LINE__, m);       \
64         err++;                                                  \
65     } while(0)
66 
67 /* 26 items -- even */
68 static char *s[] = {
69     "Bob", "Alice", "John", "Ceres",
70     "Helga", "Drepper", "Emeralda", "Zoran",
71     "Momo", "Frank", "Pema", "Xavier",
72     "Yeva", "Gedun", "Irina", "Nono",
73     "Wiener", "Vincent", "Tsering", "Karnica",
74     "Lulu", "Quincy", "Osama", "Riley",
75     "Ursula", "Sam"
76 };
77 /* 23 items -- odd, prime */
78 static long n[] = {
79     879045, 394, 99405644, 33434, 232323, 4334, 5454,
80     343, 45545, 454, 324, 22, 34344, 233, 45345, 343,
81     848405, 3434, 3434344, 3535, 93994, 2230404, 4334
82 };
83 
84 static struct three t[] = {
85     i3(879045), i3(394), i3(99405644), i3(33434), i3(232323), i3(4334), i3(5454),
86     i3(343), i3(45545), i3(454), i3(324), i3(22), i3(34344), i3(233), i3(45345), i3(343),
87     i3(848405), i3(3434), i3(3434344), i3(3535), i3(93994), i3(2230404), i3(4334)
88 };
89 
test_qsort(void)90 int test_qsort(void)
91 {
92 	int i;
93 	int err=0;
94 
95 	qsort(s, sizeof(s)/sizeof(s[0]), sizeof(s[0]), scmp);
96 	for (i=0; i<(int) (sizeof(s)/sizeof(char *)-1); i++) {
97 		if (strcmp(s[i], s[i+1]) > 0) {
98 			FAIL("string sort");
99 			for (i=0; i<(int)(sizeof(s)/sizeof(char *)); i++)
100 				printf("\t%s\n", s[i]);
101 			break;
102 		}
103 	}
104 
105 	qsort(n, sizeof(n)/sizeof(n[0]), sizeof(n[0]), icmp);
106 	for (i=0; i<(int)(sizeof(n)/sizeof(n[0])-1); i++) {
107 		if (n[i] > n[i+1]) {
108 			FAIL("integer sort");
109 			for (i=0; i<(int)(sizeof(n)/sizeof(n[0])); i++)
110 				printf("\t%ld\n", n[i]);
111 			break;
112 		}
113 	}
114 
115         qsort(t, sizeof(t)/sizeof(t[0]), sizeof(t[0]), tcmp);
116 	for (i=0; i<(int)(sizeof(t)/sizeof(t[0])-1); i++) {
117                 if (tcmp(&t[i], &t[i+1]) > 0) {
118 			FAIL("three byte sort");
119 			for (i=0; i<(int)(sizeof(t)/sizeof(t[0])); i++)
120                                 printf("\t0x%02x%02x%02x\n", t[i].b[0], t[i].b[1], t[i].b[2]);
121 			break;
122 		}
123 	}
124 
125 
126 	return err;
127 }
128 
129 #undef qsort
130 #define TEST_NAME qsort
131 #include "testcase.h"
132