Index: /trunk/include/VBox/com/list.h =================================================================== --- /trunk/include/VBox/com/list.h (revision 45519) +++ /trunk/include/VBox/com/list.h (revision 45520) @@ -5,5 +5,5 @@ /* - * Copyright (C) 2011 Oracle Corporation + * Copyright (C) 2011-2013 Oracle Corporation * * This file is part of VirtualBox Open Source Edition (OSE), as @@ -30,5 +30,7 @@ #include #include +#include #include + /** @@ -55,6 +57,6 @@ * @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. */ @@ -85,6 +87,6 @@ * @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. */ @@ -98,8 +100,8 @@ */ template <> -class RTCList: public RTCListBase +class RTCList: public RTCListBase { /* Traits */ - typedef Utf8Str T; + typedef com::Utf8Str T; typedef T *ITYPE; static const bool MT = false; @@ -115,6 +117,6 @@ * @throws std::bad_alloc */ - RTCList(size_t cCapacity = BASE::DefaultCapacity) - : BASE(cCapacity) {} + RTCList(size_t cCapacity = BASE::kDefaultCapacity) + : BASE(cCapacity) {} /** @@ -131,7 +133,8 @@ { com::SafeArray sfaOther(ComSafeArrayInArg(other)); - realloc(sfaOther.size()); - m_cSize = sfaOther.size(); - for (size_t i = 0; i < m_cSize; ++i) + size_t const cElementsOther = sfaOther.size(); + resizeArray(cElementsOther); + m_cElements = cElementsOther; + for (size_t i = 0; i < cElementsOther; ++i) RTCListHelper::set(m_pArray, i, T(sfaOther[i])); } @@ -148,7 +151,7 @@ */ RTCList(const com::SafeArray &other) - : BASE(other.size()) - { - for (size_t i = 0; i < m_cSize; ++i) + : BASE(other.size()) + { + for (size_t i = 0; i < m_cElements; ++i) RTCListHelper::set(m_pArray, i, T(other[i])); } @@ -165,14 +168,17 @@ { m_guard.enterWrite(); + /* Values cleanup */ - RTCListHelper::eraseRange(m_pArray, 0, m_cSize); + RTCListHelper::eraseRange(m_pArray, 0, m_cElements); + /* Copy */ - if (other.size() != m_cCapacity) - realloc_no_elements_clean(other.size()); - m_cSize = other.size(); - for (size_t i = 0; i < other.size(); ++i) + size_t cElementsOther = other.size(); + if (cElementsOther != m_cCapacity) + resizeArrayNoErase(cElementsOther); + m_cElements = cElementsOther; + for (size_t i = 0; i < cElementsOther; ++i) RTCListHelper::set(m_pArray, i, T(other[i])); + m_guard.leaveWrite(); - return *this; } Index: /trunk/include/VBox/com/mtlist.h =================================================================== --- /trunk/include/VBox/com/mtlist.h (revision 45519) +++ /trunk/include/VBox/com/mtlist.h (revision 45520) @@ -5,5 +5,5 @@ /* - * Copyright (C) 2011 Oracle Corporation + * Copyright (C) 2011-2013 Oracle Corporation * * This file is part of VirtualBox Open Source Edition (OSE), as @@ -30,4 +30,5 @@ #include #include +#include #include @@ -55,6 +56,6 @@ * @throws std::bad_alloc */ - RTCList(size_t cCapacity = BASE::DefaultCapacity) - : BASE(cCapacity) {} + RTCMTList(size_t cCapacity = BASE::kDefaultCapacity) + : BASE(cCapacity) {} /* Define our own new and delete. */ @@ -85,5 +86,5 @@ * @throws std::bad_alloc */ - RTCList(size_t cCapacity = BASE::DefaultCapacity) + RTCMTList(size_t cCapacity = BASE::kDefaultCapacity) : BASE(cCapacity) {} @@ -98,8 +99,8 @@ */ template <> -class RTCMTList: public RTCListBase +class RTCMTList: public RTCListBase { /* Traits */ - typedef Utf8Str T; + typedef com::Utf8Str T; typedef T *ITYPE; static const bool MT = true; @@ -115,6 +116,6 @@ * @throws std::bad_alloc */ - RTCMTList(size_t cCapacity = BASE::DefaultCapacity) - : BASE(cCapacity) {} + RTCMTList(size_t cCapacity = BASE::kDefaultCapacity) + : BASE(cCapacity) {} /** @@ -131,7 +132,8 @@ { com::SafeArray sfaOther(ComSafeArrayInArg(other)); - realloc(sfaOther.size()); - m_cSize = sfaOther.size(); - for (size_t i = 0; i < m_cSize; ++i) + size_t const cElementsOther = sfaOther.size(); + resizeArray(cElementsOther); + m_cElements = cElementsOther; + for (size_t i = 0; i < cElementsOther; ++i) RTCListHelper::set(m_pArray, i, T(sfaOther[i])); } @@ -150,5 +152,5 @@ : BASE(other.size()) { - for (size_t i = 0; i < m_cSize; ++i) + for (size_t i = 0; i < m_cElements; ++i) RTCListHelper::set(m_pArray, i, T(other[i])); } @@ -166,9 +168,9 @@ m_guard.enterWrite(); /* Values cleanup */ - RTCListHelper::eraseRange(m_pArray, 0, m_cSize); + RTCListHelper::eraseRange(m_pArray, 0, m_cElements); /* Copy */ if (other.size() != m_cCapacity) - realloc_no_elements_clean(other.size()); - m_cSize = other.size(); + resizeArrayNoErase(other.size()); + m_cElements = other.size(); for (size_t i = 0; i < other.size(); ++i) RTCListHelper::set(m_pArray, i, T(other[i])); Index: /trunk/include/iprt/cpp/list.h =================================================================== --- /trunk/include/iprt/cpp/list.h (revision 45519) +++ /trunk/include/iprt/cpp/list.h (revision 45520) @@ -4,5 +4,5 @@ /* - * Copyright (C) 2011 Oracle Corporation + * Copyright (C) 2011-2013 Oracle Corporation * * This file is part of VirtualBox Open Source Edition (OSE), as @@ -30,4 +30,5 @@ #include #include /* for memcpy */ +#include #include /* For std::bad_alloc */ @@ -134,14 +135,11 @@ 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) - { - size_t i = 0; - while(i < cSize) - { + static inline size_t find(T2 *p, const T1 &v, size_t cElements) + { + 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) @@ -163,14 +161,11 @@ 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) - { - size_t i = 0; - while(i < cSize) - { + static inline size_t find(T1 **p, const T1 &v, size_t cElements) + { + 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) @@ -180,8 +175,8 @@ } static inline void erase(T1 **p, size_t i) { delete p[i]; } - static inline void eraseRange(T1 **p, size_t cFrom, size_t cSize) - { - for (size_t i = cFrom; i < cFrom + cSize; ++i) - delete p[i]; + static inline void eraseRange(T1 **p, size_t iFrom, size_t cItems) + { + while (cItems-- > 0) + delete p[iFrom++]; } }; @@ -195,13 +190,15 @@ 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::result GET_RTYPE; typedef typename RTCIfPtr::result GET_CRTYPE; + /** @} */ public: @@ -214,11 +211,11 @@ * @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); } @@ -233,11 +230,16 @@ */ RTCListBase(const RTCListBase& other) - : m_pArray(0) - , m_cSize(0) - , m_cCapacity(0) - { - realloc_no_elements_clean(other.m_cSize); - RTCListHelper::copyTo(m_pArray, other.m_pArray, 0, other.m_cSize); - m_cSize = other.m_cSize; + : m_pArray(0) + , m_cElements(0) + , m_cCapacity(0) + { + other.m_guard.enterRead(); + + size_t const cElementsOther = other.m_cElements; + resizeArrayNoErase(cElementsOther); + RTCListHelper::copyTo(m_pArray, other.m_pArray, 0, cElementsOther); + m_cElements = cElementsOther; + + other.m_guard.leaveRead(); } @@ -247,7 +249,11 @@ ~RTCListBase() { - RTCListHelper::eraseRange(m_pArray, 0, m_cSize); + RTCListHelper::eraseRange(m_pArray, 0, m_cElements); if (m_pArray) + { RTMemFree(m_pArray); + m_pArray = NULL; + } + m_cElements = m_cCapacity = 0; } @@ -256,5 +262,5 @@ * * 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. @@ -266,5 +272,5 @@ { m_guard.enterWrite(); - realloc(cCapacity); + resizeArray(cCapacity); m_guard.leaveWrite(); } @@ -275,5 +281,11 @@ * @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; + } /** @@ -282,5 +294,11 @@ * @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; + } /** @@ -289,10 +307,19 @@ * @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. @@ -302,11 +329,54 @@ { 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::set(m_pArray, i, val); - ++m_cSize; - m_guard.leaveWrite(); - + ++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 &insert(size_t i, const RTCListBase &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::copyTo(&m_pArray[i], other.m_pArray, 0, cElementsOther); + m_cElements += cElementsOther; + } + + m_guard.leaveWrite(); + other.m_guard.leaveRead(); return *this; } @@ -333,13 +403,5 @@ RTCListBase &prepend(const RTCListBase &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::copyTo(m_pArray, other.m_pArray, 0, other.m_cSize); - m_cSize += other.m_cSize; - m_guard.leaveWrite(); - - return *this; + return insert(0, other); } @@ -354,8 +416,8 @@ { m_guard.enterWrite(); - if (m_cSize == m_cCapacity) - realloc_grow(m_cCapacity + DefaultCapacity); - RTCListHelper::set(m_pArray, m_cSize, val); - ++m_cSize; + if (m_cElements == m_cCapacity) + growArray(m_cCapacity + kDefaultCapacity); + RTCListHelper::set(m_pArray, m_cElements, val); + ++m_cElements; m_guard.leaveWrite(); @@ -366,5 +428,6 @@ * 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 @@ -372,20 +435,20 @@ RTCListBase &append(const RTCListBase &other) { - 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::copyTo(m_pArray, other.m_pArray, m_cSize, other.m_cSize); - m_cSize += other.m_cSize; - } - m_guard.leaveWrite(); - + AssertReturn(this != &other, *this); + + other.m_guard.enterRead(); + m_guard.enterWrite(); + + 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. @@ -398,15 +461,20 @@ return *this; - m_guard.enterWrite(); + other.m_guard.enterRead(); + m_guard.enterWrite(); + /* Delete all items. */ - RTCListHelper::eraseRange(m_pArray, 0, m_cSize); + RTCListHelper::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::copyTo(m_pArray, other.m_pArray, 0, other.m_cSize); - m_guard.leaveWrite(); - + RTCListHelper::copyTo(m_pArray, other.m_pArray, 0, other.m_cElements); + + m_guard.leaveWrite(); + other.m_guard.leaveRead(); return *this; } @@ -415,8 +483,6 @@ * 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. @@ -425,8 +491,14 @@ { m_guard.enterWrite(); - RTCListHelper::erase(m_pArray, i); - RTCListHelper::set(m_pArray, i, val); - m_guard.leaveWrite(); - + + if (i < m_cElements) + { + RTCListHelper::erase(m_pArray, i); + RTCListHelper::set(m_pArray, i, val); + } + else + AssertMsgFailed(("i=%zu m_cElements=%zu\n", i, m_cElements)); + + m_guard.leaveWrite(); return *this; } @@ -435,12 +507,13 @@ * Return the first item as constant object. * - * @note No boundary checks are done. Make sure there is at least one - * element. - * - * @return The first item. + * @return A reference or pointer to 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::at(m_pArray, 0); m_guard.leaveRead(); @@ -451,12 +524,13 @@ * Return the first item. * - * @note No boundary checks are done. Make sure there is at least one - * element. - * - * @return The first item. + * @return A reference or pointer to 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::at(m_pArray, 0); m_guard.leaveRead(); @@ -467,13 +541,14 @@ * Return the last item as constant object. * - * @note No boundary checks are done. Make sure there is at least one - * element. - * - * @return The last item. + * @return A reference or pointer to 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::at(m_pArray, m_cSize - 1); + Assert(m_cElements > 0); + GET_CRTYPE res = RTCListHelper::at(m_pArray, m_cElements - 1); m_guard.leaveRead(); return res; @@ -483,13 +558,14 @@ * Return the last item. * - * @note No boundary checks are done. Make sure there is at least one - * element. - * - * @return The last item. + * @return A reference or pointer to 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::at(m_pArray, m_cSize - 1); + Assert(m_cElements > 0); + GET_RTYPE res = RTCListHelper::at(m_pArray, m_cElements - 1); m_guard.leaveRead(); return res; @@ -499,8 +575,8 @@ * 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. */ @@ -508,4 +584,5 @@ { m_guard.enterRead(); + AssertMsgStmt(i < m_cElements, ("i=%zu m_cElements=%zu\n", i, m_cElements), i = m_cElements - 1); GET_CRTYPE res = RTCListHelper::at(m_pArray, i); m_guard.leaveRead(); @@ -516,8 +593,8 @@ * 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. */ @@ -525,4 +602,5 @@ { m_guard.enterRead(); + AssertMsgStmt(i < m_cElements, ("i=%zu m_cElements=%zu\n", i, m_cElements), i = m_cElements - 1); GET_RTYPE res = RTCListHelper::at(m_pArray, i); m_guard.leaveRead(); @@ -533,8 +611,8 @@ * 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. */ @@ -542,4 +620,5 @@ { m_guard.enterRead(); + AssertMsgStmt(i < m_cElements, ("i=%zu m_cElements=%zu\n", i, m_cElements), i = m_cElements - 1); T &res = RTCListHelper::at(m_pArray, i); m_guard.leaveRead(); @@ -548,14 +627,13 @@ /** - * 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(); @@ -568,15 +646,14 @@ /** - * 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(); @@ -597,7 +674,7 @@ { m_guard.enterRead(); - bool res = RTCListHelper::find(m_pArray, val, m_cSize) != m_cSize; - m_guard.leaveRead(); - return res; + bool fRc = RTCListHelper::find(m_pArray, val, m_cElements) < m_cElements; + m_guard.leaveRead(); + return fRc; } @@ -605,6 +682,6 @@ * 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() @@ -616,10 +693,12 @@ * 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(); } @@ -627,17 +706,11 @@ * 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::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(); } @@ -646,19 +719,24 @@ * 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). - */ - void removeRange(size_t iFrom, size_t iTo) - { - m_guard.enterWrite(); - RTCListHelper::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; + * @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 iStart, size_t iEnd) + { + AssertReturnVoid(iStart <= iEnd); + m_guard.enterWrite(); + + 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::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(); } @@ -670,16 +748,19 @@ { m_guard.enterWrite(); + /* Values cleanup */ - RTCListHelper::eraseRange(m_pArray, 0, m_cSize); - if (m_cSize != DefaultCapacity) - realloc_no_elements_clean(DefaultCapacity); - m_cSize = 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. + RTCListHelper::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. * * @warning If you change anything in the underlaying list, this memory @@ -689,10 +770,10 @@ * @returns the raw memory. */ - ITYPE* raw() const - { - m_guard.enterRead(); - ITYPE* res = m_pArray; - m_guard.leaveRead(); - return res; + ITYPE *raw() const + { + m_guard.enterRead(); + ITYPE *pRet = m_pArray; + m_guard.leaveRead(); + return pRet; } @@ -708,60 +789,64 @@ * 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. - */ - void realloc(size_t cNewSize) + * Generic resizes the array, surplus elements are erased. + * + * @param cElementsNew The new array size. + * @throws std::bad_alloc. + */ + 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::eraseRange(m_pArray, cNewSize, m_cSize - cNewSize); - realloc_no_elements_clean(cNewSize); - } - - void realloc_no_elements_clean(size_t cNewSize) + RTCListHelper::eraseRange(m_pArray, cElementsNew, m_cElements - cElementsNew); + + resizeArrayNoErase(cElementsNew); + } + + /** + * 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) + /* Resize the array. */ + if (cElementsNew > 0) { - RTMemFree(m_pArray); - m_pArray = 0; - } - m_cCapacity = cNewSize; - - /* Resize the array. */ - if (cNewSize > 0) - { - m_pArray = static_cast(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(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; } @@ -769,16 +854,19 @@ * 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) - { - /* Resize the array. */ - m_cCapacity = cNewSize; - m_pArray = static_cast(RTMemRealloc(m_pArray, sizeof(ITYPE) * cNewSize)); - if (!m_pArray) + void growArray(size_t cElementsNew) + { + Assert(cElementsNew > m_cCapacity); + void *pvNew = RTMemRealloc(m_pArray, sizeof(ITYPE) * cElementsNew); + if (pvNew) { - /** @todo you leak memory. */ - m_cCapacity = 0; - m_cSize = 0; + m_cCapacity = cElementsNew; + m_pArray = static_cast(pvNew); + } + else + { #ifdef RT_EXCEPTIONS_ENABLED throw std::bad_alloc(); @@ -787,8 +875,26 @@ } + /** + * 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::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; @@ -798,5 +904,5 @@ template -const size_t RTCListBase::DefaultCapacity = 10; +const size_t RTCListBase::kDefaultCapacity = 10; /** @@ -820,9 +926,9 @@ * @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. */ @@ -851,6 +957,6 @@ * @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. */ @@ -879,6 +985,6 @@ * @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. */ Index: /trunk/include/iprt/cpp/mtlist.h =================================================================== --- /trunk/include/iprt/cpp/mtlist.h (revision 45519) +++ /trunk/include/iprt/cpp/mtlist.h (revision 45520) @@ -4,5 +4,5 @@ /* - * Copyright (C) 2011 Oracle Corporation + * Copyright (C) 2011-2013 Oracle Corporation * * This file is part of VirtualBox Open Source Edition (OSE), as @@ -28,5 +28,4 @@ #include - #include @@ -42,6 +41,24 @@ { public: - RTCListGuard() { int rc = RTSemRWCreate(&m_hRWSem); AssertRC(rc); } - ~RTCListGuard() { RTSemRWDestroy(m_hRWSem); } + RTCListGuard() : m_hRWSem(NIL_RTSEMRW) + { +#if defined(RT_LOCK_STRICT_ORDER) && defined(IN_RING3) + RTLOCKVALCLASS hClass; + int rc = RTLockValidatorClassCreate(&hClass, true /*fAutodidact*/, RT_SRC_POS, "RTCListGuard"); + AssertStmt(RT_SUCCESS(rc), hClass = NIL_RTLOCKVALCLASS); + rc = RTSemRWCreateEx(&m_hRWSem, 0 /*fFlags*/, hClass, RTLOCKVAL_SUB_CLASS_NONE, NULL /*pszNameFmt*/); + AssertRC(rc); +#else + int rc = RTSemRWCreateEx(&m_hRWSem, 0 /*fFlags*/, NIL_RTLOCKVALCLASS, 0, NULL); + AssertRC(rc); +#endif + } + + ~RTCListGuard() + { + RTSemRWDestroy(m_hRWSem); + m_hRWSem = NIL_RTSEMRW; + } + inline void enterRead() const { int rc = RTSemRWRequestRead(m_hRWSem, RT_INDEFINITE_WAIT); AssertRC(rc); } inline void leaveRead() const { int rc = RTSemRWReleaseRead(m_hRWSem); AssertRC(rc); } @@ -87,6 +104,6 @@ * @throws std::bad_alloc */ - RTCMTList(size_t cCapacity = BASE::DefaultCapacity) - : BASE(cCapacity) {} + RTCMTList(size_t cCapacity = BASE::kDefaultCapacity) + : BASE(cCapacity) {} /* Define our own new and delete. */ @@ -115,6 +132,6 @@ * @throws std::bad_alloc */ - RTCMTList(size_t cCapacity = BASE::DefaultCapacity) - : BASE(cCapacity) {} + RTCMTList(size_t cCapacity = BASE::kDefaultCapacity) + : BASE(cCapacity) {} /* Define our own new and delete. */ @@ -143,6 +160,6 @@ * @throws std::bad_alloc */ - RTCMTList(size_t cCapacity = BASE::DefaultCapacity) - : BASE(cCapacity) {} + RTCMTList(size_t cCapacity = BASE::kDefaultCapacity) + : BASE(cCapacity) {} /* Define our own new and delete. */ Index: /trunk/src/VBox/Runtime/testcase/tstIprtList.cpp =================================================================== --- /trunk/src/VBox/Runtime/testcase/tstIprtList.cpp (revision 45519) +++ /trunk/src/VBox/Runtime/testcase/tstIprtList.cpp (revision 45520) @@ -34,4 +34,5 @@ #include #include +#include @@ -166,5 +167,5 @@ L testList; - const size_t defCap = L::DefaultCapacity; + const size_t defCap = L::kDefaultCapacity; RTTESTI_CHECK(testList.isEmpty()); RTTESTI_CHECK(testList.size() == 0); @@ -376,11 +377,114 @@ RTTESTI_CHECK(testList5.capacity() == 0); + /* + * Negative testing. + */ + bool fMayPanic = RTAssertMayPanic(); + bool fQuiet = RTAssertAreQuiet(); + RTAssertSetMayPanic(false); + RTAssertSetQuiet(true); + + L testList6; + for (size_t i = 0; i < cTestItems; ++i) + testList6.insert(i, paTestData[i]); + RTTESTI_CHECK(testList6.size() == cTestItems); + + /* Insertion beyond the end of the array ends up at the end. */ + size_t cBefore = testList6.size(); + testList6.insert(cBefore + 3, paTestData[0]); + RTTESTI_CHECK(testList6.size() == cBefore + 1); + RTTESTI_CHECK(testList6.at(cBefore) == paTestData[0]); + + cBefore = testList6.size(); + L testList7(testList6); + testList6.insert(testList6.size() + 42, testList7); + RTTESTI_CHECK(testList6.size() == cBefore + testList7.size()); + + /* Inserting, appending or prepending a list to itself is not supported. */ + cBefore = testList6.size(); + testList6.insert(3, testList6); + RTTESTI_CHECK(testList6.size() == cBefore); + + cBefore = testList6.size(); + testList6.append(testList6); + RTTESTI_CHECK(testList6.size() == cBefore); + + cBefore = testList6.size(); + testList6.prepend(testList6); + RTTESTI_CHECK(testList6.size() == cBefore); + + /* Replace does nothing if the index is bad. */ + cBefore = testList6.size(); + testList6.replace(cBefore, testList6[6]); + RTTESTI_CHECK(testList6.size() == cBefore); + + cBefore = testList6.size(); + testList6.replace(cBefore + 64, testList6[6]); + RTTESTI_CHECK(testList6.size() == cBefore); + + /* Indexing beyond the array returns the last element. */ + cBefore = testList6.size(); + RTTESTI_CHECK(testList6[cBefore] == testList6.last()); + RTTESTI_CHECK(testList6[cBefore + 42] == testList6.last()); + + RTTESTI_CHECK(&testList6[cBefore] == &testList6[cBefore - 1]); + RTTESTI_CHECK(&testList6[cBefore + 42] == &testList6[cBefore - 1]); + + /* removeAt does nothing if the index is bad. */ + cBefore = testList6.size(); + testList6.removeAt(cBefore); + RTTESTI_CHECK(testList6.size() == cBefore); + + cBefore = testList6.size(); + testList6.removeAt(cBefore + 42); + RTTESTI_CHECK(testList6.size() == cBefore); + + L testListEmpty1; RTTESTI_CHECK(!testListEmpty1.size()); + testListEmpty1.removeFirst(); + RTTESTI_CHECK(!testListEmpty1.size()); + + testListEmpty1.removeLast(); + RTTESTI_CHECK(!testListEmpty1.size()); + + testListEmpty1.removeAt(128); + RTTESTI_CHECK(!testListEmpty1.size()); + + /* removeRange interprets indexes beyond the end as the end of array (asserted). */ + testListEmpty1.removeRange(42, 128); + RTTESTI_CHECK(!testListEmpty1.size()); + + cBefore = testList6.size(); + testList6.removeRange(cBefore, cBefore); + RTTESTI_CHECK(testList6.size() == cBefore); + + cBefore = testList6.size(); + testList6.removeRange(cBefore + 12, cBefore + 128); + RTTESTI_CHECK(testList6.size() == cBefore); + + /* If end is less or equal to the start, nothing is done. */ + testListEmpty1.removeRange(128, 0); + RTTESTI_CHECK(!testListEmpty1.size()); + + cBefore = testList6.size(); + testList6.removeRange(cBefore, 0); + RTTESTI_CHECK(testList6.size() == cBefore); + + cBefore = testList6.size(); + testList6.removeRange(0, 0); + RTTESTI_CHECK(testList6.size() == cBefore); + + cBefore = testList6.size(); + testList6.removeRange(0, 0); + RTTESTI_CHECK(testList6.size() == cBefore); + + RTAssertSetQuiet(fQuiet); + RTAssertSetMayPanic(fMayPanic); } /* define RTCList here to see what happens without MT support ;) * (valgrind is the preferred tool to check). */ -#define MTTESTLISTTYPE RTCMTList -#define MTTESTTYPE uint32_t -#define MTTESTITEMS 1000 +#define MTTESTLISTTYPE RTCMTList +#define MTTESTTYPE uint32_t +#define MTTESTITEMS 1000 /** @@ -390,5 +494,5 @@ * @param pvUser The provided user data. */ -DECLCALLBACK(int) mttest1(RTTHREAD hSelf, void *pvUser) +static DECLCALLBACK(int) MtTest1ThreadProc(RTTHREAD hSelf, void *pvUser) { MTTESTLISTTYPE *pTestList = (MTTESTLISTTYPE *)pvUser; @@ -407,5 +511,5 @@ * @param pvUser The provided user data. */ -DECLCALLBACK(int) mttest2(RTTHREAD hSelf, void *pvUser) +static DECLCALLBACK(int) MtTest2ThreadProc(RTTHREAD hSelf, void *pvUser) { MTTESTLISTTYPE *pTestList = (MTTESTLISTTYPE *)pvUser; @@ -424,5 +528,5 @@ * @param pvUser The provided user data. */ -DECLCALLBACK(int) mttest3(RTTHREAD hSelf, void *pvUser) +static DECLCALLBACK(int) MtTest3ThreadProc(RTTHREAD hSelf, void *pvUser) { MTTESTLISTTYPE *pTestList = (MTTESTLISTTYPE *)pvUser; @@ -441,5 +545,5 @@ * @param pvUser The provided user data. */ -DECLCALLBACK(int) mttest4(RTTHREAD hSelf, void *pvUser) +static DECLCALLBACK(int) MtTest4ThreadProc(RTTHREAD hSelf, void *pvUser) { MTTESTLISTTYPE *pTestList = (MTTESTLISTTYPE *)pvUser; @@ -450,5 +554,6 @@ { /* Make sure there is at least one item in the list. */ - while (pTestList->isEmpty()) {}; + while (pTestList->isEmpty()) + RTThreadYield(); a = pTestList->at(RTRandU32Ex(0, (uint32_t)pTestList->size() - 1)); } @@ -463,5 +568,5 @@ * @param pvUser The provided user data. */ -DECLCALLBACK(int) mttest5(RTTHREAD hSelf, void *pvUser) +static DECLCALLBACK(int) MtTest5ThreadProc(RTTHREAD hSelf, void *pvUser) { MTTESTLISTTYPE *pTestList = (MTTESTLISTTYPE *)pvUser; @@ -471,5 +576,6 @@ { /* Make sure there is at least one item in the list. */ - while (pTestList->isEmpty()) {}; + while (pTestList->isEmpty()) + RTThreadYield(); pTestList->replace(RTRandU32Ex(0, (uint32_t)pTestList->size() - 1), 0xFF00FF00); } @@ -484,5 +590,5 @@ * @param pvUser The provided user data. */ -DECLCALLBACK(int) mttest6(RTTHREAD hSelf, void *pvUser) +static DECLCALLBACK(int) MtTest6ThreadProc(RTTHREAD hSelf, void *pvUser) { MTTESTLISTTYPE *pTestList = (MTTESTLISTTYPE *)pvUser; @@ -492,5 +598,6 @@ { /* Make sure there is at least one item in the list. */ - while (pTestList->isEmpty()) {}; + while (pTestList->isEmpty()) + RTThreadYield(); pTestList->removeAt(RTRandU32Ex(0, (uint32_t)pTestList->size() - 1)); } @@ -508,33 +615,25 @@ RTTestISubF("MT test with 6 threads (%u tests per thread).", MTTESTITEMS); - RTTHREAD hThread1, hThread2, hThread3, hThread4, hThread5, hThread6; - int rc = VINF_SUCCESS; - - MTTESTLISTTYPE testList; - rc = RTThreadCreate(&hThread1, &mttest1, &testList, 0, RTTHREADTYPE_DEFAULT, RTTHREADFLAGS_WAITABLE, "mttest1"); - AssertRC(rc); - rc = RTThreadCreate(&hThread2, &mttest2, &testList, 0, RTTHREADTYPE_DEFAULT, RTTHREADFLAGS_WAITABLE, "mttest2"); - AssertRC(rc); - rc = RTThreadCreate(&hThread3, &mttest3, &testList, 0, RTTHREADTYPE_DEFAULT, RTTHREADFLAGS_WAITABLE, "mttest3"); - AssertRC(rc); - rc = RTThreadCreate(&hThread4, &mttest4, &testList, 0, RTTHREADTYPE_DEFAULT, RTTHREADFLAGS_WAITABLE, "mttest4"); - AssertRC(rc); - rc = RTThreadCreate(&hThread5, &mttest5, &testList, 0, RTTHREADTYPE_DEFAULT, RTTHREADFLAGS_WAITABLE, "mttest5"); - AssertRC(rc); - rc = RTThreadCreate(&hThread6, &mttest6, &testList, 0, RTTHREADTYPE_DEFAULT, RTTHREADFLAGS_WAITABLE, "mttest6"); - AssertRC(rc); - - rc = RTThreadWait(hThread1, RT_INDEFINITE_WAIT, 0); - AssertRC(rc); - rc = RTThreadWait(hThread2, RT_INDEFINITE_WAIT, 0); - AssertRC(rc); - rc = RTThreadWait(hThread3, RT_INDEFINITE_WAIT, 0); - AssertRC(rc); - rc = RTThreadWait(hThread4, RT_INDEFINITE_WAIT, 0); - AssertRC(rc); - rc = RTThreadWait(hThread5, RT_INDEFINITE_WAIT, 0); - AssertRC(rc); - rc = RTThreadWait(hThread6, RT_INDEFINITE_WAIT, 0); - AssertRC(rc); + int rc; + MTTESTLISTTYPE testList; + RTTHREAD ahThreads[6]; + static PFNRTTHREAD apfnThreads[6] = + { + MtTest1ThreadProc, MtTest2ThreadProc, MtTest3ThreadProc, MtTest4ThreadProc, MtTest5ThreadProc, MtTest6ThreadProc + }; + + for (unsigned i = 0; i < RT_ELEMENTS(ahThreads); i++) + { + RTTESTI_CHECK_RC_RETV(RTThreadCreateF(&ahThreads[i], apfnThreads[i], &testList, 0, + RTTHREADTYPE_DEFAULT, RTTHREADFLAGS_WAITABLE, "mttest%u", i), VINF_SUCCESS); + } + + uint64_t tsMsDeadline = RTTimeMilliTS() + 60000; + for (unsigned i = 0; i < RT_ELEMENTS(ahThreads); i++) + { + uint64_t tsNow = RTTimeMilliTS(); + uint32_t cWait = tsNow > tsMsDeadline ? 5000 : tsMsDeadline - tsNow; + RTTESTI_CHECK_RC(RTThreadWait(ahThreads[i], tsNow, NULL), VINF_SUCCESS); + } RTTESTI_CHECK_RETV(testList.size() == MTTESTITEMS * 2); @@ -557,11 +656,4 @@ RTTestBanner(hTest); - /* Some host info. */ - RTTestIPrintf(RTTESTLVL_ALWAYS, "sizeof(void*)=%d", sizeof(void*)); - - /* - * The tests. - */ - /* * Native types.