diff options
Diffstat (limited to 'include/iprt/cpp/list.h')
| -rw-r--r-- | include/iprt/cpp/list.h | 506 |
1 files changed, 306 insertions, 200 deletions
diff --git a/include/iprt/cpp/list.h b/include/iprt/cpp/list.h index 97c1a193..ca8c8f3c 100644 --- a/include/iprt/cpp/list.h +++ b/include/iprt/cpp/list.h @@ -3,7 +3,7 @@ */ /* - * Copyright (C) 2011 Oracle Corporation + * Copyright (C) 2011-2013 Oracle Corporation * * This file is part of VirtualBox Open Source Edition (OSE), as * available from http://www.virtualbox.org. This file is free software; @@ -29,6 +29,7 @@ #include <iprt/cpp/meta.h> #include <iprt/mem.h> #include <iprt/string.h> /* for memcpy */ +#include <iprt/assert.h> #include <new> /* For std::bad_alloc */ @@ -133,16 +134,13 @@ class RTCListHelper public: static inline void set(T2 *p, size_t i, const T1 &v) { p[i] = v; } static inline T1 & at(T2 *p, size_t i) { return p[i]; } - static inline size_t find(T2 *p, const T1 &v, size_t cSize) + static inline size_t find(T2 *p, const T1 &v, size_t cElements) { - size_t i = 0; - while(i < cSize) - { + size_t i = cElements; + while (i-- > 0) if (p[i] == v) - break; - ++i; - } - return i; + return i; + return cElements; } static inline void copyTo(T2 *p, T2 *const p1 , size_t iTo, size_t cSize) { @@ -162,16 +160,13 @@ class RTCListHelper<T1, T1*> public: static inline void set(T1 **p, size_t i, const T1 &v) { p[i] = new T1(v); } static inline T1 & at(T1 **p, size_t i) { return *p[i]; } - static inline size_t find(T1 **p, const T1 &v, size_t cSize) + static inline size_t find(T1 **p, const T1 &v, size_t cElements) { - size_t i = 0; - while(i < cSize) - { + size_t i = cElements; + while (i-- > 0) if (*p[i] == v) - break; - ++i; - } - return i; + return i; + return cElements; } static inline void copyTo(T1 **p, T1 **const p1 , size_t iTo, size_t cSize) { @@ -179,10 +174,10 @@ public: p[iTo + i] = new T1(*p1[i]); } static inline void erase(T1 **p, size_t i) { delete p[i]; } - static inline void eraseRange(T1 **p, size_t cFrom, size_t cSize) + static inline void eraseRange(T1 **p, size_t iFrom, size_t cItems) { - for (size_t i = cFrom; i < cFrom + cSize; ++i) - delete p[i]; + while (cItems-- > 0) + delete p[iFrom++]; } }; @@ -194,15 +189,17 @@ public: template <class T, typename ITYPE, bool MT> class RTCListBase { - /** - * Traits + /** @name Traits. * * Defines the return type of most of the getter methods. If the internal * used type is a pointer, we return a reference. If not we return by * value. + * + * @{ */ typedef typename RTCIfPtr<ITYPE, T&, T>::result GET_RTYPE; typedef typename RTCIfPtr<ITYPE, const T&, T>::result GET_CRTYPE; + /** @} */ public: /** @@ -213,13 +210,13 @@ public: * @param cCapacitiy The initial capacity the list has. * @throws std::bad_alloc */ - RTCListBase(size_t cCapacity = DefaultCapacity) - : m_pArray(0) - , m_cSize(0) - , m_cCapacity(0) + RTCListBase(size_t cCapacity = kDefaultCapacity) + : m_pArray(0) + , m_cElements(0) + , m_cCapacity(0) { if (cCapacity > 0) - realloc_grow(cCapacity); + growArray(cCapacity); } /** @@ -232,13 +229,18 @@ public: * @throws std::bad_alloc */ RTCListBase(const RTCListBase<T, ITYPE, MT>& other) - : m_pArray(0) - , m_cSize(0) - , m_cCapacity(0) + : m_pArray(0) + , m_cElements(0) + , m_cCapacity(0) { - realloc_no_elements_clean(other.m_cSize); - RTCListHelper<T, ITYPE>::copyTo(m_pArray, other.m_pArray, 0, other.m_cSize); - m_cSize = other.m_cSize; + other.m_guard.enterRead(); + + size_t const cElementsOther = other.m_cElements; + resizeArrayNoErase(cElementsOther); + RTCListHelper<T, ITYPE>::copyTo(m_pArray, other.m_pArray, 0, cElementsOther); + m_cElements = cElementsOther; + + other.m_guard.leaveRead(); } /** @@ -246,16 +248,20 @@ public: */ ~RTCListBase() { - RTCListHelper<T, ITYPE>::eraseRange(m_pArray, 0, m_cSize); + RTCListHelper<T, ITYPE>::eraseRange(m_pArray, 0, m_cElements); if (m_pArray) + { RTMemFree(m_pArray); + m_pArray = NULL; + } + m_cElements = m_cCapacity = 0; } /** * Sets a new capacity within the list. * * If the new capacity is bigger than the old size, it will be simply - * preallocated more space for the new items. If the new capacity is + * preallocated more space for the new items. If the new capacity is * smaller than the previous size, items at the end of the list will be * deleted. * @@ -265,7 +271,7 @@ public: void setCapacity(size_t cCapacity) { m_guard.enterWrite(); - realloc(cCapacity); + resizeArray(cCapacity); m_guard.leaveWrite(); } @@ -274,26 +280,47 @@ public: * * @return The actual capacity. */ - size_t capacity() const { return m_cCapacity; } + size_t capacity() const + { + m_guard.enterRead(); + size_t cRet = m_cCapacity; + m_guard.leaveRead(); + return cRet; + } /** * Check if an list contains any items. * * @return True if there is more than zero items, false otherwise. */ - bool isEmpty() const { return m_cSize == 0; } + bool isEmpty() const + { + m_guard.enterRead(); + bool fEmpty = m_cElements == 0; + m_guard.leaveRead(); + return fEmpty; + } /** * Return the current count of elements within the list. * * @return The current element count. */ - size_t size() const { return m_cSize; } + size_t size() const + { + m_guard.enterRead(); + size_t cRet = m_cElements; + m_guard.leaveRead(); + return cRet; + } /** * Inserts an item to the list at position @a i. * - * @param i The position of the new item. + * @param i The position of the new item. The must be within or at the + * exact end of the list. Indexes specified beyond the end of + * the list will be changed to an append() operation and strict + * builds will raise an assert. * @param val The new item. * @return a reference to this list. * @throws std::bad_alloc @@ -301,13 +328,56 @@ public: RTCListBase<T, ITYPE, MT> &insert(size_t i, const T &val) { m_guard.enterWrite(); - if (m_cSize == m_cCapacity) - realloc_grow(m_cCapacity + DefaultCapacity); - memmove(&m_pArray[i + 1], &m_pArray[i], (m_cSize - i) * sizeof(ITYPE)); + + AssertMsgStmt(i <= m_cElements, ("i=%zu m_cElements=%zu\n", i, m_cElements), i = m_cElements); + + if (m_cElements == m_cCapacity) + growArray(m_cCapacity + kDefaultCapacity); + + memmove(&m_pArray[i + 1], &m_pArray[i], (m_cElements - i) * sizeof(ITYPE)); RTCListHelper<T, ITYPE>::set(m_pArray, i, val); - ++m_cSize; + ++m_cElements; + m_guard.leaveWrite(); + return *this; + } + + /** + * Inserts a list to the list at position @a i. + * + * @param i The position of the new item. The must be within or at the + * exact end of the list. Indexes specified beyond the end of + * the list will be changed to an append() operation and strict + * builds will raise an assert. + * @param other The other list. This MUST not be the same as the destination + * list, will assert and return without doing anything if this + * happens. + * @return a reference to this list. + * @throws std::bad_alloc + */ + RTCListBase<T, ITYPE, MT> &insert(size_t i, const RTCListBase<T, ITYPE, MT> &other) + { + AssertReturn(this != &other, *this); + + other.m_guard.enterRead(); + m_guard.enterWrite(); + + AssertMsgStmt(i <= m_cElements, ("i=%zu m_cElements=%zu\n", i, m_cElements), i = m_cElements); + size_t cElementsOther = other.m_cElements; + if (RT_LIKELY(cElementsOther > 0)) + { + if (m_cCapacity - m_cElements < cElementsOther) + growArray(m_cCapacity + (cElementsOther - (m_cCapacity - m_cElements))); + if (i < m_cElements) + memmove(&m_pArray[i + cElementsOther], &m_pArray[i], (m_cElements - i) * sizeof(ITYPE)); + + RTCListHelper<T, ITYPE>::copyTo(&m_pArray[i], other.m_pArray, 0, cElementsOther); + m_cElements += cElementsOther; + } + + m_guard.leaveWrite(); + other.m_guard.leaveRead(); return *this; } @@ -332,15 +402,7 @@ public: */ RTCListBase<T, ITYPE, MT> &prepend(const RTCListBase<T, ITYPE, MT> &other) { - m_guard.enterWrite(); - if (m_cCapacity - m_cSize < other.m_cSize) - realloc_grow(m_cCapacity + (other.m_cSize - (m_cCapacity - m_cSize))); - memmove(&m_pArray[other.m_cSize], &m_pArray[0], m_cSize * sizeof(ITYPE)); - RTCListHelper<T, ITYPE>::copyTo(m_pArray, other.m_pArray, 0, other.m_cSize); - m_cSize += other.m_cSize; - m_guard.leaveWrite(); - - return *this; + return insert(0, other); } /** @@ -353,10 +415,10 @@ public: RTCListBase<T, ITYPE, MT> &append(const T &val) { m_guard.enterWrite(); - if (m_cSize == m_cCapacity) - realloc_grow(m_cCapacity + DefaultCapacity); - RTCListHelper<T, ITYPE>::set(m_pArray, m_cSize, val); - ++m_cSize; + if (m_cElements == m_cCapacity) + growArray(m_cCapacity + kDefaultCapacity); + RTCListHelper<T, ITYPE>::set(m_pArray, m_cElements, val); + ++m_cElements; m_guard.leaveWrite(); return *this; @@ -365,28 +427,29 @@ public: /** * Append a list of type T to the list. * - * @param other The list to append. + * @param other The list to append. Must not be the same as the destination + * list, will assert and return without doing anything. * @return a reference to this list. * @throws std::bad_alloc */ RTCListBase<T, ITYPE, MT> &append(const RTCListBase<T, ITYPE, MT> &other) { + AssertReturn(this != &other, *this); + + other.m_guard.enterRead(); m_guard.enterWrite(); - if (RT_LIKELY(other.m_cSize > 0)) - { - if (m_cCapacity - m_cSize < other.m_cSize) - realloc_grow(m_cCapacity + (other.m_cSize - (m_cCapacity - m_cSize))); - RTCListHelper<T, ITYPE>::copyTo(m_pArray, other.m_pArray, m_cSize, other.m_cSize); - m_cSize += other.m_cSize; - } - m_guard.leaveWrite(); + insert(m_cElements, other); + + m_guard.leaveWrite(); + other.m_guard.leaveRead(); return *this; } /** - * Copy the items of the other list into this list. All previous items of - * this list are deleted. + * Copy the items of the other list into this list. + * + * All previous items of this list are deleted. * * @param other The list to copy. * @return a reference to this list. @@ -397,51 +460,61 @@ public: if (RT_UNLIKELY(this == &other)) return *this; + other.m_guard.enterRead(); m_guard.enterWrite(); + /* Delete all items. */ - RTCListHelper<T, ITYPE>::eraseRange(m_pArray, 0, m_cSize); + RTCListHelper<T, ITYPE>::eraseRange(m_pArray, 0, m_cElements); + /* Need we to realloc memory. */ - if (other.m_cSize != m_cCapacity) - realloc_no_elements_clean(other.m_cSize); - m_cSize = other.m_cSize; + if (other.m_cElements != m_cCapacity) + resizeArrayNoErase(other.m_cElements); + m_cElements = other.m_cElements; + /* Copy new items. */ - RTCListHelper<T, ITYPE>::copyTo(m_pArray, other.m_pArray, 0, other.m_cSize); - m_guard.leaveWrite(); + RTCListHelper<T, ITYPE>::copyTo(m_pArray, other.m_pArray, 0, other.m_cElements); + m_guard.leaveWrite(); + other.m_guard.leaveRead(); return *this; } /** * Replace an item in the list. * - * @note No boundary checks are done. Make sure @a i is equal or greater zero - * and smaller than RTCList::size. - * - * @param i The position of the item to replace. + * @param i The position of the item to replace. If this is out of range, + * the request will be ignored, strict builds will assert. * @param val The new value. * @return a reference to this list. */ RTCListBase<T, ITYPE, MT> &replace(size_t i, const T &val) { m_guard.enterWrite(); - RTCListHelper<T, ITYPE>::erase(m_pArray, i); - RTCListHelper<T, ITYPE>::set(m_pArray, i, val); - m_guard.leaveWrite(); + if (i < m_cElements) + { + RTCListHelper<T, ITYPE>::erase(m_pArray, i); + RTCListHelper<T, ITYPE>::set(m_pArray, i, val); + } + else + AssertMsgFailed(("i=%zu m_cElements=%zu\n", i, m_cElements)); + + m_guard.leaveWrite(); return *this; } /** * Return the first item as constant object. * - * @note No boundary checks are done. Make sure there is at least one - * element. + * @return A reference or pointer to the first item. * - * @return The first item. + * @note No boundary checks are done. Make sure there is at least one + * element. */ GET_CRTYPE first() const { m_guard.enterRead(); + Assert(m_cElements > 0); GET_CRTYPE res = RTCListHelper<T, ITYPE>::at(m_pArray, 0); m_guard.leaveRead(); return res; @@ -450,14 +523,15 @@ public: /** * Return the first item. * - * @note No boundary checks are done. Make sure there is at least one - * element. + * @return A reference or pointer to the first item. * - * @return The first item. + * @note No boundary checks are done. Make sure there is at least one + * element. */ GET_RTYPE first() { m_guard.enterRead(); + Assert(m_cElements > 0); GET_RTYPE res = RTCListHelper<T, ITYPE>::at(m_pArray, 0); m_guard.leaveRead(); return res; @@ -466,15 +540,16 @@ public: /** * Return the last item as constant object. * - * @note No boundary checks are done. Make sure there is at least one - * element. + * @return A reference or pointer to the last item. * - * @return The last item. + * @note No boundary checks are done. Make sure there is at least one + * element. */ GET_CRTYPE last() const { m_guard.enterRead(); - GET_CRTYPE res = RTCListHelper<T, ITYPE>::at(m_pArray, m_cSize - 1); + Assert(m_cElements > 0); + GET_CRTYPE res = RTCListHelper<T, ITYPE>::at(m_pArray, m_cElements - 1); m_guard.leaveRead(); return res; } @@ -482,15 +557,16 @@ public: /** * Return the last item. * - * @note No boundary checks are done. Make sure there is at least one - * element. + * @return A reference or pointer to the last item. * - * @return The last item. + * @note No boundary checks are done. Make sure there is at least one + * element. */ GET_RTYPE last() { m_guard.enterRead(); - GET_RTYPE res = RTCListHelper<T, ITYPE>::at(m_pArray, m_cSize - 1); + Assert(m_cElements > 0); + GET_RTYPE res = RTCListHelper<T, ITYPE>::at(m_pArray, m_cElements - 1); m_guard.leaveRead(); return res; } @@ -498,15 +574,16 @@ public: /** * Return the item at position @a i as constant object. * - * @note No boundary checks are done. Make sure @a i is equal or greater zero - * and smaller than RTCList::size. - * - * @param i The position of the item to return. + * @param i The position of the item to return. This better not be out of + * bounds, however should it be the last element of the array + * will be return and strict builds will raise an assertion. + * Should the array be empty, a crash is very likely. * @return The item at position @a i. */ GET_CRTYPE at(size_t i) const { m_guard.enterRead(); + AssertMsgStmt(i < m_cElements, ("i=%zu m_cElements=%zu\n", i, m_cElements), i = m_cElements - 1); GET_CRTYPE res = RTCListHelper<T, ITYPE>::at(m_pArray, i); m_guard.leaveRead(); return res; @@ -515,15 +592,16 @@ public: /** * Return the item at position @a i. * - * @note No boundary checks are done. Make sure @a i is equal or greater zero - * and smaller than RTCList::size. - * - * @param i The position of the item to return. + * @param i The position of the item to return. This better not be out of + * bounds, however should it be the last element of the array + * will be return and strict builds will raise an assertion. + * Should the array be empty, a crash is very likely. * @return The item at position @a i. */ GET_RTYPE at(size_t i) { m_guard.enterRead(); + AssertMsgStmt(i < m_cElements, ("i=%zu m_cElements=%zu\n", i, m_cElements), i = m_cElements - 1); GET_RTYPE res = RTCListHelper<T, ITYPE>::at(m_pArray, i); m_guard.leaveRead(); return res; @@ -532,31 +610,31 @@ public: /** * Return the item at position @a i as mutable reference. * - * @note No boundary checks are done. Make sure @a i is equal or greater zero - * and smaller than RTCList::size. - * - * @param i The position of the item to return. + * @param i The position of the item to return. This better not be out of + * bounds, however should it be the last element of the array + * will be return and strict builds will raise an assertion. + * Should the array be empty, a crash is very likely. * @return The item at position @a i. */ T &operator[](size_t i) { m_guard.enterRead(); + AssertMsgStmt(i < m_cElements, ("i=%zu m_cElements=%zu\n", i, m_cElements), i = m_cElements - 1); T &res = RTCListHelper<T, ITYPE>::at(m_pArray, i); m_guard.leaveRead(); return res; } /** - * Return the item at position @a i. If @a i isn't valid within the list a - * default value is returned. + * Return the item at position @a i or default value if out of range. * * @param i The position of the item to return. - * @return The item at position @a i. + * @return The item at position @a i or default value. */ T value(size_t i) const { m_guard.enterRead(); - if (RT_UNLIKELY(i >= m_cSize)) + if (RT_UNLIKELY(i >= m_cElements)) { m_guard.leaveRead(); return T(); @@ -567,17 +645,16 @@ public: } /** - * Return the item at position @a i. If @a i isn't valid within the list - * @a defaultVal is returned. + * Return the item at position @a i, or @a defaultVal if out of range. * * @param i The position of the item to return. * @param defaultVal The value to return in case @a i is invalid. - * @return The item at position @a i. + * @return The item at position @a i or @a defaultVal. */ T value(size_t i, const T &defaultVal) const { m_guard.enterRead(); - if (RT_UNLIKELY(i >= m_cSize)) + if (RT_UNLIKELY(i >= m_cElements)) { m_guard.leaveRead(); return defaultVal; @@ -596,16 +673,16 @@ public: bool contains(const T &val) const { m_guard.enterRead(); - bool res = RTCListHelper<T, ITYPE>::find(m_pArray, val, m_cSize) != m_cSize; + bool fRc = RTCListHelper<T, ITYPE>::find(m_pArray, val, m_cElements) < m_cElements; m_guard.leaveRead(); - return res; + return fRc; } /** * Remove the first item. * - * @note No boundary checks are done. Make sure there is at least one - * element. + * @note You should make sure the list isn't empty. Strict builds will assert. + * The other builds will quietly ignore the request. */ void removeFirst() { @@ -615,51 +692,52 @@ public: /** * Remove the last item. * - * @note No boundary checks are done. Make sure there is at least one - * element. + * @note You should make sure the list isn't empty. Strict builds will assert. + * The other builds will quietly ignore the request. */ void removeLast() { - removeAt(m_cSize - 1); + m_guard.enterWrite(); + removeAtLocked(m_cElements - 1); + m_guard.leaveWrite(); } /** * Remove the item at position @a i. * - * @note No boundary checks are done. Make sure @a i is equal or greater zero - * and smaller than RTCList::size. - * - * @param i The position of the item to remove. + * @param i The position of the item to remove. Out of bounds values will + * be ignored and an assertion will be raised in strict builds. */ void removeAt(size_t i) { m_guard.enterWrite(); - RTCListHelper<T, ITYPE>::erase(m_pArray, i); - /* Not last element? */ - if (i < m_cSize - 1) - memmove(&m_pArray[i], &m_pArray[i + 1], (m_cSize - i - 1) * sizeof(ITYPE)); - --m_cSize; + removeAtLocked(i); m_guard.leaveWrite(); } /** * Remove a range of items from the list. * - * @note No boundary checks are done. Make sure @a iFrom is equal or - * greater zero and smaller than RTCList::size. @a iTo has to be - * greater than @a iFrom and equal or smaller than RTCList::size. - * - * @param iFrom The start position of the items to remove. - * @param iTo The end position of the items to remove (excluded). + * @param iStart The start position of the items to remove. + * @param iEnd The end position of the items to remove (excluded). */ - void removeRange(size_t iFrom, size_t iTo) + void removeRange(size_t iStart, size_t iEnd) { + AssertReturnVoid(iStart <= iEnd); m_guard.enterWrite(); - RTCListHelper<T, ITYPE>::eraseRange(m_pArray, iFrom, iTo - iFrom); - /* Not last elements? */ - if (m_cSize - iTo > 0) - memmove(&m_pArray[iFrom], &m_pArray[iTo], (m_cSize - iTo) * sizeof(ITYPE)); - m_cSize -= iTo - iFrom; + + AssertMsgStmt(iEnd <= m_cElements, ("iEnd=%zu m_cElements=%zu\n", iEnd, m_cElements), iEnd = m_cElements); + AssertMsgStmt(iStart < m_cElements, ("iStart=%zu m_cElements=%zu\n", iStart, m_cElements), iStart = m_cElements); + size_t const cElements = iEnd - iStart; + if (cElements > 0) + { + Assert(iStart < m_cElements); + RTCListHelper<T, ITYPE>::eraseRange(m_pArray, iStart, cElements); + if (m_cElements > iEnd) + memmove(&m_pArray[iStart], &m_pArray[iEnd], (m_cElements - iEnd) * sizeof(ITYPE)); + m_cElements -= cElements; + } + m_guard.leaveWrite(); } @@ -669,18 +747,21 @@ public: void clear() { m_guard.enterWrite(); + /* Values cleanup */ - RTCListHelper<T, ITYPE>::eraseRange(m_pArray, 0, m_cSize); - if (m_cSize != DefaultCapacity) - realloc_no_elements_clean(DefaultCapacity); - m_cSize = 0; + RTCListHelper<T, ITYPE>::eraseRange(m_pArray, 0, m_cElements); + if (m_cElements != kDefaultCapacity) + resizeArrayNoErase(kDefaultCapacity); + m_cElements = 0; + m_guard.leaveWrite(); } /** - * Return the raw array. For native types this is a pointer to continuous - * memory of the items. For pointer types this is a continuous memory of - * pointers to the items. + * Return the raw array. + * + * For native types this is a pointer to continuous memory of the items. For + * pointer types this is a continuous memory of pointers to the items. * * @warning If you change anything in the underlaying list, this memory * will very likely become invalid. So take care when using this @@ -688,12 +769,12 @@ public: * * @returns the raw memory. */ - ITYPE* raw() const + ITYPE *raw() const { m_guard.enterRead(); - ITYPE* res = m_pArray; + ITYPE *pRet = m_pArray; m_guard.leaveRead(); - return res; + return pRet; } RTCListBase<T, ITYPE, MT> &operator<<(const T &val) @@ -707,89 +788,114 @@ public: /** * The default capacity of the list. This is also used as grow factor. */ - static const size_t DefaultCapacity; + static const size_t kDefaultCapacity; protected: /** - * Generic realloc, which does some kind of boundary checking. + * Generic resizes the array, surplus elements are erased. + * + * @param cElementsNew The new array size. + * @throws std::bad_alloc. */ - void realloc(size_t cNewSize) + void resizeArray(size_t cElementsNew) { /* Same size? */ - if (cNewSize == m_cCapacity) + if (cElementsNew == m_cCapacity) return; /* If we get smaller we have to delete some of the objects at the end of the list. */ - if ( cNewSize < m_cSize + if ( cElementsNew < m_cElements && m_pArray) - RTCListHelper<T, ITYPE>::eraseRange(m_pArray, cNewSize, m_cSize - cNewSize); - realloc_no_elements_clean(cNewSize); + RTCListHelper<T, ITYPE>::eraseRange(m_pArray, cElementsNew, m_cElements - cElementsNew); + + resizeArrayNoErase(cElementsNew); } - void realloc_no_elements_clean(size_t cNewSize) + /** + * Resizes the array without doing the erase() thing on surplus elements. + * + * @param cElementsNew The new array size. + * @throws std::bad_alloc. + */ + void resizeArrayNoErase(size_t cElementsNew) { /* Same size? */ - if (cNewSize == m_cCapacity) + if (cElementsNew == m_cCapacity) return; - /* If we get smaller we have to delete some of the objects at the end - of the list. */ - if ( cNewSize < m_cSize - && m_pArray) - m_cSize -= m_cSize - cNewSize; - - /* If we get zero we delete the array it self. */ - if ( cNewSize == 0 - && m_pArray) - { - RTMemFree(m_pArray); - m_pArray = 0; - } - m_cCapacity = cNewSize; - /* Resize the array. */ - if (cNewSize > 0) + if (cElementsNew > 0) { - m_pArray = static_cast<ITYPE*>(RTMemRealloc(m_pArray, sizeof(ITYPE) * cNewSize)); - if (!m_pArray) + void *pvNew = RTMemRealloc(m_pArray, sizeof(ITYPE) * cElementsNew); + if (!pvNew) { - /** @todo you leak memory. */ - m_cCapacity = 0; - m_cSize = 0; #ifdef RT_EXCEPTIONS_ENABLED throw std::bad_alloc(); #endif + return; } + m_pArray = static_cast<ITYPE*>(pvNew); + } + /* If we get zero we delete the array it self. */ + else if (m_pArray) + { + RTMemFree(m_pArray); + m_pArray = NULL; } + + m_cCapacity = cElementsNew; + if (m_cElements > cElementsNew) + m_cElements = cElementsNew; } /** * Special realloc method which require that the array will grow. * + * @param cElementsNew The new array size. + * @throws std::bad_alloc. * @note No boundary checks are done! */ - void realloc_grow(size_t cNewSize) + void growArray(size_t cElementsNew) { - /* Resize the array. */ - m_cCapacity = cNewSize; - m_pArray = static_cast<ITYPE*>(RTMemRealloc(m_pArray, sizeof(ITYPE) * cNewSize)); - if (!m_pArray) + Assert(cElementsNew > m_cCapacity); + void *pvNew = RTMemRealloc(m_pArray, sizeof(ITYPE) * cElementsNew); + if (pvNew) + { + m_cCapacity = cElementsNew; + m_pArray = static_cast<ITYPE*>(pvNew); + } + else { - /** @todo you leak memory. */ - m_cCapacity = 0; - m_cSize = 0; #ifdef RT_EXCEPTIONS_ENABLED throw std::bad_alloc(); #endif } } + /** + * Remove the item at position @a i. + * + * @param i The position of the item to remove. Out of bounds values will + * be ignored and an assertion will be raised in strict builds. + * @remarks + */ + void removeAtLocked(size_t i) + { + AssertMsgReturnVoid(i < m_cElements, ("i=%zu m_cElements=%zu\n", i, m_cElements)); + + RTCListHelper<T, ITYPE>::erase(m_pArray, i); + if (i < m_cElements - 1) + memmove(&m_pArray[i], &m_pArray[i + 1], (m_cElements - i - 1) * sizeof(ITYPE)); + --m_cElements; + } + + /** The internal list array. */ ITYPE *m_pArray; /** The current count of items in use. */ - size_t m_cSize; + size_t m_cElements; /** The current capacity of the internal array. */ size_t m_cCapacity; /** The guard used to serialize the access to the items. */ @@ -797,7 +903,7 @@ protected: }; template <class T, typename ITYPE, bool MT> -const size_t RTCListBase<T, ITYPE, MT>::DefaultCapacity = 10; +const size_t RTCListBase<T, ITYPE, MT>::kDefaultCapacity = 10; /** * Template class which automatically determines the type of list to use. @@ -819,11 +925,11 @@ public: * @param cCapacitiy The initial capacity the list has. * @throws std::bad_alloc */ - RTCList(size_t cCapacity = BASE::DefaultCapacity) - : BASE(cCapacity) {} + RTCList(size_t cCapacity = BASE::kDefaultCapacity) + : BASE(cCapacity) {} RTCList(const BASE &other) - : BASE(other) {} + : BASE(other) {} /* Define our own new and delete. */ RTMEMEF_NEW_AND_DELETE_OPERATORS(); @@ -850,8 +956,8 @@ public: * @param cCapacitiy The initial capacity the list has. * @throws std::bad_alloc */ - RTCList(size_t cCapacity = BASE::DefaultCapacity) - : BASE(cCapacity) {} + RTCList(size_t cCapacity = BASE::kDefaultCapacity) + : BASE(cCapacity) {} /* Define our own new and delete. */ RTMEMEF_NEW_AND_DELETE_OPERATORS(); @@ -878,8 +984,8 @@ public: * @param cCapacitiy The initial capacity the list has. * @throws std::bad_alloc */ - RTCList(size_t cCapacity = BASE::DefaultCapacity) - : BASE(cCapacity) {} + RTCList(size_t cCapacity = BASE::kDefaultCapacity) + : BASE(cCapacity) {} /* Define our own new and delete. */ RTMEMEF_NEW_AND_DELETE_OPERATORS(); |