COMMON: Improve storage management of Array.

Now our Array class distinguishs between initialized and uninitialized
objects. It furthermore always calls the destructor of no longer contained
elements. This should help with non-POD objects stored in our Array class.

Thanks to Bertrand for his feedback on this.

2 files changed, 137 insertions, 47 deletions

diff --git a/common/array.h b/common/array.h
index 18cecfb98f..ef0ee27f24 100644
--- a/common/array.h
+++ b/common/array.h
@@ -25,6 +25,7 @@
 #include "common/scummsys.h"
 #include "common/algorithm.h"
 #include "common/textconsole.h"	// For error()
+#include "common/memory.h"
 
 namespace Common {
 
@@ -37,23 +38,7 @@ namespace Common {
  * 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 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).
+ * std::vector. However, there are some differences.
  */
 template<class T>
 class Array {
@@ -74,7 +59,7 @@ public:
 	Array(const Array<T> &array) : _capacity(array._size), _size(array._size), _storage(0) {
 		if (array._storage) {
 			allocCapacity(_size);
-			copy(array._storage, array._storage + _size, _storage);
+			uninitialized_copy(array._storage, array._storage + _size, _storage);
 		}
 	}
 
@@ -85,11 +70,11 @@ public:
 	Array(const T2 *data, int n) {
 		_size = n;
 		allocCapacity(n);
-		copy(data, data + _size, _storage);
+		uninitialized_copy(data, data + _size, _storage);
 	}
 
 	~Array() {
-		delete[] _storage;
+		freeStorage(_storage, _size);
 		_storage = 0;
 		_capacity = _size = 0;
 	}
@@ -97,14 +82,14 @@ public:
 	/** Appends element to the end of the array. */
 	void push_back(const T &element) {
 		if (_size + 1 <= _capacity)
-			_storage[_size++] = element;
+			new ((void *)&_storage[_size++]) T(element);
 		else
 			insert_aux(end(), &element, &element + 1);
 	}
 
 	void push_back(const Array<T> &array) {
 		if (_size + array.size() <= _capacity) {
-			copy(array.begin(), array.end(), end());
+			uninitialized_copy(array.begin(), array.end(), end());
 			_size += array.size();
 		} else
 			insert_aux(end(), array.begin(), array.end());
@@ -114,6 +99,8 @@ public:
 	void pop_back() {
 		assert(_size > 0);
 		_size--;
+		// We also need to destroy the last object properly here.
+		_storage[_size].~T();
 	}
 
 	/** Returns a reference to the first element of the array. */
@@ -157,6 +144,8 @@ public:
 		T tmp = _storage[idx];
 		copy(_storage + idx + 1, _storage + _size, _storage + idx);
 		_size--;
+		// We also need to destroy the last object properly here.
+		_storage[_size].~T();
 		return tmp;
 	}
 
@@ -176,10 +165,10 @@ public:
 		if (this == &array)
 			return *this;
 
-		delete[] _storage;
+		freeStorage(_storage, _size);
 		_size = array._size;
 		allocCapacity(_size);
-		copy(array._storage, array._storage + _size, _storage);
+		uninitialized_copy(array._storage, array._storage + _size, _storage);
 
 		return *this;
 	}
@@ -189,7 +178,7 @@ public:
 	}
 
 	void clear() {
-		delete[] _storage;
+		freeStorage(_storage, _size);
 		_storage = 0;
 		_size = 0;
 		_capacity = 0;
@@ -240,15 +229,15 @@ public:
 
 		if (oldStorage) {
 			// Copy old data
-			copy(oldStorage, oldStorage + _size, _storage);
-			delete[] oldStorage;
+			uninitialized_copy(oldStorage, oldStorage + _size, _storage);
+			freeStorage(oldStorage, _size);
 		}
 	}
 
 	void resize(uint newSize) {
 		reserve(newSize);
 		for (uint i = _size; i < newSize; ++i)
-			_storage[i] = T();
+			new ((void *)&_storage[i]) T();
 		_size = newSize;
 	}
 
@@ -272,7 +261,7 @@ protected:
 	void allocCapacity(uint capacity) {
 		_capacity = capacity;
 		if (capacity) {
-			_storage = new T[capacity];
+			_storage = (T *)malloc(sizeof(T) * capacity);
 			if (!_storage)
 				::error("Common::Array: failure to allocate %u bytes", capacity * (uint)sizeof(T));
 		} else {
@@ -280,6 +269,12 @@ protected:
 		}
 	}
 
+	void freeStorage(T *storage, const uint elements) {
+		for (uint i = 0; i < elements; ++i)
+			storage[i].~T();
+		free(storage);
+	}
+
 	/**
 	 * Insert a range of elements coming from this or another array.
 	 * Unlike std::vector::insert, this method does not accept
@@ -299,29 +294,49 @@ protected:
 		const uint n = last - first;
 		if (n) {
 			const uint idx = pos - _storage;
-			T *oldStorage = _storage;
-			if (_size + n > _capacity || (_storage <= first && first <= _storage + _size) ) {
-				// If there is not enough space, allocate more and
-				// copy old elements over.
+			if (_size + n > _capacity || (_storage <= first && first <= _storage + _size)) {
+				T *const oldStorage = _storage;
+
+				// If there is not enough space, allocate more.
 				// 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.
+				// storage to avoid conflicts.
 				allocCapacity(roundUpCapacity(_size + n));
-				copy(oldStorage, oldStorage + idx, _storage);
-				pos = _storage + idx;
-			}
-
-			// Make room for the new elements by shifting back
-			// existing ones.
-			copy_backward(oldStorage + idx, oldStorage + _size, _storage + _size + n);
 
-			// Insert the new elements.
-			copy(first, last, pos);
+				// Copy the data from the old storage till the position where
+				// we insert new data
+				uninitialized_copy(oldStorage, oldStorage + idx, _storage);
+				// Copy the data we insert
+				uninitialized_copy(first, last, _storage + idx);
+				// Afterwards copy the old data from the position where we
+				// insert.
+				uninitialized_copy(oldStorage + idx, oldStorage + _size, _storage + idx + n);
+
+				freeStorage(oldStorage, _size);
+			} else if (idx + n <= _size) {
+				// Make room for the new elements by shifting back
+				// existing ones.
+				// 1. Move a part of the data to the uninitialized area
+				uninitialized_copy(_storage + _size - n, _storage + _size, _storage + _size);
+				// 2. Move a part of the data to the initialized area
+				copy_backward(pos, _storage + _size - n, _storage + _size);
+
+				// Insert the new elements.
+				copy(first, last, pos);
+			} else {
+				// Copy the old data from the position till the end to the new
+				// place.
+				uninitialized_copy(pos, _storage + _size, _storage + idx + n);
+
+				// Copy a part of the new data to the position inside the
+				// initialized space.
+				copy(first, first + (_size - idx), pos);
+				
+				// Copy a part of the new data to the position inside the
+				// uninitialized space.
+				uninitialized_copy(first + (_size - idx), last, _storage + _size);
+			}
 
 			// Finally, update the internal state
-			if (_storage != oldStorage) {
-				delete[] oldStorage;
-			}
 			_size += n;
 		}
 		return pos;
diff --git a/common/memory.h b/common/memory.h
new file mode 100644
index 0000000000..1870850d27
--- /dev/null
+++ b/common/memory.h
@@ -0,0 +1,75 @@
+/* ScummVM - Graphic Adventure Engine
+ *
+ * ScummVM is the legal property of its developers, whose names
+ * are too numerous to list here. Please refer to the COPYRIGHT
+ * file distributed with this source distribution.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef COMMON_MEMORY_H
+#define COMMON_MEMORY_H
+
+#include "common/scummsys.h"
+
+// FIXME: We sadly can't assume standard C++ headers to be present on every
+// system we support, so we should get rid of this. The solution should be to
+// write a simple placement new on our own. It might be noteworthy we can't
+// easily do that for systems which do have a <new>, since it might clash with
+// the default definition otherwise!
+// Symbian does not have <new> but the new operator 
+#if !defined(__SYMBIAN32__) 
+#include <new>
+#endif
+
+namespace Common {
+
+/**
+ * Copies data from the range [first, last) to [dst, dst + (last - first)).
+ * It requires the range [dst, dst + (last - first)) to be valid and
+ * uninitialized.
+ */
+template<class In, class Type>
+Type *uninitialized_copy(In first, In last, Type *dst) {
+	while (first != last)
+		new ((void *)dst++) Type(*first++);
+	return dst;
+}
+
+/**
+ * Initializes the memory [first, first + (last - first)) with the value x.
+ * It requires the range [first, first + (last - first)) to be valid and
+ * uninitialized.
+ */
+/*template<class Type, class Value>
+void uninitialized_fill(Type *first, Type *last, const Value &x) {
+	while (first != last)
+		new ((void *)first++) Type(x);
+}*/
+
+/**
+ * Initializes the memory [dst, dst + n) with the value x.
+ * It requires the range [dst, dst + n) to be valid and
+ * uninitialized.
+ */
+/*template<class Type, class Value>
+void uninitialized_fill_n(Type *dst, size_t n, const Value &x) {
+	while (n--)
+		new ((void *)dst++) Type(x);
+}*/
+
+} // End of namespace Common
+
+#endif