From 88319a727a5adc4888ec17e5ee091e14ce176afd Mon Sep 17 00:00:00 2001
From: Max Horn
Date: Mon, 16 May 2011 15:23:09 +0200
Subject: COMMON: Fix inserting an array into itself under certain conditions

---
 common/array.h      |  5 ++++-
 test/common/array.h | 28 ++++++++++++++++++++++++++++
 2 files changed, 32 insertions(+), 1 deletion(-)

diff --git a/common/array.h b/common/array.h
index 87325d60d3..7ab4a1b042 100644
--- a/common/array.h
+++ b/common/array.h
@@ -293,9 +293,12 @@ protected:
 		if (n) {
 			const uint idx = pos - _storage;
 			T *oldStorage = _storage;
-			if (_size + n > _capacity) {
+			if (_size + n > _capacity || (_storage <= first && first <= _storage + _size) ) {
 				// If there is not enough space, allocate more and
 				// copy old elements over.
+				// Likewise, if this is a self-insert, we allocate new
+				// storage to avoid conflicts. This is not the most efficient
+				// way to ensure that, but probably the simplest on.
 				allocCapacity(roundUpCapacity(_size + n));
 				copy(oldStorage, oldStorage + idx, _storage);
 				pos = _storage + idx;
diff --git a/test/common/array.h b/test/common/array.h
index f17edd3984..c10270436f 100644
--- a/test/common/array.h
+++ b/test/common/array.h
@@ -107,6 +107,34 @@ class ArrayTestSuite : public CxxTest::TestSuite
 
 	}
 
+	void test_self_insert() {
+		Common::Array<int> array;
+		int i;
+
+		// Insert some data -- and make sure we have enough space for
+		// *twice* as much data. This way, there is no need to allocate
+		// new storage, so if the insert() operation is "clever", it
+		// will try to reuse the existing storage.
+		// This in turn may uncover bugs if the insertion code does not
+		// expect self-insertions.
+		array.reserve(128);
+		for (i = 0; i < 64; ++i)
+			array.push_back(i);
+
+		// Now insert the array into the middle of itself
+		array.insert_at(12, array);
+
+		// Verify integrity
+		TS_ASSERT_EQUALS(array.size(), 128UL);
+
+		for (i = 0; i < 12; ++i)
+			TS_ASSERT_EQUALS(array[i], i);
+		for (i = 0; i < 64; ++i)
+			TS_ASSERT_EQUALS(array[i+12], i);
+		for (i = 12; i < 64; ++i)
+			TS_ASSERT_EQUALS(array[i+64], i);
+	}
+
 
 	void test_remove_at() {
 		Common::Array<int> array;
-- 
cgit v1.2.3