1 #include <inttypes.h>
2 #include <stdlib.h>
3 #include <stdio.h>
4 #include <string.h>
5 #include "test.h"
6
scmp(const void * a,const void * b)7 static int scmp(const void *a, const void *b)
8 {
9 return strcmp(*(char **)a, *(char **)b);
10 }
11
icmp(const void * a,const void * b)12 static int icmp(const void *a, const void *b)
13 {
14 return *(int*)a - *(int*)b;
15 }
16
ccmp(const void * a,const void * b)17 static int ccmp(const void *a, const void *b)
18 {
19 return *(char*)a - *(char*)b;
20 }
21
cmp64(const void * a,const void * b)22 static int cmp64(const void *a, const void *b)
23 {
24 const uint64_t *ua = a, *ub = b;
25 return *ua < *ub ? -1 : *ua != *ub;
26 }
27
28 /* 26 items -- even */
29 static const char *s[] = {
30 "Bob", "Alice", "John", "Ceres",
31 "Helga", "Drepper", "Emeralda", "Zoran",
32 "Momo", "Frank", "Pema", "Xavier",
33 "Yeva", "Gedun", "Irina", "Nono",
34 "Wiener", "Vincent", "Tsering", "Karnica",
35 "Lulu", "Quincy", "Osama", "Riley",
36 "Ursula", "Sam"
37 };
38 static const char *s_sorted[] = {
39 "Alice", "Bob", "Ceres", "Drepper",
40 "Emeralda", "Frank", "Gedun", "Helga",
41 "Irina", "John", "Karnica", "Lulu",
42 "Momo", "Nono", "Osama", "Pema",
43 "Quincy", "Riley", "Sam", "Tsering",
44 "Ursula", "Vincent", "Wiener", "Xavier",
45 "Yeva", "Zoran"
46 };
47
48 /* 23 items -- odd, prime */
49 static int n[] = {
50 879045, 394, 99405644, 33434, 232323, 4334, 5454,
51 343, 45545, 454, 324, 22, 34344, 233, 45345, 343,
52 848405, 3434, 3434344, 3535, 93994, 2230404, 4334
53 };
54 static int n_sorted[] = {
55 22, 233, 324, 343, 343, 394, 454, 3434,
56 3535, 4334, 4334, 5454, 33434, 34344, 45345, 45545,
57 93994, 232323, 848405, 879045, 2230404, 3434344, 99405644
58 };
59
str_test(const char ** a,const char ** a_sorted,int len)60 static void str_test(const char **a, const char **a_sorted, int len)
61 {
62 int i;
63 qsort(a, len, sizeof *a, scmp);
64 for (i=0; i<len; i++) {
65 if (strcmp(a[i], a_sorted[i]) != 0) {
66 t_error("string sort failed at index %d\n", i);
67 t_printf("\ti\tgot\twant\n");
68 for (i=0; i<len; i++)
69 t_printf("\t%d\t%s\t%s\n", i, a[i], a_sorted[i]);
70 break;
71 }
72 }
73 }
74
int_test(int * a,int * a_sorted,int len)75 static void int_test(int *a, int *a_sorted, int len)
76 {
77 int i;
78 qsort(a, len, sizeof *a, icmp);
79 for (i=0; i<len; i++) {
80 if (a[i] != a_sorted[i]) {
81 t_error("integer sort failed at index %d\n", i);
82 t_printf("\ti\tgot\twant\n");
83 for (i=0; i<len; i++)
84 t_printf("\t%d\t%d\t%d\n", i, a[i], a_sorted[i]);
85 break;
86 }
87 }
88 }
89
uint64_gen(uint64_t * p,uint64_t * p_sorted,int n)90 static void uint64_gen(uint64_t *p, uint64_t *p_sorted, int n)
91 {
92 int i;
93 uint64_t r = 0;
94 t_randseed(n);
95 for (i = 0; i < n; i++) {
96 r += t_randn(20);
97 p[i] = r;
98 }
99 memcpy(p_sorted, p, n * sizeof *p);
100 t_shuffle(p, n);
101 }
102
uint64_test(uint64_t * a,uint64_t * a_sorted,int len)103 static void uint64_test(uint64_t *a, uint64_t *a_sorted, int len)
104 {
105 int i;
106 qsort(a, len, sizeof *a, cmp64);
107 for (i=0; i<len; i++) {
108 if (a[i] != a_sorted[i]) {
109 t_error("uint64 sort failed at index %d\n", i);
110 t_printf("\ti\tgot\twant\n");
111 for (i=0; i<len; i++)
112 t_printf("\t%d\t%" PRIu64 "\t%" PRIu64 "\n", i, a[i], a_sorted[i]);
113 break;
114 }
115 }
116 }
117
118 #define T(a, a_sorted) do { \
119 char p[] = a; \
120 qsort(p, sizeof p - 1, 1, ccmp); \
121 if (memcmp(p, a_sorted, sizeof p) != 0) { \
122 t_error("character sort failed\n"); \
123 t_printf("\tgot: \"%s\"\n", p); \
124 t_printf("\twant: \"%s\"\n", a_sorted); \
125 } \
126 } while(0)
127
char_test(void)128 static void char_test(void)
129 {
130 T("", "");
131 T("1", "1");
132 T("11", "11");
133 T("12", "12");
134 T("21", "12");
135 T("111", "111");
136 T("211", "112");
137 T("121", "112");
138 T("112", "112");
139 T("221", "122");
140 T("212", "122");
141 T("122", "122");
142 T("123", "123");
143 T("132", "123");
144 T("213", "123");
145 T("231", "123");
146 T("321", "123");
147 T("312", "123");
148 T("1423", "1234");
149 T("51342", "12345");
150 T("261435", "123456");
151 T("4517263", "1234567");
152 T("37245618", "12345678");
153 T("812436597", "123456789");
154 T("987654321", "123456789");
155 T("321321321", "111222333");
156 T("49735862185236174", "11223344556677889");
157 }
158
main(void)159 int main(void)
160 {
161 int i;
162
163 str_test(s, s_sorted, sizeof s/sizeof*s);
164 int_test(n, n_sorted, sizeof n/sizeof*n);
165 char_test();
166 for (i = 1023; i<=1026; i++) {
167 uint64_t p[1026], p_sorted[1026];
168 uint64_gen(p, p_sorted, i);
169 uint64_test(p, p_sorted, i);
170 }
171 return t_status;
172 }
173