From af02b83b888c693c292960072195f0e1caf1d2a1 Mon Sep 17 00:00:00 2001
From: "Ondrej Zajicek (work)" <santiago@crfreenet.org>
Date: Mon, 9 Sep 2019 02:43:39 +0200
Subject: 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.
---
 lib/bitmap_test.c | 186 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 186 insertions(+)
 create mode 100644 lib/bitmap_test.c

(limited to 'lib/bitmap_test.c')

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();
+}
-- 
cgit v1.2.3