1 files changed, 62 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;