Fixed a bug in Common::Array (including a unit test for it), and changed the way the internal storage growth over time.

The bug could result in incorrect results when using push_back (or insert_at)
to insert data from an array into itself if this insertions would cause the
internal array storage to grow. Also added a unit test for this bug.

Furthermore, if the internal storage needs to grow, it will now be resized to the next power of two,
instead of being increased by 32.

svn-id: r40907

2 files changed, 124 insertions, 23 deletions

diff --git a/common/array.h b/common/array.h
index 704254f692..7852cabf06 100644
--- a/common/array.h
+++ b/common/array.h
@@ -30,12 +30,33 @@
 
 namespace Common {
 
-// TODO: Improve the storage management of this class.
-// In particular, don't use new[] and delete[], but rather
-// construct/destruct objects manually. This way, we can
-// ensure that storage which is not currently used does not
-// correspond to a live active object.
-// (This is only of interest for array of non-POD objects).
+/**
+ * This class implements a dynamically sized container, which
+ * can be accessed similar to a regular C++ array. Accessing
+ * elements is performed in constant time (like with plain arrays).
+ * In addition, one can append, insert and remove entries (this
+ * is the 'dynamic' part). Doing that in general takes time
+ * proportional to the number of elements in the array.
+ *
+ * The container class closest to this in the C++ standard library is
+ * std::vector. However, there are some differences. The most important one is
+ * that std::vector has a far more sophisticated (and complicated) memory
+ * management scheme. There, only elements that 'live' are actually constructed
+ * (i.e., have their constructor called), and objects that are removed are
+ * immediately destructed (have their destructor called).
+ * With Common::Array, this is not the case; instead, it simply uses new[] and
+ * delete[] to allocate whole blocks of objects, possibly more than are
+ * currently 'alive'. This simplifies memory management, but may have
+ * undesirable side effects when one wants to use an Array of complex
+ * data types.
+ *
+ * @todo Improve the storage management of this class.
+ * In particular, don't use new[] and delete[], but rather
+ * construct/destruct objects manually. This way, we can
+ * ensure that storage which is not currently used does not
+ * correspond to a live active object.
+ * (This is only of interest for array of non-POD objects).
+ */
 template<class T>
 class Array {
 protected:
@@ -51,11 +72,13 @@ public:
 
 public:
 	Array() : _capacity(0), _size(0), _storage(0) {}
-	Array(const Array<T> &array) : _capacity(0), _size(0), _storage(0) {
-		_capacity = _size = array._size;
-		_storage = new T[_capacity];
-		assert(_storage);
-		copy(array._storage, array._storage + _size, _storage);
+
+	Array(const Array<T> &array) : _capacity(array._size), _size(array._size), _storage(0) {
+		if (array._storage) {
+			_storage = new T[_capacity];
+			assert(_storage);
+			copy(array._storage, array._storage + _size, _storage);
+		}
 	}
 
 	/**
@@ -77,14 +100,18 @@ public:
 
 	/** Appends element to the end of the array. */
 	void push_back(const T &element) {
-		ensureCapacity(_size + 1);
-		_storage[_size++] = element;
+		if (_size + 1 <= _capacity)
+			_storage[_size++] = element;
+		else
+			insert_aux(end(), &element, &element + 1);
 	}
 
 	void push_back(const Array<T> &array) {
-		ensureCapacity(_size + array._size);
-		copy(array._storage, array._storage + array._size, _storage + _size);
-		_size += array._size;
+		if (_size + array.size() <= _capacity) {
+			copy(array.begin(), array.end(), end());
+			_size += array.size();
+		} else
+			insert_aux(end(), array.begin(), array.end());
 	}
 
 	/** Removes the last element of the array. */
@@ -117,12 +144,10 @@ public:
 		return _storage[_size-1];
 	}
 
+
 	void insert_at(int idx, const T &element) {
 		assert(idx >= 0 && (uint)idx <= _size);
-		ensureCapacity(_size + 1);
-		copy_backward(_storage + idx, _storage + _size, _storage + _size + 1);
-		_storage[idx] = element;
-		_size++;
+		insert_aux(_storage + idx, &element, &element + 1);
 	}
 
 	T remove_at(int idx) {
@@ -215,10 +240,63 @@ public:
 	}
 
 protected:
-	void ensureCapacity(uint len) {
-		if (len >= _capacity)
-			reserve(len + 32);
+	static uint roundUpCapacity(uint capacity) {
+		// Round up capacity to the next power of 2;
+		// we use a minimal capacity of 8.
+		uint capa = 8;
+		while (capa < capacity)
+			capa <<= 1;
+		return capa;
 	}
+
+	/**
+	 * Insert a range of elements coming from this or another array.
+	 * Unlike std::vector::insert, this method does not accept
+	 * arbitrary iterators, mainly because our iterator system is
+	 * seriously limited and does not distinguish between input iterators,
+	 * output iterators, forward iterators or random access iterators.
+	 *
+	 * So, we simply restrict to Array iterators. Extending this to arbitrary
+	 * random access iterators would be trivial.
+	 *
+	 * Moreover, this method does not handle all cases of inserting a subrange
+	 * of an array into itself; this is why it is private for now.
+	 */
+	iterator insert_aux(iterator pos, const_iterator first, const_iterator last) {
+		assert(_storage <= pos && pos <= _storage + _size);
+		assert(first <= last);
+		const uint n = last - first;
+		if (n) {
+			const uint idx = pos - _storage;
+			T *newStorage = _storage;
+			if (_size + n > _capacity) {
+				// If there is not enough space, allocate more and
+				// copy old elements over.
+				uint newCapacity = roundUpCapacity(_size + n);
+				newStorage = new T[newCapacity]();
+				assert(newStorage);
+				copy(_storage, _storage + idx, newStorage);
+				pos = newStorage + idx;
+			}
+
+			// Make room for the new elements by shifting back
+			// existing ones.
+			copy_backward(_storage + idx, _storage + _size, newStorage + _size + n);
+
+			// Insert the new elements.
+			copy(first, last, pos);
+
+			// Finally, update the internal state
+			if (newStorage != _storage) {
+				delete[] _storage;
+				_capacity = roundUpCapacity(_size + n);
+				_storage = newStorage;
+			}
+			_size += n;
+		}
+		return pos;
+	}
+
 };
 
 } // End of namespace Common
diff --git a/test/common/array.h b/test/common/array.h
index cb793004a4..bce4e8cba1 100644
--- a/test/common/array.h
+++ b/test/common/array.h
@@ -124,6 +124,29 @@ class ArrayTestSuite : public CxxTest::TestSuite
 		TS_ASSERT_EQUALS(array2.size(), (unsigned int)3);
 	}
 
+	struct SafeInt {
+		int val;
+		SafeInt() : val(0) {}
+		SafeInt(int v) : val(v) {}
+		~SafeInt() { val = -1; }
+		bool operator==(int v) {
+			return val == v;
+		}
+	};
+
+	void test_push_back_ex() {
+		// This test makes sure that inserting an element invalidates
+		// references/iterators/pointers to elements in the array itself
+		// only *after* their value has been copied.
+		Common::Array<SafeInt> array;
+
+		array.push_back(42);
+		for (int i = 0; i < 40; ++i) {
+			array.push_back(array[0]);
+			TS_ASSERT_EQUALS(array[i], 42);
+		}
+	}
+
 	void test_copy_constructor() {
 		Common::Array<int> array1;