Fix the instancing maintenance

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()