1#include <inttypes.h>
2#include <stdlib.h>
3#include <stdio.h>
4#include <string.h>
5#include "test.h"
6
7static int scmp(const void *a, const void *b)
8{
9	return strcmp(*(char **)a, *(char **)b);
10}
11
12static int icmp(const void *a, const void *b)
13{
14	return *(int*)a - *(int*)b;
15}
16
17static int ccmp(const void *a, const void *b)
18{
19	return *(char*)a - *(char*)b;
20}
21
22static 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 */
29static 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};
38static 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 */
49static 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};
54static 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
60static 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
75static 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
90static 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
103static 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
128static 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
159int 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