diff options
Diffstat (limited to 'EASTL/test/source/TestIntrusiveList.cpp')
| -rw-r--r-- | EASTL/test/source/TestIntrusiveList.cpp | 403 |
1 files changed, 403 insertions, 0 deletions
diff --git a/EASTL/test/source/TestIntrusiveList.cpp b/EASTL/test/source/TestIntrusiveList.cpp new file mode 100644 index 0000000..60b2378 --- /dev/null +++ b/EASTL/test/source/TestIntrusiveList.cpp @@ -0,0 +1,403 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#include "EASTLTest.h" +#include <EASTL/intrusive_list.h> +#include <EABase/eabase.h> + +EA_DISABLE_ALL_VC_WARNINGS() +#include <stdio.h> +#include <stdarg.h> +#include <stddef.h> + +#ifndef EA_COMPILER_NO_STANDARD_CPP_LIBRARY + #include <string> +#endif +EA_RESTORE_ALL_VC_WARNINGS() + +using namespace eastl; + + +namespace +{ + + /// IntNode + /// + /// Test intrusive_list node. + /// + struct IntNode : public eastl::intrusive_list_node + { + int mX; + + IntNode(int x = 0) + : mX(x) { } + + operator int() const + { return mX; } + }; + + + /// ListInit + /// + /// Utility class for setting up a list. + /// + class ListInit + { + public: + ListInit(intrusive_list<IntNode>& container, IntNode* pNodeArray) + : mpContainer(&container), mpNodeArray(pNodeArray) + { + mpContainer->clear(); + } + + ListInit& operator+=(int x) + { + mpNodeArray->mX = x; + mpContainer->push_back(*mpNodeArray++); + return *this; + } + + ListInit& operator,(int x) + { + mpNodeArray->mX = x; + mpContainer->push_back(*mpNodeArray++); + return *this; + } + + protected: + intrusive_list<IntNode>* mpContainer; + IntNode* mpNodeArray; + }; + +} // namespace + + + + +// Template instantations. +// These tell the compiler to compile all the functions for the given class. +template class eastl::intrusive_list<IntNode>; + + + +int TestIntrusiveList() +{ + int nErrorCount = 0; + int i; + + { + // Verify that intrusive_list_node is a POD, at least when EASTL_VALIDATE_INTRUSIVE_LIST is disabled. + #if !EASTL_VALIDATE_INTRUSIVE_LIST + // is_pod doesn't currently detect structs as PODs, even though it should. + // This is due to limitations in C++. + // VERIFY(eastl::is_pod<eastl::intrusive_list_node>::value); + + const size_t offset = offsetof(intrusive_list_node, mpPrev); + VERIFY(offset == sizeof(intrusive_list_node*)); + #endif + } + + { + IntNode nodes[20]; + + intrusive_list<IntNode> ilist; + + // Enforce that the intrusive_list copy ctor is visible. If it is not, + // then the class is not a POD type as it is supposed to be. + delete new intrusive_list<IntNode>(ilist); + + #ifndef __GNUC__ // GCC warns on this, though strictly specaking it is allowed to. + // Enforce that offsetof() can be used with an intrusive_list in a struct; + // it requires a POD type. Some compilers will flag warnings or even errors + // when this is violated. + struct Test { + intrusive_list<IntNode> m; + }; + (void)offsetof(Test, m); + #endif + + // begin / end + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "ctor()", -1)); + + + // push_back + ListInit(ilist, nodes) += 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "push_back()", 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1)); + + + // iterator / begin + intrusive_list<IntNode>::iterator it = ilist.begin(); + VERIFY(it->mX == 0); + ++it; + VERIFY(it->mX == 1); + ++it; + VERIFY(it->mX == 2); + ++it; + VERIFY(it->mX == 3); + + + // const_iterator / begin + const intrusive_list<IntNode> cilist; + intrusive_list<IntNode>::const_iterator cit; + for(cit = cilist.begin(); cit != cilist.end(); ++cit) + VERIFY(cit == cilist.end()); // This is guaranteed to be false. + + + // reverse_iterator / rbegin + intrusive_list<IntNode>::reverse_iterator itr = ilist.rbegin(); + VERIFY(itr->mX == 9); + ++itr; + VERIFY(itr->mX == 8); + ++itr; + VERIFY(itr->mX == 7); + ++itr; + VERIFY(itr->mX == 6); + + + // iterator++/-- + { + intrusive_list<IntNode>::iterator it1(ilist.begin()); + intrusive_list<IntNode>::iterator it2(ilist.begin()); + + ++it1; + ++it2; + if ((it1 != it2++) || (++it1 != it2)) + VERIFY(!"[iterator::increment] fail\n"); + + if ((it1 != it2--) || (--it1 != it2)) + VERIFY(!"[iterator::decrement] fail\n"); + } + + + // clear / empty + VERIFY(!ilist.empty()); + + ilist.clear(); + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "clear()", -1)); + VERIFY(ilist.empty()); + + + // splice + ListInit(ilist, nodes) += 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; + + ilist.splice(++ilist.begin(), ilist, --ilist.end()); + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "splice(single)", 0, 9, 1, 2, 3, 4, 5, 6, 7, 8, -1)); + + intrusive_list<IntNode> ilist2; + ListInit(ilist2, nodes+10) += 10, 11, 12, 13, 14, 15, 16, 17, 18, 19; + + ilist.splice(++++ilist.begin(), ilist2); + VERIFY(VerifySequence(ilist2.begin(), ilist2.end(), int(), "splice(whole)", -1)); + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "splice(whole)", 0, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 1, 2, 3, 4, 5, 6, 7, 8, -1)); + + ilist.splice(ilist.begin(), ilist, ++++ilist.begin(), ----ilist.end()); + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "splice(range)", 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 1, 2, 3, 4, 5, 6, 0, 9, 7, 8, -1)); + + ilist.clear(); + ilist.swap(ilist2); + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "swap(empty)", -1)); + VERIFY(VerifySequence(ilist2.begin(), ilist2.end(), int(), "swap(empty)", -1)); + + ilist2.push_back(nodes[0]); + ilist.splice(ilist.begin(), ilist2); + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "splice(single)", 0, -1)); + VERIFY(VerifySequence(ilist2.begin(), ilist2.end(), int(), "splice(single)", -1)); + + + // splice(single) -- evil case (splice at or right after current position) + ListInit(ilist, nodes) += 0, 1, 2, 3, 4; + ilist.splice(++++ilist.begin(), *++++ilist.begin()); + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "splice(single)", 0, 1, 2, 3, 4, -1)); + ilist.splice(++++++ilist.begin(), *++++ilist.begin()); + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "splice(single)", 0, 1, 2, 3, 4, -1)); + + + // splice(range) -- evil case (splice right after current position) + ListInit(ilist, nodes) += 0, 1, 2, 3, 4; + ilist.splice(++++ilist.begin(), ilist, ++ilist.begin(), ++++ilist.begin()); + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "splice(range)", 0, 1, 2, 3, 4, -1)); + + + // push_front / push_back + ilist.clear(); + ilist2.clear(); + for(i = 4; i >= 0; --i) + ilist.push_front(nodes[i]); + for(i = 5; i < 10; ++i) + ilist2.push_back(nodes[i]); + + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "push_front()", 0, 1, 2, 3, 4, -1)); + VERIFY(VerifySequence(ilist2.begin(), ilist2.end(), int(), "push_back()", 5, 6, 7, 8, 9, -1)); + + for(i = 4; i >= 0; --i) + { + ilist.pop_front(); + ilist2.pop_back(); + } + + VERIFY(ilist.empty() && ilist2.empty()); + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "pop_front()", -1)); + VERIFY(VerifySequence(ilist2.begin(), ilist2.end(), int(), "pop_back()", -1)); + + + // contains / locate + for(i = 0; i < 5; ++i) + ilist.push_back(nodes[i]); + + VERIFY( ilist.contains(nodes[2])); + VERIFY(!ilist.contains(nodes[7])); + + it = ilist.locate(nodes[3]); + VERIFY(it->mX == 3); + + it = ilist.locate(nodes[8]); + VERIFY(it == ilist.end()); + + + // reverse + ilist.reverse(); + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "push_front()", 4, 3, 2, 1, 0, -1)); + + + // validate / validate_iterator + VERIFY(ilist.validate()); + it = ilist.locate(nodes[3]); + VERIFY((ilist.validate_iterator(it) & (isf_valid | isf_can_dereference)) != 0); + VERIFY( ilist.validate_iterator(intrusive_list<IntNode>::iterator(NULL)) == isf_none); + + + // swap() + ilist.swap(ilist2); + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "swap()", -1)); + VERIFY(VerifySequence(ilist2.begin(), ilist2.end(), int(), "swap()", 4, 3, 2, 1, 0, -1)); + + + // erase() + ListInit(ilist2, nodes) += 0, 1, 2, 3, 4; + ListInit(ilist, nodes+5) += 5, 6, 7, 8, 9; + ilist.erase(++++ilist.begin()); + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "erase(single)", 5, 6, 8, 9, -1)); + + ilist.erase(ilist.begin(), ilist.end()); + VERIFY(VerifySequence(ilist.begin(), ilist.end(), int(), "erase(all)", -1)); + + ilist2.erase(++ilist2.begin(), ----ilist2.end()); + VERIFY(VerifySequence(ilist2.begin(), ilist2.end(), int(), "erase(range)", 0, 3, 4, -1)); + + + // size + VERIFY(ilist2.size() == 3); + + + // pop_front / pop_back + ilist2.pop_front(); + VERIFY(VerifySequence(ilist2.begin(), ilist2.end(), int(), "pop_front()", 3, 4, -1)); + + ilist2.pop_back(); + VERIFY(VerifySequence(ilist2.begin(), ilist2.end(), int(), "pop_back()", 3, -1)); + } + + + { + // Test copy construction and assignment. + // The following *should* not compile. + + intrusive_list<IntNode> ilist1; + intrusive_list<IntNode> ilist2(ilist1); + ilist1 = ilist2; + } + + + { + // void sort() + // void sort(Compare compare) + + const int kSize = 10; + IntNode nodes[kSize]; + + intrusive_list<IntNode> listEmpty; + listEmpty.sort(); + VERIFY(VerifySequence(listEmpty.begin(), listEmpty.end(), int(), "list::sort", -1)); + + intrusive_list<IntNode> list1; + ListInit(list1, nodes) += 1; + list1.sort(); + VERIFY(VerifySequence(list1.begin(), list1.end(), int(), "list::sort", 1, -1)); + list1.clear(); + + intrusive_list<IntNode> list4; + ListInit(list4, nodes) += 1, 9, 2, 3; + list4.sort(); + VERIFY(VerifySequence(list4.begin(), list4.end(), int(), "list::sort", 1, 2, 3, 9, -1)); + list4.clear(); + + intrusive_list<IntNode> listA; + ListInit(listA, nodes) += 1, 9, 2, 3, 5, 7, 4, 6, 8, 0; + listA.sort(); + VERIFY(VerifySequence(listA.begin(), listA.end(), int(), "list::sort", 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1)); + listA.clear(); + + intrusive_list<IntNode> listB; + ListInit(listB, nodes) += 1, 9, 2, 3, 5, 7, 4, 6, 8, 0; + listB.sort(eastl::less<int>()); + VERIFY(VerifySequence(listB.begin(), listB.end(), int(), "list::sort", 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1)); + listB.clear(); + } + + + { + // void merge(this_type& x); + // void merge(this_type& x, Compare compare); + + const int kSize = 8; + IntNode nodesA[kSize]; + IntNode nodesB[kSize]; + + intrusive_list<IntNode> listA; + ListInit(listA, nodesA) += 1, 2, 3, 4, 4, 5, 9, 9; + + intrusive_list<IntNode> listB; + ListInit(listB, nodesB) += 1, 2, 3, 4, 4, 5, 9, 9; + + listA.merge(listB); + VERIFY(VerifySequence(listA.begin(), listA.end(), int(), "list::merge", 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 9, 9, 9, 9, -1)); + VERIFY(VerifySequence(listB.begin(), listB.end(), int(), "list::merge", -1)); + } + + + { + // void unique(); + // void unique(BinaryPredicate); + + const int kSize = 8; + IntNode nodesA[kSize]; + IntNode nodesB[kSize]; + + intrusive_list<IntNode> listA; + ListInit(listA, nodesA) += 1, 2, 3, 4, 4, 5, 9, 9; + listA.unique(); + VERIFY(VerifySequence(listA.begin(), listA.end(), int(), "list::unique", 1, 2, 3, 4, 5, 9, -1)); + + intrusive_list<IntNode> listB; + ListInit(listB, nodesB) += 1, 2, 3, 4, 4, 5, 9, 9; + listB.unique(eastl::equal_to<int>()); + VERIFY(VerifySequence(listA.begin(), listA.end(), int(), "list::unique", 1, 2, 3, 4, 5, 9, -1)); + } + + + return nErrorCount; +} + + + + + + + + + + + + |