[Scummvm-cvs-logs] SF.net SVN: scummvm:[40907] scummvm/trunk
fingolfin at users.sourceforge.net
fingolfin at users.sourceforge.net
Tue May 26 13:28:40 CEST 2009
Revision: 40907
http://scummvm.svn.sourceforge.net/scummvm/?rev=40907&view=rev
Author: fingolfin
Date: 2009-05-26 11:28:38 +0000 (Tue, 26 May 2009)
Log Message:
-----------
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.
Modified Paths:
--------------
scummvm/trunk/common/array.h
scummvm/trunk/test/common/array.h
Modified: scummvm/trunk/common/array.h
===================================================================
--- scummvm/trunk/common/array.h 2009-05-26 10:14:24 UTC (rev 40906)
+++ scummvm/trunk/common/array.h 2009-05-26 11:28:38 UTC (rev 40907)
@@ -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:
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 @@
/** 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 @@
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 @@
}
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
Modified: scummvm/trunk/test/common/array.h
===================================================================
--- scummvm/trunk/test/common/array.h 2009-05-26 10:14:24 UTC (rev 40906)
+++ scummvm/trunk/test/common/array.h 2009-05-26 11:28:38 UTC (rev 40907)
@@ -124,6 +124,29 @@
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;
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
More information about the Scummvm-git-logs
mailing list