Lib: Basic and hierarchical bitmaps

Basic bitmap is obvious. Hierarchical bitmap is structure of several
bitmaps, where higher levels are conjunctions of intervals on level
below, allowing for efficient lookup of first unset bit.

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