diff options
author | Franklin Wei <git@fwei.tk> | 2019-05-15 18:16:27 -0400 |
---|---|---|
committer | Franklin Wei <git@fwei.tk> | 2019-05-15 18:16:27 -0400 |
commit | f940276fd9bc38ae34d4119fd1d983171a627400 (patch) | |
tree | 117a191e61c070548b4c55b35f6d1159f98f03f9 /apps/plugins/puzzles/src/sort.c | |
parent | 4ed57276542124a22c26ebb1d307996fc3a7556c (diff) | |
download | rockbox-f940276fd9bc38ae34d4119fd1d983171a627400.tar.gz rockbox-f940276fd9bc38ae34d4119fd1d983171a627400.zip |
puzzles: resync with upstream
This brings the puzzles source to upstream commit e2135d5. (I've made my own
changes on top of that.)
This brings in a couple bugfixes and a new solver for Dominosa.
Change-Id: I11d46b43171787832330a5e2e0d2f353f36f727d
Diffstat (limited to 'apps/plugins/puzzles/src/sort.c')
-rw-r--r-- | apps/plugins/puzzles/src/sort.c | 160 |
1 files changed, 160 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/sort.c b/apps/plugins/puzzles/src/sort.c new file mode 100644 index 0000000000..d1897b6fdf --- /dev/null +++ b/apps/plugins/puzzles/src/sort.c | |||
@@ -0,0 +1,160 @@ | |||
1 | /* | ||
2 | * Implement arraysort() defined in puzzles.h. | ||
3 | * | ||
4 | * Strategy: heapsort. | ||
5 | */ | ||
6 | |||
7 | #include <stddef.h> | ||
8 | #include <string.h> | ||
9 | |||
10 | #include "puzzles.h" | ||
11 | |||
12 | static 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)) | ||
31 | #define SWAP(i,j) memswap(PTR(i), PTR(j), size) | ||
32 | #define CMP(i,j) cmp(PTR(i), PTR(j), ctx) | ||
33 | |||
34 | #define LCHILD(i) (2*(i)+1) | ||
35 | #define RCHILD(i) (2*(i)+2) | ||
36 | #define PARENT(i) (((i)-1)/2) | ||
37 | |||
38 | static void downheap(void *array, size_t nmemb, size_t size, | ||
39 | arraysort_cmpfn_t cmp, void *ctx, size_t i) | ||
40 | { | ||
41 | while (LCHILD(i) < nmemb) { | ||
42 | /* Identify the smallest element out of i and its children. */ | ||
43 | size_t j = i; | ||
44 | if (CMP(j, LCHILD(i)) < 0) | ||
45 | j = LCHILD(i); | ||
46 | if (RCHILD(i) < nmemb && | ||
47 | CMP(j, RCHILD(i)) < 0) | ||
48 | j = RCHILD(i); | ||
49 | |||
50 | if (j == i) | ||
51 | return; /* smallest element is already where it should be */ | ||
52 | |||
53 | SWAP(j, i); | ||
54 | i = j; | ||
55 | } | ||
56 | } | ||
57 | |||
58 | void arraysort_fn(void *array, size_t nmemb, size_t size, | ||
59 | arraysort_cmpfn_t cmp, void *ctx) | ||
60 | { | ||
61 | size_t i; | ||
62 | |||
63 | if (nmemb < 2) | ||
64 | return; /* trivial */ | ||
65 | |||
66 | /* | ||
67 | * Stage 1: build the heap. | ||
68 | * | ||
69 | * Linear-time if we do it by downheaping the elements in | ||
70 | * decreasing order of index, instead of the more obvious approach | ||
71 | * of upheaping in increasing order. (Also, it means we don't need | ||
72 | * the upheap function at all.) | ||
73 | * | ||
74 | * We don't need to downheap anything in the second half of the | ||
75 | * array, because it can't have any children to swap with anyway. | ||
76 | */ | ||
77 | for (i = PARENT(nmemb-1) + 1; i-- > 0 ;) | ||
78 | downheap(array, nmemb, size, cmp, ctx, i); | ||
79 | |||
80 | /* | ||
81 | * Stage 2: dismantle the heap by repeatedly swapping the root | ||
82 | * element (at index 0) into the last position and then | ||
83 | * downheaping the new root. | ||
84 | */ | ||
85 | for (i = nmemb-1; i > 0; i--) { | ||
86 | SWAP(0, i); | ||
87 | downheap(array, i, size, cmp, ctx, 0); | ||
88 | } | ||
89 | } | ||
90 | |||
91 | #ifdef SORT_TEST | ||
92 | |||
93 | #include <stdlib.h> | ||
94 | #include <time.h> | ||
95 | |||
96 | int 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 | |||
103 | int 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 | |||
109 | int 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 */ | ||