Converted set to map

5 files changed, 488 insertions, 0 deletions

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);
+}