summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--gfx/gl/instanceVertices.h83
-rw-r--r--test/test-instancing.cpp105
2 files changed, 152 insertions, 36 deletions
diff --git a/gfx/gl/instanceVertices.h b/gfx/gl/instanceVertices.h
index c2ddb1d..036b48e 100644
--- a/gfx/gl/instanceVertices.h
+++ b/gfx/gl/instanceVertices.h
@@ -32,37 +32,38 @@ public:
InstanceProxy &
operator=(InstanceProxy && other)
{
+ if (instances) {
+ instances->release(*this);
+ }
instances = std::exchange(other.instances, nullptr);
index = other.index;
+ return *this;
+ }
+ template<typename U>
+ T &
+ operator=(U && v)
+ {
+ return instances->at(index) = std::forward<U>(v);
}
operator T &()
{
- return *get();
+ return instances->at(index);
}
operator const T &() const
{
- return *get();
- }
- template<typename U>
- T &
- operator=(U && v)
- {
- instances->map();
- return instances->data[index] = std::forward<U>(v);
+ return instances->at(index);
}
T *
get()
{
- instances->map();
- return &instances->data[index];
+ return &instances->at(index);
}
const T *
get() const
{
- instances->map();
- return &instances->data[index];
+ return &instances->at(index);
}
T *
operator->()
@@ -77,12 +78,12 @@ public:
T &
operator*()
{
- return *get();
+ return instances->at(index);
}
const T &
operator*() const
{
- return *get();
+ return instances->at(index);
}
private:
@@ -100,22 +101,16 @@ public:
if (!unused.empty()) {
auto idx = unused.back();
unused.pop_back();
- new (data + idx) T(std::forward<Params>(params)...);
+ index[idx] = next++;
+ new (&at(idx)) T(std::forward<Params>(params)...);
return InstanceProxy {this, idx};
}
if (next >= capacity) {
resize(capacity * 2);
}
- new (data + next) T(std::forward<Params>(params)...);
- return InstanceProxy {this, next++};
- }
-
- void
- release(const InstanceProxy & p)
- {
- map();
- data[p.index].~T();
- unused.push_back(p.index);
+ index.emplace_back(next++);
+ new (data + index.back()) T(std::forward<Params>(params)...);
+ return InstanceProxy {this, index.size() - 1};
}
const auto &
@@ -136,6 +131,30 @@ protected:
friend InstanceProxy;
void
+ release(const InstanceProxy & p)
+ {
+ // Destroy p's object
+ at(p.index).~T();
+ if (next-- > index[p.index]) {
+ // Remember p.index is free index now
+ unused.push_back(p.index);
+ // Move last object into p's slot
+ new (&at(p.index)) T {std::move(data[next])};
+ (data[next]).~T();
+ for (auto & i : index) {
+ if (i == next) {
+ i = index[p.index];
+ break;
+ }
+ }
+ index[p.index] = 100000;
+ }
+ else {
+ index.pop_back();
+ }
+ }
+
+ void
allocBuffer(std::size_t newCapacity)
{
glBindBuffer(GL_ARRAY_BUFFER, buffer);
@@ -160,6 +179,13 @@ protected:
capacity = newCapacity;
}
+ T &
+ at(size_t pindex)
+ {
+ map();
+ return data[index[pindex]];
+ }
+
void
map() const
{
@@ -179,7 +205,12 @@ protected:
glBuffer buffer;
mutable T * data {};
+ // Size of buffer
std::size_t capacity {};
+ // # used of capacity
std::size_t next {};
+ // Index into buffer given to nth proxy
+ std::vector<size_t> index;
+ // List of free spaces in index
std::vector<size_t> unused;
};
diff --git a/test/test-instancing.cpp b/test/test-instancing.cpp
index 2eb3647..8837071 100644
--- a/test/test-instancing.cpp
+++ b/test/test-instancing.cpp
@@ -1,10 +1,12 @@
#define BOOST_TEST_MODULE instancing
+#include "stream_support.hpp"
#include "testHelpers.h"
#include "testMainWindow.h"
#include "ui/applicationBase.h"
#include <boost/test/data/test_case.hpp>
#include <boost/test/unit_test.hpp>
+#include <set>
#include <gfx/gl/instanceVertices.h>
@@ -20,28 +22,25 @@ BOOST_AUTO_TEST_CASE(createDestroy)
BOOST_REQUIRE(data);
BOOST_CHECK_EQUAL(0, next);
BOOST_CHECK(unused.empty());
+ BOOST_CHECK(index.empty());
unmap();
BOOST_CHECK(!data);
}
-BOOST_AUTO_TEST_CASE(storeRetreive)
-{ // Read write raw buffer, not normally allowed
- std::vector<int> test(capacity);
- map();
- std::copy(test.begin(), test.end(), data);
- BOOST_CHECK_EQUAL_COLLECTIONS(test.begin(), test.end(), data, data + capacity);
-}
-
BOOST_AUTO_TEST_CASE(acquireRelease)
{
{
auto proxy = acquire();
*proxy = 20;
BOOST_CHECK_EQUAL(1, next);
+ BOOST_REQUIRE_EQUAL(1, index.size());
+ BOOST_CHECK_EQUAL(0, index.front());
+ BOOST_CHECK(unused.empty());
}
- BOOST_CHECK_EQUAL(1, next);
+ BOOST_CHECK_EQUAL(0, next);
BOOST_CHECK_EQUAL(1, unused.size());
BOOST_CHECK_EQUAL(0, unused.front());
+ BOOST_CHECK_EQUAL(1, index.size());
}
BOOST_AUTO_TEST_CASE(acquireReleaseMove)
@@ -54,9 +53,10 @@ BOOST_AUTO_TEST_CASE(acquireReleaseMove)
*proxy2 = 40;
BOOST_CHECK_EQUAL(1, next);
}
- BOOST_CHECK_EQUAL(1, next);
+ BOOST_CHECK_EQUAL(0, next);
BOOST_CHECK_EQUAL(1, unused.size());
BOOST_CHECK_EQUAL(0, unused.front());
+ BOOST_CHECK_EQUAL(1, index.size());
}
BOOST_AUTO_TEST_CASE(initialize)
@@ -78,4 +78,89 @@ BOOST_AUTO_TEST_CASE(resize)
BOOST_CHECK_EQUAL_COLLECTIONS(expected.begin(), expected.end(), proxies.begin(), proxies.end());
}
+BOOST_AUTO_TEST_CASE(shuffle)
+{
+ std::vector<decltype(acquire())> proxies;
+ BOOST_CHECK_EQUAL(0, proxies.emplace_back(acquire(0)));
+ BOOST_CHECK_EQUAL(1, proxies.emplace_back(acquire(1)));
+ BOOST_CHECK_EQUAL(2, proxies.emplace_back(acquire(2)));
+ BOOST_CHECK_EQUAL(3, proxies.emplace_back(acquire(3)));
+ BOOST_CHECK_EQUAL(4, next);
+ BOOST_CHECK_EQUAL(data + 0, proxies[0].get());
+ BOOST_CHECK_EQUAL(data + 1, proxies[1].get());
+ BOOST_CHECK_EQUAL(data + 2, proxies[2].get());
+ BOOST_CHECK_EQUAL(data + 3, proxies[3].get());
+ BOOST_CHECK(unused.empty());
+ BOOST_REQUIRE_EQUAL(4, index.size());
+ BOOST_CHECK_EQUAL(0, index[0]);
+ BOOST_CHECK_EQUAL(1, index[1]);
+ BOOST_CHECK_EQUAL(2, index[2]);
+ BOOST_CHECK_EQUAL(3, index[3]);
+ // Remove 1, 3 moves to [1]
+ proxies.erase(proxies.begin() + 1);
+ BOOST_REQUIRE_EQUAL(4, index.size());
+ BOOST_REQUIRE_EQUAL(1, unused.size());
+ BOOST_CHECK_EQUAL(1, unused[0]);
+ BOOST_CHECK_EQUAL(data + 0, proxies[0].get());
+ BOOST_CHECK_EQUAL(data + 2, proxies[1].get());
+ BOOST_CHECK_EQUAL(data + 1, proxies[2].get());
+ // Remove 1, 2 moves to [1]
+ proxies.erase(proxies.begin() + 1);
+ BOOST_REQUIRE_EQUAL(4, index.size());
+ BOOST_REQUIRE_EQUAL(2, unused.size());
+ BOOST_CHECK_EQUAL(1, unused[0]);
+ BOOST_CHECK_EQUAL(2, unused[1]);
+ BOOST_CHECK_EQUAL(data + 0, proxies[0].get());
+ BOOST_CHECK_EQUAL(data + 1, proxies[1].get());
+ // Add new, takes 2 at [2]
+ BOOST_CHECK_EQUAL(4, proxies.emplace_back(acquire(4)));
+ BOOST_REQUIRE_EQUAL(4, index.size());
+ BOOST_REQUIRE_EQUAL(1, unused.size());
+ BOOST_CHECK_EQUAL(1, unused[0]);
+ BOOST_CHECK_EQUAL(data + 0, proxies[0].get());
+ BOOST_CHECK_EQUAL(data + 1, proxies[1].get());
+ BOOST_CHECK_EQUAL(data + 2, proxies[2].get());
+}
+
+BOOST_DATA_TEST_CASE(shuffle_random, boost::unit_test::data::xrange(0, 10), x)
+{
+ std::ignore = x;
+ std::mt19937 gen(std::random_device {}());
+ std::map<int, InstanceVertices<int>::InstanceProxy> proxies;
+ const std::string_view actions = "aaaaaaaarararrraarrrararararaarrrarararararararararraarrrraaaarararaararar";
+ int n {};
+ for (const auto action : actions) {
+ switch (action) {
+ case 'a':
+ BOOST_REQUIRE_EQUAL(n, proxies.emplace(n, acquire(n)).first->second);
+ n++;
+ break;
+ case 'r':
+ BOOST_REQUIRE(!proxies.empty());
+ auto e = std::next(proxies.begin(),
+ std::uniform_int_distribution<> {0, static_cast<int>(proxies.size() - 1)}(gen));
+ proxies.erase(e);
+ break;
+ }
+
+ BOOST_REQUIRE_EQUAL(next, proxies.size());
+ for (const auto & [n, p] : proxies) {
+ BOOST_REQUIRE_EQUAL(n, p);
+ }
+ std::set<size_t> iused;
+ for (size_t i {}; i < index.size(); i++) {
+ if (std::find(unused.begin(), unused.end(), i) == unused.end()) {
+ iused.emplace(index[i]);
+ }
+ }
+ BOOST_TEST_CONTEXT(index) {
+ BOOST_REQUIRE_EQUAL(iused.size(), next);
+ if (!iused.empty()) {
+ BOOST_REQUIRE_EQUAL(*iused.begin(), 0);
+ BOOST_REQUIRE_EQUAL(*iused.rbegin(), next - 1);
+ }
+ }
+ }
+}
+
BOOST_AUTO_TEST_SUITE_END()
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-10 14:42:46 +0000