From 5727f06c5694a4831881322876e3ba4d8ce3b743 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sat, 20 Jul 2024 10:05:51 +0200 Subject: Finally fixed selfsim logic --- test/111_gendata_h48_h0/00_h_0.in | 0 test/111_gendata_h48_h0/00_h_0.out | 23 --- test/111_gendata_h48_h0/gendata_h48_tests.c | 33 --- test/111_h48map/00_small.in | 11 + test/111_h48map/00_small.out | 3 + test/111_h48map/01_large.in | 303 ++++++++++++++++++++++++++++ test/111_h48map/01_large.out | 83 ++++++++ test/111_h48map/h48map_tests.c | 83 ++++++++ test/112_gendata_h48/00_h_0.in | 2 + test/112_gendata_h48/00_h_0.out | 23 +++ test/112_gendata_h48/gendata_h48_tests.c | 43 ++++ test/112_h48map/00_small.in | 11 - test/112_h48map/00_small.out | 3 - test/112_h48map/01_large.in | 303 ---------------------------- test/112_h48map/01_large.out | 83 -------- test/112_h48map/h48map_tests.c | 83 -------- 16 files changed, 551 insertions(+), 539 deletions(-) delete mode 100644 test/111_gendata_h48_h0/00_h_0.in delete mode 100644 test/111_gendata_h48_h0/00_h_0.out delete mode 100644 test/111_gendata_h48_h0/gendata_h48_tests.c create mode 100644 test/111_h48map/00_small.in create mode 100644 test/111_h48map/00_small.out create mode 100644 test/111_h48map/01_large.in create mode 100644 test/111_h48map/01_large.out create mode 100644 test/111_h48map/h48map_tests.c create mode 100644 test/112_gendata_h48/00_h_0.in create mode 100644 test/112_gendata_h48/00_h_0.out create mode 100644 test/112_gendata_h48/gendata_h48_tests.c delete mode 100644 test/112_h48map/00_small.in delete mode 100644 test/112_h48map/00_small.out delete mode 100644 test/112_h48map/01_large.in delete mode 100644 test/112_h48map/01_large.out delete mode 100644 test/112_h48map/h48map_tests.c (limited to 'test') diff --git a/test/111_gendata_h48_h0/00_h_0.in b/test/111_gendata_h48_h0/00_h_0.in deleted file mode 100644 index e69de29..0000000 diff --git a/test/111_gendata_h48_h0/00_h_0.out b/test/111_gendata_h48_h0/00_h_0.out deleted file mode 100644 index 04e8bf6..0000000 --- a/test/111_gendata_h48_h0/00_h_0.out +++ /dev/null @@ -1,23 +0,0 @@ -59903605 - -cocsepdata: -Classes: 3393 -Max value: 9 -0: 1 -1: 6 -2: 63 -3: 468 -4: 3068 -5: 15438 -6: 53814 -7: 71352 -8: 8784 -9: 96 - -h48: -0: 1 -1: 1 -2: 4 -3: 34 -4: 331 -5: 3612 diff --git a/test/111_gendata_h48_h0/gendata_h48_tests.c b/test/111_gendata_h48_h0/gendata_h48_tests.c deleted file mode 100644 index e9de3c0..0000000 --- a/test/111_gendata_h48_h0/gendata_h48_tests.c +++ /dev/null @@ -1,33 +0,0 @@ -#include "../test.h" - -#define MAXDEPTH 5 -#define COCSEPSIZE 1119792 -#define ETABLESIZE ((3393 * 495 * 70) >> 1) - -int64_t gendata_h48h0k4(void *, uint8_t); - -void run(void) { - char str[STRLENMAX]; - uint8_t i; - uint32_t *buf, *h48info; - size_t result; - - fgets(str, STRLENMAX, stdin); - buf = (uint32_t *)malloc(sizeof(uint32_t) * 60000000); - result = gendata_h48h0k4(buf, MAXDEPTH); - h48info = buf + (ETABLESIZE + COCSEPSIZE) / 4; - - printf("%zu\n\n", result); - - printf("cocsepdata:\n"); - printf("Classes: %" PRIu32 "\n", buf[COCSEPSIZE/4-12]); - printf("Max value: %" PRIu32 "\n", buf[COCSEPSIZE/4-11]); - for (i = 0; i < 10; i++) - printf("%" PRIu32 ": %" PRIu32 "\n", i, buf[COCSEPSIZE/4-10+i]); - - printf("\nh48:\n"); - for (i = 0; i < MAXDEPTH+1; i++) - printf("%" PRIu32 ": %" PRIu32 "\n", i, h48info[i+1]); - - free(buf); -} diff --git a/test/111_h48map/00_small.in b/test/111_h48map/00_small.in new file mode 100644 index 0000000..ee8e591 --- /dev/null +++ b/test/111_h48map/00_small.in @@ -0,0 +1,11 @@ +11 +7 +4 +34 +12 +45 +7 +34 +13 +45 +5 diff --git a/test/111_h48map/00_small.out b/test/111_h48map/00_small.out new file mode 100644 index 0000000..260e804 --- /dev/null +++ b/test/111_h48map/00_small.out @@ -0,0 +1,3 @@ +2 +34 12 +45 5 diff --git a/test/111_h48map/01_large.in b/test/111_h48map/01_large.in new file mode 100644 index 0000000..1812b40 --- /dev/null +++ b/test/111_h48map/01_large.in @@ -0,0 +1,303 @@ +307 +293 +150 +100053 +417 +100045 +164 +100007 +235 +100007 +207 +100011 +406 +100072 +29 +100033 +188 +100015 +358 +100013 +248 +100068 +218 +100047 +398 +100046 +263 +100000 +471 +100076 +219 +100021 +115 +100019 +329 +100015 +178 +100049 +59 +100052 +319 +100071 +232 +100058 +174 +100009 +46 +100060 +349 +100030 +287 +100051 +203 +100069 +359 +100011 +296 +100051 +223 +100014 +233 +100031 +264 +100017 +180 +100076 +22 +100016 +213 +100030 +55 +100037 +3 +100011 +467 +100002 +165 +100029 +161 +100022 +67 +100038 +374 +100075 +4 +100066 +156 +100051 +144 +100020 +480 +100039 +265 +100029 +195 +100087 +245 +100099 +287 +100041 +308 +100042 +32 +100026 +312 +100060 +434 +100006 +392 +100010 +269 +100079 +414 +100046 +161 +100086 +139 +100010 +88 +100036 +117 +100047 +376 +100069 +17 +100041 +314 +100074 +320 +100090 +225 +100092 +424 +100020 +325 +100096 +318 +100046 +238 +100028 +13 +100072 +73 +100096 +262 +100025 +82 +100001 +107 +100067 +410 +100044 +449 +100063 +276 +100026 +392 +100062 +407 +100091 +411 +100012 +400 +100073 +331 +100051 +83 +100010 +385 +100096 +484 +100043 +352 +100025 +207 +100077 +272 +100089 +192 +100005 +291 +100024 +243 +100091 +445 +100046 +162 +100053 +380 +100058 +157 +100065 +464 +100051 +306 +100056 +236 +100025 +198 +100093 +230 +100088 +494 +100033 +70 +100073 +218 +100048 +486 +100059 +77 +100027 +142 +100045 +418 +100012 +68 +100059 +448 +100084 +339 +100017 +39 +100048 +83 +100004 +321 +100051 +441 +100016 +308 +100088 +334 +100033 +476 +100064 +51 +100060 +324 +100043 +149 +100084 +116 +100026 +351 +100051 +396 +100060 +377 +100069 +301 +100015 +319 +100014 +466 +100038 +194 +100068 +41 +100038 +295 +100097 +394 +100017 +34 +100013 +223 +100053 +339 +100019 +67 +100018 +24 +100081 +205 +100071 +440 +100025 +228 +100014 +169 +100016 +121 +100011 +444 +100069 +460 +100079 +139 +100063 +169 +100070 +132 +100072 +119 +100095 +126 +100042 +217 +100008 +272 +100022 +121 diff --git a/test/111_h48map/01_large.out b/test/111_h48map/01_large.out new file mode 100644 index 0000000..f5e00d8 --- /dev/null +++ b/test/111_h48map/01_large.out @@ -0,0 +1,83 @@ +82 +100000 471 +100001 107 +100002 165 +100004 321 +100005 291 +100006 392 +100007 207 +100008 272 +100009 46 +100010 88 +100011 296 +100012 68 +100013 223 +100014 169 +100015 178 +100016 121 +100017 34 +100018 24 +100019 67 +100020 325 +100021 115 +100022 67 +100024 243 +100025 82 +100026 312 +100027 142 +100028 13 +100029 161 +100030 55 +100031 264 +100033 70 +100036 117 +100037 3 +100038 194 +100039 265 +100041 308 +100042 32 +100043 149 +100044 449 +100045 164 +100046 161 +100047 376 +100048 83 +100049 59 +100051 83 +100052 319 +100053 339 +100056 236 +100058 157 +100059 77 +100060 324 +100062 407 +100063 169 +100064 51 +100065 464 +100066 156 +100067 410 +100068 41 +100069 17 +100070 132 +100071 232 +100072 29 +100073 218 +100074 320 +100075 4 +100076 22 +100077 272 +100079 139 +100081 205 +100084 116 +100086 139 +100087 245 +100088 334 +100089 192 +100090 225 +100091 411 +100092 424 +100093 230 +100095 126 +100096 262 +100097 394 +100099 287 diff --git a/test/111_h48map/h48map_tests.c b/test/111_h48map/h48map_tests.c new file mode 100644 index 0000000..d70bc3a --- /dev/null +++ b/test/111_h48map/h48map_tests.c @@ -0,0 +1,83 @@ +#include "../test.h" + +#define MAP_KEYSHIFT UINT64_C(40) +#define MAXPOS 1000 + +typedef struct { + uint64_t n; + uint64_t capacity; + uint64_t randomizer; + uint64_t *table; +} h48map_t; + +typedef struct { + uint64_t key; + uint64_t val; +} kvpair_t; + +void h48map_create(h48map_t *, uint64_t, uint64_t); +void h48map_destroy(h48map_t *); +void h48map_insertmin(h48map_t *, uint64_t, uint64_t); +uint64_t h48map_value(h48map_t *, uint64_t); +kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *); + +char str[STRLENMAX]; + +int compare(const void *x, const void *y) { + uint64_t a = ((kvpair_t *)x)->key; + uint64_t b = ((kvpair_t *)y)->key; + + if (a > b) return 1; + if (a == b) return 0; + return -1; +} + +uint64_t readl(void) { + fgets(str, STRLENMAX, stdin); + return atoll(str); +} + +void run(void) { + h48map_t map; + uint64_t n, i, j, capacity, randomizer, x, y, v; + kvpair_t kv, a[MAXPOS], b[MAXPOS]; + + capacity = readl(); + randomizer = readl(); + n = readl(); + + for (i = 0; i < n; i++) { + x = readl(); + y = readl(); + a[i] = (kvpair_t) { .key = x, .val = y }; + } + + h48map_create(&map, capacity, randomizer); + for (i = 0; i < n; i++) + h48map_insertmin(&map, a[i].key, a[i].val); + + i = 0; + for (kv = h48map_nextkvpair(&map, &i), j = 0; + i != map.capacity && j < MAXPOS; + kv = h48map_nextkvpair(&map, &i) + ) { + b[j++] = kv; + } + qsort(b, j, sizeof(kvpair_t), compare); + + printf("%" PRIu64 "\n", map.n); + for (i = 0; i < j; i++) + printf("%" PRIu64 " %" PRIu64 "\n", b[i].key, b[i].val); + if (map.n != j) + printf("Wrong number of elements: map->n = %" PRIu64 ", " + "but scan returns %" PRIu64 "\n", map.n, j); + for (i = 0; i < n; i++) { + v = h48map_value(&map, a[i].key); + if (v > a[i].val) + printf("Value for key %" PRId64 " is larger than " + "expected (%" PRIu64 " > %" PRIu64 ")\n", + a[i].key, v, a[i].val); + } + + h48map_destroy(&map); +} diff --git a/test/112_gendata_h48/00_h_0.in b/test/112_gendata_h48/00_h_0.in new file mode 100644 index 0000000..cb6e5ed --- /dev/null +++ b/test/112_gendata_h48/00_h_0.in @@ -0,0 +1,2 @@ +5 +0 diff --git a/test/112_gendata_h48/00_h_0.out b/test/112_gendata_h48/00_h_0.out new file mode 100644 index 0000000..04e8bf6 --- /dev/null +++ b/test/112_gendata_h48/00_h_0.out @@ -0,0 +1,23 @@ +59903605 + +cocsepdata: +Classes: 3393 +Max value: 9 +0: 1 +1: 6 +2: 63 +3: 468 +4: 3068 +5: 15438 +6: 53814 +7: 71352 +8: 8784 +9: 96 + +h48: +0: 1 +1: 1 +2: 4 +3: 34 +4: 331 +5: 3612 diff --git a/test/112_gendata_h48/gendata_h48_tests.c b/test/112_gendata_h48/gendata_h48_tests.c new file mode 100644 index 0000000..485d9d0 --- /dev/null +++ b/test/112_gendata_h48/gendata_h48_tests.c @@ -0,0 +1,43 @@ +#include "../test.h" + +#define COCSEPSIZE 1119792 +#define ETABLESIZE ((3393 * 495 * 70) >> 1) + +int64_t gendata_h48h0k4(void *, uint8_t); + +int64_t gendata_h48_fixture(void *buf, uint8_t maxdepth, uint8_t h) { + if (h == 0) + return gendata_h48h0k4(buf, maxdepth); + fprintf(stderr, "Error: gendata h48 for h>0 not implemented yet\n"); + exit(1); +} + +void run(void) { + char str[STRLENMAX]; + uint8_t i, maxdepth, h; + uint32_t *buf, *h48info; + size_t result; + + fgets(str, STRLENMAX, stdin); + maxdepth = atoi(str); + fgets(str, STRLENMAX, stdin); + h = atoi(str); + + buf = (uint32_t *)malloc(sizeof(uint32_t) * 60000000); + result = gendata_h48_fixture(buf, maxdepth, h); + h48info = buf + (ETABLESIZE + COCSEPSIZE) / 4; + + printf("%zu\n\n", result); + + printf("cocsepdata:\n"); + printf("Classes: %" PRIu32 "\n", buf[COCSEPSIZE/4-12]); + printf("Max value: %" PRIu32 "\n", buf[COCSEPSIZE/4-11]); + for (i = 0; i < 10; i++) + printf("%" PRIu32 ": %" PRIu32 "\n", i, buf[COCSEPSIZE/4-10+i]); + + printf("\nh48:\n"); + for (i = 0; i < maxdepth+1; i++) + printf("%" PRIu32 ": %" PRIu32 "\n", i, h48info[i+1]); + + free(buf); +} diff --git a/test/112_h48map/00_small.in b/test/112_h48map/00_small.in deleted file mode 100644 index ee8e591..0000000 --- a/test/112_h48map/00_small.in +++ /dev/null @@ -1,11 +0,0 @@ -11 -7 -4 -34 -12 -45 -7 -34 -13 -45 -5 diff --git a/test/112_h48map/00_small.out b/test/112_h48map/00_small.out deleted file mode 100644 index 260e804..0000000 --- a/test/112_h48map/00_small.out +++ /dev/null @@ -1,3 +0,0 @@ -2 -34 12 -45 5 diff --git a/test/112_h48map/01_large.in b/test/112_h48map/01_large.in deleted file mode 100644 index 1812b40..0000000 --- a/test/112_h48map/01_large.in +++ /dev/null @@ -1,303 +0,0 @@ -307 -293 -150 -100053 -417 -100045 -164 -100007 -235 -100007 -207 -100011 -406 -100072 -29 -100033 -188 -100015 -358 -100013 -248 -100068 -218 -100047 -398 -100046 -263 -100000 -471 -100076 -219 -100021 -115 -100019 -329 -100015 -178 -100049 -59 -100052 -319 -100071 -232 -100058 -174 -100009 -46 -100060 -349 -100030 -287 -100051 -203 -100069 -359 -100011 -296 -100051 -223 -100014 -233 -100031 -264 -100017 -180 -100076 -22 -100016 -213 -100030 -55 -100037 -3 -100011 -467 -100002 -165 -100029 -161 -100022 -67 -100038 -374 -100075 -4 -100066 -156 -100051 -144 -100020 -480 -100039 -265 -100029 -195 -100087 -245 -100099 -287 -100041 -308 -100042 -32 -100026 -312 -100060 -434 -100006 -392 -100010 -269 -100079 -414 -100046 -161 -100086 -139 -100010 -88 -100036 -117 -100047 -376 -100069 -17 -100041 -314 -100074 -320 -100090 -225 -100092 -424 -100020 -325 -100096 -318 -100046 -238 -100028 -13 -100072 -73 -100096 -262 -100025 -82 -100001 -107 -100067 -410 -100044 -449 -100063 -276 -100026 -392 -100062 -407 -100091 -411 -100012 -400 -100073 -331 -100051 -83 -100010 -385 -100096 -484 -100043 -352 -100025 -207 -100077 -272 -100089 -192 -100005 -291 -100024 -243 -100091 -445 -100046 -162 -100053 -380 -100058 -157 -100065 -464 -100051 -306 -100056 -236 -100025 -198 -100093 -230 -100088 -494 -100033 -70 -100073 -218 -100048 -486 -100059 -77 -100027 -142 -100045 -418 -100012 -68 -100059 -448 -100084 -339 -100017 -39 -100048 -83 -100004 -321 -100051 -441 -100016 -308 -100088 -334 -100033 -476 -100064 -51 -100060 -324 -100043 -149 -100084 -116 -100026 -351 -100051 -396 -100060 -377 -100069 -301 -100015 -319 -100014 -466 -100038 -194 -100068 -41 -100038 -295 -100097 -394 -100017 -34 -100013 -223 -100053 -339 -100019 -67 -100018 -24 -100081 -205 -100071 -440 -100025 -228 -100014 -169 -100016 -121 -100011 -444 -100069 -460 -100079 -139 -100063 -169 -100070 -132 -100072 -119 -100095 -126 -100042 -217 -100008 -272 -100022 -121 diff --git a/test/112_h48map/01_large.out b/test/112_h48map/01_large.out deleted file mode 100644 index f5e00d8..0000000 --- a/test/112_h48map/01_large.out +++ /dev/null @@ -1,83 +0,0 @@ -82 -100000 471 -100001 107 -100002 165 -100004 321 -100005 291 -100006 392 -100007 207 -100008 272 -100009 46 -100010 88 -100011 296 -100012 68 -100013 223 -100014 169 -100015 178 -100016 121 -100017 34 -100018 24 -100019 67 -100020 325 -100021 115 -100022 67 -100024 243 -100025 82 -100026 312 -100027 142 -100028 13 -100029 161 -100030 55 -100031 264 -100033 70 -100036 117 -100037 3 -100038 194 -100039 265 -100041 308 -100042 32 -100043 149 -100044 449 -100045 164 -100046 161 -100047 376 -100048 83 -100049 59 -100051 83 -100052 319 -100053 339 -100056 236 -100058 157 -100059 77 -100060 324 -100062 407 -100063 169 -100064 51 -100065 464 -100066 156 -100067 410 -100068 41 -100069 17 -100070 132 -100071 232 -100072 29 -100073 218 -100074 320 -100075 4 -100076 22 -100077 272 -100079 139 -100081 205 -100084 116 -100086 139 -100087 245 -100088 334 -100089 192 -100090 225 -100091 411 -100092 424 -100093 230 -100095 126 -100096 262 -100097 394 -100099 287 diff --git a/test/112_h48map/h48map_tests.c b/test/112_h48map/h48map_tests.c deleted file mode 100644 index d70bc3a..0000000 --- a/test/112_h48map/h48map_tests.c +++ /dev/null @@ -1,83 +0,0 @@ -#include "../test.h" - -#define MAP_KEYSHIFT UINT64_C(40) -#define MAXPOS 1000 - -typedef struct { - uint64_t n; - uint64_t capacity; - uint64_t randomizer; - uint64_t *table; -} h48map_t; - -typedef struct { - uint64_t key; - uint64_t val; -} kvpair_t; - -void h48map_create(h48map_t *, uint64_t, uint64_t); -void h48map_destroy(h48map_t *); -void h48map_insertmin(h48map_t *, uint64_t, uint64_t); -uint64_t h48map_value(h48map_t *, uint64_t); -kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *); - -char str[STRLENMAX]; - -int compare(const void *x, const void *y) { - uint64_t a = ((kvpair_t *)x)->key; - uint64_t b = ((kvpair_t *)y)->key; - - if (a > b) return 1; - if (a == b) return 0; - return -1; -} - -uint64_t readl(void) { - fgets(str, STRLENMAX, stdin); - return atoll(str); -} - -void run(void) { - h48map_t map; - uint64_t n, i, j, capacity, randomizer, x, y, v; - kvpair_t kv, a[MAXPOS], b[MAXPOS]; - - capacity = readl(); - randomizer = readl(); - n = readl(); - - for (i = 0; i < n; i++) { - x = readl(); - y = readl(); - a[i] = (kvpair_t) { .key = x, .val = y }; - } - - h48map_create(&map, capacity, randomizer); - for (i = 0; i < n; i++) - h48map_insertmin(&map, a[i].key, a[i].val); - - i = 0; - for (kv = h48map_nextkvpair(&map, &i), j = 0; - i != map.capacity && j < MAXPOS; - kv = h48map_nextkvpair(&map, &i) - ) { - b[j++] = kv; - } - qsort(b, j, sizeof(kvpair_t), compare); - - printf("%" PRIu64 "\n", map.n); - for (i = 0; i < j; i++) - printf("%" PRIu64 " %" PRIu64 "\n", b[i].key, b[i].val); - if (map.n != j) - printf("Wrong number of elements: map->n = %" PRIu64 ", " - "but scan returns %" PRIu64 "\n", map.n, j); - for (i = 0; i < n; i++) { - v = h48map_value(&map, a[i].key); - if (v > a[i].val) - printf("Value for key %" PRId64 " is larger than " - "expected (%" PRIu64 " > %" PRIu64 ")\n", - a[i].key, v, a[i].val); - } - - h48map_destroy(&map); -} -- cgit v1.3