aboutsummaryrefslogtreecommitdiffstats
path: root/tests
diff options
context:
space:
mode:
Diffstat (limited to 'tests')
-rw-r--r--tests/gui/quadtree.cc127
-rw-r--r--tests/ice40/hx1k.cc2
-rw-r--r--tests/ice40/hx8k.cc2
-rw-r--r--tests/ice40/lp1k.cc2
-rw-r--r--tests/ice40/lp384.cc2
-rw-r--r--tests/ice40/lp8k.cc2
-rw-r--r--tests/ice40/up5k.cc2
7 files changed, 133 insertions, 6 deletions
diff --git a/tests/gui/quadtree.cc b/tests/gui/quadtree.cc
new file mode 100644
index 00000000..083a0057
--- /dev/null
+++ b/tests/gui/quadtree.cc
@@ -0,0 +1,127 @@
+/*
+ * nextpnr -- Next Generation Place and Route
+ *
+ * Copyright (C) 2018 Serge Bazanski <q3k@symbioticeda.com>
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ */
+
+#include "gtest/gtest.h"
+#include "nextpnr.h"
+#include "quadtree.h"
+
+USING_NEXTPNR_NAMESPACE
+
+using QT = QuadTree<int, int>;
+
+class QuadTreeTest : public ::testing::Test
+{
+ protected:
+ virtual void SetUp()
+ {
+ qt_ = new QT(QT::BoundingBox(0, 0, width_, height_));
+ }
+ virtual void TearDown()
+ {
+ delete qt_;
+ }
+
+ int width_ = 100;
+ int height_ = 100;
+ QT *qt_;
+};
+
+// Test that we're doing bound checking correctly.
+TEST_F(QuadTreeTest, insert_bound_checking)
+{
+ ASSERT_TRUE(qt_->insert(QT::BoundingBox(10, 10, 20, 20), 10));
+ ASSERT_TRUE(qt_->insert(QT::BoundingBox(0, 0, 100, 100), 10));
+ ASSERT_FALSE(qt_->insert(QT::BoundingBox(10, 10, 101, 20), 10));
+ ASSERT_FALSE(qt_->insert(QT::BoundingBox(-1, 10, 101, 20), 10));
+ ASSERT_FALSE(qt_->insert(QT::BoundingBox(-1, -1, 20, 20), 10));
+}
+
+// Test whether we are not losing any elements.
+TEST_F(QuadTreeTest, insert_count)
+{
+ auto rng = NEXTPNR_NAMESPACE::DeterministicRNG();
+
+ // Add 10000 random rectangles.
+ for (unsigned int i = 0; i < 10000; i++) {
+ int x0 = rng.rng(width_);
+ int y0 = rng.rng(height_);
+ int w = rng.rng(width_ - x0);
+ int h = rng.rng(width_ - y0);
+ int x1 = x0 + w;
+ int y1 = y0 + h;
+ ASSERT_TRUE(qt_->insert(QT::BoundingBox(x0, y0, x1, y1), i));
+ ASSERT_EQ(qt_->size(), i+1);
+ }
+ // Add 100000 random points.
+ for (unsigned int i = 0; i < 100000; i++) {
+ int x0 = rng.rng(width_);
+ int y0 = rng.rng(height_);
+ int x1 = x0;
+ int y1 = y0;
+ ASSERT_TRUE(qt_->insert(QT::BoundingBox(x0, y0, x1, y1), i));
+ ASSERT_EQ(qt_->size(), i+10001);
+ }
+}
+
+// Test that we can insert and retrieve the same element.
+TEST_F(QuadTreeTest, insert_retrieve_same)
+{
+ auto rng = NEXTPNR_NAMESPACE::DeterministicRNG();
+
+ // Add 10000 small random rectangles.
+ rng.rngseed(0);
+ for (int i = 0; i < 10000; i++) {
+ int x0 = rng.rng(width_);
+ int y0 = rng.rng(height_);
+ int w = rng.rng(width_ - x0);
+ int h = rng.rng(width_ - y0);
+ int x1 = x0 + w/4;
+ int y1 = y0 + h/4;
+ ASSERT_TRUE(qt_->insert(QT::BoundingBox(x0, y0, x1, y1), i));
+ }
+
+ // Restart RNG, make sure we get the same rectangles back.
+ rng.rngseed(0);
+ for (int i = 0; i < 10000; i++) {
+ int x0 = rng.rng(width_);
+ int y0 = rng.rng(height_);
+ int w = rng.rng(width_ - x0);
+ int h = rng.rng(width_ - y0);
+ int x1 = x0 + w/4;
+ int y1 = y0 + h/4;
+
+ // try to find something in the middle of the square
+ int x = (x1-x0)/2+x0;
+ int y = (y1-y0)/2+y0;
+
+ auto res = qt_->get(x, y);
+ // Somewhat arbirary test to make sure we don't return obscene
+ // amounts of data.
+ ASSERT_LT(res.size(), 200UL);
+ bool found = false;
+ for (auto elem : res) {
+ // Is this what we're looking for?
+ if (elem == i) {
+ found = true;
+ break;
+ }
+ }
+ ASSERT_TRUE(found);
+ }
+}
diff --git a/tests/ice40/hx1k.cc b/tests/ice40/hx1k.cc
index 6c3205f3..b7990a82 100644
--- a/tests/ice40/hx1k.cc
+++ b/tests/ice40/hx1k.cc
@@ -59,7 +59,7 @@ TEST_F(HX1KTest, wire_names)
assert(wire == ctx->getWireByName(name));
wire_count++;
}
- ASSERT_EQ(wire_count, 27682);
+ ASSERT_EQ(wire_count, 27690);
}
TEST_F(HX1KTest, pip_names)
diff --git a/tests/ice40/hx8k.cc b/tests/ice40/hx8k.cc
index 485a2d31..d5b489eb 100644
--- a/tests/ice40/hx8k.cc
+++ b/tests/ice40/hx8k.cc
@@ -59,7 +59,7 @@ TEST_F(HX8KTest, wire_names)
assert(wire == ctx->getWireByName(name));
wire_count++;
}
- ASSERT_EQ(wire_count, 135174);
+ ASSERT_EQ(wire_count, 135182);
}
TEST_F(HX8KTest, pip_names)
diff --git a/tests/ice40/lp1k.cc b/tests/ice40/lp1k.cc
index b1092700..b258d115 100644
--- a/tests/ice40/lp1k.cc
+++ b/tests/ice40/lp1k.cc
@@ -59,7 +59,7 @@ TEST_F(LP1KTest, wire_names)
assert(wire == ctx->getWireByName(name));
wire_count++;
}
- ASSERT_EQ(wire_count, 27682);
+ ASSERT_EQ(wire_count, 27690);
}
TEST_F(LP1KTest, pip_names)
diff --git a/tests/ice40/lp384.cc b/tests/ice40/lp384.cc
index 287293d9..a2d91e7d 100644
--- a/tests/ice40/lp384.cc
+++ b/tests/ice40/lp384.cc
@@ -59,7 +59,7 @@ TEST_F(LP384Test, wire_names)
assert(wire == ctx->getWireByName(name));
wire_count++;
}
- ASSERT_EQ(wire_count, 8294);
+ ASSERT_EQ(wire_count, 8302);
}
TEST_F(LP384Test, pip_names)
diff --git a/tests/ice40/lp8k.cc b/tests/ice40/lp8k.cc
index efe61b5b..a1c8c88c 100644
--- a/tests/ice40/lp8k.cc
+++ b/tests/ice40/lp8k.cc
@@ -59,7 +59,7 @@ TEST_F(LP8KTest, wire_names)
assert(wire == ctx->getWireByName(name));
wire_count++;
}
- ASSERT_EQ(wire_count, 135174);
+ ASSERT_EQ(wire_count, 135182);
}
TEST_F(LP8KTest, pip_names)
diff --git a/tests/ice40/up5k.cc b/tests/ice40/up5k.cc
index 342a7c0a..6761db2e 100644
--- a/tests/ice40/up5k.cc
+++ b/tests/ice40/up5k.cc
@@ -59,7 +59,7 @@ TEST_F(UP5KTest, wire_names)
assert(wire == ctx->getWireByName(name));
wire_count++;
}
- ASSERT_EQ(wire_count, 103383);
+ ASSERT_EQ(wire_count, 103391);
}
TEST_F(UP5KTest, pip_names)