From 7946c8efc2e2a44a8e78e1263c1691ce9f412a09 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 18 Jul 2024 11:09:50 +0200 Subject: Converted set to map --- 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 | 88 ++++++++++++ test/112_h48set/00_small.in | 6 - test/112_h48set/00_small.out | 3 - test/112_h48set/01_large.in | 153 --------------------- test/112_h48set/01_large.out | 83 ----------- test/112_h48set/h48set_tests.c | 64 --------- 10 files changed, 488 insertions(+), 309 deletions(-) create mode 100644 test/112_h48map/00_small.in create mode 100644 test/112_h48map/00_small.out create mode 100644 test/112_h48map/01_large.in create mode 100644 test/112_h48map/01_large.out create mode 100644 test/112_h48map/h48map_tests.c delete mode 100644 test/112_h48set/00_small.in delete mode 100644 test/112_h48set/00_small.out delete mode 100644 test/112_h48set/01_large.in delete mode 100644 test/112_h48set/01_large.out delete mode 100644 test/112_h48set/h48set_tests.c (limited to 'test') 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 @@ +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 new file mode 100644 index 0000000..260e804 --- /dev/null +++ b/test/112_h48map/00_small.out @@ -0,0 +1,3 @@ +2 +34 12 +45 5 diff --git a/test/112_h48map/01_large.in b/test/112_h48map/01_large.in new file mode 100644 index 0000000..1812b40 --- /dev/null +++ b/test/112_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/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 @@ +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 new file mode 100644 index 0000000..ce8f657 --- /dev/null +++ b/test/112_h48map/h48map_tests.c @@ -0,0 +1,88 @@ +#include "../test.h" + +#define MAP_KEYSHIFT UINT64_C(40) + +typedef struct { + uint64_t n; + uint64_t capacity; + uint64_t mod; + 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_clear(h48map_t *); +void h48map_destroy(h48map_t *); +uint64_t h48map_lookup(h48map_t *, uint64_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, mod, x, y, v; + kvpair_t kv, *a, *b; + + capacity = readl(); + mod = readl(); + n = readl(); + + a = malloc(n * sizeof(kvpair_t)); + b = malloc(n * sizeof(kvpair_t)); + for (i = 0; i < n; i++) { + x = readl(); + y = readl(); + a[i] = (kvpair_t) { .key = x, .val = y }; + } + + h48map_create(&map, capacity, mod); + 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; + 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); + free(a); + free(b); +} 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 @@ -11 -7 -3 -34 -45 -34 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 @@ -2 -34 -45 diff --git a/test/112_h48set/01_large.in b/test/112_h48set/01_large.in deleted file mode 100644 index a70ef9a..0000000 --- a/test/112_h48set/01_large.in +++ /dev/null @@ -1,153 +0,0 @@ -307 -293 -150 -100053 -100045 -100007 -100007 -100011 -100072 -100033 -100015 -100013 -100068 -100047 -100046 -100000 -100076 -100021 -100019 -100015 -100049 -100052 -100071 -100058 -100009 -100060 -100030 -100051 -100069 -100011 -100051 -100014 -100031 -100017 -100076 -100016 -100030 -100037 -100011 -100002 -100029 -100022 -100038 -100075 -100066 -100051 -100020 -100039 -100029 -100087 -100099 -100041 -100042 -100026 -100060 -100006 -100010 -100079 -100046 -100086 -100010 -100036 -100047 -100069 -100041 -100074 -100090 -100092 -100020 -100096 -100046 -100028 -100072 -100096 -100025 -100001 -100067 -100044 -100063 -100026 -100062 -100091 -100012 -100073 -100051 -100010 -100096 -100043 -100025 -100077 -100089 -100005 -100024 -100091 -100046 -100053 -100058 -100065 -100051 -100056 -100025 -100093 -100088 -100033 -100073 -100048 -100059 -100027 -100045 -100012 -100059 -100084 -100017 -100048 -100004 -100051 -100016 -100088 -100033 -100064 -100060 -100043 -100084 -100026 -100051 -100060 -100069 -100015 -100014 -100038 -100068 -100038 -100097 -100017 -100013 -100053 -100019 -100018 -100081 -100071 -100025 -100014 -100016 -100011 -100069 -100079 -100063 -100070 -100072 -100095 -100042 -100008 -100022 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 @@ -82 -100000 -100001 -100002 -100004 -100005 -100006 -100007 -100008 -100009 -100010 -100011 -100012 -100013 -100014 -100015 -100016 -100017 -100018 -100019 -100020 -100021 -100022 -100024 -100025 -100026 -100027 -100028 -100029 -100030 -100031 -100033 -100036 -100037 -100038 -100039 -100041 -100042 -100043 -100044 -100045 -100046 -100047 -100048 -100049 -100051 -100052 -100053 -100056 -100058 -100059 -100060 -100062 -100063 -100064 -100065 -100066 -100067 -100068 -100069 -100070 -100071 -100072 -100073 -100074 -100075 -100076 -100077 -100079 -100081 -100084 -100086 -100087 -100088 -100089 -100090 -100091 -100092 -100093 -100095 -100096 -100097 -100099 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 @@ -#include "../test.h" - -char str[STRLENMAX]; - -typedef struct { - int64_t n; - int64_t capacity; - int64_t mod; - int64_t *table; -} h48set_t; - -void h48set_create(h48set_t *, int64_t, int64_t); -void h48set_clear(h48set_t *); -void h48set_destroy(h48set_t *); -int64_t h48set_lookup(h48set_t *, int64_t); -void h48set_insert(h48set_t *, int64_t); -bool h48set_contains(h48set_t *, int64_t); -int64_t h48set_save(h48set_t *, int64_t *); - -int compare(const void *x, const void *y) { - int64_t a = *(int64_t *)x; - int64_t b = *(int64_t *)y; - - if (a > b) return 1; - if (a == b) return 0; - return -1; -} - -int64_t readl(void) { - fgets(str, STRLENMAX, stdin); - return atoll(str); -} - -void run(void) { - h48set_t set; - int64_t n, i, k, capacity, mod, *a, *b; - - capacity = readl(); - mod = readl(); - n = readl(); - - a = malloc(n * sizeof(int64_t)); - b = malloc(n * sizeof(int64_t)); - for (i = 0; i < n; i++) - a[i] = readl(); - - h48set_create(&set, capacity, mod); - for (i = 0; i < n; i++) - h48set_insert(&set, a[i]); - - k = h48set_save(&set, b); - qsort(b, k, sizeof(int64_t), compare); - - printf("%" PRId64 "\n", k); - for (i = 0; i < k; i++) - printf("%" PRId64 "\n", b[i]); - for (i = 0; i < n; i++) - if (!h48set_contains(&set, a[i])) - printf("Set does not contain %" PRId64 "\n", a[i]); - - h48set_destroy(&set); - free(a); - free(b); -} -- cgit v1.3