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