diff options
| -rw-r--r-- | common/array.h | 124 | ||||
| -rw-r--r-- | test/common/array.h | 23 |
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; |