aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano@tronto.net>2024-07-18 11:09:50 +0200
committerSebastiano Tronto <sebastiano@tronto.net>2024-07-18 11:09:50 +0200
commit7946c8efc2e2a44a8e78e1263c1691ce9f412a09 (patch)
treef04505d6444a59b26c8c2e55311b70bbbf1ce364
parent3d060c348fdfff074a9b902d56f539664789d831 (diff)
downloadnissy-core-7946c8efc2e2a44a8e78e1263c1691ce9f412a09.tar.gz
nissy-core-7946c8efc2e2a44a8e78e1263c1691ce9f412a09.zip
Converted set to map
Diffstat
-rw-r--r--TODO.txt34
-rw-r--r--src/solve_h48.h180
-rw-r--r--src/utils.h2
-rw-r--r--test/112_h48map/00_small.in11
-rw-r--r--test/112_h48map/00_small.out3
-rw-r--r--test/112_h48map/01_large.in (renamed from test/112_h48set/01_large.in)150
-rw-r--r--test/112_h48map/01_large.out83
-rw-r--r--test/112_h48map/h48map_tests.c88
-rw-r--r--test/112_h48set/00_small.in6
-rw-r--r--test/112_h48set/00_small.out3
-rw-r--r--test/112_h48set/01_large.out83
-rw-r--r--test/112_h48set/h48set_tests.c64
12 files changed, 483 insertions, 224 deletions
diff --git a/TODO.txt b/TODO.txt
index 6175672..00b85c0 100644
--- a/TODO.txt
+++ b/TODO.txt
@@ -1,14 +1,38 @@
1Bug in esep table generation 1Bug in esep table generation
2 - Re-do stats 2 - add pre-computation of h48 coordinates at distance <=7?
3 - unit tests (but how do I test? just leave it there to check regressions)
3 - Add long-running test for h0k4 (maybe as a tool?) 4 - Add long-running test for h0k4 (maybe as a tool?)
4 - try DFS for h0 solver 5 - compute all tables for h<11
5 - use dfs for computing big table, save distance %3 until the last two steps, 6 - compute visited up to a fixed depth (7? 8?)
6 then clean the table and double loop over moves to fill the value 7 - compute additional step (if needed) to fill <=base
7 - dfs for tables with h=1 to 10? 8 - brute-force the last 2 steps (only 18 moves + 18*15 move pairs)
9 - compare with known h0 results (from long-running test)
10 - compute table for h=11
11 - is is worth pre-computing stuff?
12 - can it be unified to the other computation, or is it much better
13 to do it ad hoc?
14 - optimize
15 - use cached values for invcoord_esep? check if it is faster
8 16
17(OLD:
9 - Fails for UFRUFU, try command 18 - Fails for UFRUFU, try command
10 ./run solve -solver H48 -options "2;20" -n 1 -M 10 -cube \ 19 ./run solve -solver H48 -options "2;20" -n 1 -M 10 -cube \
11 "$(./run frommoves -moves "UFRUFU")" 20 "$(./run frommoves -moves "UFRUFU")"
21)
22
23table base for k=2 (4 most common values start at)
24 0 8
25 1 8
26 2 8
27 3 8 or 9 (very close)
28 4 9
29 5 9
30 6 9
31 7 9 or 10 (very close)
32 8 10
33 9 10
34 10 10
35 11 11
12 36
13Solver 37Solver
14 - cleanup h48 solver 38 - cleanup h48 solver
diff --git a/src/solve_h48.h b/src/solve_h48.h
index ed63209..c7cc91c 100644
--- a/src/solve_h48.h
+++ b/src/solve_h48.h
@@ -1,3 +1,7 @@
1#define MAP_UNSET UINT64_C(0xFFFFFFFFFFFFFFFF)
2#define MAP_KEYMASK UINT64_C(0xFFFFFFFFFF)
3#define MAP_KEYSHIFT UINT64_C(40)
4
1#define COCSEP_CLASSES ((size_t)3393) 5#define COCSEP_CLASSES ((size_t)3393)
2#define COCSEP_TABLESIZE ((size_t)_3p7 << (size_t)7) 6#define COCSEP_TABLESIZE ((size_t)_3p7 << (size_t)7)
3#define COCSEP_VISITEDSIZE ((COCSEP_TABLESIZE + (size_t)7) / (size_t)8) 7#define COCSEP_VISITEDSIZE ((COCSEP_TABLESIZE + (size_t)7) / (size_t)8)
@@ -24,11 +28,16 @@
24#define MAX_SOLUTION_LENGTH 20 28#define MAX_SOLUTION_LENGTH 20
25 29
26typedef struct { 30typedef struct {
27 int64_t n; 31 uint64_t n;
28 int64_t capacity; 32 uint64_t capacity;
29 int64_t mod; 33 uint64_t mod;
30 int64_t *table; 34 uint64_t *table;
31} h48set_t; 35} h48map_t;
36
37typedef struct {
38 uint64_t key;
39 uint64_t val;
40} kvpair_t;
32 41
33typedef struct { 42typedef struct {
34 cube_t cube; 43 cube_t cube;
@@ -41,6 +50,16 @@ typedef struct {
41 cube_t *rep; 50 cube_t *rep;
42} dfsarg_cocsep_t; 51} dfsarg_cocsep_t;
43 52
53/* TODO keep or not? */
54typedef struct {
55 cube_t cube;
56 int8_t nmoves;
57 int8_t depth;
58 uint8_t moves[MAX_SOLUTION_LENGTH];
59 uint32_t *cocsepdata;
60 h48map_t *visited;
61} dfsarg_genh48set_t;
62
44typedef struct { 63typedef struct {
45 uint8_t depth; 64 uint8_t depth;
46 uint32_t *cocsepdata; 65 uint32_t *cocsepdata;
@@ -74,30 +93,31 @@ typedef struct {
74 char *s; 93 char *s;
75} dfsarg_solveh48stats_t; 94} dfsarg_solveh48stats_t;
76 95
77_static void h48set_create(h48set_t *, int64_t, int64_t); 96_static void h48map_create(h48map_t *, uint64_t, uint64_t);
78_static void h48set_clear(h48set_t *); 97_static void h48map_clear(h48map_t *);
79_static void h48set_destroy(h48set_t *); 98_static void h48map_destroy(h48map_t *);
80_static_inline int64_t h48set_lookup(h48set_t *, int64_t); 99_static uint64_t h48map_lookup(h48map_t *, uint64_t);
81_static_inline void h48set_insert(h48set_t *, int64_t); 100_static void h48map_insertmin(h48map_t *, uint64_t, uint64_t);
82_static_inline bool h48set_contains(h48set_t *, int64_t); 101_static uint64_t h48map_value(h48map_t *, uint64_t);
83_static inline int64_t h48set_save(h48set_t *, int64_t *); 102_static kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *);
84 103
85_static_inline int64_t coord_h48(cube_t, const uint32_t *, uint8_t); 104_static_inline int64_t coord_h48(cube_t, const uint32_t *, uint8_t);
86_static_inline int64_t coord_h48_edges(cube_t, int64_t, uint8_t, uint8_t); 105_static_inline int64_t coord_h48_edges(cube_t, int64_t, uint8_t, uint8_t);
87_static_inline cube_t invcoord_h48(int64_t, const cube_t *, uint8_t); 106_static_inline cube_t invcoord_h48(int64_t, const cube_t *, uint8_t);
88 107
108_static_inline bool get_visited(const uint8_t *, int64_t);
109_static_inline void set_visited(uint8_t *, int64_t);
110_static_inline uint8_t get_esep_pval(const uint32_t *, int64_t);
111_static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t);
112
89_static size_t gendata_cocsep(void *, uint64_t *, cube_t *); 113_static size_t gendata_cocsep(void *, uint64_t *, cube_t *);
90_static uint32_t gendata_cocsep_dfs(dfsarg_cocsep_t *); 114_static uint32_t gendata_cocsep_dfs(dfsarg_cocsep_t *);
115_static int64_t gen_h48map_short(uint8_t, const uint32_t *, h48map_t *);
91_static size_t gendata_h48h0k4(void *, uint8_t); 116_static size_t gendata_h48h0k4(void *, uint8_t);
92_static int64_t gendata_h48h0k4_bfs(bfsarg_esep_t *); 117_static int64_t gendata_h48h0k4_bfs(bfsarg_esep_t *);
93_static int64_t gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *); 118_static int64_t gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *);
94_static int64_t gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *); 119_static int64_t gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *);
95 120
96_static_inline bool get_visited(const uint8_t *, int64_t);
97_static_inline void set_visited(uint8_t *, int64_t);
98_static_inline uint8_t get_esep_pval(const uint32_t *, int64_t);
99_static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t);
100
101_static void solve_h48_appendsolution(dfsarg_solveh48_t *); 121_static void solve_h48_appendsolution(dfsarg_solveh48_t *);
102_static_inline int8_t get_h48_cdata(cube_t, uint32_t *, uint32_t *); 122_static_inline int8_t get_h48_cdata(cube_t, uint32_t *, uint32_t *);
103_static_inline int8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint32_t *); 123_static_inline int8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint32_t *);
@@ -109,78 +129,84 @@ _static int64_t solve_h48stats_dfs(dfsarg_solveh48stats_t *);
109_static int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]); 129_static int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]);
110 130
111_static void 131_static void
112h48set_create(h48set_t *set, int64_t capacity, int64_t mod) 132h48map_create(h48map_t *map, uint64_t capacity, uint64_t mod)
113{ 133{
114 set->capacity = capacity; 134 map->capacity = capacity;
115 set->mod = mod; 135 map->mod = mod;
116 136
117 set->table = malloc(set->capacity * sizeof(int64_t)); 137 map->table = malloc(map->capacity * sizeof(int64_t));
118 h48set_clear(set); 138 h48map_clear(map);
119} 139}
120 140
121_static void 141_static void
122h48set_clear(h48set_t *set) 142h48map_clear(h48map_t *map)
123{ 143{
124 int64_t i; 144 memset(map->table, 0xFF, map->capacity * sizeof(uint64_t));
125 145 map->n = 0;
126 for (i = 0; i < set->capacity; i++)
127 set->table[i] = -1;
128
129 set->n = 0;
130} 146}
131 147
132_static void 148_static void
133h48set_destroy(h48set_t *set) 149h48map_destroy(h48map_t *map)
134{ 150{
135 free(set->table); 151 free(map->table);
136} 152}
137 153
138/* Returns the index in where x should be inserted, or -1 if x is in the set */ 154_static_inline uint64_t
139_static_inline int64_t 155h48map_lookup(h48map_t *map, uint64_t x)
140h48set_lookup(h48set_t *set, int64_t x)
141{ 156{
142 int64_t hash, i; 157 uint64_t hash, i;
143 158
144 hash = ((x % set->capacity) * set->mod) % set->capacity; 159 hash = ((x % map->capacity) * map->mod) % map->capacity;
145 for (i = hash; set->table[i] != -1; i = (i+1) % set->capacity) 160 for (i = hash;
146 if (set->table[i] == x) 161 map->table[i] != MAP_UNSET && (map->table[i] & MAP_KEYMASK) != x;
147 return -1; 162 i = (i+1) % map->capacity
163 ) ;
148 164
149 return i; 165 return i;
150} 166}
151 167
152_static_inline void 168_static_inline void
153h48set_insert(h48set_t *set, int64_t x) 169h48map_insertmin(h48map_t *map, uint64_t key, uint64_t val)
154{ 170{
155 int64_t i; 171 uint64_t i, oldval, min;
156 172
157 i = h48set_lookup(set, x); 173 i = h48map_lookup(map, key);
158 if (i != -1) { 174 oldval = map->table[i] >> MAP_KEYSHIFT;
159 set->table[i] = x; 175 min = _min(val, oldval);
160 set->n++; 176
161 } 177 map->n += map->table[i] == MAP_UNSET;
178 map->table[i] = (key & MAP_KEYMASK) | (min << MAP_KEYSHIFT);
162} 179}
163 180
164_static_inline bool 181_static_inline uint64_t
165h48set_contains(h48set_t *set, int64_t x) 182h48map_value(h48map_t *map, uint64_t key)
166{ 183{
167 int64_t i; 184 return map->table[h48map_lookup(map, key)] >> MAP_KEYSHIFT;
168
169 i = h48set_lookup(set, x);
170
171 return i == -1;
172} 185}
173 186
174_static int64_t 187_static kvpair_t
175h48set_save(h48set_t *set, int64_t *a) 188h48map_nextkvpair(h48map_t *map, uint64_t *p)
176{ 189{
177 int64_t i, j; 190 kvpair_t kv;
191 uint64_t pair;
192
193 kv.key = MAP_UNSET;
194 kv.val = MAP_UNSET;
178 195
179 for (i = 0, j = 0; i < set->capacity; i++) 196 DBG_ASSERT(*p < map->capacity, kv,
180 if (set->table[i] != -1) 197 "Error looping over map: given index %" PRIu64 " is out of "
181 a[j++] = set->table[i]; 198 "range [0,%" PRIu64 "]", *p, map->capacity);
182 199
183 return j; 200 for ( ; *p < map->capacity; (*p)++) {
201 if (map->table[*p] != MAP_UNSET) {
202 pair = map->table[(*p)++];
203 kv.key = pair & MAP_KEYMASK;
204 kv.val = pair >> MAP_KEYSHIFT;
205 return kv;
206 }
207 }
208
209 return kv;
184} 210}
185 211
186_static_inline int64_t 212_static_inline int64_t
@@ -358,6 +384,34 @@ gendata_cocsep_dfs(dfsarg_cocsep_t *arg)
358 return cc; 384 return cc;
359} 385}
360 386
387_static int64_t
388gen_h48map_short(uint8_t n, const uint32_t *cocsepdata, h48map_t *map)
389{
390/*
391 uint8_t i, j, m;
392 int64_t coord;
393 cube_t cube, d;
394
395 cube = solvedcube();
396 coord = coord_h48(cube, cocsepdata, 11);
397 for (i = 0; i < n; i++) {
398 for (j = 0; (coord = h48map_next(map, &j)) != -1; ) {
399 cube = invcoord_h48(coord, cocsepdata, 11);
400 for (m = 0; m < 18; m++) {
401 d = move(cube, m);
402TODO
403 }
404 }
405 }
406*/
407}
408
409_static int64_t
410gen_h48set_short_dfs(dfsarg_genh48set_t *arg)
411{
412 /* TODO */
413}
414
361/* 415/*
362TODO description 416TODO description
363generating fixed table with h=0, k=4 417generating fixed table with h=0, k=4
@@ -756,9 +810,9 @@ solve_h48stats(
756 for (i = 0; i < 12; i++) 810 for (i = 0; i < 12; i++)
757 solutions[i] = (char)99; 811 solutions[i] = (char)99;
758 812
759 for (arg.depth = 0; 813 for (arg.depth = 0;
760 arg.depth <= maxmoves && solutions[11] == 99; 814 arg.depth <= maxmoves && solutions[11] == 99;
761 arg.depth++) 815 arg.depth++)
762 { 816 {
763 arg.nmoves = 0; 817 arg.nmoves = 0;
764 solve_h48stats_dfs(&arg); 818 solve_h48stats_dfs(&arg);
diff --git a/src/utils.h b/src/utils.h
index 021ca75..87402e6 100644
--- a/src/utils.h
+++ b/src/utils.h
@@ -1,4 +1,6 @@
1#define _swap(x, y) do { x ^= y; y ^= x; x ^= y; } while (0) 1#define _swap(x, y) do { x ^= y; y ^= x; x ^= y; } while (0)
2#define _min(x, y) ((x) < (y) ? (x) : (y))
3#define _max(x, y) ((x) > (y) ? (x) : (y))
2 4
3_static int64_t factorial(int64_t); 5_static int64_t factorial(int64_t);
4_static bool isperm(uint8_t *, int64_t); 6_static bool isperm(uint8_t *, int64_t);
diff --git a/test/112_h48map/00_small.in b/test/112_h48map/00_small.in
new file mode 100644
index 0000000..ee8e591
--- /dev/null
+++ b/test/112_h48map/00_small.in
@@ -0,0 +1,11 @@
111
27
34
434
512
645
77
834
913
1045
115
diff --git a/test/112_h48map/00_small.out b/test/112_h48map/00_small.out
new file mode 100644
index 0000000..260e804
--- /dev/null
+++ b/test/112_h48map/00_small.out
@@ -0,0 +1,3 @@
12
234 12
345 5
diff --git a/test/112_h48set/01_large.in b/test/112_h48map/01_large.in
index a70ef9a..1812b40 100644
--- a/test/112_h48set/01_large.in
+++ b/test/112_h48map/01_large.in
@@ -2,152 +2,302 @@
2293 2293
3150 3150
4100053 4100053
5417
5100045 6100045
7164
6100007 8100007
9235
7100007 10100007
11207
8100011 12100011
13406
9100072 14100072
1529
10100033 16100033
17188
11100015 18100015
19358
12100013 20100013
21248
13100068 22100068
23218
14100047 24100047
25398
15100046 26100046
27263
16100000 28100000
29471
17100076 30100076
31219
18100021 32100021
33115
19100019 34100019
35329
20100015 36100015
37178
21100049 38100049
3959
22100052 40100052
41319
23100071 42100071
43232
24100058 44100058
45174
25100009 46100009
4746
26100060 48100060
49349
27100030 50100030
51287
28100051 52100051
53203
29100069 54100069
55359
30100011 56100011
57296
31100051 58100051
59223
32100014 60100014
61233
33100031 62100031
63264
34100017 64100017
65180
35100076 66100076
6722
36100016 68100016
69213
37100030 70100030
7155
38100037 72100037
733
39100011 74100011
75467
40100002 76100002
77165
41100029 78100029
79161
42100022 80100022
8167
43100038 82100038
83374
44100075 84100075
854
45100066 86100066
87156
46100051 88100051
89144
47100020 90100020
91480
48100039 92100039
93265
49100029 94100029
95195
50100087 96100087
97245
51100099 98100099
99287
52100041 100100041
101308
53100042 102100042
10332
54100026 104100026
105312
55100060 106100060
107434
56100006 108100006
109392
57100010 110100010
111269
58100079 112100079
113414
59100046 114100046
115161
60100086 116100086
117139
61100010 118100010
11988
62100036 120100036
121117
63100047 122100047
123376
64100069 124100069
12517
65100041 126100041
127314
66100074 128100074
129320
67100090 130100090
131225
68100092 132100092
133424
69100020 134100020
135325
70100096 136100096
137318
71100046 138100046
139238
72100028 140100028
14113
73100072 142100072
14373
74100096 144100096
145262
75100025 146100025
14782
76100001 148100001
149107
77100067 150100067
151410
78100044 152100044
153449
79100063 154100063
155276
80100026 156100026
157392
81100062 158100062
159407
82100091 160100091
161411
83100012 162100012
163400
84100073 164100073
165331
85100051 166100051
16783
86100010 168100010
169385
87100096 170100096
171484
88100043 172100043
173352
89100025 174100025
175207
90100077 176100077
177272
91100089 178100089
179192
92100005 180100005
181291
93100024 182100024
183243
94100091 184100091
185445
95100046 186100046
187162
96100053 188100053
189380
97100058 190100058
191157
98100065 192100065
193464
99100051 194100051
195306
100100056 196100056
197236
101100025 198100025
199198
102100093 200100093
201230
103100088 202100088
203494
104100033 204100033
20570
105100073 206100073
207218
106100048 208100048
209486
107100059 210100059
21177
108100027 212100027
213142
109100045 214100045
215418
110100012 216100012
21768
111100059 218100059
219448
112100084 220100084
221339
113100017 222100017
22339
114100048 224100048
22583
115100004 226100004
227321
116100051 228100051
229441
117100016 230100016
231308
118100088 232100088
233334
119100033 234100033
235476
120100064 236100064
23751
121100060 238100060
239324
122100043 240100043
241149
123100084 242100084
243116
124100026 244100026
245351
125100051 246100051
247396
126100060 248100060
249377
127100069 250100069
251301
128100015 252100015
253319
129100014 254100014
255466
130100038 256100038
257194
131100068 258100068
25941
132100038 260100038
261295
133100097 262100097
263394
134100017 264100017
26534
135100013 266100013
267223
136100053 268100053
269339
137100019 270100019
27167
138100018 272100018
27324
139100081 274100081
275205
140100071 276100071
277440
141100025 278100025
279228
142100014 280100014
281169
143100016 282100016
283121
144100011 284100011
285444
145100069 286100069
287460
146100079 288100079
289139
147100063 290100063
291169
148100070 292100070
293132
149100072 294100072
295119
150100095 296100095
297126
151100042 298100042
299217
152100008 300100008
301272
153100022 302100022
303121
diff --git a/test/112_h48map/01_large.out b/test/112_h48map/01_large.out
new file mode 100644
index 0000000..f5e00d8
--- /dev/null
+++ b/test/112_h48map/01_large.out
@@ -0,0 +1,83 @@
182
2100000 471
3100001 107
4100002 165
5100004 321
6100005 291
7100006 392
8100007 207
9100008 272
10100009 46
11100010 88
12100011 296
13100012 68
14100013 223
15100014 169
16100015 178
17100016 121
18100017 34
19100018 24
20100019 67
21100020 325
22100021 115
23100022 67
24100024 243
25100025 82
26100026 312
27100027 142
28100028 13
29100029 161
30100030 55
31100031 264
32100033 70
33100036 117
34100037 3
35100038 194
36100039 265
37100041 308
38100042 32
39100043 149
40100044 449
41100045 164
42100046 161
43100047 376
44100048 83
45100049 59
46100051 83
47100052 319
48100053 339
49100056 236
50100058 157
51100059 77
52100060 324
53100062 407
54100063 169
55100064 51
56100065 464
57100066 156
58100067 410
59100068 41
60100069 17
61100070 132
62100071 232
63100072 29
64100073 218
65100074 320
66100075 4
67100076 22
68100077 272
69100079 139
70100081 205
71100084 116
72100086 139
73100087 245
74100088 334
75100089 192
76100090 225
77100091 411
78100092 424
79100093 230
80100095 126
81100096 262
82100097 394
83100099 287
diff --git a/test/112_h48map/h48map_tests.c b/test/112_h48map/h48map_tests.c
new file mode 100644
index 0000000..ce8f657
--- /dev/null
+++ b/test/112_h48map/h48map_tests.c
@@ -0,0 +1,88 @@
1#include "../test.h"
2
3#define MAP_KEYSHIFT UINT64_C(40)
4
5typedef struct {
6 uint64_t n;
7 uint64_t capacity;
8 uint64_t mod;
9 uint64_t *table;
10} h48map_t;
11
12typedef struct {
13 uint64_t key;
14 uint64_t val;
15} kvpair_t;
16
17void h48map_create(h48map_t *, uint64_t, uint64_t);
18void h48map_clear(h48map_t *);
19void h48map_destroy(h48map_t *);
20uint64_t h48map_lookup(h48map_t *, uint64_t);
21void h48map_insertmin(h48map_t *, uint64_t, uint64_t);
22uint64_t h48map_value(h48map_t *, uint64_t);
23kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *);
24
25char str[STRLENMAX];
26
27int compare(const void *x, const void *y) {
28 uint64_t a = ((kvpair_t *)x)->key;
29 uint64_t b = ((kvpair_t *)y)->key;
30
31 if (a > b) return 1;
32 if (a == b) return 0;
33 return -1;
34}
35
36uint64_t readl(void) {
37 fgets(str, STRLENMAX, stdin);
38 return atoll(str);
39}
40
41void run(void) {
42 h48map_t map;
43 uint64_t n, i, j, capacity, mod, x, y, v;
44 kvpair_t kv, *a, *b;
45
46 capacity = readl();
47 mod = readl();
48 n = readl();
49
50 a = malloc(n * sizeof(kvpair_t));
51 b = malloc(n * sizeof(kvpair_t));
52 for (i = 0; i < n; i++) {
53 x = readl();
54 y = readl();
55 a[i] = (kvpair_t) { .key = x, .val = y };
56 }
57
58 h48map_create(&map, capacity, mod);
59 for (i = 0; i < n; i++)
60 h48map_insertmin(&map, a[i].key, a[i].val);
61
62 i = 0;
63 for (kv = h48map_nextkvpair(&map, &i), j = 0;
64 i != map.capacity;
65 kv = h48map_nextkvpair(&map, &i)
66 ) {
67 b[j++] = kv;
68 }
69 qsort(b, j, sizeof(kvpair_t), compare);
70
71 printf("%" PRIu64 "\n", map.n);
72 for (i = 0; i < j; i++)
73 printf("%" PRIu64 " %" PRIu64 "\n", b[i].key, b[i].val);
74 if (map.n != j)
75 printf("Wrong number of elements: map->n = %" PRIu64 ", "
76 "but scan returns %" PRIu64 "\n", map.n, j);
77 for (i = 0; i < n; i++) {
78 v = h48map_value(&map, a[i].key);
79 if (v > a[i].val)
80 printf("Value for key %" PRId64 " is larger than "
81 "expected (%" PRIu64 " > %" PRIu64 ")\n",
82 a[i].key, v, a[i].val);
83 }
84
85 h48map_destroy(&map);
86 free(a);
87 free(b);
88}
diff --git a/test/112_h48set/00_small.in b/test/112_h48set/00_small.in
deleted file mode 100644
index d788d5b..0000000
--- a/test/112_h48set/00_small.in
+++ /dev/null
@@ -1,6 +0,0 @@
111
27
33
434
545
634
diff --git a/test/112_h48set/00_small.out b/test/112_h48set/00_small.out
deleted file mode 100644
index 29c08e5..0000000
--- a/test/112_h48set/00_small.out
+++ /dev/null
@@ -1,3 +0,0 @@
12
234
345
diff --git a/test/112_h48set/01_large.out b/test/112_h48set/01_large.out
deleted file mode 100644
index 6632336..0000000
--- a/test/112_h48set/01_large.out
+++ /dev/null
@@ -1,83 +0,0 @@
182
2100000
3100001
4100002
5100004
6100005
7100006
8100007
9100008
10100009
11100010
12100011
13100012
14100013
15100014
16100015
17100016
18100017
19100018
20100019
21100020
22100021
23100022
24100024
25100025
26100026
27100027
28100028
29100029
30100030
31100031
32100033
33100036
34100037
35100038
36100039
37100041
38100042
39100043
40100044
41100045
42100046
43100047
44100048
45100049
46100051
47100052
48100053
49100056
50100058
51100059
52100060
53100062
54100063
55100064
56100065
57100066
58100067
59100068
60100069
61100070
62100071
63100072
64100073
65100074
66100075
67100076
68100077
69100079
70100081
71100084
72100086
73100087
74100088
75100089
76100090
77100091
78100092
79100093
80100095
81100096
82100097
83100099
diff --git a/test/112_h48set/h48set_tests.c b/test/112_h48set/h48set_tests.c
deleted file mode 100644
index d9310a9..0000000
--- a/test/112_h48set/h48set_tests.c
+++ /dev/null
@@ -1,64 +0,0 @@
1#include "../test.h"
2
3char str[STRLENMAX];
4
5typedef struct {
6 int64_t n;
7 int64_t capacity;
8 int64_t mod;
9 int64_t *table;
10} h48set_t;
11
12void h48set_create(h48set_t *, int64_t, int64_t);
13void h48set_clear(h48set_t *);
14void h48set_destroy(h48set_t *);
15int64_t h48set_lookup(h48set_t *, int64_t);
16void h48set_insert(h48set_t *, int64_t);
17bool h48set_contains(h48set_t *, int64_t);
18int64_t h48set_save(h48set_t *, int64_t *);
19
20int compare(const void *x, const void *y) {
21 int64_t a = *(int64_t *)x;
22 int64_t b = *(int64_t *)y;
23
24 if (a > b) return 1;
25 if (a == b) return 0;
26 return -1;
27}
28
29int64_t readl(void) {
30 fgets(str, STRLENMAX, stdin);
31 return atoll(str);
32}
33
34void run(void) {
35 h48set_t set;
36 int64_t n, i, k, capacity, mod, *a, *b;
37
38 capacity = readl();
39 mod = readl();
40 n = readl();
41
42 a = malloc(n * sizeof(int64_t));
43 b = malloc(n * sizeof(int64_t));
44 for (i = 0; i < n; i++)
45 a[i] = readl();
46
47 h48set_create(&set, capacity, mod);
48 for (i = 0; i < n; i++)
49 h48set_insert(&set, a[i]);
50
51 k = h48set_save(&set, b);
52 qsort(b, k, sizeof(int64_t), compare);
53
54 printf("%" PRId64 "\n", k);
55 for (i = 0; i < k; i++)
56 printf("%" PRId64 "\n", b[i]);
57 for (i = 0; i < n; i++)
58 if (!h48set_contains(&set, a[i]))
59 printf("Set does not contain %" PRId64 "\n", a[i]);
60
61 h48set_destroy(&set);
62 free(a);
63 free(b);
64}

Generated with cgit - Back to sebastiano.tronto.net