diff options
Diffstat (limited to 'common/array.h')
-rw-r--r-- | common/array.h | 109 |
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; |