Added pre-computation of short h48 positions

6 files changed, 151 insertions, 12 deletions

diff --git a/test/112_h48map/h48map_tests.c b/test/112_h48map/h48map_tests.c
index ce8f657..d70bc3a 100644
--- a/test/112_h48map/h48map_tests.c
+++ b/test/112_h48map/h48map_tests.c
@@ -1,11 +1,12 @@
 #include "../test.h"
 
 #define MAP_KEYSHIFT          UINT64_C(40)
+#define MAXPOS 1000
 
 typedef struct {
         uint64_t n;
         uint64_t capacity;
-        uint64_t mod;
+        uint64_t randomizer;
         uint64_t *table;
 } h48map_t;
 
@@ -15,9 +16,7 @@ typedef struct {
 } 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 *);
@@ -40,28 +39,26 @@ uint64_t readl(void) {
 
 void run(void) {
         h48map_t map;
-        uint64_t n, i, j, capacity, mod, x, y, v;
-        kvpair_t kv, *a, *b;
+        uint64_t n, i, j, capacity, randomizer, x, y, v;
+        kvpair_t kv, a[MAXPOS], b[MAXPOS];
 
         capacity = readl();
-        mod = readl();
+        randomizer = 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);
+        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;
+             i != map.capacity && j < MAXPOS;
              kv = h48map_nextkvpair(&map, &i)
         ) {
                 b[j++] = kv;
@@ -83,6 +80,4 @@ void run(void) {
         }
 
         h48map_destroy(&map);
-        free(a);
-        free(b);
 }
diff --git a/test/113_gen_h48short/00_depth_1.in b/test/113_gen_h48short/00_depth_1.in
new file mode 100644
index 0000000..c86f15b
--- /dev/null
+++ b/test/113_gen_h48short/00_depth_1.in
@@ -0,0 +1,28 @@
+73
+157
+1
+
+For longer test:
+
+20000003
+20000023
+8
+
+Short h48: generating depth 0
+found 1
+Short h48: generating depth 1
+found 1
+Short h48: generating depth 2
+found 4
+Short h48: generating depth 3
+found 34
+Short h48: generating depth 4
+found 333
+Short h48: generating depth 5
+found 3815
+Short h48: generating depth 6
+found 45382
+Short h48: generating depth 7
+found 548562
+Short h48: generating depth 8
+found 6839723
diff --git a/test/113_gen_h48short/00_depth_1.out b/test/113_gen_h48short/00_depth_1.out
new file mode 100644
index 0000000..b0dba31
--- /dev/null
+++ b/test/113_gen_h48short/00_depth_1.out
@@ -0,0 +1,3 @@
+2
+0 0
+71075840 1
diff --git a/test/113_gen_h48short/01_depth_3.in b/test/113_gen_h48short/01_depth_3.in
new file mode 100644
index 0000000..920e70a
--- /dev/null
+++ b/test/113_gen_h48short/01_depth_3.in
@@ -0,0 +1,3 @@
+73
+157
+3
diff --git a/test/113_gen_h48short/01_depth_3.out b/test/113_gen_h48short/01_depth_3.out
new file mode 100644
index 0000000..dbce376
--- /dev/null
+++ b/test/113_gen_h48short/01_depth_3.out
@@ -0,0 +1,40 @@
+40
+0 0
+70981632 3
+71075840 1
+71086080 3
+142067712 2
+218789888 3
+218884096 2
+283879424 2
+283899904 3
+283953152 3
+283973632 2
+360548808 3
+360835072 3
+473668032 3
+473956352 3
+499869696 3
+500011008 3
+598679552 3
+599109185 3
+662171648 3
+662601226 3
+724818316 3
+725106688 3
+790513664 3
+790607872 3
+904991108 3
+926726144 3
+928729088 3
+1009662340 3
+1088755203 3
+1171758595 3
+1206452224 3
+1206480896 3
+1277360128 3
+1277454336 3
+1403695492 3
+1403697540 3
+1403736452 3
+1403738500 3
diff --git a/test/113_gen_h48short/gen_h48short.c b/test/113_gen_h48short/gen_h48short.c
new file mode 100644
index 0000000..399ef1e
--- /dev/null
+++ b/test/113_gen_h48short/gen_h48short.c
@@ -0,0 +1,70 @@
+#include "../test.h"
+
+#define COCSEP_CLASSES 3393
+#define MAXPOS 200
+
+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 *);
+kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *);
+size_t gendata_cocsep(void *, uint64_t *, cube_t *);
+uint64_t gen_h48short(
+    uint8_t, const uint32_t *, const cube_t *, const uint64_t *, h48map_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) {
+        uint32_t cocsepdata[300000];
+        h48map_t map;
+        uint64_t n, i, j, capacity, randomizer, selfsim[COCSEP_CLASSES];
+        kvpair_t kv, b[MAXPOS];
+        cube_t crep[COCSEP_CLASSES];
+
+        capacity = readl();
+        randomizer = readl();
+        n = readl();
+
+        h48map_create(&map, capacity, randomizer);
+        gendata_cocsep(cocsepdata, selfsim, crep);
+        gen_h48short(n, cocsepdata, crep, selfsim, &map);
+
+        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);
+
+        h48map_destroy(&map);
+}