summaryrefslogtreecommitdiff
path: root/apps/plugins/puzzles/src/sort.c
diff options
context:
space:
mode:
Diffstat (limited to 'apps/plugins/puzzles/src/sort.c')
-rw-r--r--apps/plugins/puzzles/src/sort.c91
1 files changed, 1 insertions, 90 deletions
diff --git a/apps/plugins/puzzles/src/sort.c b/apps/plugins/puzzles/src/sort.c
index d1897b6fdf..e82f4ec6dc 100644
--- a/apps/plugins/puzzles/src/sort.c
+++ b/apps/plugins/puzzles/src/sort.c
@@ -9,26 +9,8 @@
9 9
10#include "puzzles.h" 10#include "puzzles.h"
11 11
12static void memswap(void *av, void *bv, size_t size)
13{
14 char t[4096];
15 char *a = (char *)av, *b = (char *)bv;
16
17 while (size > 0) {
18 size_t thissize = size < sizeof(t) ? size : sizeof(t);
19
20 memcpy(t, a, thissize);
21 memcpy(a, b, thissize);
22 memcpy(b, t, thissize);
23
24 size -= thissize;
25 a += thissize;
26 b += thissize;
27 }
28}
29
30#define PTR(i) ((char *)array + size * (i)) 12#define PTR(i) ((char *)array + size * (i))
31#define SWAP(i,j) memswap(PTR(i), PTR(j), size) 13#define SWAP(i,j) swap_regions(PTR(i), PTR(j), size)
32#define CMP(i,j) cmp(PTR(i), PTR(j), ctx) 14#define CMP(i,j) cmp(PTR(i), PTR(j), ctx)
33 15
34#define LCHILD(i) (2*(i)+1) 16#define LCHILD(i) (2*(i)+1)
@@ -87,74 +69,3 @@ void arraysort_fn(void *array, size_t nmemb, size_t size,
87 downheap(array, i, size, cmp, ctx, 0); 69 downheap(array, i, size, cmp, ctx, 0);
88 } 70 }
89} 71}
90
91#ifdef SORT_TEST
92
93#include <stdlib.h>
94#include <time.h>
95
96int testcmp(const void *av, const void *bv, void *ctx)
97{
98 int a = *(const int *)av, b = *(const int *)bv;
99 const int *keys = (const int *)ctx;
100 return keys[a] < keys[b] ? -1 : keys[a] > keys[b] ? +1 : 0;
101}
102
103int resetcmp(const void *av, const void *bv)
104{
105 int a = *(const int *)av, b = *(const int *)bv;
106 return a < b ? -1 : a > b ? +1 : 0;
107}
108
109int main(int argc, char **argv)
110{
111 typedef int Array[3723];
112 Array data, keys;
113 int iteration;
114 unsigned seed;
115
116 seed = (argc > 1 ? strtoul(argv[1], NULL, 0) : time(NULL));
117 printf("Random seed = %u\n", seed);
118 srand(seed);
119
120 for (iteration = 0; iteration < 10000; iteration++) {
121 int j;
122 const char *fail = NULL;
123
124 for (j = 0; j < lenof(data); j++) {
125 data[j] = j;
126 keys[j] = rand();
127 }
128
129 arraysort(data, lenof(data), testcmp, keys);
130
131 for (j = 1; j < lenof(data); j++) {
132 if (keys[data[j]] < keys[data[j-1]])
133 fail = "output misordered";
134 }
135 if (!fail) {
136 Array reset;
137 memcpy(reset, data, sizeof(data));
138 qsort(reset, lenof(reset), sizeof(*reset), resetcmp);
139 for (j = 0; j < lenof(reset); j++)
140 if (reset[j] != j)
141 fail = "output not permuted";
142 }
143
144 if (fail) {
145 printf("Failed at iteration %d: %s\n", iteration, fail);
146 printf("Key values:\n");
147 for (j = 0; j < lenof(keys); j++)
148 printf(" [%2d] %10d\n", j, keys[j]);
149 printf("Output sorted order:\n");
150 for (j = 0; j < lenof(data); j++)
151 printf(" [%2d] %10d\n", data[j], keys[data[j]]);
152 return 1;
153 }
154 }
155
156 printf("OK\n");
157 return 0;
158}
159
160#endif /* SORT_TEST */