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 <stdio.h>
26 #include <string.h>
27
scmp(const void * a,const void * b)28 static int scmp(const void *a, const void *b)
29 {
30 return strcmp(*(char **)a, *(char **)b);
31 }
32
icmp(const void * a,const void * b)33 static int icmp(const void *a, const void *b)
34 {
35 return *(int*)a - *(int*)b;
36 }
37
38 struct three {
39 unsigned char b[3];
40 };
41
42 #define i3(x) \
43 { (unsigned char) ((x) >> 16), (unsigned char) ((x) >> 8), \
44 (unsigned char) ((x) >> 0) }
45
tcmp(const void * av,const void * bv)46 static int tcmp(const void *av, const void *bv)
47 {
48 const struct three *a = av, *b = bv;
49 int c;
50 int i;
51
52 for (i = 0; i < 3; i++) {
53 c = (int) a->b[i] - (int) b->b[i];
54 if (c)
55 return c;
56 }
57 return 0;
58 }
59
60 #define FAIL(m) do { \
61 printf(__FILE__ ":%d: %s failed\n", __LINE__, m); \
62 err++; \
63 } while(0)
64
test_qsort(void)65 int test_qsort(void)
66 {
67 int i;
68 int err=0;
69 /* 26 items -- even */
70 char *s[] = {
71 "Bob", "Alice", "John", "Ceres",
72 "Helga", "Drepper", "Emeralda", "Zoran",
73 "Momo", "Frank", "Pema", "Xavier",
74 "Yeva", "Gedun", "Irina", "Nono",
75 "Wiener", "Vincent", "Tsering", "Karnica",
76 "Lulu", "Quincy", "Osama", "Riley",
77 "Ursula", "Sam"
78 };
79 /* 23 items -- odd, prime */
80 int n[] = {
81 879045, 394, 99405644, 33434, 232323, 4334, 5454,
82 343, 45545, 454, 324, 22, 34344, 233, 45345, 343,
83 848405, 3434, 3434344, 3535, 93994, 2230404, 4334
84 };
85
86 struct three t[] = {
87 i3(879045), i3(394), i3(99405644), i3(33434), i3(232323), i3(4334), i3(5454),
88 i3(343), i3(45545), i3(454), i3(324), i3(22), i3(34344), i3(233), i3(45345), i3(343),
89 i3(848405), i3(3434), i3(3434344), i3(3535), i3(93994), i3(2230404), i3(4334)
90 };
91
92 qsort(s, sizeof(s)/sizeof(char *), sizeof(char *), scmp);
93 for (i=0; i<(int) (sizeof(s)/sizeof(char *)-1); i++) {
94 if (strcmp(s[i], s[i+1]) > 0) {
95 FAIL("string sort");
96 for (i=0; i<(int)(sizeof(s)/sizeof(char *)); i++)
97 printf("\t%s\n", s[i]);
98 break;
99 }
100 }
101
102 qsort(n, sizeof(n)/sizeof(int), sizeof(int), icmp);
103 for (i=0; i<(int)(sizeof(n)/sizeof(int)-1); i++) {
104 if (n[i] > n[i+1]) {
105 FAIL("integer sort");
106 for (i=0; i<(int)(sizeof(n)/sizeof(int)); i++)
107 printf("\t%d\n", n[i]);
108 break;
109 }
110 }
111
112 qsort(t, sizeof(t)/sizeof(t[0]), sizeof(t[0]), tcmp);
113 for (i=0; i<(int)(sizeof(t)/sizeof(t[0])-1); i++) {
114 if (tcmp(&t[i], &t[i+1]) > 0) {
115 FAIL("three byte sort");
116 for (i=0; i<(int)(sizeof(t)/sizeof(t[0])); i++)
117 printf("\t0x%02x%02x%02x\n", t[i].b[0], t[i].b[1], t[i].b[2]);
118 break;
119 }
120 }
121
122
123 return err;
124 }
125
126 #undef qsort
127 #define TEST_NAME qsort
128 #include "testcase.h"
129
