1 files changed, 186 insertions, 0 deletions
diff --git a/lib/bitmap_test.c b/lib/bitmap_test.c
new file mode 100644
index 00000000..0595a4d0
--- /dev/null
+++ b/lib/bitmap_test.c
@@ -0,0 +1,186 @@
+/*
+ *	BIRD Library -- Bitmap Tests
+ *
+ *	(c) 2019 Ondrej Zajicek <santiago@crfreenet.org>
+ *	(c) 2019 CZ.NIC z.s.p.o.
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#include "test/birdtest.h"
+#include "sysdep/config.h"
+#include "lib/bitmap.h"
+
+#define MAX_NUM (1 << 20)
+#define MAX_SET (1 << 19)
+#define MAX_CLR (1 << 17)
+
+#define STEP_NUM 1000
+#define STEP_SET 1000
+#define STEP_CLR 500
+
+static int
+t_bmap_set_clear_random(void)
+{
+  struct bmap b;
+
+  resource_init();
+  bmap_init(&b, &root_pool, 1024);
+
+  char expected[MAX_NUM] = {};
+  uint i, n;
+
+  for (i = 0; i < MAX_SET; i++)
+  {
+    do n = bt_random() % MAX_NUM;
+    while (expected[n]);
+
+    bmap_set(&b, n);
+    expected[n] = 1;
+  }
+
+  for (i = 0; i < MAX_CLR; i++)
+  {
+    do n = bt_random() % MAX_NUM;
+    while (!expected[n]);
+
+    bmap_clear(&b, n);
+    expected[n] = 0;
+  }
+
+  for (i = 0; i < MAX_NUM; i++)
+    if (bmap_test(&b, i) != expected[i])
+      bt_abort_msg("Bitmap mismatch on %d (should be %d %d)", i, bmap_test(&b, i), expected[i]);
+
+  return 1;
+}
+
+static int
+t_hmap_set_clear_random(void)
+{
+  struct hmap b;
+
+  resource_init();
+  hmap_init(&b, &root_pool, 1024);
+
+  char expected[MAX_NUM] = {};
+  uint i, n;
+
+  for (i = 0; i < MAX_SET; i++)
+  {
+    do n = bt_random() % MAX_NUM;
+    while (expected[n]);
+
+    hmap_set(&b, n);
+    expected[n] = 1;
+  }
+
+  hmap_check(&b);
+
+  for (i = 0; i < MAX_CLR; i++)
+  {
+    do n = bt_random() % MAX_NUM;
+    while (!expected[n]);
+
+    hmap_clear(&b, n);
+    expected[n] = 0;
+  }
+
+  hmap_check(&b);
+
+  for (i = 0; i < MAX_NUM; i++)
+    if (hmap_test(&b, i) != expected[i])
+      bt_abort_msg("Bitmap mismatch on %d (should be %d %d)", i, hmap_test(&b, i), expected[i]);
+
+  for (i = 0; 1; i++)
+  {
+    n = hmap_first_zero(&b);
+    bt_assert(n >= i);
+    bt_assert(n <= MAX_NUM);
+
+    for (; i < n; i++)
+      bt_assert(expected[i]);
+
+    if (n == MAX_NUM)
+      break;
+
+    bt_assert(!expected[i]);
+
+    hmap_set(&b, n);
+  }
+
+  hmap_check(&b);
+
+  return 1;
+}
+
+static int
+t_hmap_set_clear_fill(void)
+{
+  struct hmap b;
+
+  resource_init();
+  hmap_init(&b, &root_pool, 1024);
+
+  char expected[MAX_NUM] = {};
+  uint i, j, n, max = 0;
+
+  for (i = 0; i < STEP_NUM; i++)
+  {
+    uint last = 0;
+    uint step_set = bt_random() % STEP_SET;
+    uint step_clr = bt_random() % STEP_CLR;
+
+    for (j = 0; j < step_set; j++)
+    {
+      n = hmap_first_zero(&b);
+      bt_assert(n > last || !last);
+      bt_assert(n < MAX_NUM);
+
+      if (!last)
+	last = n;
+
+      for (; last < n; last++)
+	bt_assert(expected[last]);
+
+      bt_assert(!expected[n]);
+
+      hmap_set(&b, n);
+      expected[n] = 1;
+      max = MAX(max, n);
+    }
+
+    for (j = 0; j < step_clr; j++)
+    {
+      uint k = 0;
+      do n = bt_random() % max;
+      while (!expected[n] && (k++ < 8));
+
+      if (!expected[n])
+	continue;
+
+      hmap_clear(&b, n);
+      expected[n] = 0;
+    }
+  }
+
+  for (i = 0; i < MAX_NUM; i++)
+    if (hmap_test(&b, i) != expected[i])
+      bt_abort_msg("Bitmap mismatch on %d (should be %d %d)", i, hmap_test(&b, i), expected[i]);
+
+  hmap_check(&b);
+
+  return 1;
+}
+
+int
+main(int argc, char *argv[])
+{
+  bt_init(argc, argv);
+
+  bt_test_suite(t_bmap_set_clear_random, "BMap - random sequence of sets / clears");
+  bt_test_suite(t_hmap_set_clear_random, "HMap - random sequence of sets / clears");
+  bt_test_suite(t_hmap_set_clear_fill, "HMap - linear sets and random clears");
+
+  return bt_exit_value();
+}