Converted set to map

9 files changed, 335 insertions, 156 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_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 @@
 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.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);
-}